Approximate Nearest Neighbor Search Small World Approach
Alexander Ponomarenko, Yury Mal’kov, Andrey Logvinov, Vladimir Krylov
MERA Labs LLC, Nizhny Novgorod, Russia
aponom@meralabs.com, ymalkov@meralabs.com, alogvinov@meralabs.com, vkrylov@meralabs.com

ABSTRACTIn this paper we propose a novel approach to solving the nearest
neighbor search problem. We propose to build a data structure
where the greedy search algorithm can be applied which is
known to have logarithmic complexity in structures withnavigable small world properties. The distinctive feature of ourapproach is that we build a non-hierarchical structure withpossibility of local minimums which are circumvented by
performing a series of searches starting from arbitrary elementsof the structure. The performed simulation shows that thestructure built using the proposed algorithms has navigablesmall world properties with logarithmic search complexity
which is retained even for high-dimensional data.
Keywords: Similarity Search, Small World, Distributed Data
Structure

relations, namely, pivoting and compact partitions encompass
all the existing methods. Pivot technique relies on taking
pivots and mapping the metric space onto
using thedistance and they can outperform a compact partitioning index
if it has enough memory. Methods based on compact partition
are more efficient for spaces with high dimensionality.
However, methods from both classes generally use either data
structures with tree topology (GNAT, GHT, SAT, BST, VT,MT) or, in some cases, distance matrix (ALAESA, LAESA)
We suggest using for solving nearest neighbor problem a data
structure with small word network topology presented by graph, where every object from is uniquely associatedwith vertex from . Thereby searching for the closest
element to query from the data set will take the form ofsearching for a vertex in the graph.
Application of that approach is based on follows:

1.

INTRODUCTION

We present a new approach for solving nearest neighbor search
problem in general metric space. This problem appears when
we need to find a closest object
from finite set of objects
to given query, where is the set of all possible
objects (data domain). Closeness or proximity of two objects
is defined as distance function.
In general, the search problem can be described as follows:
Let be a domain, d a distance measure on , and (ametric space. Given a setof elements, preprocess or
structure the data, so that proximity queries are answered
efficiently.
The nearest neighbor search problem is relevant to many
applications such as pattern recognition and classification [1],content-based image retrieval [2], machine learning [3],Recommendation systems [4], searching similar DNA sequence[5], semantic document retrieval [6].
In a trivial case data structure is a simple linear list. The
complexity of addition operation is, but searching for
closest object for requires evaluation of the metric function
for every element from the set of objects . This amounts tocomplexity, where is the number of objects in .
General way to reduce amount of distance measure calculations
consists of building a set of equivalence classes, discardingsome classes, and exhaustively searching the rest [7]. Authors
also showed that two main techniques based on equivalence

There exist algorithms for building small world
networks that have the ability to perform nearest
neighbor and addition of a new object to the structurewith complexity of[8].
Small world networks have no root element.
All operations (addition and search) use only local
information and can be initiated from any elementthat has been added to the structure.

This gives opportunity for building decentralized similarity
search oriented storage systems where physical data location
doesn’t depend on the content because every data object can beplaced on the arbitrary physical machine and can be connectedwith other by links like in p2p systems. Such storage systems
can provide simultaneous access to large numbers of users for
performing data search and addition), have good fault tolerance
and have unlimited scalability in terms of performance andcapacity.
One of the basic vertex search algorithms in graphs is greedy
search. This algorithm has simple implementation on the
structure that has small world network topology and can beinitiated from every vertex.
In order for the result of the algorithm to be the exact nearest
element to the query, the network should contain the Delaunaygraph as its subgraph, which is dual to the Voronoi tessellation[9].
However, the requirement of search in for the exact nearest
neighbor can be excessive (optional) for the applications

