Pith. sign in

REVIEW 4 major objections 5 minor 77 references

DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph

T0 review · 4 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read One graph index can serve hybrid vector retrieval at any alpha.

desk verdict The empirical case for DEG is solid and the experiments are extensive, but the claimed RNG guarantee in Lemma 4.3 does not cover the actual approximate construction, so the paper should be read as a systems paper, not a theoretically grounded one. read the letter →

arxiv 2502.07343 v1 pith:45VDMGJC submitted 2025-02-11 cs.DB

Ziqi Yin , Jianyang Gao , Pasquale Balsebre , Gao Cong , Cheng Long This is my paper · ORCID
classification cs.DB
keywords hybridvectorqueryapproximatenearestneighborsearchgraph-basedindexParetofrontierRelativeNeighborhoodGraphdynamicedgepruningmulti-modalretrievaldatabase
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that a single graph index can answer hybrid vector queries, where each object has two vectors and the score is the $\alpha$-weighted sum of the two distances, without knowing the weight $\alpha$ when the index is built. Existing approaches either fix $\alpha$ at construction time or build one index per vector, so their accuracy degrades sharply when queries use other $\alpha$ values. DEG instead stores for every edge the range of $\alpha$ in which that edge is useful, and at query time it routes only through edges active for the query's $\alpha$. On four real datasets the authors report that DEG matches or beats all fixed-$\alpha$ baselines in every $\alpha$ interval and performs on par with an Oracle that builds a dedicated index for each $\alpha$. If correct, this means dynamic query preferences need no index rebuild or overlay.

What carries the argument

The mechanism is the active range attached to each edge of the Dynamic Edge Navigation Graph. For a candidate edge $(x,y)$ and a witness $z$, the RNG pruning condition is $\alpha\,\delta_e(x,z)+(1-\alpha)\delta_s(x,z) < \alpha\,\delta_e(x,y)+(1-\alpha)\delta_s(x,y)$ together with the symmetric inequality for $y$; because both sides are linear in $\alpha$, the set of $\alpha$ values where $z$ prunes $(x,y)$ is an interval $r^z = r^z_1 \cap r^z_2$, and the edge's active range is the complement $[0,1]\setminus\bigcup_z r^z$. This reduces dynamic pruning to storing one interval per edge, which is what lets a single index skip redundant edges differently for each query $\alpha$.

What would settle it

For a sample of nodes on OpenImage or CC3M, compute the exact multi-layer Pareto frontier by brute-force skyline over all other nodes and compare it with the GPS candidate set under the same size bound; if for any $\alpha$ in a fine grid the true nearest neighbor is absent from the GPS candidate set, the coverage premise fails. A complementary test is to check whether an edge whose active range is shorter than the threshold $t_h = 0.1$ is ever the only bridge to a true nearest neighbor for some query $\alpha$.

Watch

Extended reading notes

Core claim

The central claim is that the candidate neighbors a node needs for every $\alpha$ are captured by the multi-layer Pareto frontier in the two-dimensional space of the two vector distances, and that the Greedy Pareto Frontier Search (GPS) finds a cheap approximate version by expanding neighbors of neighbors on the partially built graph. DEG then applies the Relative Neighborhood Graph (RNG) pruning rule, written as two linear inequalities in $\alpha$ for each potential witness node, to assign each surviving edge an active range: the set of $\alpha$ values for which the edge is not the longest side of any triangle. At query time, edges whose active range does not contain the query's $\alpha$ are skipped, so one graph behaves like a family of RNGs parameterized by $\alpha$. The authors prove that the exact version of this construction yields an RNG for every $\alpha$ (Theorem 4.1 and Lemma 4.3), and the edge seed set is chosen as the inverse Pareto frontier of the dataset centroid so distant seeds do not slow greedy search.

Load-bearing premise

The construction assumes that the approximate, bounded candidate set gathered by GPS on the partially built graph still contains the true nearest neighbor for every $\alpha$; the proof of coverage covers only the exact Pareto frontier over the full dataset.

Editorial extensions

