Archive for the ‘R-Trees’ Category

Datomic R-trees

Thursday, February 6th, 2014

Datomic R-trees by James Sofra.

From the description:

Slides for a talk given at Melbourne Functional Users Group on an R-tree based spatial indexer for Datomic.

The slides do a good job explaining the advantages of Datomic for spatial data and using R-trees with it.

References from the slides that you will find helpful:

R-TREES. A Dynamic Index Structure for Spatial Searching. A. Guttman (1984)

Sort-based query-adaptive loading of R-trees, Daniar Achakeev, Bernhard Seeger, Peter Widmayer. (2012)

Sort-based parallel loading of R-trees, Daniar Achakeev, Marc Seidemann, Markus Schmidt, Bernhard Seeger. (2012)

The R*-tree: an efficient and robust access method for points and rectangles (1990), by Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger. (1990)

OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree, Taewon Lee, Sukho Lee. (2003)

The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree, Lars Arge. (2004)

Compact Hilbert indices, Christopher Hamilton. (2006)

R-Trees: Theory and Applications, Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos and Yannis Theodoridis. (2006)

See also:

Similarity Indexing: Algorithms and Performance (1996)

Monday, September 20th, 2010

Similarity Indexing: Algorithms and Performance (1996) Authors: David A. White , Ramesh Jain KeyWords Similarity Indexing, High Dimensional Feature Vectors, Approximate k-Nearest Neighbor Searching, Closest Points, Content-Based Retrieval, Image and Video Database Retrieval.

The authors of this paper coined the phrase “similarity indexing.”

A bit dated now but interesting as a background to techniques currently in use.

A topic map tracing the development of one of the “similarity” techniques would make an excellent thesis project.

The TV-tree — an index structure for high-dimensional data (1994)

Saturday, September 18th, 2010

The TV-tree — an index structure for high-dimensional data (1994) Authors: King-ip Lin , H. V. Jagadish , Christos Faloutsos Keywords:Spatial Index, Similarity Retrieval, Query by Context, R*-Tree, High-Dimensionality Feature Spaces.


We propose a file structure to index high-dimensionality data, typically, points in some feature space. The idea is to use only a few of the features, utilizing additional features whenever the additional discriminatory power is absolutely necessary. We present in detail the design of our tree structure and the associated algorithms that handle such `varying length’ feature vectors. Finally we report simulation results, comparing the proposed structure with the R -tree, which is one of the most successful methods for low-dimensionality spaces. The results illustrate the superiority of our method, with up to 80% savings in disk accesses.

The notion of “…utilizing additional features whenever the additional discriminatory power is absolutely necessary…” is an important one.

Compare to fixed simplistic discrimination and/or fixed complex, high-overhead, discrimination between subject representatives.

Either one represents a failure of imagination.