described above. So the problem for finding the exact nearest
neighbor can be substituted for the approximate nearest
neighbor search, since we don’t need to support whole/exact
Delaunay graph.
For the search algorithm to be logarithmically scalable, thesmall world network should have navigation property that was
already discussed in [8]In this paper we present the algorithm for data structure
construction based on small world network topology with graphwhich uses greedy search algorithm for finding
approximate nearest neighbor. Graph
contains
approximate Delaunay graph and has navigation property.
Search algorithm has the ability to change accuracy of searchwithout modification of the structure. Presented algorithms do
not use the coordinate representation and do not presume theproperties of linear spaces, because they are based only on themetric computation between objects, and therefore is applicable
to data from general metric spaces.

2.

RELATED WORKS

Kd-tree [10] and quadra trees [11] were among the firststructures for solving exact nearest neighbor search problem.
They perform well in 2-3 dimensions (search complexity isclose to), but analysis of the worst case for thatstructures [12] indicatessearch complexity,
where is dimensionality.
Other structures which have tree topology such as variants of
kd-trees, R-trees and structures based on space-filling curves are
surveyed in [13]. They also have good performance whensearching in a low-dimension () metric space, but theyquickly lose their effectiveness with increasing number ofdimensions [14]. A more effective data structure for exact
nearest neighbor search inwith search complexity
has been described in [15]. But as can be seen,
search complexity has exponential dependence from the numberof dimensions.
Structures such as mvp-tree [16], vps-tree and vpsb-tree [17] use“vantage point” technique, but no analysis has been provided
for search complexity in spaces with high number ofdimensions.
In general, presently there are no methods for effective exact
nearest neighbor search in high-dimensionality metric space.
The reason behind it lies in the "curse" of dimensionality [7].
To avoid the curse of dimensionality while retaining thelogarithmic scaling of the number of elements, it was
proposed to reduce the requirements for finding the nearest
neighbor, making it approximate.
Thus a large number of papers appeared which proposed tosearch for nearest neighbor with ε accuracy (ε-NNS). For
example, Arya and Mount proposed methods with searchcomplexity, but preprocessing requires
algorithm was applicable only to data from Ed [18].

andKleinberg proposed two methods [19] for solving ε-NNS. First
method requires
preprocessing time and query
time polynomial inand. Another method withpreprocessing polynomial in d, ε and n, but with query time
. Also both methods are applicable only to datafrom Ed
The first algorithms with search complexity polynomial in ,, ε-1 and polynomial preprocessing time for fixed ε were
proposed by Indyk and Motwani in [20] and Kushilevitz,
Ostrovsky and Rabani in [21]. Indyk and Motwani were the firstones to relax ε-ANN problem to approximate point location inequal balls (ε-PLEB). For the formulation of the problem in εPLEB points in metric space expand to the balls with center atthis point and radius (1+ ε)r, it is necessary to determine whichball belongs to the query . Also in [20] proposed a second
method, which uses the concept of locality-sensitive
hashing regarding formulation of the problem ε-PLEB, withsearch time,
however requires near quadratic memory (for small ε). In
addition, the first method is applicable only for , and thesecond for the Hamming space.
In general, the concept of locality-sensitive hashing has become
popular in the last decade to solve the ANN problem. Other
works using the concept of locality-sensitive hashing are [22],[23]. But they all have the same major drawback: eachalgorithm is focused on a narrow class of metrics such as
Hamming distance, Jakarta or norms for Euclidean space.
Thus it is necessary to create digests in order to decide which
method to choose.
The first structure for solving ANN in Ed with topology of small
world networks is Raynet [24]. It is an extension of earlier
work by the same authors Voronet [25], which solved the
problem of the exact NN in E2. Originally Voronet
was envisioned as a p2p network, where every node hascoordinates in E2. In Raynet every node has the coordinates in
Ed. The system supports two levels of links - short for correct
work of the greedy search algorithm and long - for logarithmic
search. Short links correspond to edges of Delaunay graph,i.e. each object has references to objects that are neighbors of its
Voronoi region. The main difference of Raynet from Voronet isthat in Raynet every object doesn’t know all of its Voronoi
neighbors, i.e. Raynet obtains neighborhood withapproximately using the Monte Carlo method.
Raynet is the closest work to ours in terms of general concept.
But unlike Raynet, we propose a structure that works with
objects from arbitrary metric spaces.