If this is right

  • A single DEG index can serve queries with arbitrary $\alpha$, so applications that learn or change the weight per query do not need to rebuild their index.
  • Across the $\alpha$ intervals $[0,0.2]$ through $[0.8,1.0]$, DEG reports the best recall-QPS trade-off among HNSWF, HNSWM, and HNSWO on OpenImage, Ins-SG, Howto100M, and CC3M.
  • On OpenImage, DEG's search performance is comparable to an Oracle that builds five separate HNSW indexes at $\alpha = 0.1, 0.3, 0.5, 0.7, 0.9$.
  • DEG's construction time is comparable to the single-index baselines, and on the 10M-scale Twitter-US dataset it finished building in about 12 hours while the baselines did not finish within two days.
  • Ablation experiments attribute most of the gain to the active-range pruning: routing through all edges regardless of $\alpha$ clearly hurts performance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the active-range idea is a general recipe for any two-metric weighted search; any graph index whose pruning rule can be written as inequalities in $\alpha$ can store the interval in which each edge obeys the rule, not just RNG-based indexes.
  • Editorial inference: the formal coverage guarantee applies to the exact Pareto frontier over the whole dataset, while GPS returns a bounded approximate frontier, so the approximation is the natural stress point; adversarial or highly clustered data could expose missing alpha-specific neighbors.
  • Editorial inference: the paper notes that with more than two vectors the active range becomes a region in a higher-dimensional weight space, so an extension would need approximate polytope or sampling methods rather than simple intervals.
  • Editorial inference: because $\alpha=0$ and $\alpha=1$ reduce to ordinary single-vector ANNS, DEG offers a way to serve both unimodal and hybrid queries from one index, though the paper's own appendix reports that a dedicated single-modality Oracle still wins at the extremes.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper introduces DEG, a graph-based approximate nearest neighbor search index for hybrid vector queries (HVQ), where the query distance is a weighted sum of two modality distances with a query-specific alpha. DEG constructs a single graph by inserting nodes one by one, obtaining candidate neighbor sets through a greedy Pareto frontier search (GPS), pruning candidate edges with a dynamic active-range strategy derived from the Relative Neighborhood Graph (RNG) pruning rule, and choosing edge seeds that are far from the dataset centroid. At query time, edges are activated only when the query alpha lies in their active range, and a greedy search with early termination is used. The paper reports experiments on four real-world datasets comparing DEG with Fusion, Merging, Overlay, and Oracle baselines, plus ablations, parameter sensitivity, and a scalability study.

Significance. If the empirical claims hold, DEG is a useful contribution: it provides a single graph index that serves hybrid vector queries across varying alpha, avoiding the cost of building a separate index per alpha, and its reported accuracy-efficiency trade-off is competitive with an Oracle that builds per-alpha HNSW indexes. The paper's strengths include extensive comparisons on four datasets, ablations that isolate the contribution of each component, and a released implementation. The main weakness is that the theoretical justification for the construction, especially Lemma 4.3, is not valid for the actual algorithm, so the explanatory narrative overclaims what is formally guaranteed.

major comments (4)
  1. [§4.3, Lemma 4.3 and Appendix C] Lemma 4.3 states that applying the dynamic edge pruning strategy with all objects as candidate neighbors yields an exact RNG for any alpha, but Algorithm 3, line 6, obtains candidate neighbors via GPS with a bounded budget e_fconstruction (Algorithm 1). The proof in Appendix C assumes that any edge that could be inserted without violating the RNG property would be included, which requires that every possible RNG witness be present in the candidate set. No such completeness guarantee is established for GPS. Consequently, the built graph is not proven to satisfy the RNG property for any alpha, and the statement that 'the nearest neighbor can always be found for the query using the greedy search algorithm' is not supported for the actual construction.
  2. [§4.2-§4.3, relationship between Pareto frontier and RNG witnesses] Even replacing the approximate GPS output with an exact Pareto frontier would not repair Lemma 4.3. The RNG pruning condition for an edge (x,y) requires a witness z with Dist(x,z) < Dist(x,y) and Dist(y,z) < Dist(x,y). Such a z need not be Pareto-optimal with respect to x: z may be dominated by some p that is closer to x in both modalities while z is still closer than (x,y) to both x and y. Therefore Theorem 4.1, which only guarantees that the nearest neighbor of x lies in the Pareto frontier, does not imply that RNG witnesses are contained in the candidate set. The theoretical argument needs an additional property or a clearly stated heuristic assumption.
  3. [§4.2, Algorithm 1 (GPS)] The paper does not provide any formal approximation guarantee for the GPS algorithm. Its output is a bounded set of at most e_fconstruction nodes obtained by expanding neighbors of neighbors from the current seed set, and the paper's 'neighbor of a neighbor is likely to be a neighbor' claim is left as an unverified heuristic. Since the quality of the candidate set is load-bearing for the claim that DEG maintains high recall across all alpha values, the authors should either prove a bounded-error property for GPS or explicitly state that the candidate-generation step is heuristic and outside the formal correctness claim.
  4. [§4.3, Equations (4)-(5), Case 4] The range computation for Case 4 is incorrect when the ratio exceeds 1. In Case 4, the inequality is alpha * D < N with D < 0 and N < 0, so it is equivalent to alpha > N/D. If N/D > 1, no alpha in [0,1] satisfies the inequality, but the formula r_z^1 = [min(1, ratio), 1] returns [1,1], incorrectly including alpha = 1. This can misassign active ranges and cause edges to be incorrectly skipped at alpha = 1. The formula should return the empty set when the ratio is greater than 1.
