Searching in General Metric Spaces

Abstract

This paper begins with an overview of the classical problem of Nearest Neighbor Searching (NNS) in normed vector spaces. As we progress through the literature on the subject, we simultaneously increase the generality of the setting until we reach the case of searching in general metric spaces. At that point, the characteristic that controls the hardness of nearest-neighbor searching becomes elusive. Nevertheless, we argue with concrete examples that at least in the high-precision regime, the complexity of the Approximate Nearest Neighbor (ANN) problem critically depends on the doubling dimension of a metric space. After briefly demonstrating the weakness of the KR-dimension as a definition of metric dimension, we begin a systematic review of searching with hierarchical nets and prove a new upper bound on the complexity of range queries in the Cover Tree model. The paper culminates in the presentation of our own dynamic ANN data structure, which answers $(1+\eps)-$ANN queries in $2^{O(\dim(S))} \min \{\log \D, \log d(q, \net_s)\} + O(|\net_s|) + O(\log n) + (1/\eps)^{O(\dim(S))}$ time, consumes $O(n^2)$ space, answers $R-$Range queries in $2^{O(\dim(S))} \log \D + \log (R/\dm) |B(q, O(R))|$ time and supports efficient insertions and deletions of points.