kdtree2.lyx

kd tree java implementation 2

\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

KDTREE2
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

old KDTREE
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

1
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

162751
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

70712
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

5
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

82904
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

31782
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

10
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

57243
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

20508
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

25
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

33738
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

11075
\end_inset 
</cell>
</row>
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

500
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

3001
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

261
\end_inset 
</cell>
</row>
</lyxtabular>

\end_inset 

 
\layout Standard

For 5,000 points in 8-dimensional unit hypercube:
\layout Standard
\align center 

\begin_inset  Tabular
<lyxtabular version="3" rows="6" columns="3">
<features>
<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
<column alignment="right" valignment="top" leftline="true" width="0">
<column alignment="right" valignment="top" leftline="true" rightline="true" width="0">
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $m$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

KDTREE2
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

old KDTREE
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

1
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

36258
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

19657
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

5
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

16876
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

7608
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

10
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

11790
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

4930
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

25
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

7133
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

3259
\end_inset 
</cell>
</row>
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

500
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

1497
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

188
\end_inset 
</cell>
</row>
</lyxtabular>

\end_inset 

 
\layout Standard

For 50,000 points in 8-dimensional unit hypercube.
 For the large data sets in higher dimensions, the new package shows the
 largest performance gain.
\layout Standard
\align center 

\begin_inset  Tabular
<lyxtabular version="3" rows="6" columns="3">
<features>
<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
<column alignment="right" valignment="top" leftline="true" width="0">
<column alignment="right" valignment="top" leftline="true" rightline="true" width="0">
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $m$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

KDTREE2
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

old KDTREE
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

1
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

8940
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

2050
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

5
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

4338
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

874
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

10
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

3144
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

601
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

25
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

2069
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

359
\end_inset 
</cell>
</row>
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

500
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

396
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

49
\end_inset 
</cell>
</row>
</lyxtabular>

\end_inset 


\layout Section

licensing
\layout Standard

The KDTREE2 software is licensed under the terms of the Academic Free Software
 License, included in file 
\family typewriter 
LICENSE 
\family default 
included with the software.
 In addition, users of this software must give appropriate citation in relevant
 technical documentation or journal paper to the author, Matthew B.
 Kennel, Institute For Nonlinear Science, preferably via a reference to
 the www.arxiv.org repository of this document.
 This requirement will be deemed to be advisory and not mandatory as is
 necessary for the purpose of inclusion of the present software with any
 software licensed under the GNU General Public License.
\layout Standard

This software is downloadable by anonymous FTP at 
\family typewriter 
ftp://lyapunov.ucsd.edu /pub/nonlinear/kd_tree/kdtree2.[zip|tar.gz].
\layout Bibliography
\bibitem {Moore91}

A.
 W.
 Moore, 
\begin_inset Quotes eld
\end_inset 

An introductory tutorial on Kd-Trees.
 Extract from Efficient Memory-based Learning for Robot Control
\begin_inset Quotes erd
\end_inset 

 (Technical Report 209).
 Computer Laboratory, University of Cambridge (1991).
 
\layout Bibliography
\bibitem {Friedman77}

J.
 H.
 Freidman, J.
 L.
 Bentley, R.
 A.
 Finkel, 
\begin_inset Quotes eld
\end_inset 

An Algorithm for Finding Best Matches in Logarithmic Expected Time
\begin_inset Quotes erd
\end_inset 

, ACM Trans.
 Math.
 Soft (TOMS), 3, 209--226, (1997)
\layout Bibliography
\bibitem {Talbert}

D.
 A.
 Talbert, D.
 Fisher, 
\begin_inset Quotes eld
\end_inset 

An empirical analysis of techniques for constructing and searching k-dimensional
 trees
\begin_inset Quotes erd
\end_inset 

, Conference on Knowledge Discovery in Data, Proceedings of the sixth ACM
 SIGKDD international conference on Knowledge discovery and data mining,
 Boston, Massachusetts, United States, 26--33 (2000) 
\layout Bibliography
\bibitem {Sproul}

R.
 F.
 Sproull, 
\begin_inset Quotes eld
\end_inset 

Refinements to Nearest-Neighbor Searchingin k-Dimensional Trees
\begin_inset Quotes erd
\end_inset 

, Algorithmica, 6, 579-589 (1991).
 
\the_end