[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:
Depends
depends on SERVER-8791 Create a uniform index API across all... Closed
Related
is related to SERVER-1436 index plugin api Closed
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
2. Extend existing BTree to include R* tree functionality (e.g. geo dependent splitting, hilbert value inserts) and implement MBR bucket functions



 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,
any update on your progress? i would be happy to contribute dev/test resources if this looks promising.

Comment by paul kennedy [ 03/Dec/11 ]

hi,
from my perspective the current spatial index on points only is insufficent for us to move to mongodb. I believe the engine needs to index (R-tree) all spatial data types as supported by GeoJSON, ie point, line, polygon, multipoint. each data type build on point, so they are not terribly complex, but not having them indexed makes it impossible to use mongo, which is why geocouch exists.

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,
have you already made progress on the integration of your R* implementation?

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. Kamel, C. Faloutsos: Hilbert R-Tree: An Improved R-Tree Using Fractals. VLDB '94 Proceedings of the 20th International Conference on Very Large Data Bases 1994: 500-509.

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.
Happy to help review it when you publish though.

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.

Generated at Thu Feb 08 03:03:22 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.