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 条

[11] Online learning to Hash for nearest neighbor search
Qian J.-B.
Hu W.
Chen H.-H.
Dong Y.-H.
Kongzhi yu Juece/Control and Decision, 2019, 34 (12): : 2567 - 2575
[12] Explicit Embeddings for Nearest Neighbor Search with Mercer Kernels
Anthony Bourrier
Florent Perronnin
Rémi Gribonval
Patrick Pérez
Hervé Jégou
Journal of Mathematical Imaging and Vision, 2015, 52 : 459 - 468
[13] Nearest Neighbor Search for Summarization of Japanese Judgment Documents
Shimbo, Akito
Sugawara, Yuta
Yamada, Hiroaki
Tokunaga, Takenobu
LEGAL KNOWLEDGE AND INFORMATION SYSTEMS, 2023, 379 : 335 - 340
[14] A Spatial Cloaking Framework Based on Range Search for Nearest Neighbor Search
Kim, Hyoungshick
DATA PRIVACY MANAGEMENT AND AUTONOMOUS SPONTANEOUS SECURITY, 2010, 5939 : 93 - 105
[15] An Error Minimizing Partitioning Method for the Nearest Neighbor Search
Lee, Seunghoon
Kim, Jaekwang
Lee, Jaedong
Lee, Jee-Hyong
MECHATRONICS AND INDUSTRIAL INFORMATICS, PTS 1-4, 2013, 321-324 : 2165 - 2170
[16] PRODUCT TREE QUANTIZATION FOR APPROXIMATE NEAREST NEIGHBOR SEARCH
Yuan, Jiangbo
Liu, Xiuwen
2015 IEEE INTERNATIONAL CONFERENCE ON IMAGE PROCESSING (ICIP), 2015, : 2035 - 2039
[17] Randomized Approximate Nearest Neighbor Search with Limited Adaptivity
Liu, Mingmou
Pan, Xiaoyin
Yin, Yitong
ACM TRANSACTIONS ON PARALLEL COMPUTING, 2018, 5 (01)
[18] Nearest Neighbor Subsequence Search in Time Series Data
Ahsan, Ramoza
Bashir, Muzammil
Neamtu, Rodica
Rundensteiner, Elke A.
Sarkozy, Gabor
2019 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA), 2019, : 2057 - 2066
[19] FAST NEAREST NEIGHBOR SEARCH WITH TRANSFORMED RESIDUAL QUANTIZATION
Yuan, Jiangbo
Liu, Xiuwen
2016 15TH IEEE INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND APPLICATIONS (ICMLA 2016), 2016, : 971 - 976
[20] Explicit Embeddings for Nearest Neighbor Search with Mercer Kernels
Bourrier, Anthony
Perronnin, Florent
Gribonval, Remi
Perez, Patrick
Jegou, Herve
JOURNAL OF MATHEMATICAL IMAGING AND VISION, 2015, 52 (03) : 459 - 468

← 1 2 3 4 5 →