[SERVER-3551] RTree Implementation for Spatial Indexing Created: 08/Aug/11 Updated: 06/Apr/23 |
|
| Status: | Backlog |
| Project: | Core Server |
| Component/s: | Geo, Index Maintenance |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | New Feature | Priority: | Major - P3 |
| Reporter: | Nicholas Knize | Assignee: | Backlog - Query Optimization |
| Resolution: | Unresolved | Votes: | 12 |
| Labels: | indexing, performance, query | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||||||||||
| Assigned Teams: |
Query Optimization
|
||||||||||||||||
| Participants: | |||||||||||||||||
| Description |
|
This feature could be implemented in a number of ways. 1. Extend existing BTree to include B+ Tree functionality, implement MBR bucket functionality |
| Comments |
| Comment by Radoslav Petranov [ 31/Aug/14 ] |
|
Hi there, Could someone please give some sort of a progress update? Is this feature something that you guys plan to release in 2014/2015? This is an essential element for many geo-based apps and it would be really helpful if you guys could just give us a general idea of where is RTree indexing on the roadmap for you. Thanks in advance and cheers! |
| Comment by paul kennedy [ 03/Dec/11 ] |
|
Hi Nicholas, |
| Comment by paul kennedy [ 03/Dec/11 ] |
|
hi, I do not mind if you use r-tree or anything else. The end game is a spatial index using bounding box envelopes. Can this please get bumped up the development priority list. It would be highly appreciated by many geospatial developers. |
| Comment by Christian Tonhäuser [ 01/Oct/11 ] |
|
Hi Nicholas, I'm currently facing a similar issue in a project of mine, and this sounds like the ideal solution to me. |
| Comment by Nicholas Knize [ 16/Aug/11 ] |
|
Sounds great Eliot! I will post a copy to my GitHub account and notify when its ready for review. Re: some background on this feature. I believe it was Greg Studer that I spoke w/ on #mongodb about polygonal indexing and search. There was no support for polygonal clipping (aka query failed unless a point fell w/in the polygon search area; see: http://twitpic.com/67457c ) This is a much needed feature for spatial search beyond simple point data. Greg mentioned there wouldn't be much work in this area because of the interest to migrate to an RTree approach (ala. PostGIS, Oracle Spatial, etc.) sometime in v.2.1. Is that not the case? At any rate, the implementation is primarily an extension of the following publications (w/ some original contribution and distributed modifications): N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331. I will keep this issue posted w/ updates. |
| Comment by Eliot Horowitz (Inactive) [ 16/Aug/11 ] |
|
I'm not sure this is something we want to bring in right now. |
| Comment by Nicholas Knize [ 16/Aug/11 ] |
|
I am about halfway done merging an initial R* implementation. I wouldn't mind someone assigning this task to me so I can keep updating the progress. When I finish I can push the code to a working branch on GitHub for peer review and community testing. |
| Comment by Nicholas Knize [ 09/Aug/11 ] |
|
Thanks Eliot. I've got an R* implementation i'm working to merge in my own sandbox... I created this feature in case the whistle blowers wanted to flag it as a duplicate effort. I'd prefer not waste time if someone is already working it. |