Dynamic Exploration Graph: A Novel Approach for Efficient Nearest Neighbor Search in Evolving Multimedia Datasets

• URL: http://arxiv.org/abs/2607.27640v1
• Date: Thu, 30 Jul 2026 03:50:40 GMT
• Title: Dynamic Exploration Graph: A Novel Approach for Efficient Nearest Neighbor Search in Evolving Multimedia Datasets
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval [0.0]
  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.
  arXiv  Detail & Related papers  (2026-07-30T03:22:17Z)
• Graph Structure Learning with Temporal Graph Information Bottleneck for Inductive Representation Learning [1.3728301825671199]
  We propose a versatile framework that integrates Graph Structure Learning (GSL) with Temporal Graph Information Bottleneck (TGIB)<n>We design a novel two-step GSL-based structural enhancer to enrich and optimize node neighborhoods.<n>The TGIB refines the optimized graph by extending the information bottleneck principle to temporal graphs, regularizing both edges and features.
  arXiv  Detail & Related papers  (2025-08-20T17:13:19Z)
• RGL: A Graph-Centric, Modular Framework for Efficient Retrieval-Augmented Generation on Graphs [58.10503898336799]
  We introduce the RAG-on-Graphs Library (RGL), a modular framework that seamlessly integrates the complete RAG pipeline.<n>RGL addresses key challenges by supporting a variety of graph formats and integrating optimized implementations for essential components.<n>Our evaluations demonstrate that RGL not only accelerates the prototyping process but also enhances the performance and applicability of graph-based RAG systems.
  arXiv  Detail & Related papers  (2025-03-25T03:21:48Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• TempoKGAT: A Novel Graph Attention Network Approach for Temporal Graph Analysis [3.5707423185282656]
  This paper presents a new type of graph attention network, called TempoKGAT, which combines time-decaying weight and a selective neighbor aggregation mechanism on the spatial domain.<n>We evaluate our approach on multiple datasets from the traffic, energy, and health sectors involvingtemporal data.
  arXiv  Detail & Related papers  (2024-08-29T09:54:46Z)
• From random-walks to graph-sprints: a low-latency node embedding framework on continuous-time dynamic graphs [4.372841335228306]
  We propose a framework for continuous-time-dynamic-graphs (CTDGs) that has low latency and is competitive with state-of-the-art, higher latency models. In our framework, time-aware node embeddings summarizing multi-hop information are computed using only single-hop operations on the incoming edges. We demonstrate that our graph-sprints features, combined with a machine learning, achieve competitive performance.
  arXiv  Detail & Related papers  (2023-07-17T12:25:52Z)
• Directed Acyclic Graph Structure Learning from Dynamic Graphs [44.21230819336437]
  Estimating the structure of directed acyclic graphs (DAGs) of features (variables) plays a vital role in revealing the latent data generation process. We study the learning problem of node feature generation mechanism on such ubiquitous dynamic graph data.
  arXiv  Detail & Related papers  (2022-11-30T14:22:01Z)
• EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
  We propose a novel graph clustering network called Embedding-Induced Graph Refinement Clustering Network (EGRC-Net) EGRC-Net effectively utilizes the learned embedding to adaptively refine the initial graph and enhance the clustering performance. Our proposed methods consistently outperform several state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-19T09:08:43Z)
• Time-aware Dynamic Graph Embedding for Asynchronous Structural Evolution [60.695162101159134]
  Existing works merely view a dynamic graph as a sequence of changes. We formulate dynamic graphs as temporal edge sequences associated with joining time of. vertex and timespan of edges. A time-aware Transformer is proposed to embed. vertex' dynamic connections and ToEs into the learned. vertex representations.
  arXiv  Detail & Related papers  (2022-07-01T15:32:56Z)
• Efficient Dynamic Graph Representation Learning at Scale [66.62859857734104]
  We propose Efficient Dynamic Graph lEarning (EDGE), which selectively expresses certain temporal dependency via training loss to improve the parallelism in computations. We show that EDGE can scale to dynamic graphs with millions of nodes and hundreds of millions of temporal events and achieve new state-of-the-art (SOTA) performance.
  arXiv  Detail & Related papers  (2021-12-14T22:24:53Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs [54.13919050090926]
  We propose an end-to-end structural temporal Graph Neural Network model for detecting anomalous edges in dynamic graphs. In particular, we first extract the $h$-hop enclosing subgraph centered on the target edge and propose the node labeling function to identify the role of each node in the subgraph. Based on the extracted features, we utilize Gated recurrent units (GRUs) to capture the temporal information for anomaly detection.
  arXiv  Detail & Related papers  (2020-05-15T09:17:08Z)

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.