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 条

[31] Efficient Nearest Neighbor Search by Removing Anti-hub
Tanaka, Kimihiro
Matsui, Yusuke
Satoh, Shin'ichi
PROCEEDINGS OF THE 2021 INTERNATIONAL CONFERENCE ON MULTIMEDIA RETRIEVAL (ICMR '21), 2021, : 285 - 293
[32] Bregman Hyperplane Trees for Fast Approximate Nearest Neighbor Search
Naidan, Bilegsaikhan
Hetland, Magnus Lie
INTERNATIONAL JOURNAL OF MULTIMEDIA DATA ENGINEERING & MANAGEMENT, 2012, 3 (04): : 75 - 87
[33] Visible Nearest Neighbor Search for Objects Moving on Consecutive Trajectories
Luo, Xinyuan
Chen, Ke
Pang, Guifeng
Shou, Lidan
Chen, Gang
2017 15TH IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL AND DISTRIBUTED PROCESSING WITH APPLICATIONS AND 2017 16TH IEEE INTERNATIONAL CONFERENCE ON UBIQUITOUS COMPUTING AND COMMUNICATIONS (ISPA/IUCC 2017), 2017, : 1296 - 1303
[34] Improvement by Sorting and Thresholding in PCA Based Nearest Neighbor Search
Ichihashi, Hidetomo
Ogita, Toshiro
Honda, Katsuhiro
Notsu, Akira
2012 IEEE INTERNATIONAL CONFERENCE ON FUZZY SYSTEMS (FUZZ-IEEE), 2012,
[35] STACKED PRODUCT QUANTIZATION FOR NEAREST NEIGHBOR SEARCH ON LARGE DATASETS
Wang, Jun
Li, Zhiyang
Du, Yegang
Qu, Wenyu
2016 IEEE TRUSTCOM/BIGDATASE/ISPA, 2016, : 1621 - 1627
[36] Fast nearest neighbor search algorithm using the cache technique
Choi, Wonseok
Oh, Seyoung
ADVANCED ROBOTICS, 2013, 27 (15) : 1175 - 1187
[37] The role of local dimensionality measures in benchmarking nearest neighbor search
Aumuller, Martin
Ceccarello, Matteo
INFORMATION SYSTEMS, 2021, 101
[38] Distributed Adaptive Binary Quantization for Fast Nearest Neighbor Search
Liu, Xianglong
Li, Zhujin
Deng, Cheng
Tao, Dacheng
IEEE TRANSACTIONS ON IMAGE PROCESSING, 2017, 26 (11) : 5324 - 5336
[39] Online Nearest Neighbor Search Using Hamming Weight Trees
Eghbali, Sepehr
Ashtiani, Hassan
Tahvildari, Ladan
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2020, 42 (07) : 1729 - 1740
[40] DOUBLE-BIT QUANTIZATION AND WEIGHTING FOR NEAREST NEIGHBOR SEARCH
Deng, Han
Xie, Hongtao
Ma, Wei
Mao, Zhendong
Zhou, Chuan
2017 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2017, : 1717 - 1721

← 1 2 3 4 5 →