10

Where can I find enough documentation to implement an R*-Tree? Specifically, I need to be able to:

  • Insert nodes
  • Remove nodes
  • Search for K nearest neighbours
  • Find all nearest neighbours within distance x.

Is there a single place where this algorithm is clearly documented? Or is there a clean, open source implementation I can study? Even better, if you can point me to a javascript implementation then my work is already done.

fmark
  • 57,259
  • 27
  • 100
  • 107
  • 3
    Why is the [paper linked in the cited article](http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf) insufficient for your needs? It contains a full algorithm description... – Mark Elliot Jan 17 '11 at 01:20
  • 4
    @Mark E - The linked paper only describes one portion of the algorithm, relying on further citations for the remainder. Furthermore, I would probably find it easier to grok code rather than an academic paper. – fmark Jan 17 '11 at 01:29
  • That's fair, and you would've enhanced your question by providing that detail. FWIW, Wikipedia also cites some C++ code samples; I'll go out on a limb and just expect that that code doesn't meet your cleanliness and documentation standards, or something -- but that information might've been useful, too. – Mark Elliot Jan 17 '11 at 01:34
  • 1
    The gaps are probably answered by the R-Tree, on which the R*-Tree extends by improving various methods such as the splitting strategy and overflow handling. Did you also check the Guttman article? – Has QUIT--Anony-Mousse Dec 18 '11 at 13:45
  • Found an R* Tree library on some website. https://github.com/imbcmdth/RTree/raw/master/src/rtree.js –  Jan 17 '11 at 01:23
  • Awesome, who knew there was some else crazy enough to have done this already! – fmark Jan 17 '11 at 01:31
  • "r tree javascript" is a suggested result in Google. –  Jan 17 '11 at 01:32
  • Actually it is not an R*-Tree, but a regular R-tree. – Has QUIT--Anony-Mousse Dec 18 '11 at 13:44

0 Answers0