Diamond-Tree: An Index Structure for High-Dimensionality Approximate Searching

A selection query applied to a database often has the selection predicate imperfectly specified. We present a technique, called the Diamond- tree, for indexing fields to perform similarity-based retrieval, given some applicable measures of approximation. Typically, the number of features (or dimensions of similarity) is large, so that the search space has a high-dimensionality, and most tradition methods perform poorly.