Damn Cool Algorithms: Quadtrees and Hilbert Curves(blog.notdot.net)
blog.notdot.net
Damn Cool Algorithms: Quadtrees and Hilbert Curves
http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
15 comments
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.
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.
Whilst I was an intern at Google I worked with Hilbert Curves. Range queries are something BigTable and Cassandra excel at and are the core database component of any Hilbert Curve based spatial index.
The real issue is building the database queries. Google released Uzaygezen[1], a Java library for multi-dimensional indexing, that handles the majority of this for you.
[1]: http://code.google.com/p/uzaygezen/
The real issue is building the database queries. Google released Uzaygezen[1], a Java library for multi-dimensional indexing, that handles the majority of this for you.
[1]: http://code.google.com/p/uzaygezen/
I did not get this in the article - how exactly do we construct range queries (which the Hilbert curve improves on) here? Is the quadtree range resolved into actual coordinates, or is the datatype of the index bound to be integer, so we can query a range over the index (0110110 to 0110111 = 54 to 55, so the query range is [54, 55])?
Thanks Smerity that was really interesting - we are looking at applying special searches to Riak.
This technique is simultaneously cool and depressing. Remember all that cool stuff you learned in computational geometry? Throw it out.
Just associate geometry with a set of well chosen ids, and you can stuff it into really simple, conventional data structures and do all of the spatial operations you wanted to quickly and simply in practice.
Just associate geometry with a set of well chosen ids, and you can stuff it into really simple, conventional data structures and do all of the spatial operations you wanted to quickly and simply in practice.
I'm a bit confused. I've naively put axis-aligned bounding-boxes (AABBs) in my octree without any kind of thought. I put them in the smallest box that contains them. I also keep a byte using bits to mark the sectors they intersect, a cache that greatly cheapens things.
It works very well. I even keep small things like bullets in my octree (most game engines keep them separate), putting them in an AABB representing their position for some duration.
I am doing my queries in nanoseconds.
Its worth saying that for big worlds (think minecraft++), octrees don't work as well as zoning systems e.g. pages. You can of course use a hierarchy, using pages or zones with octrees in them.
It works very well. I even keep small things like bullets in my octree (most game engines keep them separate), putting them in an AABB representing their position for some duration.
I am doing my queries in nanoseconds.
Its worth saying that for big worlds (think minecraft++), octrees don't work as well as zoning systems e.g. pages. You can of course use a hierarchy, using pages or zones with octrees in them.
Does anyone know if there's a commercial database using quadtrees or hilbert curves? (Aside from the libraries mentioned in the comments, I mean something more productized)
Oracle used to use a similar fractal curve system for their spatial index, but has since moved to R-trees.
I believe MongoDB is using a geohash system for their spatial queries as well.
I believe MongoDB is using a geohash system for their spatial queries as well.
Thanks, I had never heard of geohashes before, but it sounds like they might really help with a problem I've been having lately.
How would someone implement this, then? Is it really just an index column besides the data tuples, containing the recursive quadrant position (111111 for bottom-right in a 3-level grid)? And, what datatype would you use for this - clearly, an integer is not long enough if you have a great number of levels..
Ok I just wrapped my head around it. For querying to work here, the datatype HAS to be integer or long, or else queries on higher levels would not return the tuples associated with lower-level-quads.
[deleted](1)
The Wikipedia description of Geohashes is a bit odd in that its base32 decoding uses the alphabet with some letters (a, i...) left out instead of simply using [0-9a-v]. Anyone know why that would make sense?
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.