Fast and exact fixed-radius neighbor search based on sorting
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10491220" target="_blank" >RIV/00216208:11320/24:10491220 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=pJtICrozOZ" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=pJtICrozOZ</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.7717/peerj-cs.1929" target="_blank" >10.7717/peerj-cs.1929</a>
Alternative languages
Result language
angličtina
Original language name
Fast and exact fixed-radius neighbor search based on sorting
Original language description
Fixed -radius near neighbor search is a fundamental data operation that retrieves all data points within a user -specified distance to a query point. There are efficient algorithms that can provide fast approximate query responses, but they often have a very compute -intensive indexing phase and require careful parameter tuning. Therefore, exact brute force and tree -based search methods are still widely used. Here we propose a new fixed -radius near neighbor search method, called SNN, that significantly improves over brute force and tree -based methods in terms of index and query time, provably returns exact results, and requires no parameter tuning. SNN exploits a sorting of the data points by their first principal component to prune the query search space. Further speedup is gained from an efficient implementation using high-level basic linear algebra subprograms (BLAS). We provide theoretical analysis of our method and demonstrate its practical performance when used standalone and when applied within the DBSCAN clustering algorithm.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10102 - Applied mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
PeerJ Computer Science
ISSN
2376-5992
e-ISSN
2376-5992
Volume of the periodical
10
Issue of the periodical within the volume
March 29, 2024
Country of publishing house
US - UNITED STATES
Number of pages
23
Pages from-to
e1929
UT code for WoS article
001194752800001
EID of the result in the Scopus database
2-s2.0-85190374252