Anisotropic K-Nearest Neighbor Search Using Covariance Quadtree

Abstract

We present a variant of the hyper-quadtree that divides a multidimensional space according to the hyperplanes associated to the principal components of the data in each hyperquadrant. Each of the hyper-quadrants is a data partition in a multidimensional subspace, whose intrinsic dimensionality is reduced from the root dimensionality by means of the principal components analysis, which discards the irrelevant eigenvalues of the local covariance matrix. In the present method a component is irrelevant if its length is smaller than, or comparable to, the local inter-data spacing. Thus, the covariance hyperquadtree is fully adaptive to the local dimensionality. The proposed data-structure is used to compute the anisotropic K nearest neighbors (kNN), supported by the Mahalanobis metric. As an application, we used the present k nearest neighbors method to perform density estimation over a noisy data distribution. Such estimation method can be further incorporated to the smoothed particle hydrodynamics, allowing computer simulations of anisotropic fluid flows.