Skip navigation
Please use this identifier to cite or link to this item:
Title: Searching in General Metric Spaces
Authors: Papazov, Hristo
Advisors: Naor, Assaf
Department: Mathematics
Class Year: 2021
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.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2021

Files in This Item:
File Description SizeFormat 
PAPAZOV-HRISTO-THESIS.pdf357.48 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.