Abstract
Randomized partition trees have recently been shown to be very effective in solving nearest neighbor search problem. In spite of enjoying strong theoretical guarantee, it suffers from high space complexity, since each internal node of the tree needs to store a $d$ dimensional projection direction leading to a $O(nd)$ space complexity for a dataset of size $n$. Inspired by the fast Johnson-Lindenstrauss transform, in this paper, we propose a sparse version of randomized partition tree where each internal node needs to store only a few non-zero entries, as opposed to all $d$ entries, leading to significant space savings without sacrificing much in terms of nearest neighbor search accuracy. As a by product of this, query time of our proposed method is slightly better than that of its non-sparse counterpart for large dataset size. Our theoretical results indicate that our proposed method enjoys the same theoretical guarantee as that of the original non-sparse RP-tree. Experimental evaluations on four real world dataset strongly suggest that nearest neighbor search performance of our proposed sparse RP-tree is very similar to that of its non-sparse counterpart in terms of accuracy and number of retrieved points.
Introduction
Nearest Neighbor (NN) search is a fundamental task in machine learning, yet it faces significant scalability challenges as datasets grow in size ($n$) and dimensionality ($d$). Randomized Partition (RP) trees address this by recursively splitting the data space using random projections, enabling sub-linear search times. However, standard RP-trees require storing a full $d$-dimensional projection vector at every internal node, resulting in a prohibitive $O(nd)$ space complexity. This paper introduces Sparse RP-trees, a memory-efficient variant that reduces storage requirements by up to 90% while maintaining high accuracy.
Methodology
The core innovation lies in replacing dense projection vectors with sparse ones. To ensure that sparsity does not lead to information loss (especially on sparse data), the authors employ a two-step process:
- Densification Preprocessing: Inspired by the Fast Johnson-Lindenstrauss Transform, data points are pre-multiplied by a Walsh-Hadamard matrix ($H$) and a random diagonal matrix ($D$). This $HD$ transform "spreads" information across all dimensions while preserving norms and relative distances.
- Sparse Projection: Nodes are split using a projection vector $BU$, where $U$ is a random unit vector and $B$ is a sparse diagonal matrix determined by Bernoulli trials with probability $p$. This reduces the storage per node from $d$ entries to approximately $p \times d$.
Experimental Evaluation
The proposed method was evaluated on four real-world datasets with varying characteristics, ranging from texture information to handwritten digits. The dataset statistics are summarized below:
The experiments focused on the trade-off between sparsity ($p$) and search performance (accuracy and number of retrieved points).
Results and Discussion
The results demonstrate that sparsity is remarkably effective. As shown in the table below, reducing the sparsity parameter $p$ to 0.1 (a 90% reduction in coordinate storage) results in negligible loss in accuracy across all datasets.
Key observations include:
- Accuracy Stability: On the SIFT dataset, the accuracy remains at 0.993 even when sparsity is reduced to 10% ($p=0.1$).
- Theoretical Equivalence: The authors prove that the "potential function" used to bound failure probabilities in RP-trees remains nearly identical for the sparse version, with only a small, controllable error term.
- Query Efficiency: While the $HD$ transform adds a fixed $O(d \log d)$ cost per query, the reduced number of multiplications during tree traversal leads to faster query times for large datasets ($n \ge d^2$).
Conclusion
Sparse RP-trees offer a compelling solution for high-dimensional nearest neighbor search where memory is a constraint. By combining a densification preprocessing step with sparse random projections, the method achieves significant space savings without sacrificing the theoretical guarantees or empirical performance of traditional RP-trees. Future work may explore direct comparisons with modern sparse hashing techniques and further optimization of the preprocessing overhead.
Summary updated