3.

STRUCTURE OVERVIEW

We solve the problem of approximate nearest neighbor search
formulated as follows: given objects from domain with

distance function. For finite set
an effective probability search method is required tofindwhich is closest to. Effective method meansthat search complexity must scale logarithmically with thenumber of elements in . The exact search is not guaranteed, i.e.
the result of the algorithm may be an element that is nottrue nearest neighbor, nevertheless structure and algorithms aredesigned to minimize the probability of this and there is apossibility to adjust it by varying the parameter of the searchalgorithm without changing the structure.
The structure of is constructed as a small world network
described by a graph, where the objects from the set
are uniquely mapped to the vertices from the set . The set ofedges is determined by the structure construction
algorithm, so as to ensure correct operation of the greedy searchalgorithm.
Since in the proposed structure each vertex is uniquely mapped
to an element from the set , we will use the terms"vertex", "element" or "object" interchangeably. We will use theterm “friends” for vertices that share an edge. List ofvertices that share a common edge with the vertex iscalled the friend list of vertex .

4.

SEARCH ALGORITHM

Greedy Search
The basic search algorithm traverses the edges of the graphfrom one vertex to another. The algorithm takes two
parameters: query and the vertex
whichis the starting point of search (the entry point). Starting from theentry point at each vertex the algorithm computes the metricvalue from query q to each vertex from the friend list of thecurrent vertex and then selects the vertex with minimal value ofthe metric. If the metric value between the query and theselected vertex is smaller than between the query and thecurrent element, then the algorithm moves to that vertex. Afterthat the algorithm repeats. The algorithm stops at the vertex
whose friend list doesn’t contain a vertex that is closer to thequery than the vertex itself. That vertex is a local minimum.
Greedy_Search(q: object, venter_point: object)
1 vcurr ← venter_point;
2 dmin ← d(q, vcurr); vnext ← NIL;
3 foreach vfriend
vcurr.getFriends() do
4if d(query, vfriend) < dmin then5dmin ← d(q, vfriend);
6
vnext ← vfriend;
7 if vnext = Nil then return vcurr;
8 else return Greedy_Search(q, vnext);
The element which is a local minimum with respect
to query q, can be either the true closest element to the query q
from the entire set of elements of , or a false closest..

If every element in the structure had in their friend list all of its
Voronoi neighbors, then this would exclude the existenceof false local minimums. Maintaining this condition isequivalent to constructing Delaunay graph, which is dual to theVoronoi diagram.
Because it is impossible to determine exact Delaunay graph [26](excluding the variant of the complete graph) we cannot avoid
the existence of local minimums.
But for the problem of approximate searching as defined
above it is not an obstacle since approximate search does not
require the entire Delaunay graph [24]. As shown below, theprobability of finding the true nearest element tends
exponentially towards 1 with increase of the average number ofedges in the approximated Delaunay graph.
Multi Search
In order to be able to find the true closest element in a
network with local minimums, we propose the following
modification of the search algorithm. We propose to use aseries of m searches initiated from random vertices and choose
the result element that is closest to the query from the set offound elements. Since the greedy search
Greedy_Search(q, venterPoint ϵ V)is deterministic foreach entry point venterPoint ϵ V it either results in a success finding the true nearest neigbor, or with a failure - finding theelement that is not the nearest neighbor of q.

