Fast nearest-neighbor searching for nonlinear signal processing

被引：46
|
作者：
Merkwirth, C [1 ]
Parlitz, U [1 ]
Lauterborn, W [1 ]
机构：
[1] Univ Gottingen, Drittes Phys Inst, D-37073 Gottingen, Germany
来源：
PHYSICAL REVIEW E | 2000年 / 62卷 / 02期
关键词：
D O I：
10.1103/PhysRevE.62.2089
中图分类号：
O35 [流体力学]; O53 [等离子体物理学];
学科分类号：
070204 ; 080103 ; 080704 ;
摘要：
A fast algorithm for exact and approximate nearest-neighbor searching is presented that is suitable for tasks encountered in nonlinear signal processing. Empirical benchmarks show that the algorithm's performance depends mainly on the (fractal) dimension D-d of the data set, which is usually smaller than the dimension D-s of the vector space in which the data points are embedded. We also compare the running time of our algorithm with those of two previously proposed algorithms for nearest-neighbor searching.
引用
收藏
页码：2089 / 2097
页数：9
相关论文
共 50 条
  • [21] Nearest-neighbor methods
    Sutton, Clifton
    WILEY INTERDISCIPLINARY REVIEWS-COMPUTATIONAL STATISTICS, 2012, 4 (03): : 307 - 309
  • [22] On nearest-neighbor graphs
    Eppstein, D
    Paterson, MS
    Yao, FF
    DISCRETE & COMPUTATIONAL GEOMETRY, 1997, 17 (03) : 263 - 282
  • [23] Fast and Accurate Estimation of the HARDI Signal in Diffusion MRI Using a Nearest-Neighbor Interpolation Approach
    Ben Alaya, I.
    Jribi, M.
    Ghorbel, F.
    Sappey-Marinier, D.
    Kraiem, T.
    IRBM, 2017, 38 (03) : 156 - 166
  • [24] Improving motion-planning algorithms by efficient nearest-neighbor searching
    Yershova, Anna
    LaValle, Steven M.
    IEEE TRANSACTIONS ON ROBOTICS, 2007, 23 (01) : 151 - 157
  • [25] SOME HEURISTICS FOR NEAREST-NEIGHBOR SEARCHING IN CHEMICAL-STRUCTURE FILES
    WILLETT, P
    JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1983, 23 (01): : 22 - 25
  • [26] Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures
    Agarwal, Pankaj K.
    Fox, Kyle
    Munagala, Kamesh
    Nath, Abhinandan
    PODS'16: PROCEEDINGS OF THE 35TH ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, 2016, : 429 - 440
  • [27] Fast Approximate Nearest-Neighbor Field by Cascaded Spherical Hashing
    Torres-Xirau, Iban
    Salvador, Jordi
    Perez-Pellitero, Eduardo
    COMPUTER VISION - ACCV 2014, PT IV, 2015, 9006 : 461 - 475
  • [28] Can Nearest Neighbor Searching Be Simple and Always Fast?
    Alvarez, Victor
    Kirkpatrick, David G.
    Seidel, Raimund
    ALGORITHMS - ESA 2011, 2011, 6942 : 82 - 92
  • [29] TRANSPOSING CONDUCTORS IN SIGNAL BUSES TO REDUCE NEAREST-NEIGHBOR CROSSTALK
    VOELKER, RH
    IEEE TRANSACTIONS ON MICROWAVE THEORY AND TECHNIQUES, 1995, 43 (05) : 1095 - 1099
  • [30] Nearest-Neighbor Error Correcting Codes on a Hexagonal Signal Constellation
    Morita, Hiroyoshi
    2015 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2015, : 2480 - 2484
12345