dorsal/arxiv
View SchemaKDTREE 2: Fortran 95 and C++ software to efficiently search for near neighbors in a multi-dimensional Euclidean space
| Authors | Matthew B. Kennel |
|---|---|
| Categories | |
| ArXiv ID | physics/0408067 |
| URL | https://arxiv.org/abs/physics/0408067 |
Abstract
Many data-based statistical algorithms require that one find \textit{near or nearest neighbors} to a given vector among a set of points in that vector space, usually with Euclidean topology. The k-d data structure and search algorithms are the generalization of classical binary search trees to higher dimensional spaces, so that one may locate near neighbors to an example vector in $O(\log N)$ time instead of the brute-force O(N) time, with $N$ being the size of the data base. KDTREE2 is a Fortran 95 module, and a parallel set of C++ classes which implement tree construction and search routines to find either a set of $m$ nearest neighbors to an example, or all the neighbors within some Euclidean distance $r.$ The two versions are independent and function fully on their own. Considerable care has been taken in the implementation of the search methods, resulting in substantially higher computational efficiency (up to an order of magnitude faster) than the author's previous Internet-distributed version. Architectural improvements include rearrangement for memory cache-friendly performance, heap-based priority queues for large $m$searches, and more effective pruning of search paths by geometrical constraints to avoid wasted effort. The improvements are the most potent in the more difficult and slowest cases: larger data base sizes, higher dimensionality manifolds containing the data set, and larger numbers of neighbors to search for. The C++ implementation requires the Standard Template Library as well as the BOOST C++ library be installed.
{
"annotation_id": "70344b90-404b-44b0-aca7-09baa52f696c",
"date_created": "2026-03-02T18:00:52.606000Z",
"date_modified": "2026-03-02T18:00:52.606000Z",
"file_hash": "bebae9efd3f4e0d757e529d794056b4b93ad7203f57d809403dab9b2e7e5448f",
"private": false,
"record": {
"abstract": "Many data-based statistical algorithms require that one find \\textit{near or\nnearest neighbors} to a given vector among a set of points in that vector\nspace, usually with Euclidean topology. The k-d data structure and search\nalgorithms are the generalization of classical binary search trees to higher\ndimensional spaces, so that one may locate near neighbors to an example vector\nin $O(\\log N)$ time instead of the brute-force O(N) time, with $N$ being the\nsize of the data base. KDTREE2 is a Fortran 95 module, and a parallel set of\nC++ classes which implement tree construction and search routines to find\neither a set of $m$ nearest neighbors to an example, or all the neighbors\nwithin some Euclidean distance $r.$ The two versions are independent and\nfunction fully on their own. Considerable care has been taken in the\nimplementation of the search methods, resulting in substantially higher\ncomputational efficiency (up to an order of magnitude faster) than the author\u0027s\nprevious Internet-distributed version. Architectural improvements include\nrearrangement for memory cache-friendly performance, heap-based priority queues\nfor large $m$searches, and more effective pruning of search paths by\ngeometrical constraints to avoid wasted effort. The improvements are the most\npotent in the more difficult and slowest cases: larger data base sizes, higher\ndimensionality manifolds containing the data set, and larger numbers of\nneighbors to search for. The C++ implementation requires the Standard Template\nLibrary as well as the BOOST C++ library be installed.",
"arxiv_id": "physics/0408067",
"authors": [
"Matthew B. Kennel"
],
"categories": [
"physics.data-an",
"physics.comp-ph"
],
"title": "KDTREE 2: Fortran 95 and C++ software to efficiently search for near neighbors in a multi-dimensional Euclidean space",
"url": "https://arxiv.org/abs/physics/0408067"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d1d95e21-1ddf-4317-a144-efc18abb7dbd",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}