Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.00402 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912281275662336 |
|---|---|
| author | Yu, Song Lin, Shengyuan Gong, Shufeng Xie, Yongqing Liu, Ruicheng Zhou, Yijie Sun, Ji Zhang, Yanfeng Li, Guoliang Yu, Ge |
| author_facet | Yu, Song Lin, Shengyuan Gong, Shufeng Xie, Yongqing Liu, Ruicheng Zhou, Yijie Sun, Ji Zhang, Yanfeng Li, Guoliang Yu, Ge |
| contents | The graph-based index has been widely adopted to meet the demand for approximate nearest neighbor search (ANNS) for high-dimensional vectors. However, in dynamic scenarios involving frequent vector insertions and deletions, existing systems improve update throughput by adopting a batch update method. However, a large batch size leads to significant degradation in search accuracy.
This work aims to improve the performance of graph-based ANNS systems in small-batch update scenarios, while maintaining high search efficiency and accuracy. We identify two key issues in existing batch update systems for small-batch updates. First, the system needs to scan the entire index file to identify and update the affected vertices, resulting in excessive unnecessary I/O. Second, updating the affected vertices introduces many new neighbors, frequently triggering neighbor pruning. To address these issues, we propose a topology-aware localized update strategy for graph-based ANN index. We introduce a lightweight index topology to identify affected vertices efficiently and employ a localized update strategy that modifies only the affected vertices in the index file. To mitigate frequent heavy neighbor pruning, we propose a similar neighbor replacement strategy, which connects the affected vertices to only a small number (typically one) of the most similar outgoing neighbors of the deleted vertex during repair. Based on extensive experiments on real-world datasets, our update strategy achieves 2.47X-6.45X higher update throughput than the state-of-the-art system FreshDiskANN while maintaining high search efficiency and accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_00402 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Topology-Aware Localized Update Strategy for Graph-Based ANN Index Yu, Song Lin, Shengyuan Gong, Shufeng Xie, Yongqing Liu, Ruicheng Zhou, Yijie Sun, Ji Zhang, Yanfeng Li, Guoliang Yu, Ge Databases The graph-based index has been widely adopted to meet the demand for approximate nearest neighbor search (ANNS) for high-dimensional vectors. However, in dynamic scenarios involving frequent vector insertions and deletions, existing systems improve update throughput by adopting a batch update method. However, a large batch size leads to significant degradation in search accuracy. This work aims to improve the performance of graph-based ANNS systems in small-batch update scenarios, while maintaining high search efficiency and accuracy. We identify two key issues in existing batch update systems for small-batch updates. First, the system needs to scan the entire index file to identify and update the affected vertices, resulting in excessive unnecessary I/O. Second, updating the affected vertices introduces many new neighbors, frequently triggering neighbor pruning. To address these issues, we propose a topology-aware localized update strategy for graph-based ANN index. We introduce a lightweight index topology to identify affected vertices efficiently and employ a localized update strategy that modifies only the affected vertices in the index file. To mitigate frequent heavy neighbor pruning, we propose a similar neighbor replacement strategy, which connects the affected vertices to only a small number (typically one) of the most similar outgoing neighbors of the deleted vertex during repair. Based on extensive experiments on real-world datasets, our update strategy achieves 2.47X-6.45X higher update throughput than the state-of-the-art system FreshDiskANN while maintaining high search efficiency and accuracy. |
| title | A Topology-Aware Localized Update Strategy for Graph-Based ANN Index |
| topic | Databases |
| url | https://arxiv.org/abs/2503.00402 |