2025/01/01 by Nico Hezel, Kai Uwe Barthel, Bruno Schilling +2 · 1 citation
Computer Science · #Advanced Image and Video Retrieval Techniques #Data Management and Algorithms #Image Retrieval and Classification Techniques #cs.IR
paper · pdf · doi:10.1007/978-981-96-2054-8_25
published as Proc. MMM 2025, pp. 333-347
openalex publication_date 2025/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29 · arxiv created 2026/07/30 · arxiv updated 2026/07/31
Approximate Nearest Neighbor Search (ANNS) represents a fundamental problem in various applications (image-search, recommendation systems). While graph-based algorithms have demonstrated a good balance between search accuracy and time, handling dynamic datasets, where data points are continuously added or removed, remains a challenge. This paper introduces the Dynamic Exploration Graph (DEG), an extension of the continuous refining Exploration Graph, which retains high search efficiency for static dataset while adding essential support for dynamic data. At the core of the DEG design are two key innovations: a novel vertex deletion algorithm which guarantees graph connectivity and a data distribution-agnostic method for graph expansion. Through these mechanisms, the DEG maintains a balanced and well-connected structure, even under continuous data alterations. Empirical experiments in both streaming and online scenarios demonstrate the superior performance of the DEG, surpassing existing dynamic graph algorithms in terms of construction time and search efficiency. Although optimized for dynamic datasets, the DEG delivers results as good as current state-of-the-art approaches for static dataset, underscoring its broad applicability.