minor comments (5)
  1. [Appendix A-C] The appendix theorem and lemma numbers do not match the main text: Appendix A proves 'Theorem 3.1' while the statement is Theorem 4.1, and Appendices B and C refer to Lemmas 3.2 and 3.3 instead of Lemmas 4.2 and 4.3.
  2. [§5.2.1 and elsewhere] There are several typographical issues, including 'but but' in §5.2.5, 'CCM' instead of 'CC3M' in §5.2.1, and inconsistent rendering of method names such as 'HNSW M' and 'HNSW F'.
  3. [Algorithm 2, line 10] The notation '|u| >= th' in Algorithm 2 uses set cardinality notation for what is actually the length or measure of an interval; this should be clarified, for example by writing length(u) or using interval-length notation.
  4. [§4.5] The early stopping mechanism is described only in prose; since it modifies the standard greedy search and interacts with the active-range skipping, a pseudocode listing for the search algorithm would improve reproducibility.
  5. [Tables 3-5] In Tables 3, 4, and 5, the DEG rows are marked N/A for non-default hyperparameters without an explicit note explaining that DEG is fixed at M=40 and e_fconstruction=200 throughout; adding a table note would avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the active-range logic is a self-contained derivation and the empirical claims are benchmarked externally, with only a non-circular theory-application gap in Lemma 4.3.

full rationale

The paper's central empirical claim, that DEG outperforms baselines under varying alpha, is evaluated against external methods (HNSWF, HNSWM, HNSWO, and the Oracle HNSWOr) on five real datasets; no parameter is fitted to the target recall/QPS results, so the 'prediction' is not a renamed fit. The active-range computation in Section 4.3 and Algorithm 2 directly solves the RNG pruning inequalities (Equations 2-5), so the claim that an edge is active exactly where it is not pruned by the candidate set follows from the algebra of the definition rather than from the target result. Theorem 4.1, stating that the exact Pareto frontier contains the nearest neighbor for every alpha, is proved from the dominance definition and the weighted distance formula, and the proof does not presuppose the conclusion. The only theoretical concern, that Lemma 4.3 assumes all dataset objects as candidates while Algorithm 3 uses bounded approximate Pareto frontiers from GPS, is an applicability or overclaim gap rather than a circular reduction; it does not feed any fitted value back into the experimental comparison. Self-citations appear only in peripheral contexts, such as RaBitQ in the related-work survey, and the RNG-to-MRNG equivalence used in the appendix proof of Lemma 4.3 is attributed to external references [20,69]. Thus no derivation step reduces by construction to its own input, and the empirical ranking rests on independent benchmarks.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central construction rests on standard graph-based ANNS machinery (RNG, HNSW insertion), a novel but unproven candidate-quality heuristic (GPS), and one hand-set threshold (th). No new physical or conceptual entities are postulated.

free parameters (3)
  • th (active range threshold) = 0.1
    Hand-set threshold for the minimum width of an edge's active range before it is kept; no sensitivity experiment is reported, and it directly controls how many edges survive pruning.
  • M (max edges per node) = 40
    Standard HNSW-style hyperparameter; chosen to match the HNSWF baseline; not fitted to the reported results.
  • efConstruction (candidate pool size) = 200
    Standard HNSW-style hyperparameter; chosen to match the HNSWF baseline; bounds the GPS candidate set.
assumptions (4)
  • standard math Relative Neighborhood Graph pruning preserves greedy-search navigability (exact RNG is exact MRNG)
    Invoked from prior work in Section 3.2 and used to argue DEG's edge skipping maintains search effectiveness (Lemma 4.3).
  • standard math Skyline computation in two dimensions can be done efficiently and correctly (Borzsony et al. 2001)
    Used by FindPF in Algorithm 4 and by the edge seed computation; correctness is assumed from the cited skyline operator.
  • domain assumption The hybrid distance in Eq. 1 is a metric for every alpha in [0,1], so triangle-inequality-based RNG pruning applies
    The paper does not state this explicitly but relies on it when applying RNG pruning to the weighted distance.
  • ad hoc to paper The neighbor-of-a-neighbor heuristic in GPS yields approximate Pareto frontiers that contain the true nearest neighbors for all alpha
    Algorithm 1 greedily expands neighbors and bounds the candidate set by efConstruction; no guarantee is provided that the true NN for an arbitrary alpha lies in the result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph." pith.science (2026). https://pith.science/paper/45VDMGJC