Thus search of the closest element to the same query may
result in finding of the true nearest neighbor or a false nearest
neigbor depending on the entry point from which the searchalgorithm started.
Since we can choose the entry point at random, there is a
probability of finding the true closest to the particular elementq (but not to all elements). Moreover, this probability is always
nonzero, because it is always possible to choose the exact
nearest neighbor as the entry point, which subsequently will be
returned by the greedy search algorithm.
If probability to find true closest in one search attempt is p thenprobability to find the same element in search attempts is, so failure probability decreases exponentiallywith the number of search attempts. Thus, we can
improve search precision, increasing the parameter - number
independent searches.
Multi_Search(object q, integer: m)
1 results: SET[objects];
2 for (i0; i < m; i++) do
3
enter_point
getRandomEnterPoint();
4
local_min
Greedy_Search(query,enter_point)
5
if local_min
results then6
results.add(result);
7 return results;

7

3
8
6

9

10
A
D

B

C

1

0

4

5

11

Fig 1
If
, where is the number of elements in the structure,
the algorithm becomes exhaustive search.
If the graph of the network has small-world properties, then it ispossible tp choose a random vertex in a number of random steps
proportional to, which doesn’t affect overall logarithmic
search complexity.
Therefore the overall complexity of the search will increase no
more than times.

5.

DATA ADDITION ALGORITHM

Since we build an approximation of the Delaunay graph, there
is much freedom in the choice of construction algorithm. For
example in [24] it is proposed to build approximate Delaunaygraph which minimizes the volume of Voronoi region for a
fixed number of edges for each vertex in the graph. In [27] it is
proposed to connect new element with k closest objects which
are already in the structure. It is based on the idea thatintersection of the set of elements which are Voronoi neighbors
and the k closest elements is large. In [27], [28] authors also
have shown theoretically and confirmed by experimental resultsthat graph which constructed by proposed algorithm hasproperties of small world network if elements arrive in random
order.
We propose a modified variant of this algorithm which isdistinguished by the fact that that the search for k nearest
elements uses a series of searches.
The algorithm takes three parameters: the object to be added tothe structure and two positive integers k
and init_attempts. First, the algorithm determines a setof local minima, using the procedure Multi_Search, which

produces a series of independent searches on init_attempts ofrandomly selected elements from the set of objects that alreadyhave been added to the structure. After that algorithm
determines neighborhood u, which contains all neighbors ofeach found local minimums. Set u is sorted in ascending orderby distance from the object new_object to be added. Afterthat new_object is connected with thefirst K nearest elements from the set of u.
Nearest_Neighbor_Add(object: new_object,integer: k, integer: init_attempts)
1 SET[object]: localMins
MultiAttempts_Search(new_object,
init_attempts);
2 SET[object]: u; //neighborhood;
3 foreach object: local_min
localMinsdo
4uu
local_min.getFriends();
6 sort the set u so to satisfy thecondition d(u[i], new_object) < d(u[i+1],
new_object)
7 for (i0; i < k; i++) do
8u[i].connect(new_object);9
new_object.connect(u[i]);Fig 1 shows the structure which is constructed by
Nearest_Neighbor_Add algorithm for points from E2.
Circles denote the elements. The numbers nearthems correspond to the addition order. Solid lines show
the links (edges) between elements. Dotted lines correspond tothe borders of Voronoi tessellation. Delaunay graph edges
between elements 0 and 10, 1 and 9 are missing. The
structure obtained by the algorithm with parameters m = 3
and attemptsNumber = 5. Element with number 0 is a local
minimum, which is not the closest to queries that fall into theshaded area "A", respectively 10 for the "B", 9 for D and 1 forthe region"C". Hatched lines show the paths of the two searchalgorithm runs for query q in the region "B". The algorithm run
which starts from vertex 7 stops on the element 10 which is
local minimum, but not the closest to the query q. However,
the algorithm run which starts from vertex 5 finds the true
closest vertex to the query q.

6.

EXPERIMENT RESULTS
D=10
D=20
D=40
D=5

Fraction of visited elements

1

assumption that there is no exponential dependence from thedimension of space. But it requires more careful study.

7.

CONCLUSION

