Source-linked AI summary
A Versioned Unified Graph Index for Dynamic Timestamp-Aware Nearest Neighbor Search
Jun Woo Chung, Weijie Zhao
TL;DR
Time-aware approximate nearest neighbor search on dynamic vector datasets must support arbitrary temporal ranges efficiently. TiGER uses a unified graph with versioned connectivity for direct valid traversal, achieving up to a 5x QPS improvement while maintaining comparable or superior recall to filtering baselines.
Problem
Temporal similarity search requires efficient retrieval over contiguous or disjoint time constraints in large, dynamic datasets.
Method
TiGER maintains a unified proximity graph with versioned connectivity metadata and dynamic predecessor links for direct temporal traversal during search.
Results
Up to a 5x improvement in query performance was achieved across standard ANN benchmarks while maintaining comparable or superior recall to pre- and post-filtering baselines.
Takeaways & Limitations
TiGER supports flexible temporal filtering and dynamic updates without requiring separate graphs, post-filtering, or extensive reconstruction.
Takeaways & Limitations
Future work includes integrating more complex graph structures, handling small timestamp omissions in edge aggregation, and adapting parameters or structure to workload patterns.
Abstract
from arXiv · showhide
We present TiGER (Time-Integrated Graph for Efficient Retrieval), a novel approach for performing fast time-aware approximate nearest neighbor searches on dynamic vector datasets with flexibility over any possible time range. Our proposed algorithm builds and maintains a unified graph for all vectors by leveraging an index structure based on integrated versioned connectivity, allowing arbitrary time intervals to be queried directly on the unified graph without having to traverse invalid vectors. This forgoes the need for post-search filtering or merging, or separate graphs for each possible composite range. Empirical evaluations show that our method attains up to a 5x improvement in queries per second (QPS) without compromising accuracy over baselines based on filtering or per-time-segment sub-graphs. We believe that this method will enable efficient temporal analysis across evolving datasets in real-time recommendation systems, log analysis, and any scenario requiring fast similarity search over dynamic, time-segmented data.
1 INTRODUCTION
Time-constrained similarity search is important for large-scale retrieval, but existing filtering strategies struggle with tight, shifting, or complex temporal constraints. TiGER addresses this with a unified, versioned graph that supports direct temporal traversal and dynamic updates.
- Motivation: Similarity search under temporal restrictions is a common requirement for retrieving information within specified timeframes.The paper situates temporal filtering within range-filtering approximate nearest neighbor search.
- Existing limitations: Post-filtering can waste computation by retrieving excess candidates, especially under tight constraints.It searches without constraints and filters the results afterward.
- Existing limitations: Pre-filtering requires impractical maintenance of graphs for all possible filters, while per-timestamp graphs require query-time merging and ordering.Dynamic graph construction for each query is also computationally costly.
- Challenges: Shifting queries and constraints in evolving datasets create a need for temporal filtering without heavy reconstruction or excessive search overhead.This motivates a flexible approach for dynamic data.
- Our Approach: TiGER retrieves top-k approximate neighbors directly for contiguous or disjoint timestamp sets using a unified index.The method avoids multiple graphs and extensive post-processing for arbitrary timestamp selections.
- Our Approach: A versioned proximity graph annotates nodes and edges with temporal validity while dynamic predecessor links preserve reachability during insertions.This supports direct traversal without query-specific graph modification or broken connectivity.
- Contributions: TiGER achieves up to a 5x QPS improvement while maintaining comparable or superior recall to pre- and post-filtering baselines.The contribution statement reports this result as an empirical evaluation outcome.
2 PRELIMINARY
Proximity graphs support efficient approximate nearest neighbor search by connecting nearby vectors, while persistent structures preserve historical versions for temporal access. Together, these ideas provide relevant foundations for time-aware graph indexing.
- Proximity graphs: Proximity graphs connect nearby vectors and support approximate nearest neighbor queries through graph traversal.This reduces the computational cost relative to exhaustive search.
- Persistent data structures: Persistent data structures retain multiple data versions so historical states can be accessed without duplication.For temporal constraints, encoding node and edge validity supports continuous updating across time.
3 TIGER FRAMEWORK
TiGER uses a single versioned graph with temporal metadata and connectivity mechanisms to support searches over arbitrary timestamp ranges. Its timestamp-aware traversal and integrated edge database avoid invalid vectors, separate time-specific indexes, and repeated edge aggregation.
- Unified versioned graph: TiGER maintains a single incrementally updated graph whose nodes and edges carry temporal metadata for arbitrary time-range queries.The unified index avoids separate structures for each time slice or complex post-processing.
- Unified versioned graph: Each vertex records active timestamps, while each outgoing edge state is versioned across intervals between changes.For timestamps from one edge-state change until the next, the recorded state defines the vertex’s outgoing edges.
- Graph construction and connectivity: Insertion first performs a timestamp-blind greedy search for le nearby nodes, adds outgoing edges, then connects the new vertex through a suitable predecessor while removing the earliest-timestamp edge if needed.The predecessor connection increments push(vmin), preserving the bounded edge-management mechanism.
- Timestamp-aware search: Timestamp-limited search follows standard proximity-graph traversal but only uses nodes and edges valid for the requested timestamps.Versioned structures yield relevant edges directly, eliminating post-filtering and multiple time-specific indexes.
- Graph construction and connectivity: TiGER preserves reachability during insertion by assigning prev(v), enforcing push(v) ≤ le, and recursively marking a prev chain active at the current timestamp.This guarantees a path from the origin to every active vertex without exceeding edge limits or reconstructing the index.
- Edge database: The edge database accelerates contiguous or discretely contiguous timestamp queries by aggregating edge information, with one aggregation search reusable for batch queries sharing a range.This complements TiGER’s support for noncontiguous timestamp sets.
4 EXPERIMENTS
Experiments simulate dynamic timestamped workloads on standard ANN datasets and compare TiGER with pre-filtering and post-filtering HNSW. TiGER leads in QPS–recall tradeoffs for both contiguous and discrete timestamp queries.
- Workload Simulation: Experiments simulate dynamic insertions by assigning vectors artificial timestamps, building an initial graph, inserting later vectors sequentially, and issuing timestamp-constrained searches.
- Datasets and Settings: The evaluation uses SIFT 1M and GloVe-100 with 128- and 100-dimensional vectors, respectively, and sets k = 100.
- Datasets and Settings: The study varies tn between 2500 and 5000 and |Tq| among 3, 10, 20, 30, and 50 to cover tighter and looser filters.
- Contiguous Timestamp Queries: TiGER consistently leads pre-filtering and post-filtering in QPS versus recall across contiguous filter lengths.
- Discrete Timestamp Queries: TiGER retains gains over baselines for discrete timestamp sets, although the lead is slightly less pronounced than for contiguous sets.
5 RELATED WORK
Related methods integrate filtering into graph-based ANN search through compressed range indices, hierarchical labels, merged elemental graphs, or composite graphs. Their reported limitations include weak support for disjoint ranges, dynamic updates, or scalable maintenance.
- SeRF compresses indices for contiguous numeric ranges using edge validity annotations but does not natively support disjoint ranges or full dynamic updates.
- UNG organizes data hierarchically by label containment for filtered ANNS, but adding data can require cross-range reconstruction.
- iRangeGraph precomputes elemental range graphs and merges them during queries, while disjoint ranges incur substantial query-time overhead and dynamic updates are unsupported.
- Filtered-DiskANN provides filter-aware graph variants, but frequently evolving filters are difficult to maintain.
- NHQ combines vector similarity and attribute compatibility in a composite graph and uses joint pruning during traversal.
- DIGRA supports dynamic range-aware queries, but its updates are restricted to single-threaded execution, limiting scalability in high-throughput environments.
6 CONCLUSIONS
The paper identifies inefficiency, dynamic-update difficulties, and noncontiguous-filter limitations in existing approaches, then introduces TiGER as a unified solution. Evaluations report up to 5x higher query performance than HNSW filtering baselines, while future work targets broader graph and edge-database capabilities.
- Existing approaches are computationally inefficient or problematic for dynamic updates and noncontiguous filters.
- TiGER uses a unified proximity graph with versioned connectivity metadata to support time-filtered RFANN searches without pre-filtering or post-filtering.
- Up to 5x improvement in query performance is reported across a wide range of filters versus HNSW with pre-filtering and post-filtering.
- Future work includes integrating more complex graph structures, extending edge-database aggregation to small timestamp omissions, and adapting parameters or structure to workload patterns.
A.1 EDGE DATABASE
The edge database accelerates TiGER searches for contiguous timestamp filters, especially as the queried range grows, but provides little visible benefit for discrete filters. The evaluation compares standard edge-database searches with brute-force edge-validity checks.
- The ablation compares TiGER search speeds with and without the edge database for contiguous and discrete timestamp filters.
- Contiguous filters gain visible speed improvements from the edge database, with the benefit increasing as |Tq| grows.
- Discrete filters show little visible difference between searches with and without the edge database.
B ADDITIONAL FIGURES
Figure 7 shows timestamp-specific effective graphs and their combination for querying timestamps 2 and 4. Node 5 is excluded from the combined graph because it is active only at timestamp 3.
- Figure 7 compares effective graphs across construction timestamps with the combined graph used for timestamps 2 and 4.
- Node 5 does not appear in the combined timestamp graph because it is present or active only at timestamp 3.
- Figure 8 illustrates a top-k limit of 2, marking the query vector with a green crosshair and traversed paths and nodes in blue.
- Node v4 is assessed for valid edges despite its insertion timestamp being 3 because its active timestamps include 4, allowing it to bridge nodes 3 and 6.