Rank Cover Trees for Nearest Neighbor
SearchMichael E. HOULE

Michael NETTNIIRWTH Aachen University, GERMANY

WhyWhatText, images, market data, biological data, scientific data,and other forms of information are currently being gatheredin large data repositories at a rate that greatly outstrips ourability to analyze and to interpret. Together with this
explosion of information, the demand for effective methods
for searching, clustering, categorizing, summarizing andmatching within data sets continues to grow. For suchapplications, solutions based on similarity search areamong the most effective proposed in statistics, patternrecognition, and machine learning. The design and analysis
of effective similarity search structures has consequently
been the subject of intensive research for many decades.

We propose the rank cover tree (RCT), a probabilistic data
structure for similarity search in general metric spaces. TheRCT reinterprets the design and analysis of the Cover Treein terms of neighbor ranks as measured from the query
point, rather than explicit distances. The ranked-based
analysis results in a significantly smaller dependence on theintrinsic dimensionality over practical data set sizes. This
allows the RCT to find approximations of very high qualities,
orders of magnitudes faster than structures for exact
similarity search. Moreover, the RCT is highly competitive
with the SASH heuristic in terms of its speed-up accuracy
trade-off.

Similarity Search
Idea of Sampling

Curse of Dimensionality

Observations
 Sequential scans outperform classical search structures.
 Similarity values concentrate around their mean.
 Similar and dissimilar points
are hardly distinguishable.
 Spatial intuitions from 3Dspaces are invalid.
Consequences
Use approximate similarity
search.

We try to find items similar to a query q withrespect to some data set T .
 Suppose for a subset S' we already know an itemx that is similar to q .
T S that is similar to x is likely to be An item ysimilar to q , and the probability of this is known!
Rank Cover Trees
Construction

Performance on real data sets

For each item x T , introduce x
x
into levels 0,. .. , x . The
are geometrically distributed by1/ hp= n with tree height h .
 Build a partial RCT on the highest
level by connecting all items inthat level to an artificial root node.
 Connect next level by selecting
approximate nearest-neighbors
found in the partial RCT.
 Errors are amplified, but we cancontrol them!

The following figures display the trade-off between approximation quality andquery time. Query times are measured as factors of the time consumed by asequential scan. The query time of the Cover Tree structure for exact similarity
searches is provided as a reference point ( ). The plots include the RCT forheights 3, 4, 5 and 8 ( ,, and ) and the SASH heuristic ( X ).

SearchAmsterdam Library of Object Images

Forrest Cover Types

GisetteIsoletPoker Hand

Spambase

Find the k items most similar to a query q .
 For each level i , find a cover set C .
i Start with C
h containing the artificial root.
 C is constructed from Cii 1 by keeping the k ichildren of all elements in C i , which are most similar
to the query q .

k i = max {k n, 1 }, where is parameterallowing to trade-off between accuracy and query time.
− 1 /h

連絡先： Michael E. HOULE (フール マイケル) ／ 国立情報学研究所 客員教授
TEL : 03-4212-2538

FAX : 03-3556-1916

Email : meh@nii.ac.jp