Journal of Algorithms and Computation
Open Access

Dynamic Approximate Nearest Neighbor Search in High-Dimensional Spaces: A Hybrid Graph-Tree Approach

Document Type : Research Paper

Author

Amirali Ghajari

Islamic Azad University Central Tehran Branch

https://doi.org/10.22059/jac.2026.407468.1249
Abstract
State-of-the-art static Approximate Nearest Neighbor (ANN) search methods, like HNSW, are inefficient for dynamic environments due to costly index rebuilds. This paper addresses this gap by proposing the Hybrid Graph-Tree (HGT), a novel data structure for high-performance ANN search on streaming data. HGT synergistically combines a global navigational tree for rapid search space pruning with localized navigable graphs at its leaves for accurate local search. A key feature is an efficient leaf-splitting mechanism that maintains index balance and performance during continuous insertions without global reconstruction. Our extensive experiments demonstrate that HGT achieves query performance competitive with static HNSW while offering orders-of-magnitude faster insertions. The structure’s ability to maintain stable query latency and high recall under dynamic workloads establishes it as a robust solution for next-generation vector databases and real-time AI systems, bridging the critical gap between static index performance and dynamic data requirements.

Keywords

Vector Databases
Streaming Data
Computational Geometry
Curse of Dimensionality
Vector Embeddings
Incremental Indexing
Metric Indexing
Low-Latency Updates
Journal of Algorithms and Computation
Volume 58, Issue 1
July 2026
Pages 60-81

Home

Guide for Authors

Submit Manuscript

Reviewers

Contact Us