Practical Nearest Neighbor Search in the Plane

被引：0

作者：

Connor, Michael ^{[1
]}

Kumar, Piyush ^{[1
]}

机构：

[1] Florida State Univ, Dept Comp Sci, Tallahassee, FL 32306 USA

来源：

EXPERIMENTAL ALGORITHMS, PROCEEDINGS | 2010年 / 6049卷

关键词：

Nearest Neighbor Search; Delaunay Triangulation; Morton ordering; Randomized algorithms;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper shows that using some very simple practical assumptions, one can design an algorithm that finds the nearest neighbor of a given query point in O(log n) time in theory and faster than the state of the art in practice. The algorithm and proof are both simple and the experimental results clearly show that we can beat the state of the art on most distributions in two dimensions.

引用

页码：501 / 512

页数：12

共 50 条

[1] Succinct nearest neighbor search
Tellez, Eric Sadit
Chavez, Edgar
Navarro, Gonzalo
INFORMATION SYSTEMS, 2013, 38 (07) : 1019 - 1030
[2] Revisiting kd-tree for Nearest Neighbor Search
Ram, Parikshit
Sinha, Kaushik
KDD'19: PROCEEDINGS OF THE 25TH ACM SIGKDD INTERNATIONAL CONFERENCCE ON KNOWLEDGE DISCOVERY AND DATA MINING, 2019, : 1378 - 1388
[3] Projection Search For Approximate Nearest Neighbor
Feng, Cheng
Yang, Bo
2016 17TH IEEE/ACIS INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCE, NETWORKING AND PARALLEL/DISTRIBUTED COMPUTING (SNPD), 2016, : 33 - 38
[4] Hardness of Approximate Nearest Neighbor Search
Rubinstein, Aviad
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 1260 - 1268
[5] Fast Nearest Neighbor Search with Keywords
Tao, Yufei
Sheng, Cheng
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2014, 26 (04) : 878 - 888
[6] QuickN: Practical and Secure Nearest Neighbor Search on Encrypted Large-Scale Data
Wang, Boyang
Hou, Yantian
Li, Ming
IEEE TRANSACTIONS ON CLOUD COMPUTING, 2022, 10 (03) : 2066 - 2078
[7] Locally Optimized Hashing for Nearest Neighbor Search
Tokui, Seiya
Sato, Issei
Nakagawa, Hiroshi
ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PART II, 2015, 9078 : 498 - 509
[8] Hash Bit Selection for Nearest Neighbor Search
Liu, Xianglong
He, Junfeng
Chang, Shih-Fu
IEEE TRANSACTIONS ON IMAGE PROCESSING, 2017, 26 (11) : 5367 - 5380
[9] Singleton indexes for nearest neighbor. search
Tellez, E. S.
Ruiz, G.
Chavez, E.
INFORMATION SYSTEMS, 2016, 60 : 50 - 68
[10] Confirmation Sampling for Exact Nearest Neighbor Search
Christiani, Tobias
Pagh, Rasmus
Thorup, Mikkel
SIMILARITY SEARCH AND APPLICATIONS, SISAP 2020, 2020, 12440 : 97 - 110

← 1 2 3 4 5 →