We have proposed a method of organizing data into a small
world topology data structure suited for approximate nearest
neighbor search in metric space.
We have created a modified nearest neighbor connection
algorithm which is one of the possible algorithms forconstruction of small world data structures with navigation
properties.
Simulation results confirm logarithmic dependency of searchcomplexity from the number of elements in the structure.
All proposed algorithms use only local information on each stepand can be initiated from any vertex.

0,1

All elements in the structure are of the same type, there is nocentral or root element.

0,01

Thus, all mentioned structure properties are a basis for using thestructure for building totally decentralized data storage systems.
10

100

1000

10000

1000001000000

Items count

8.

REFERENCES

Fig 2

We have implemented the algorithms presented above in orderto validate our assumptions about
the logarithmic search complexity dependence of the total
number of elements.
We used randomly selected points from the ED as test
dataset. L2 (Euclidean distance) was selected as proximity
function
elements were added to the structure. We chose the number ofsearch attempts m so that the probability of finding the true
closest element to the query was not less than 95%. The numberof metric calculations was measured. The graph shows
the percent of scanned elements (vertical) with an increasein the number of added elements in the structure (horizontal).

[1] T. M. Cover and P. E. Hart, "Nearest neighbor patternclassification," Information Theory, IEEE Transactions on,
vol. 13, no. 1, pp. 21-27, Jan. 1967.
[2] M. Flickner, et al., "Query by image and video content: theQBIC system ," Computer, vol. 28, no. 9, pp. 23-32, Sep.
1995 .
[3] Salzberg, S. Cost, and Steven, "A Weighted Nearest
Neighbor Algorithm for Learning with Symbolic
Features," Machine Learning, vol. 10, no. 1, pp. 57-78,
1993.
[4] B. Sarwar, G. Karypis, J. Konstan, and J. Reidl, "Itembased collaborative filtering recommendation algorithms,"
in Proceedings of the 10th international conference on
World Wide Web, New York, USA, 2001, pp. 285-295.

The graph (Fig 2) shows that with the increase of numberof elements in the structure, the percentage of visited elements
decreases, and the curve becomes a straight line with angle 45
degrees. This gives us grounds to speakof logarithmic complexity of the search on the numberof scanned elements.

[5] Rhoads, W. Rychlik, and R. Unknown, "A computer
program for choosing optimal oligonudeotides for filter
hybridization, sequencing and in vitro amplification ofDNA," Nucletic Acids Research, vol. 17, no. 21, pp. 85438551, Oct. 1989.

The graph shows that the curve for higher
dimensions behaves similarly. From this we can make the[6] S. Deerwester, S. Dumais, G. Furnas, T. Landauer, and R.
Harshman, "Indexing by Latent Semantic Analysis," J.

