An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval

• URL: http://arxiv.org/abs/2607.27623v1
• Date: Thu, 30 Jul 2026 03:22:17 GMT
• Title: An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval
• Abstract summary: This paper presents a "continuous refining Exploration Graph" (crEG)<n>It is a novel approach for rapidly constructing a compact exploration graph with state-of-the-art search performance.<n>Both algorithms are specifically designed to produce and operate on undirected graphs with even degrees.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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".

Related papers

• Dynamic Exploration Graph: A Novel Approach for Efficient Nearest Neighbor Search in Evolving Multimedia Datasets [0.0]
  This paper introduces the Dynamic Exploration Graph (DEG), an extension of the continuous refining Exploration Graph.<n>At the core of the DEG design are two key innovations: a novel deletion algorithm which guarantees graph connectivity and a data distribution-agnostic method for graph expansion.<n> Empirical experiments in both streaming and online scenarios demonstrate the superior performance of the DEG.
  arXiv  Detail & Related papers  (2026-07-30T03:50:40Z)
• GraphER: An Efficient Graph-Based Enrichment and Reranking Method for Retrieval-Augmented Generation [47.014599006114594]
  GraphER is a graph-based enrichment and reranking method that captures multiple forms of proximity beyond semantic similarity.<n>It does not require a knowledge graph, allowing GraphER to integrate seamlessly with standard vector stores.<n> Experiments on multiple retrieval benchmarks demonstrate the effectiveness of the proposed approach.
  arXiv  Detail & Related papers  (2026-03-26T01:30:22Z)
• GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions [54.570944939061555]
  We present a comprehensive study of GPU-accelerated graph-based vector search algorithms.<n>We establish a detailed taxonomy of GPU optimization strategies and clarify the mapping between algorithmic tasks and hardware execution units.<n>Our findings offer clear guidelines for designing scalable and robust GPU-powered approximate nearest neighbor search systems.
  arXiv  Detail & Related papers  (2026-02-10T16:18:04Z)
• FastInsight: Fast and Insightful Retrieval via Fusion Operators for Graph RAG [4.927427162899616]
  Graph-based Reranker (GRanker) functions as a graph model-based search, and Semantic-Topological eXpansion (S) operates as a vector-graph search.<n>FastInsight significantly improves both retrieval accuracy and generation quality compared to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-01-26T15:23:41Z)
• Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search [23.208935102841103]
  We propose a new distance-based termination condition for beam search to replace the commonly used condition based on beam width.<n>We prove that, as long as the search graph is navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem.<n>We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors.
  arXiv  Detail & Related papers  (2025-05-21T15:18:53Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• Learning Graph Search Heuristics [48.83557172525969]
  We present PHIL (Path Heuristic with Imitation Learning), a novel neural architecture and a training algorithm for discovering graph search and navigations from data. Our function learns graph embeddings useful for inferring node distances, runs in constant time independent of graph sizes, and can be easily incorporated in an algorithm such as A* at test time. Experiments show that PHIL reduces the number of explored nodes compared to state-of-the-art methods on benchmark datasets by 58.5% on average.
  arXiv  Detail & Related papers  (2022-12-07T22:28:00Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  We propose Automatic Relation-aware Graph Network Proliferation (ARGNP) for efficiently searching GNNs. These operations can extract hierarchical node/relational information and provide anisotropic guidance for message passing on a graph. Experiments on six datasets for four graph learning tasks demonstrate that GNNs produced by our method are superior to the current state-of-the-art hand-crafted and search-based GNNs.
  arXiv  Detail & Related papers  (2022-05-31T10:38:04Z)
• Edge-featured Graph Neural Architecture Search [131.4361207769865]
  We propose Edge-featured Graph Neural Architecture Search to find the optimal GNN architecture. Specifically, we design rich entity and edge updating operations to learn high-order representations. We show EGNAS can search better GNNs with higher performance than current state-of-the-art human-designed and searched-based GNNs.
  arXiv  Detail & Related papers  (2021-09-03T07:53:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.