With the rise of deep learning and high-dimensional vector data, Approximate Nearest Neighbor Search (ANNS) has become essential for information retrieval. Graph-based indexing methods have gained significant traction due to their efficiency and high recall. However, most existing methods are designed for static or insert-only scenarios, making them unsuitable for dynamic environments characterized by high-frequency updates and real-time responsiveness, such as interactive search engines and real-time recommendations. To address these limitations, we propose Mint, an novel and robust approach that combines partial graph reconstruction with an auxiliary indexing framework to enable efficient updates and high performance. At the core of Mint lies the Neighbor-Aware Graph Reconstructing (NAGR) algorithm, which dynamically optimizes the graph structure by making neighborhood-aware adjustments. Complementing this is the Outlier-Driven Dual-Index framework (ODDI), which manages both primary and auxiliary indices in real time, ensuring adaptability to evolving data distributions and high update frequencies. Experiments show that Mint outperforms state-of-the-art methods, achieving an 83.3% improvement in update efficiency and a 5.1% increase in recall rate under dynamic update scenarios. It also delivers superior query efficiency and robustness under frequent updates, making it a powerful solution for dynamic ANNS tasks.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Mint: An Efficient and Robust In-Place Update Approach for Graph-Based Vector Index

  • Wentao Xiao,
  • Yueyang Zhan,
  • Rui Xi,
  • Zhuohan Hou,
  • Jianming Liao,
  • Yufang Sun

摘要

With the rise of deep learning and high-dimensional vector data, Approximate Nearest Neighbor Search (ANNS) has become essential for information retrieval. Graph-based indexing methods have gained significant traction due to their efficiency and high recall. However, most existing methods are designed for static or insert-only scenarios, making them unsuitable for dynamic environments characterized by high-frequency updates and real-time responsiveness, such as interactive search engines and real-time recommendations. To address these limitations, we propose Mint, an novel and robust approach that combines partial graph reconstruction with an auxiliary indexing framework to enable efficient updates and high performance. At the core of Mint lies the Neighbor-Aware Graph Reconstructing (NAGR) algorithm, which dynamically optimizes the graph structure by making neighborhood-aware adjustments. Complementing this is the Outlier-Driven Dual-Index framework (ODDI), which manages both primary and auxiliary indices in real time, ensuring adaptability to evolving data distributions and high update frequencies. Experiments show that Mint outperforms state-of-the-art methods, achieving an 83.3% improvement in update efficiency and a 5.1% increase in recall rate under dynamic update scenarios. It also delivers superior query efficiency and robustness under frequent updates, making it a powerful solution for dynamic ANNS tasks.