Rank Cover Trees for Nearest Neighbor Search
Michael E. HOULE
11Michael NETT

1,2

National Institute of Informatics, Japan2
The University of Tokyo, Japan

Summary

Idea of Sampling

K-Nearest Neighbor Search

Virtually all known distance-based similarity
search indexes make use of some form of numerical constraints (triangle inequality, additive
distance bounds, . . . ) on similarity values forpruning and selection. The use of such numerical constraints, however, often leads to large
variations in the numbers of objects examinedin the execution of a query, making it difficult
to control the execution costs. We introduce aprobabilistic data structure for similarity search,
the Rank Cover Tree (Rct), that entirely avoids
the use of numerical constraints. All internal selections are made according to the ranks of theobjects with respect to the query, allowing muchtighter control on the overall execution costs.
A rank-based probabilistic analysis shows thatwith very high probability, the Rct returns a correct query result in time that depends competitively on a measure of the intrinsic dimensionality of the data set.

• We try to find items similar to a query object q• Maintain level-wise sets Ci covering the querywith respect to some data set X ⊆ Ω.
• Suppose we found a similar point x with respect
to a (small) subset X 0 ⊆ X, for example, bymeans of a sequential scan.
• We are likely to observe transitivity: an itemy ∈ X \ X 0 which is similar to the item x is alsosimilar to q.
• The probability of observing this kind oftransitivity can be bounded!

results. Start with Ch containing the artificial root.
• Ci is constructed from the set Ci+1 by keeping theki children of all elements in Ci+1, which are mostsimilar to the query q.
• The set C0 contains the query result.
p• We choose ki = ω · max{k/ h |X|, 1}, where ω is aparameter allowing to trade-off between
accuracy and query time.
• Our analysis
shows: pif ω is chosen greater than√hlogφ( 5h)δh + max{h, e |X|}, then theapproximation is free of error with very highprobability.
• The expansion rate δ measures intrinsic
dimensionality.

qx yRecall Rates
Amsterdam Library of Object Images

10090

Motivation

8070

Construction• For each item x ∈ X, introduce x into levels

Average Recall [%]Text, images, market data, biological data, scientific data, and many other forms of information are currently being accumulated in large
data repositories at a rate that greatly outstrips
our ability to analyze and to interpret. Together
with this explosion of information, the demandfor effective methods for searching, clustering,
categorizing, summarizing and matching within
data sets continues to grow. For such applications, solutions based on similarity search areamong the earliest (and most effective) proposed in statistics, pattern recognition, and machine learning. The design and analysis of effective similarity search structures has consequently been the subject of intensive research
for many decades.

0, . . . , λx. For a tree of height h, λx follows ageometric distribution with p = |X|−1/h.
• Build a partial Rct on the highest level by
connecting items in that level to an artificial root.
• Connect the next level by using approximate
nearest neighbors found in the partial Rct.
• Well-formed with high probability.

60504030

Brute Force
SASH
ANN KD-Tree
EELSH
RCT (h=3)
RCT (h=4)
Cover Tree

201000.001

0.010.1

110
Average Query Time [ms]

100

1000

MNIST Database of Hand-Written Digits

1009080

Average Recall [%]70

Curse of Dimensionality
One can make the following observations withrespect to very high-dimensional data:

60
504030• The performance of classical data structures for

Brute Force
SASH
ANN KD-Tree
EELSH
RCT (h=3)
RCT (h=4)
Cover Tree

20

similarity search converges towards that of asequential scan.
• Point-to-point distances become
indistinguishable as they concentrate heavily
around their mean value.
• Individual search paths within a similarity searchdata structure can no longer be effectively
excluded from consideration.

1000.001

0.01

0.1

110
Average Query Time [ms]1001000

Reuters Corpus

100
9080

Additional Material

Average Recall [%]7060504030• Technical Report20• Poster10• Implementation

00.001

Brute ForceSASHRCT (h=3)
RCT (h=4)
Cover Tree0.01• Documentation

連絡先:Michael E. HOULE(フフー ル マ イ ケ ル )/国立情報学研究所
客員教授
 : 03 - 4212 - 2538
t : 03 - 3556 - 1916
B : meh @ nii.ac.jp

0.1

1
10
Average Query Time [ms]

100

1000

10000