Artikel,
Efficient Neighbor Searching in Nonlinear Time Series Analysis
International Journal of Bifurcation and Chaos, (1996)
Zusammenfassung
this paper that with relatively little effort a substantial factor in efficiency can be gained. The use of any intelligent algorithm can result in reducing CPU time (or increasing the maximal amount of data which can be handled with reasonable resources) by orders of magnitude, compared to which the differences among these methods and the gain through refinements of an existing algorithm are rather marginal. Thus we give a simple and general algorithm which is worth the effort even for sets of only moderate size. The box--assisted algorithm given here has been heuristically developed in the context of time series analysis Grassberger, 1990, Grassberger et al., 1991. Similar procedures are proposed for this purpose in Theiler, 1987, Kostelich & Yorke, 1988, while the k--d--tree (Sec. 2) seems to be the most popular approach Bingham & Kot, 1989, Farmer & Sidorowich, 1988. In Sec. 3 we describe a very simple version of a box--assisted algorithm for finding all points closer than a given distance ffl. In Sec. 4 we describe how it can be improved by using linked lists. To illustrate the usefulness of this data structure, a very fast sorting method is presented. Furthermore we describe how to modify the basic algorithm in order to find a given number of neighbors rather than a neighborhood of fixed diameter. In Sec. 5 we will discuss some examples of the performance of the algorithms described. For comparison we give results obtained using the k--d--tree algorithm described in Bingham & Kot, 1989, which represents a similar level of sophistication. Both the box--assisted and the tree implementation used were chosen rather for simplicity than for optimality. The reader who wants to go beyond this will find some suggestions in Sec. 6. 2 The classical approach: multidime...