@misc{pith2026250207343,
  author       = {Pith},
  title        = {Pith review of: DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/45VDMGJC}},
  note         = {Machine review of arXiv:2502.07343}
}
abstract

Bimodal data, such as image-text pairs, has become increasingly prevalent in the digital era. The Hybrid Vector Query (HVQ) is an effective approach for querying such data and has recently garnered considerable attention from researchers. It calculates similarity scores for objects represented by two vectors using a weighted sum of each individual vector's similarity, with a query-specific parameter $\alpha$ to determine the weight. Existing methods for HVQ typically construct Approximate Nearest Neighbors Search (ANNS) indexes with a fixed $\alpha$ value. This leads to significant performance degradation when the query's $\alpha$ dynamically changes based on the different scenarios and needs. In this study, we introduce the Dynamic Edge Navigation Graph (DEG), a graph-based ANNS index that maintains efficiency and accuracy with changing $\alpha$ values. It includes three novel components: (1) a greedy Pareto frontier search algorithm to compute a candidate neighbor set for each node, which comprises the node's approximate nearest neighbors for all possible $\alpha$ values; (2) a dynamic edge pruning strategy to determine the final edges from the candidate set and assign each edge an active range. This active range enables the dynamic use of the Relative Neighborhood Graph's pruning strategy based on the query's $\alpha$ values, skipping redundant edges at query time and achieving a better accuracy-efficiency trade-off; and (3) an edge seed method that accelerates the querying process. Extensive experiments on real-world datasets show that DEG demonstrates superior performance compared to existing methods under varying $\alpha$ values.

Figures

Figures reproduced from arXiv: 2502.07343 by the authors.

