Search papers, labs, and topics across Lattice.
This paper introduces the continuous refining Exploration Graph (crEG), a novel graph-based method for Approximate Nearest Neighbor Search (ANNS) that significantly improves construction speed and memory efficiency while maintaining high search performance. By leveraging undirected graphs with even degrees and ensuring connectivity, crEG enhances exploratory search capabilities, particularly when queries are part of the dataset. Experimental results reveal that optimizing for ANNS efficiency does not guarantee effectiveness in exploratory search scenarios, highlighting the need for tailored approaches in multimedia retrieval systems.
Efficient multimedia retrieval just got a boost with a new graph-based method that balances speed and precision, even for exploratory searches.
As datasets and the dimensionality of feature vectors continue to grow, Approximate Nearest Neighbor Search (ANNS) in large multimedia databases becomes increasingly relevant. Graph-based approaches have demonstrated to offer the best trade-off between retrieval precision and search time. Despite their ability to deliver search times several orders of magnitude faster than exact search techniques, existing methods suffer from slow constructions speeds or high memory requirements. This paper presents a continuous refining Exploration Graph (crEG), a novel approach for rapidly constructing a compact exploration graph with state-of-the-art search performance. Additionally, it provides the ability to enhance its effectiveness even further through an optional edge optimization algorithm. Both algorithms are specifically designed to produce and operate on undirected graphs with even degrees and guarantee graph connectivity at any time - a property particularly valuable for exploratory search, where the query is part of the database elements. Although such queries provide an advantageous starting point for graph search algorithms, they have been rarely considered in the context of ANNS, yet are crucial for recommendation and exploration systems. Our experiments demonstrate high efficiency in ANNS does not necessarily translate to a good performance in exploratory search.
