  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.
