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

共 16 条

[1]

Abarbanel H, 1996, ANAL OBSERVED CHAOTI

[2] An optimal algorithm for approximate nearest neighbor searching in fixed dimensions [J].

Arya, S ;

Mount, DM ;

Netanyahu, NS ;

Silverman, R ;

Wu, AY .

JOURNAL OF THE ACM, 1998, 45 (06) :891-923

[3] MAXIMUM HYPERCHAOS IN GENERALIZED HENON MAPS [J].

BAIER, G ;

KLEIN, M .

PHYSICS LETTERS A, 1990, 151 (6-7) :281-284

[4] DESIGN OF HYPERCHAOTIC FLOWS [J].

BAIER, G ;

SAHLE, S .

PHYSICAL REVIEW E, 1995, 51 (04) :R2712-R2714

[5]

Berchtold S., 1997, Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1997, P78, DOI 10.1145/263661.263671

[6]

CHENG DY, 1984, P IEEE INT C AC SPEE

[7]

Grassberger Peter, 1993, Chaos, V3, P127, DOI 10.1063/1.165979

[8] FRACTAL MEASURES AND THEIR SINGULARITIES - THE CHARACTERIZATION OF STRANGE SETS [J].

HALSEY, TC ;

JENSEN, MH ;

KADANOFF, LP ;

PROCACCIA, I ;

SHRAIMAN, BI .

PHYSICAL REVIEW A, 1986, 33 (02) :1141-1151

[9]

Kantz H, 1997, Nonlinear Time Series Analysis

[10]

McNames J., 1998, P INT WORKSH ADV BLA, P112

← 1 2 →