Search papers, labs, and topics across Lattice.
This paper introduces the Dynamic Exploration Graph (DEG), a novel approach designed to enhance the efficiency of Approximate Nearest Neighbor Search (ANNS) in evolving multimedia datasets. The DEG employs a unique vertex deletion algorithm to ensure graph connectivity and a distribution-agnostic method for graph expansion, enabling it to maintain high search efficiency even as data points are continuously added or removed. Empirical evaluations reveal that the DEG outperforms existing dynamic graph algorithms in both construction time and search efficiency, while also matching the performance of state-of-the-art methods for static datasets.
The Dynamic Exploration Graph achieves superior efficiency in dynamic nearest neighbor searches, outperforming existing algorithms while maintaining static dataset performance.
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.
