TY - GEN
T1 - A unified approach to approximate proximity searching
AU - Arya, Sunil
AU - Da Fonseca, Guilherme D.
AU - Mount, David M.
PY - 2010
Y1 - 2010
N2 - The inability to answer proximity queries efficiently for spaces of dimension d > 2 has led to the study of approximation to proximity problems. Several techniques have been proposed to address different approximate proximity problems. In this paper, we present a new and unified approach to proximity searching, which provides efficient solutions for several problems: spherical range queries, idempotent spherical range queries, spherical emptiness queries, and nearest neighbor queries. In contrast to previous data structures, our approach is simple and easy to analyze, providing a clear picture of how to exploit the particular characteristics of each of these problems. As applications of our approach, we provide simple and practical data structures that match the best previous results up to logarithmic factors, as well as advanced data structures that improve over the best previous results for all aforementioned proximity problems.
AB - The inability to answer proximity queries efficiently for spaces of dimension d > 2 has led to the study of approximation to proximity problems. Several techniques have been proposed to address different approximate proximity problems. In this paper, we present a new and unified approach to proximity searching, which provides efficient solutions for several problems: spherical range queries, idempotent spherical range queries, spherical emptiness queries, and nearest neighbor queries. In contrast to previous data structures, our approach is simple and easy to analyze, providing a clear picture of how to exploit the particular characteristics of each of these problems. As applications of our approach, we provide simple and practical data structures that match the best previous results up to logarithmic factors, as well as advanced data structures that improve over the best previous results for all aforementioned proximity problems.
UR - https://openalex.org/W2156808455
UR - https://www.scopus.com/pages/publications/78249262081
U2 - 10.1007/978-3-642-15775-2_32
DO - 10.1007/978-3-642-15775-2_32
M3 - Conference Paper published in a book
SN - 3642157742
SN - 9783642157745
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 374
EP - 385
BT - Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
T2 - 18th Annual European Symposium on Algorithms, ESA 2010
Y2 - 6 September 2010 through 8 September 2010
ER -