Figure 1
Figure 1. Figure 1a illustrates the HNSW index. Figure 1b illustrates the pruning strategy of the Relative [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. The experiment results of HNSWM and HNSWF on the OpenImage dataset (up and right is better). 3.3 Motivations Baselines. To the best of our knowledge, very little work has been done for the HVQ problem and previous work only presents two simple solutions by adapting existing ANNS indexes [67], which are detailed below: • Fusion (abbr. F): This method builds an ANNS index based on the hybrid distance by fixing 𝛼 = 0.5… view at source ↗
Figure 3
Figure 3. The framework of the DEG, including the index construction phase and index search phase. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (17 more)
Figure 4
Figure 4. Figure 4: Figure 4a illustrates the Pareto frontiers and Figure 4b illustrates the difference between the edge seed [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: The accuracy-efficiency trade-off results (upper and right is better). edge assigned a value representing the 𝛼 under which it was constructed. During the query phase, rather than traversing all edges, it only routes the edges with values closest to the query’s 𝛼 and i…
Figure 6
Figure 6. Figure 6: The accuracy-efficiency trade-off results compared to HNSWOr (upper and right is better). node is set to be 𝑀, the construction time and memory costs can be up to five times higher than other methods, leading to unfair comparison. Therefore, we set the maximum number o…
Figure 7
Figure 7. Figure 7 [PITH_FULL_IMAGE:figures/full_fig_p021_7.png]
Figure 8
Figure 8. Figure 8: b shows the memory usage of DEG and the baselines. The results show that DEG’s memory usage is slightly higher than baseline methods due to its more complex index structure. However, the high-dimensional vectors still dominate the memory consumption, making the differe…
Figure 9
Figure 9. Figure 9: The accuracy-efficiency trade-off results on OpenImage dataset with varying 𝑀 and 𝑒 𝑓𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑡𝑖𝑜𝑛. increase 𝑀 and 𝑒 𝑓𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 from 40, 200 to 50, 250, then to 60, 300 for HNSWF, HNSWM, and DEG. For HNSWO, we adjust the 𝑀 and 𝑒 𝑓𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 of each sub-index from 10…
Figure 10
Figure 10. Figure 10: Ablation Study for the DEG’s pruning strategy. 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 QPS (1/s) Overall 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 [0.0, 0.2] 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 [0.4, 0.6] 0.80 0.85 0.9…
Figure 11
Figure 11. Figure 11: Ablation Study for the Active Range. 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 QPS (1/s) Overall 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 [0.0, 0.2] 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 [0.4, 0.6] 0.80 0.85 0.90 0.95 1.0…
Figure 12
Figure 12. Figure 12: Ablation Study for candidate acquisition method. outperforms the DEG𝑠𝑡𝑎𝑡𝑖𝑐 for varying 𝛼, which indicates the active range can enhance search performance. The candidate acquisition method. To verify the effectiveness of the GPS algorithm, we replaced the GPS algorithm…
Figure 13
Figure 13. Figure 13: Ablation Study for Edge Seed Acquisition method. direction is to develop a disk-based version of our index, making it suitable for implementation in vector databases. Acknowledgments We thank the anonymous reviewers for their valuable feedback. This research is suppor…
Figure 14
Figure 14. Figure 14: The accuracy-efficiency trade-off results for the extreme query [PITH_FULL_IMAGE:figures/full_fig_p031_14.png]
Figure 15
Figure 15. Figure 15: The accuracy-efficiency trade-off results on OpenImage dataset with varying 𝑀 and 𝑒 𝑓𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑡𝑖𝑜𝑛. 0.7 0.8 0.9 1.0 Recall@10 200 500 800 1100 QPS (1/s) Overall 0.7 0.8 0.9 1.0 Recall@10 200 500 800 1100 [0.0, 0.2] 0.7 0.8 0.9 1.0 Recall@10 200 500 800 1100 [0.2, 0.4] 0…
Figure 16
Figure 16. Figure 16: The accuracy-efficiency trade-off results on OpenImage dataset with different 𝑀 and 𝑒 𝑓𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑡𝑖𝑜𝑛. 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 QPS (1/s) Overall 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 [0.0, 0.2] 0.80 0.85 0.90 0.95 1.00 Re…
Figure 17
Figure 17. Figure 17: Ablation Study for the D-RNG’s pruning strategy on the OpenImage dataset. Proc. ACM Manag. Data, Vol. 3, No. 1 (SIGMOD), Article 29. Publication date: February 2025 [PITH_FULL_IMAGE:figures/full_fig_p033_17.png]
Figure 18
Figure 18. Figure 18: Ablation Study for the Active Range on the OpenImage dataset. 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 QPS (1/s) Overall 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 [0.0, 0.2] 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 [0.2, 0.4…
Figure 19
Figure 19. Figure 19: Ablation Study for the candidate acquisition method on the OpenImage dataset. 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 QPS (1/s) Overall 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 800 1000 [0.0, 0.2] 0.80 0.85 0.90 0.95 1.00 Recall@10 200 400 600 80…
Figure 20
Figure 20. Figure 20: Ablation Study for the Edge Seed Acquisition method on the OpenImage dataset. are then organized by another R-tree. During the querying phase, similar to the NIQ-Tree, it hierarchically traverses R-trees to locate exact results. • CSSI [62]: This method uses PCA to pr…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

77 extracted references · 67 canonical work pages

  1. [1]

    Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces. Proceedings of the VLDB Endowment 11, 8 (2018), 906–919

    work page 2018

  2. [2]

    Tadas Baltrušaitis, Chaitanya Ahuja, and Louis-Philippe Morency. 2018. Multimodal machine learning: A survey and taxonomy. IEEE transactions on pattern analysis and machine intelligence 41, 2 (2018), 423–443

    work page 2018

  3. [3]

    Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM SIGMOD international conference on Management of data. 322–331

    work page 1990

  4. [4]

    Kakade, and John Langford

    Alina Beygelzimer, Sham M. Kakade, and John Langford. 2006. Cover Trees for Nearest Neighbor. InMachine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006 (ACM International Conference Proceeding Series, Vol. 148) . 97–104

    work page 2006

  5. [5]

    Borzsony, D

    S. Borzsony, D. Kossmann, and K. Stocker. 2001. The Skyline Operator. In Proceedings 17th International Conference on Data Engineering. Heidelberg, Germany, 421–430

    work page 2001

  6. [6]

    Petra Budıková. 2013. Towards Large-Scale Multi-Modal Image Search. (2013)

    work page 2013

  7. [7]

    Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search

    work page 2018

  8. [8]

    Xinyu Chen, Jiajie Xu, Rui Zhou, Pengpeng Zhao, Chengfei Liu, Junhua Fang, and Lei Zhao. 2020. S2R-Tree: A Pivot-Based Indexing Structure for Semantic-Aware Spatial Keyword Search. GeoInformatica 24, 1 (2020), 3–25

    work page 2020

Show all 77 references
  1. [9]

    Zhida Chen, Lisi Chen, Gao Cong, and Christian S. Jensen. 2021. Location- and Keyword-Based Querying of Geo-Textual Data: A Survey. The VLDB Journal 30, 4 (2021), 603–640

    2021

  2. [10]

    Cover and Peter E

    Thomas M. Cover and Peter E. Hart. 1967. Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13, 1 (1967), 21–27

    1967

  3. [11]

    Mirrokni

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, June 8-11, 2004 , Jack Snoeyink and Jean-Dan...

    2004

  4. [12]

    Mirrokni

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. In Proceedings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, June 8-11, 2004 . 253–262

    2004

  5. [13]

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018)

    2018 arXiv

  6. [14]

    Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. 2020. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint...

    2020 arXiv

  7. [15]

    Ronald Fagin, Amnon Lotem, and Moni Naor. 2001. Optimal aggregation algorithms for middleware. In Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems . 102–113

    2001

  8. [16]

    R. A. Finkel and J. L. Bentley. 1974. Quad Trees a Data Structure for Retrieval on Composite Keys. Acta Informatica 4, 1 (1974), 1–9

    1974

  9. [17]

    Steven Fortune. 2004. Voronoi Diagrams and Delaunay Triangulations. In Handbook of Discrete and Computational Geometry, Second Edition. 513–528

    2004

  10. [18]

    Maximilian Franzke, Tobias Emrich, Andreas Zufle, and Matthias Renz. 2016. Indexing Multi-Metric Data. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE) . 1122–1133

    2016

  11. [19]

    Cong Fu, Changxu Wang, and Deng Cai. 2022. High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2022), 4139–4150

    2022

  12. [20]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph. Proceedings of the VLDB Endowment 12, 5 (2019), 461–474

    2019

  13. [21]

    Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012 . 541–552

    2012

  14. [22]

    Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27

    2024

  15. [23]

    Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized Product Quantization. IEEE Trans. Pattern Anal. Mach. Intell. 36, 4 (2014), 744–755

    2014

  16. [24]

    Long Gong, Huayi Wang, Mitsunori Ogihara, and Jun Xu. 2020. iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search. Proc. VLDB Endow. 13, 9 (2020), 1483–1497. Proc. ACM Manag. Data, Vol. 3, No. 1 (SIGMOD), Article 29. Publication date: February 2025....

    2020

  17. [25]

    Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. 2013. Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval.IEEE Transactions on Pattern Analysis and Machine Intelligence 35, 12 (2013), 2916–2929

    2013

  18. [26]

    Rentong Guo, Xiaofan Luan, Long Xiang, Xiao Yan, Xiaomeng Yi, Jigao Luo, Qianya Cheng, Weizhi Xu, Jiarui Luo, Frank Liu, Zhenshan Cao, Yanliang Qiao, Ting Wang, Bo Tang, and Charles Xie. 2022. Manu: A Cloud Native Vector Database Management System. Proceedings of the VLDB Endo...

    2022

  19. [27]

    Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016 . 5713–5722

    2016

  20. [28]

    Ben Harwood and Tom Drummond. 2016. Fanng: Fast approximate nearest neighbour graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition . 5713–5722

    2016

  21. [29]

    Jae-Pil Heo, Youngwoon Lee, Junfeng He, Shih-Fu Chang, and Sung-Eui Yoon. 2015. Spherical Hashing: Binary Code Embedding with Hyperspheres. IEEE Trans. Pattern Anal. Mach. Intell. 37, 11 (2015), 2304–2316

    2015

  22. [30]

    Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015. Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search. Proc. VLDB Endow. 9, 1 (2015), 1–12

    2015

  23. [31]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimen- sionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998. 604–613

    1998

  24. [32]

    Masajiro Iwasaki. 2015. Neighborhood Graph and Tree for Indexing Highdimensional Data. Yahoo Japan Corporation. Retrieved August 22 (2015), 2020

    2015

  25. [33]

    H. V. Jagadish, Beng Chin Ooi, Kian-Lee Tan, Cui Yu, and Rui Zhang. 2005. iDistance: An adaptive B +-tree based indexing method for nearest neighbor search. ACM Trans. Database Syst. 30, 2 (2005), 364–397

    2005

  26. [34]

    Jerzy W Jaromczyk and Mirosław Kowaluk. 1991. Constructing the relative neighborhood graph in 3-dimensional Euclidean space. Discrete Applied Mathematics 31, 2 (1991), 181–191

    1991

  27. [35]

    H Jégou, M Douze, and C Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 1 (2011), 117–128

    2011

  28. [36]

    Christos Kalyvas and Theodoros Tzouramanis. 2017. A survey of skyline query processing. arXiv preprint arXiv:1704.01788 (2017)

    2017 arXiv

  29. [37]

    Khalefa, Mohamed F

    Mohamed E. Khalefa, Mohamed F. Mokbel, and Justin J. Levandoski. 2008. Skyline Query Processing for Incomplete Data. In 2008 IEEE 24th International Conference on Data Engineering . Cancun, Mexico, 556–565

    2008

  30. [38]

    Joseph B Kruskal. 1956. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.Proceedings of the American Mathematical society 7, 1 (1956), 48–50

    1956

  31. [39]

    Kankanhalli, and Anthony K

    Yifan Lei, Qiang Huang, Mohan S. Kankanhalli, and Anthony K. H. Tung. 2020. Locality-Sensitive Hashing Scheme Based on Longest Circular Co-Substring. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, Online Conference [Portland,...

    2020

  32. [40]

    Andersen, and Yuxiong He

    Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. 2020. Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . 2539–2554

    2020

  33. [41]

    Jinfeng Li, Xiao Yan, Jie Zhang, An Xu, James Cheng, Jie Liu, Kelvin Kai Wing Ng, and Ti-Chung Cheng. 2018. A General and Efficient Querying Method for Learning to Hash. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston,...

    2018

  34. [42]

    Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2020. Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement. IEEE Transactions on Knowledge and Data Engineering 32, 8 (2020), 1475–1488

    2020

  35. [43]

    Shang Liu, Gao Cong, Kaiyu Feng, Wanli Gu, and Fuzheng Zhang. 2023. Effectiveness Perspectives and a Deep Relevance Model for Spatial Keyword Queries. Proc. ACM Manag. Data 1, 1 (2023), 11:1–11:25

    2023

  36. [44]

    Yingfan Liu, Jiangtao Cui, Zi Huang, Hui Li, and Heng Tao Shen. 2014. SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search. Proc. VLDB Endow. 7, 9 (2014), 745–756

    2014

  37. [45]

    Kejing Lu, Hongya Wang, Wei Wang, and Mineichi Kudo. 2020. VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning. Proc. VLDB Endow. 13, 9 (2020), 1443–1455

    2020

  38. [46]

    Pingchuan Ma, Tao Du, and Wojciech Matusik. 2020. Efficient continuous pareto exploration in multi-task learning. In International Conference on Machine Learning . PMLR, 6522–6531

    2020

  39. [47]

    Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate Nearest Neighbor Algorithm Based on Navigable Small World Graphs. 45 (2014), 61–68

    2014

  40. [48]

    Malkov and D

    Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2020), 824–836

    2020

  41. [49]

    Yusuke Matsui, Yusuke Uchida, Hervé Jégou, and Shin’ichi Satoh. 2018. A Survey of Product Quantization. ITE Transactions on Media Technology and Applications 6, 1 (2018), 2–10. Proc. ACM Manag. Data, Vol. 3, No. 1 (SIGMOD), Article 29. Publication date: February 2025. DEG: Eff...

    2018

  42. [50]

    Antoine Miech, Jean-Baptiste Alayrac, Lucas Smaira, Ivan Laptev, Josef Sivic, and Andrew Zisserman. 2020. End-to-end learning of visual representations from uncurated instructional videos. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition . 9879–9889

    2020

  43. [51]

    Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic. 2019. HowTo100M: Learning a Text-Video Embedding by Watching Hundred Million Narrated Video Clips. In ICCV

    2019

  44. [52]

    James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Vector Database Management Techniques and Systems. In Companion of the 2024 International Conference on Management of Data . Santiago AA Chile, 597–604

    2024

  45. [53]

    Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger. 2005. Progressive Skyline Computation in Database Systems. ACM Transactions on Database Systems 30, 1 (2005), 41–82

    2005

  46. [54]

    Rodrigo Paredes and Edgar Chávez. 2005. Using the k-Nearest Neighbor Graph for Proximity Searching in Metric Spaces. In String Processing and Information Retrieval, 12th International Conference, SPIRE 2005, Buenos Aires, Argentina, November 2-4, 2005, Proceedings (Lecture Not...

    2005

  47. [55]

    Jordi Pont-Tuset, Jasper Uijlings, Soravit Changpinyo, Radu Soricut, and Vittorio Ferrari. 2020. Connecting Vision and Language with Localized Narratives. In ECCV

    2020

  48. [56]

    Zhihu Qian, Jiajie Xu, Kai Zheng, Pengpeng Zhao, and Xiaofang Zhou. 2018. Semantic-Aware Top-k Spatial Keyword Queries. World Wide Web 21, 3 (2018), 573–594

    2018

  49. [57]

    Parikshit Ram and Kaushik Sinha. 2019. Revisiting Kd-Tree for Nearest Neighbor Search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019. 1378–1388

    2019

  50. [58]

    Amaia Salvador, Nicholas Hynes, Yusuf Aytar, Javier Marin, Ferda Ofli, Ingmar Weber, and Antonio Torralba. 2017. Learning cross-modal embeddings for cooking recipes and food images. In Proceedings of the IEEE conference on computer vision and pattern recognition . 3020–3028

    2017

  51. [59]

    Ben Schafer, Dan Frankowski, Jonathan L

    J. Ben Schafer, Dan Frankowski, Jonathan L. Herlocker, and Shilad Sen. 2007. Collaborative Filtering Recommender Systems. In The Adaptive Web, Methods and Strategies of Web Personalization (Lecture Notes in Computer Science, Vol. 4321). 291–324

    2007

  52. [60]

    Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut. 2018. Conceptual Captions: A Cleaned, Hypernymed, Image Alt-text Dataset For Automatic Image Captioning. In Proceedings of ACL

    2018

  53. [61]

    Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. 2010. Efficient and Accurate Nearest Neighbor and Closest Pair Search in High-Dimensional Space. ACM Transactions on Database Systems 35, 3 (2010), 20:1–20:46

    2010

  54. [62]

    Theodoropoulos, Kjetil Nørvåg, and Christos Doulkeridis

    George S. Theodoropoulos, Kjetil Nørvåg, and Christos Doulkeridis. 2024. Efficient Semantic Similarity Search over Spatio-Textual Data. InProceedings 27th International Conference on Extending Database Technology, EDBT 2024, Paestum, Italy, March 25 - March 28 . 268–280

    2024

  55. [63]

    Yao Tian, Xi Zhao, and Xiaofang Zhou. 2024. DB-LSH 2.0: Locality-Sensitive Hashing with Query-Based Dynamic Bucketing. IEEE Transactions on Knowledge and Data Engineering 36, 3 (2024), 1000–1015

    2024

  56. [64]

    Toussaint

    Godfried T. Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern Recognit. 12, 4 (1980), 261–268

    1980

  57. [65]

    Ertem Tuncel, Hakan Ferhatosmanoglu, and Kenneth Rose. 2002. VQ-Index: An Index Structure for Similarity Searching in Multimedia Databases. In Proceedings of the 10th ACM International Conference on Multimedia 2002, Juan Les Pins, France, December 1-6, 2002 . 543–552

    2002

  58. [66]

    Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. 2014. Hashing for Similarity Search: A Survey. CoRR abs/1408.2927 (2014)

    2014 arXiv

  59. [67]

    Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. M...

    2021

  60. [68]

    Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, and Heng Tao Shen. 2018. A Survey on Learning to Hash. IEEE Trans. Pattern Anal. Mach. Intell. 40, 4 (2018), 769–790

    2018

  61. [69]

    Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. Proceedings of the VLDB Endowment 14, 11 (2021), 1964–1978

    2021

  62. [70]

    Roger Weber, Hans-Jörg Schek, and Stephen Blott. 1998. A Quantitative Analysis and Performance Study for Similarity- Search Methods in High-Dimensional Spaces. In VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City,...

    1998

  63. [71]

    Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: A Hybrid Analytical Engine towards Query Fusion for Structured and Unstructured Data. Proceedings of the VLDB Endowment 13, 12 (2020), 3152–3165. Proc. ACM Manag. Data...

    2020

  64. [72]

    Penghao Zhao, Hailin Zhang, Qinhan Yu, Zhengren Wang, Yunteng Geng, Fangcheng Fu, Ling Yang, Wentao Zhang, and Bin Cui. 2024. Retrieval-Augmented Generation for AI-Generated Content: A Survey

    2024

  65. [73]

    Wayne Xin Zhao, Jing Liu, Ruiyang Ren, and Ji-Rong Wen. 2022. Dense Text Retrieval based on Pretrained Language Models: A Survey. CoRR abs/2211.14876 (2022)

    2022 arXiv

  66. [74]

    Bolong Zheng, Xi Zhao, Lianggui Weng, Quoc Viet Hung Nguyen, Hang Liu, and Christian S. Jensen. 2022. PM-LSH: A Fast and Accurate in-Memory Framework for High-Dimensional Approximate NN and Closest Pair Search. Vldb Journal 31, 6 (2022), 1339–1363

    2022

  67. [75]

    Zhiyong Huang, Hua Lu, Beng Chin Ooi, and A.K.H. Tung. 2006. Continuous Skyline Queries for Moving Objects. IEEE Transactions on Knowledge and Data Engineering 18, 12 (2006), 1645–1658

    2006

  68. [76]

    Chun Jiang Zhu, Tan Zhu, Haining Li, Jinbo Bi, and Minghu Song. 2019. Accelerating Large-Scale Molecular Similarity Search through Exploiting High Performance Computing. In 2019 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2019, San Diego, CA, USA, Nov...

    2019

  69. [77]

    For example, [43] finds that the optimal weight for most queries ranges from 0.1 to 0.4

    It is worth noting that such a case is not a common scenario for HVQ. For example, [43] finds that the optimal weight for most queries ranges from 0.1 to 0.4. Given that our proposed DEG is tailored for HVQ, it is as expected that DEG performs worse than the ideal method, orac...

    2025

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.