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 条
  • [1] Fast nearest-neighbor searching for nonlinear signal processing
    Merkwirth, Christian
    Parlitz, Ulrich
    Lauterborn, Werner
    Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, 2000, 62 (2 A): : 2089 - 2097
  • [2] Accounting for boundary effects in nearest-neighbor searching
    Arya, S
    Mount, DM
    Narayan, O
    DISCRETE & COMPUTATIONAL GEOMETRY, 1996, 16 (02) : 155 - 176
  • [3] New Directions in Approximate Nearest-Neighbor Searching
    Mount, David M.
    ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2019, 2019, 11394 : 1 - 15
  • [4] Nearest-Neighbor Searching Under Uncertainty I
    Pankaj K. Agarwal
    Alon Efrat
    Swaminathan Sankararaman
    Wuzhou Zhang
    Discrete & Computational Geometry, 2017, 58 : 705 - 745
  • [5] Hit-directed nearest-neighbor searching
    Shanmugasundaram, V
    Maggiora, GM
    Lajiness, MS
    JOURNAL OF MEDICINAL CHEMISTRY, 2005, 48 (01) : 240 - 248
  • [6] Nearest-Neighbor Searching Under Uncertainty II
    Agarwal, Pankaj K.
    Aronov, Boris
    Har-Peled, Sariel
    Phillips, Jeff M.
    Yi, Ke
    Zhang, Wuzhou
    ACM TRANSACTIONS ON ALGORITHMS, 2016, 13 (01)
  • [7] Nearest-Neighbor Searching Under Uncertainty I
    Agarwal, Pankaj K.
    Efrat, Alon
    Sankararaman, Swaminathan
    Zhang, Wuzhou
    DISCRETE & COMPUTATIONAL GEOMETRY, 2017, 58 (03) : 705 - 745
  • [8] A fast algorithm for the nearest-neighbor classifier
    Djouadi, A
    Bouktache, E
    IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1997, 19 (03) : 277 - 282
  • [9] Fast nearest-neighbor query processing in moving-object databases
    Raptopoulou, K
    Papadopoulos, AN
    Manolopoulos, Y
    GEOINFORMATICA, 2003, 7 (02) : 113 - 137
  • [10] Fast Nearest-Neighbor Query Processing in Moving-Object Databases
    K. Raptopoulou
    A.N. Papadopoulos
    Y. Manolopoulos
    GeoInformatica, 2003, 7 : 113 - 137
12345