Core Server
  1. Core Server
  2. SERVER-3551

RTree Implementation for Spatial Indexing

    Details

    • Backport:
      No
    • # Replies:
      7
    • Last comment by Customer:
      true

      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
          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
          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
          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
          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 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 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
          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
          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
          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
          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
          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
          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
          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
          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.

            People

            • Votes:
              10 Vote for this issue
              Watchers:
              12 Start watching this issue

              Dates

              • Created:
                Updated:
                Days since reply:
                2 years, 20 weeks, 4 days ago
                Date of 1st Reply: