Add geospatial to your comparison chart please. The way in which these implement support varies widely in performance and accuracy. I've yet to find one that actually uses R-Trees. Geohashes seem to be all the rage these days.
"I've yet to find one that actually uses R-Trees."
That's because R-Trees don't scale well with random write loads.
R-tree insertion performance is extremely dependent on insertion order (search for "sort tile recursive"). They're best used for problems where the data can be bulk-loaded and left alone. If random writes are an important part of the problem (as they are for most web-based tools), R-Trees are a bad idea.
Geohashes seem to play nicely to the strengths of an indexing search engine, because you can encode quadrants into a string of characters, and use ngram analysis to compare multiple levels of precision. There's almost no extra work that goes into using geohashes with a term-based index.
That said, they carry a lot of annoying edge cases when determining the adjacency of quadrants, so they're hardly a panacea to geospatial search. Lucene 3 and 4 make a lot of progress in spatial search, but there's still a fair bit of room for improvement.
Comments
Add geospatial to your comparison chart please. The way in which these implement support varies widely in performance and accuracy. I've yet to find one that actually uses R-Trees. Geohashes seem to be all the rage these days.
"I've yet to find one that actually uses R-Trees."
That's because R-Trees don't scale well with random write loads.
R-tree insertion performance is extremely dependent on insertion order (search for "sort tile recursive"). They're best used for problems where the data can be bulk-loaded and left alone. If random writes are an important part of the problem (as they are for most web-based tools), R-Trees are a bad idea.
Geohashes seem to play nicely to the strengths of an indexing search engine, because you can encode quadrants into a string of characters, and use ngram analysis to compare multiple levels of precision. There's almost no extra work that goes into using geohashes with a term-based index.
That said, they carry a lot of annoying edge cases when determining the adjacency of quadrants, so they're hardly a panacea to geospatial search. Lucene 3 and 4 make a lot of progress in spatial search, but there's still a fair bit of room for improvement.