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 条

[21] Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search
Jaasaari, Elias
Hyvonen, Ville
Roos, Teemu
ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PAKDD 2019, PT II, 2019, 11440 : 590 - 602
[22] Quality and Efficiency in High Dimensional Nearest Neighbor Search
Tao, Yufei
Yi, Ke
Sheng, Cheng
Kalnis, Panos
ACM SIGMOD/PODS 2009 CONFERENCE, 2009, : 563 - 575
[23] A scalable solution to the nearest neighbor search problem through local-search methods on neighbor graphs
Tellez, Eric S.
Ruiz, Guillermo
Chavez, Edgar
Graff, Mario
PATTERN ANALYSIS AND APPLICATIONS, 2021, 24 (02) : 763 - 777
[24] A scalable solution to the nearest neighbor search problem through local-search methods on neighbor graphs
Eric S. Tellez
Guillermo Ruiz
Edgar Chavez
Mario Graff
Pattern Analysis and Applications, 2021, 24 : 763 - 777
[25] Probabilistic cost model for nearest neighbor search in image retrieval
Kim, Kunho
Hasan, Mohammad K.
Heo, Jae-Pil
Tai, Yu-Wing
Yoon, Sung-eui
COMPUTER VISION AND IMAGE UNDERSTANDING, 2012, 116 (09) : 991 - 998
[26] Fast additive quantization for vector compression in nearest neighbor search
Li, Jin
Lan, Xuguang
Wang, Jiang
Yang, Meng
Zheng, Nanning
MULTIMEDIA TOOLS AND APPLICATIONS, 2017, 76 (22) : 23273 - 23289
[27] Fast additive quantization for vector compression in nearest neighbor search
Jin Li
Xuguang Lan
Jiang Wang
Meng Yang
Nanning Zheng
Multimedia Tools and Applications, 2017, 76 : 23273 - 23289
[28] Processing a multimedia join through the method of nearest neighbor search
Kosch, H
Atnafu, S
INFORMATION PROCESSING LETTERS, 2002, 82 (05) : 269 - 276
[29] Efficient search for approximate nearest neighbor in high dimensional spaces
Kushilevitz, E
Ostrovsky, R
Rabani, Y
SIAM JOURNAL ON COMPUTING, 2000, 30 (02) : 457 - 474
[30] A Fast Approximate Nearest Neighbor Search Algorithm in the Hamming Space
Esmaeili, Mani Malek
Ward, Rabab Kreidieh
Fatourechi, Mehrdad
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2012, 34 (12) : 2481 - 2488

← 1 2 3 4 5 →