Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-3551

RTree Implementation for Spatial Indexing

    Details

      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

        Issue Links

          Activity

          Hide
          nknize Nicholas Knize added a comment -

          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.

          Show
          nknize Nicholas Knize added a comment - 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.
          Hide
          nknize Nicholas Knize added a comment -

          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.

          Show
          nknize Nicholas Knize added a comment - 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.
          Hide
          eliot Eliot Horowitz added a comment -

          I'm not sure this is something we want to bring in right now.
          Happy to help review it when you publish though.

          Show
          eliot Eliot Horowitz added a comment - I'm not sure this is something we want to bring in right now. Happy to help review it when you publish though.
          Hide
          nknize Nicholas Knize added a comment - - edited

          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.

          Show
          nknize Nicholas Knize added a comment - - edited 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.
          Hide
          ctonhaeuser Christian Tonhäuser added a comment -

          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.

          Show
          ctonhaeuser Christian Tonhäuser added a comment - 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.
          Hide
          p.kennedy@fugro.com.au paul kennedy added a comment -

          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.

          Show
          p.kennedy@fugro.com.au paul kennedy added a comment - 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.
          Hide
          p.kennedy@fugro.com.au paul kennedy added a comment -

          Hi Nicholas,
          any update on your progress? i would be happy to contribute dev/test resources if this looks promising.

          Show
          p.kennedy@fugro.com.au paul kennedy added a comment - Hi Nicholas, any update on your progress? i would be happy to contribute dev/test resources if this looks promising.
          Hide
          radoslav Radoslav Petranov added a comment - - edited

          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!

          Show
          radoslav Radoslav Petranov added a comment - - edited 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!

            People

            • Votes:
              13 Vote for this issue
              Watchers:
              17 Start watching this issue

              Dates

              • Created:
                Updated:
                Days since reply:
                1 year ago
                Date of 1st Reply: