Multi-Step k-Nearest Neighbor Search
Using Intrinsic Dimension
Michael E. HOULE
11Xiguo MA
2National Institute of Informatics, Japan

2

Michael NETT

1,3Vincent ORIA
3

New Jersey Institute of Technology, USA

2

The University of Tokyo, Japan

Motivation

Generalized Expansion Dimension

Algorithm MAET+Most existing solutions for similarity search
fail in handling queries with respect to highdimensional or adaptable distance functions.
For such situations, researchers have proposed
multi-step search approaches consisting of twostages: filtering and refinement. The filtering
stage of the state-of-the-art multi-step search algorithm of Seidl and Kriegel is known to examine
the minimum number of candidates necessary toguarantee a correct query result; however, thenumber of examined candidates may be unacceptably large for some applications.
We propose a multi-step search heuristic(MAET) that utilizes a measure of intrinsic dimension, the generalized expansion dimension,as the basis of an early termination condition.

• Let B(q, r1) and B(q, r2) be two co-centric balls• Compared to MAET, the only change made inwith radii 0 < r1 < r2, each containing 0 < k1 < k2
points from S. The generalized expansion
dimension with respect to those balls is definedaslog k2 − log k1.
GED(B(q, r1), B(q, r2)) =log r2 − log r1• We define the inner ball set relative to a pointq ∈ S and a neighborhood size k > 2 as

MAET+ is that observed distance values areused to dynamically estimate the lower-bounding
ratio λ.
• After each candidate v is retrieved, the ratio ofd(q, v) over d 0(q, v) is computed, and the smallest
ratio encountered so far is used as the estimateof λ.

Here δk denotes the distance from q to its
k-nearest neighbor.
• The maximum generalized expansion dimension
relative to a point q and a neighborhood sizek > 2 is defined as follows:
MGED(q, k) = max{GED(B, B(q, δk)) | B ∈ B(q, k)}.
• Allows for the estimation of intrinsic dimension in

respect to d to retrieve the candidates.
• From the candidate set, the k-NN of q withrespect to d are stored as tentative query result,and the k-th smallest target distance (dmax) ismaintained. If the size of the candidate set issmaller than k, keep the value of dmax being
infinity.
• The algorithm terminates when the value of dmax
is no greater than the largest lower-bounding
distance value encountered so far.
• At termination, the value of dmax will have been
decreased to the exact k-th smallest distancefrom q to all the objects in S, ensuring theoptimality of the algorithm.

Justification of Heuristic Approach
Although Seidl and Kriegel’s Algorithm (SK) examines the minimal number of candidates required in order to guarantee a correct query result, the total number of examined objects canbe unacceptably large. The following figure
shows distance values encountered while processing a typical 10-NN query on a real data set.
In this example, the SK algorithm examines 64
candidates, although the correct neighbor set isavailable once the 17th candidate has been examined.

Algorithm MAET
• Sequentially scan the neighborhoods of q withrespect to d 0 to retrieve the candidates.
• From the candidate set, the k-NN of q withrespect to d are stored in P as tentative query
result, and the largest lower-bounding distance ismaintained as β 0.
• From the set P, find the number of points (k1) thathave target distances to q less than λβ 0, whereλ > 1 is the lower-bounding ratio.
• From the set P, compute r = δk and r1 = δk1 .
• The algorithm terminates when k1 = k or
k1(r/r1)t < k + 1, where t is a termination
parameter controlling the performance trade-off
between accuracy and computational cost.

Exact and lower-bounding distance

0.2
0.18

0.14
0.120.1
120406080Ranking according to lower-bounding distance

連絡先:MAET+ (t=32)
SK

510152025
Number of reduced dimensions

30(a) FCT

Area A1rv∈SArea A2242220
1816
141210864

MAET+ (t=8)
MAET+ (t=16)SK

1020
304050
Number of reduced dimensions

60(b) ALOI60

r1o(q)

d0 (q, v) β 0x• For a particular query q, the correctness of the0.16201816141210864
20y0.22
Lower-bounding distance
Exact distanceexperiments: Forest Cover Type (FCT),Amsterdam Library of Object Images (ALOI) andMNIST.
• Lower-bounding distance functions aregenerated by projecting the original feature
space of a data set to new feature spaces withreduced dimensions using the Karhunen-LoèveTransform.
• MAET+ is consistently competitive with MAET.
• For the FCT data set, the performances ofMAET+ and SK are similar. However, for theother two data sets, MAET+ shows much
improvement over SK while sacrificing little inaccuracy (less than 5%).
• The performance variance over three data sets
can be explained through the differences in their
MGED values.

Running time [in %]0• Three real data sets are used for thealgorithm can be guaranteed whenevert > MGED(q, k + 1).
• Termination parameter t can be chosen throughsampling of potential queries for Algorithm
MAET, in order to correctly answer a desired
proportion of potential queries with highprobability.

Running time [in %]• Sequentially scan the neighborhoods of q withv)

Find k-NN of query q with respect to a target
distance function d, given a lower-bounding distance function d 0:

the vicinity of q.
• Can be utilized to dynamically guide decisions
made in search algorithms.

d(q,Seidl and Kriegel’s Algorithm

Experiments

Running time [in %]B(q, k) = {B(q, δj) | j 6 k − 1, δj > 0} \ {B(q, δk)}.

MAET+ (t=16)
MAET+ (t=32)
SK

50
40
30
20
100
10

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

2030
4050
Number of reduced dimensions(c) MNIST60