There are many spatial solutions out there - R-tree - Quad-Tree - SRID with positional proximity like geohash - Voronoi diagrams etc..
All have their pros & cons as do Cartesian grids. Feel free to contribute the more there are, the more solutions that can be applied to different problems, I use a Cartesian method meets my needs for my work which has a substantial data set. If you look at the LocalSolr implementation of LocalLucene you'll notice that there are multiple grids indexed at different levels / tiers. In a very similar fashion to Quad-Trees. The reason, you can 'zoom' in as low as you need to. There are multiple filters occurring for the geo filters in locallucene, first is an MMB based on bestFit or zoom level, then afterwards those results are filtered by your text intersection and finally by a radial filter. The MMB filter, pre-generates the shape or in this case box with all the id's you're interested in and using a TermEnumerator pulls those from the index. As the id's are stored in a sorted fashion it's a very fast retrieval. Without having to manage memory or a data structure outside of lucene. Storing multiple points is possible, doing a radial filter, or sorting on distance (which is what my work depends on) is tricky as I use FieldCache to retrieve actual points quickly. Multiple values in a field cache dont work. But I am looking at the Uninverted Field method of solr facets for that. You will have the same issue no matter what method you use, unless you don't care about distance. If you want to do something more complex like polygon's, you extend the Shape's class, and create either another MMB or convex hull method. Basically my belief is, that it's faster to find something if you know what your looking for. i.e. grid / box id's The bestFit method essentially lets you skip traversing and just get to the level you want. Pre-generate the id's used in a shape, and simply pull them out of the index. hossman wrote: > > > : Patrick (of local lucene fame) thinks it is possible to do extent > queries with > : the cartesian grid method -- essentially you select the "best fit" level > and > : cell, and that should be set for anything within the extent. The > advantage of > : this approach is that it is super-fast and scaleable. The disadvantage > is > : that it is only as accurate as the grid. > > i'm way out of my league on spatial search -- but couldn't you use the > grid method to whittle down the result space, and then do the computation > to determine if a true overlap exists? > > > -Hoss > > > -- View this message in context: http://www.nabble.com/Spatial-search-using-R-tree-for-indexed-bounding-boxes-tp22318859p22462731.html Sent from the Solr - User mailing list archive at Nabble.com.
