Access Restriction

Author Arya, Sunil ♦ Mount, David M. ♦ Netanyahu, Nathan S. ♦ Silverman, Ruth ♦ Wu, Angela Y.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1998
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Approximation algorithms ♦ Box-decomposition trees ♦ Closet-point queries ♦ Nearest neighbor searching ♦ Post-office problem ♦ Priority search
Abstract Consider a set of $\textit{S}$ of $\textit{n}$ data points in real $\textit{d}-dimensional$ space, Rd, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess $\textit{S}$ into a data structure, so that given any query point $\textit{q}$ ∈;d is a factor depending only on dimension and ε. In general, we show that given an integer $\textit{k}$ ≥ 1, (1 + ε)-approximations to the $\textit{k}$ nearest neighbors of $\textit{q}$ can be computed in additional $\textit{O(kd}$ log $\textit{n})$ time.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1998-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 45
Issue Number 6
Page Count 33
Starting Page 891
Ending Page 923

Open content in new tab

   Open content in new tab
Source: ACM Digital Library