News for hackers. Stuff that matters.
Re:Damn Cool Algorithms: Quadtrees and Hilbert Curves by jrockway on Wednesday January 18, 2012 @09:33PM (#3482961)
This might be obvious to many, but spatial indexes are good for more than just "show me the restaurants within five miles of me". It's a good technique to know for efficiently searching any two columns simultaneously. If you have, for example, a database of people, their hometown, and their favorite color, and you want to know all people from Chicago that like green, a spacial index over color and hometown will be vastly more efficient than a "regular" single-column index over any one of those columns. (The reason is that an index on one column doesn't efficiently produce a small resultset. If we index on color and there are five colors, an index over color only reduces the dataset by 1/5th. Similarly, indexing over hometown might reduce the size of the dataset by 1/1000th. But if we index over both columns at the same time, then the only results that the index will ever produce are results that are the exact answer to our question. No unnecessary scanning!)

Anyway, lat/long might be the easiest "pair" of columns to imagine when discussing anything "spatial", but most other two-column pairs work the exact same way.

Re:Damn Cool Algorithms: Quadtrees and Hilbert Curves by tom_b on Wednesday January 18, 2012 @10:05PM (#3483034)
Yes - I remember using these techniques addressing 2d dense matrices. The specific case was when the matrices involved grew so large that the linear access operations were causing page faults for sequential row or column access. This was a perfect example of pathologically bad memory accesses when data was stored in row-major or column-major layouts.

Very impressive speedups for these interleaved data layouts. The end goal was to embed these layouts into the compiler tools, so that the programmer would do normal two dimensional matrix allocations and would get the optimized layout based on analysis.

I wrote terrible C to accomplish these layouts and minimize the instruction counts.