Enhancing SR-Tree for Nearest Neighbor Search

Nearest neighbor search, also known as k-nearest neighbors (kNN), has become one of the essential backbones in machine learning and data mining tasks, particularly in multidimensional dynamic and evolving data environments. While dynamic index structures have been extensively utilized for indexing dynamic data, their performance in nearest neighbor search can further be improved. This paper aims to enhance SR-Tree as it has been shown to be effective for indexing high dimensional clustered data. We propose enhancements to SR-Tree structure to better handle multidimensional data and reduce query processing time. First, we improve SR-Tree using variance-based bulk-loading algorithm to build efficient tree structure. Second, we apply approximation of smallest enclosing ball and leaf-level pruning methods to improve performance of kNN queries. Third, we adapt dual-tree algorithm for SR-Tree that outperforms sequential queries for all-nearest neighbors problem in low-to-medium dimensional large datasets. These improvements were evaluated using real-world datasets across varying dimensionalities by comparing against several freely available indexing structure frameworks. Experimental results indicated considerable speedup over the state-of-the-art dynamic index implementation in nearest neighbor retrieval across high-dimensional conditions. This work also provides an open-source implementation of our enhancements to SR-Tree for the Rust ecosystem.