Amer. Soc. Inform. Sci., vol. 41, pp. 391-407, 1990.
[7] E. Chávez, G. Navarro, R. Baeza-Yates, and J. L.
Marroquín, "Searching in metric space," Journal ACM
Computing Surveys (CSUR), vol. 33, no. 3, pp. 273-321,
Sep. 2001.
[8] J. Kleinberg, "The Small-World Phenomenon: An
Algorithmic Perspective," ANNUAL ACM SYMPOSIUM
ON THEORY OF COMPUTING, vol. 32, pp. 163-170,
2000.
[9] F. Aurenhammer, "Voronoi diagrams — a survey of afundamental geometric data structure," ACM Computing
Surveys (CSUR), vol. 23, no. 3, pp. 345-405, Sep. 1991.
[10] J. L. Bentley, "Multidimensional binary search trees used
for associative searching," Communications of the ACM,
vol. 18 , no. 9, pp. 509-517, Sep. 1975.
[11] Bentley and R. Finkel, "Quad Trees: A Data Structure forRetrieval on Composite Keys," Acta Informatica, vol. 4,
no. 1, pp. 1-9, 1974.
[12] Wong and Lee, "Worst-case analysis for region and partial
region searches in multidimensional binary search trees
and balanced quad trees," Acta Informatica, vol. 9, no. 1,
pp. 23-29, 1977.
[13] H. Samet, The design and analysis of spatial data
structures. Addison-Wesley, Reading, MA, 1989.
[14] Mount, Arya, and Narayan, "Accounting for boundary
effects in nearest-neighbor searching," Discrete &Computational Geometry, vol. 16, no. 2, pp. 155-176,
1996.
[15] D. Dobkin and R. Lipton, "Multidimensional Searching
Problems," SIAM J. Comput, vol. 5, no. 2, pp. 181-186,
1976.
[16] T. Bozkaya and M. Ozsoyoglu, "Distance-based indexing
for high-dimensional metric spaces," in Proceedings of the1997 ACM SIGMOD international conference on
Management of data, New York, USA, 1997, pp. 357-368.
[17] P. Yianilos, "Data structures and algorithms for nearest
neighbor search in general metric spaces," in SODA '93
Proceedings of the fourth annual ACM-SIAM Symposium
on Discrete algorithms, Philadelphia, USA, 1993, pp. 311321.
[18] S. Arya and D. Mount, "Approximate nearest neighborqueries in fixed dimensions," in SODA '93 Proceedings ofthe fourth annual ACM-SIAM Symposium on Discretealgorithms, Philadelphia, PA, USA, 1993, pp. 271-280.

[19] J. Kleinberg, "Two algorithms for nearest-neighbor searchin high dimensions," in STOC '97 Proceedings of thetwenty-ninth annual ACM symposium on Theory ofcomputing , New York, USA, 1997, pp. 599-608.
[20] Motwani, P. Indyk, and Rajeev, "Approximate nearest
neighbors: towards removing the curse of dimensionality,"in STOC '98 Proceedings of the thirtieth annual ACM
symposium on Theory of computing, New York, USA,1998, pp. 604-613.
[21] E. Kushilevitz, R. Ostrovsky, and Y. Rabani, "Efficient
search for approximate nearest neighbor in highdimensional spaces," in STOC '98 Proceedings of thethirtieth annual ACM symposium on Theory of computing,
New York, NY, USA, 1998, pp. 614-623.
[22] A. Gionis, P. Indyk, and R. Motwani, "Similarity Search inHigh Dimensions via Hashing," in VLDB '99 Proceedingsof the 25th International Conference on Very Large Data
Bases, San Francisco, USA, 1999, pp. 518-529.
[23] A. Andoni and P. Indyk, "Near-Optimal Hashing
Algorithms for Approximate Nearest Neighbor in High
Dimensions," in 47th Annual IEEE Symposium on
Foundations of Computer Science (FOCS'06), Berkeley,
California , 2006, pp. 459-468.
[24] O. Beaumont, A.-M. Kermarrec, and É. Rivière, "Peer topeer multidimensional overlays: approximating complex
structures," in Proceedings of the 11th international
conference on Principles of distributed systems, Berlin,
Heidelberg, 2007, pp. 315-328.
[25] O. Beaumont, A.-M. Kermarrec, L. Marchal, and E.
Riviere, "VoroNet: A scalable object network based on
Voronoi tessellations," in International Parallel andDistributed Processing Symposium, Long Beach, USA ,2007, p. 20.
[26] G. Navarro, "Searching in metric spaces by spatial
approximation," in String Processing and Information
Retrieval Symposium, Cancun, Mexico, 1999, pp. 141-148.
[27] Krylov, Logvinov, Ponomarenko, and Ponomarev,"Metrized Small World Properties Data Structure," in
SEDE, Los Angeles, California USA, 2008.
[28] V. Krylov, A. Ponomarenko, A. Logvinov, and D.
Ponomarev, "Single-attribute Distributed Metrized Small
World Data Structure‖," in IEEE International Conferenceon Intelligent Computing and Intelligent Systems (CAS),
2009.