Pith. sign in

REVIEW 4 major objections 8 minor 36 references

A flat proximity graph that merges full-attribute and single-attribute edges supports arbitrary filtered nearest-neighbor search and beats the prior state of the art when few attributes are specified.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

A labeled flat proximity graph built from full- and single-attribute partitions supports arbitrary filtered ANNS and beats UNG on 1–2 attribute queries at similar recall.

T0 review reviewed 2026-07-31 challenge →

load-bearing objection Simple labeled merge of full-tuple and single-attribute NSW graphs that beats UNG on partial filters in their setup, with a real but unproved navigability gap the power-law eval mostly avoids. the 4 major comments →

arxiv 2607.24173 v1 pith:BTFEYMUD submitted 2026-07-27 cs.DB

Simple and Fast Algorithm for Graph-based Filtered Approximate Nearest Neighbor Search (Full Version)

Reon Uemura , Keito Kido , Daichi Amagata This is my paper
classification cs.DB
keywords filtered approximate nearest neighbor searchproximity graphattribute filterNSWhigh-dimensional vectorsgreedy searchedge labeling
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

High-dimensional vectors often come with categorical attributes, and users want the nearest vectors that also match a chosen subset of those attributes. Existing graph indexes either explode in size when every attribute combination is pre-built or become slow when only one or two attributes are filtered. This paper shows that a single flat graph is enough: build ordinary proximity graphs on every full attribute tuple and on every single-attribute slice, then keep the extra edges under simple labels. At query time a standard greedy walk simply ignores edges whose labels do not match the filter. On standard million-scale data the resulting search is substantially faster than the previous best method for the common one- and two-attribute cases while remaining competitive when every attribute is constrained, all at linear space in the number of attributes.

Core claim

A carefully edge-augmented flat proximity graph, obtained by unioning the graphs of all full attribute combinations with the graphs of all single-attribute partitions and labeling the added edges, lets ordinary greedy search answer arbitrary matching filters. The construction uses only O(nm) space and, under the reported settings, yields higher queries-per-second than UNG at the same recall whenever the query specifies one or two of the three attributes.

What carries the argument

The labeled flat graph G produced by Algorithm 1: every object keeps its ordinary neighbors inside its full-attribute clique (label ⊥) plus neighbors taken from each of its m single-attribute graphs (label = the neighbor’s full attribute list). Greedy search from a medoid simply skips any edge whose label fails the query filter.

Load-bearing premise

Edges drawn only from the full-tuple graphs and the m single-attribute graphs are already enough to keep greedy search navigable inside every intermediate partial filter, without ever materializing the missing combination graphs.

What would settle it

On the same SIFT/Deep/GIST collections with m=3 power-law attributes, measure QPS-versus-recall@10 for two-attribute queries; if the new graph falls below UNG across the operating range, or if recall collapses when the random start-node completion is replaced by a fixed default, the claim fails.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Vector databases can support arbitrary matching filters with a single flat index whose size grows only linearly with the number of attributes.
  • The common practical case of one- or two-attribute filters no longer forces a large slowdown relative to unfiltered search.
  • Any existing flat proximity-graph builder (NSW, KGraph, Vamana, …) can be dropped in as the Build-Graph primitive without redesigning the filter logic.
  • Index construction remains a one-time offline cost of the same asymptotic order as building m ordinary graphs on the whole set.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same labeling trick could be tried on hierarchical graphs (HNSW-style) provided the extra edges are inserted at every layer; the paper never tests this.
  • If real attribute cardinalities are far more skewed than the synthetic power-law used here, the single-attribute graphs may become dense hubs and the space bound O(nm) could hide a large constant.
  • Dynamic insertion or deletion would require maintaining both the full-tuple and single-attribute neighborhoods; the static assumption leaves that engineering open.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 8 minor

Summary. The paper addresses filtered approximate k-nearest neighbor search (filtered ANNS), where each object has a high-dimensional vector and m integer attribute values, and queries specify a vector plus values for an arbitrary subset of the attributes. The proposed index is a single flat, edge-labeled proximity graph built by merging (i) one NSW graph per full attribute tuple and (ii) one NSW graph per single-attribute value, with edges labeled ⊥ (same full tuple) or by the target's attribute list. Query processing (Algorithm 2) fills null attributes with random values to pick a medoid start node, then runs greedy search traversing only edges whose labels are ⊥ or whose target satisfies the filter. The authors claim O(nm) space, T(nm) build time, and — via QPS-vs-recall@10 experiments on SIFT/GIST/Deep with m=3 power-law attributes — substantial improvements over the state-of-the-art UNG for one- and two-attribute filters, parity for three-attribute filters, and sublinear QPS degradation as n scales to 100M.

Significance. If the empirical results hold up, the contribution is useful: a conceptually simple flat-graph design for multi-attribute filtered ANNS with O(nm) space, support for arbitrary matching filters, and consistent QPS gains over the current state of the art (UNG) in the practically dominant 1–2 attribute regime. The algorithm is easy to implement on top of any flat proximity graph, uses standard public datasets and the baseline's own public implementation, and reports a clear time/space complexity analysis, all of which aid reproducibility. The main limitation is that the central mechanism for intermediate filters is heuristic, and the current evaluation does not probe the regime (rare attribute combinations) where it could fail; the scalability claim is also weakened by the absence of any baseline at 100M points.

major comments (4)
  1. [§4 Case 3; §5, Fig. 3] §4 (Case 3) and Algorithm 2, lines 11–20: the central mechanism for intermediate filters (2 ≤ |q.A| < m) rests on an unproven navigability assumption, and the evaluation is structured so that this assumption is barely stressed. For a filter q.A=[a,b,*], traversal from a start node in block X_{a,b,c'} can use ⊥-edges (which stay inside X_{a,b,c'}) or labeled edges whose target satisfies q.A. Edges crossing between different c-blocks of X(q.A) exist only incidentally, when two nodes in different c-blocks happen to be NSW-neighbors in a single-attribute graph (G_{a,*,*} mixes all b; G_{*,b,*} mixes all a). Nothing in Algorithm 1 guarantees that the label-permitted subgraph induced on X(q.A) is connected or contains monotonic paths, so for a rare (a,b) pair greedy search can be confined to the starting c'-block and recall for that filter can collapse. Because query filters in §5 are drawn fr
  2. [§4.2, Algorithm 2] Algorithm 2, lines 2–4: the random null-fill used to determine the start node is ill-defined in a common case. If the randomly chosen value c' for the null attribute makes X_{a,b,c'} empty (possible whenever the joint distribution is not a full product — e.g., under the power-law generator some (a,b,c') triples need not occur), then G_A is empty and 'the medoid node in G_A' does not exist. Even when non-empty, a tiny X_{a,b,c'} gives a badly placed start that interacts with the fragmentation concern above. The algorithm as written never checks non-emptiness. Please state how this is handled in the implementation (e.g., resampling until X_{a,b,c'} ≠ ∅, or falling back to the medoid of G_{a,*,*}), and discuss the cost/quality impact.
  3. [§5, Figs. 5–6] §5 (scalability test, Figs. 5–6): the scalability claim is weakened by two gaps. First, UNG — the sole baseline — could not be run at 100M (reported segmentation fault in the authors' public implementation), so the paper's headline comparison has no baseline at the scale where the design (flat graph, no trie traversal) should matter most; the 100× claim against Pre-filter (QPS 0.42) is against a strawman. Second, the claim that 'QPS does not drop linearly with n but rather sublinearly' is not quantified — reading log-log slopes off Figs. 5–6 is left to the reader, and sublinear QPS decay is generic for graph ANNS, not evidence specific to this design. Either fit/report the scaling exponents, or tone the claim down; and, if feasible, compare against any baseline that runs at 100M (e.g., ACORN, which the authors' implementation of this framework should readily accommodate).
  4. [§5 (experimental setup); §4.1] §5: no index build times are reported anywhere, although build cost is a standard evaluation axis for ANNS indices and the paper makes a specific complexity claim (T(nm) for Algorithm 1, §4.1). Algorithm 1 builds one NSW per distinct full attribute tuple — with 68×10×12 possible triples and 1M–100M points, the number of distinct tuples can be very large, and many will be tiny blocks whose per-graph fixed overheads (plus per-tuple medoid computation referenced in Alg. 2, line 4) are invisible in the asymptotic statement. Report wall-clock build time and the number of distinct tuples per dataset, so readers can judge the T(nm) claim and the practicality of per-tuple graphs.
minor comments (8)
  1. [§2] §2, Preliminary: 'Note that d = O(1) and d is large' is self-contradictory as written; presumably you mean d is treated as a constant in the asymptotics while being large in practice. Please rephrase.
  2. [§2, after Definition 2] §2, recall definition: recall@k = |S ∩ S*|/k can never reach 1 when |X(q.A)| < k, yet Definition 2 returns X(q.A) in that case. With 68/10/12 distinct values and a power law, small X(q.A) will occur. State whether such queries were excluded or how recall was normalized.
  3. [§3] §3: 'HSNW' should be 'HNSW' [18].
  4. [§4.2, Algorithm 2] Algorithm 2, lines 13–21: the control flow would be clearer if the common lines 14–18 were factored out; as written, 'Run lines 14–18' inside the else-branch is informal for a pseudocode block. Also, τ is described as 'the ε·k-th dist in P' only via the comment on line 16 — please define the update rule explicitly.
  5. [§5, Figs. 2–4] Fig. 2(c): the recall axis spans [0, 1] while the other panels use [0.7, 1] or [0.75, 1], which visually understates the Deep result; harmonize axes or note the difference. Also report whether QPS/recall are means over the 1,000 queries and consider adding variance or percentile information.
  6. [§5, Table 1] Table 1: clarify whether index size includes the raw vectors or only graph structure plus labels, and give the per-dataset distinct-tuple counts (relevant to both memory and build cost).
  7. [§5] §5: K = K' = 16 is used throughout without ablation. Since K' controls the density of exactly the cross-block edges on which Case 3 depends, a sensitivity plot (recall vs. K' at fixed K) would substantially strengthen the paper at low cost.
  8. [§1] §1: 'RAG' is used without a citation or expansion; the motivation would benefit from a reference. Also, 'approximate k nearest neighbor search' is hyphenated inconsistently across the text.

Circularity Check

0 steps flagged

No circularity: algorithmic construction and empirical QPS/recall evaluation do not reduce inputs to claimed outputs by definition.

full rationale

This is a systems/algorithms paper. The index (Algorithm 1) merges full-tuple NSW graphs with m single-attribute NSW graphs and labels cross edges; query processing (Algorithm 2) is standard greedy search restricted by those labels. Recall@k is defined against exact filtered kNN on the same static data; QPS is wall-clock. Hyperparameters (K, K', ε) control the usual time–recall tradeoff and are not fitted to produce a ‘prediction’ that is forced by construction. Self-citations (authors’ prior ANNS/IVF work and the SISAP short version) appear only as related work or version note and do not supply a uniqueness theorem, ansatz, or load-bearing premise that the evaluation then re-derives. The unproved navigability claim for intermediate filters is an empirical/correctness risk, not a circular reduction of output to input. Derivation chain is self-contained against external baselines (UNG) and standard metrics; circularity score is floor.

Axiom & Free-Parameter Ledger

3 free parameters · 6 axioms · 1 invented entities

The central performance claim rests on standard ANNS graph assumptions, a static corpus, small m, synthetic attribute statistics matching ‘practice,’ and two hand-chosen degree hyperparameters. No new physical entities; the invented structure is the labeled merged graph. Free parameters are the graph degrees and the search expansion ε.

free parameters (3)
  • K (full-tuple graph degree) = 16
    Initial degree passed to Build-Graph for each X_a,b,...,c; fixed to 16 in all experiments without sensitivity study.
  • K' (single-attribute graph degree) = 16
    Degree for each per-attribute partition graph whose edges are merged with labels; fixed to 16.
  • ε (search expansion / candidate multiplier) = varied (≥1)
    Controls the ε·k candidate pool size in Algorithm 2; swept to trace QPS–recall curves, not a learned constant but a free accuracy knob the claimed tradeoff depends on.
axioms (6)
  • domain assumption X is static; dynamic inserts/deletes are out of scope
    Stated in Section 2; index construction (Algorithm 1) is offline-only.
  • domain assumption Number of attributes m is small in practice (e.g. ≤3), so O(nm) edge space is acceptable
    Invoked in Section 4 Case 2 and space-complexity paragraph; cites survey [17].
  • domain assumption Flat NSW (with HNSW-style optimization) is a sufficient base proximity graph for high-d Euclidean ANNS
    Section 4.1 chooses NSW as the Build-Graph implementation; relies on established ANNS literature rather than proving navigability of the merged labeled graph.
  • ad hoc to paper Query filters and attribute values follow the same power-law distributions used to generate labels, with m=3 and fixed distinct-value counts
    Section 5 dataset construction; evaluation workload is synthetic on top of public vectors.
  • domain assumption Matching (equality) filters only; range filters are out of scope
    Section 3 explicitly restricts to matching filters.
  • standard math Standard Euclidean distance and recall@k against exact filtered kNN are the right quality measures
    Definitions 1–2 and experimental criteria in Section 5.
invented entities (1)
  • Labeled merged proximity graph G with edge labels ⊥ or x'.A no independent evidence
    purpose: Allow one flat graph to serve full, single, and partial attribute filters by restricting traversal to edges whose labels match q.A.
    Defined in Section 4.1 Equation (2) and Algorithm 1; the paper’s core index object. Navigability under partial filters is not proved independently of the experiments.

reviewed 2026-07-31 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Simple and Fast Algorithm for Graph-based Filtered Approximate Nearest Neighbor Search (Full Version)." pith.science (2026). https://pith.science/paper/BTFEYMUD

@misc{pith2026260724173,
  author       = {Pith},
  title        = {Pith review of: Simple and Fast Algorithm for Graph-based Filtered Approximate Nearest Neighbor Search (Full Version)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BTFEYMUD}},
  note         = {Machine review of arXiv:2607.24173}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

It has been common to represent many objects as high-dimensional vectors due to the proliferation of machine learning-based embedding techniques. One of the most important functions for analyzing high-dimensional vectors is approximate nearest neighbor search, which, given a query vector, retrieves the vector that is approximately the most similar to the query vector. In many real-world applications, such as e-commerce, objects have not only vectors but also attributes, e.g., category, color, and brand, and they require a scenario where users can specify a query vector and a value for each attribute of interest. This problem, called filtered approximate nearest neighbor search, retrieves approximate nearest neighbors from a set of objects that have the specified attribute values. Efficiently solving this problem is challenging because it has to accept arbitrary query vectors and attribute values, which are not known in advance. Existing techniques suffer from slow search performance and difficulty in dealing with arbitrary combinations of attributes. This work overcomes these challenges and proposes a new algorithm for this problem. We conduct extensive experiments, and the results demonstrate the efficiency of our algorithm.

Figures

Figures reproduced from arXiv: 2607.24173 by Daichi Amagata, Keito Kido, Reon Uemura.

Figure 1
Figure 1. Figure 1: Example of our graph building Which graph index is available in our algorithm? As seen in [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: QPS vs. recall@10 for query filters with a single attribute. “×” shows Ours and “◦” shows UNG. million vectors. By default, we used 1 and 10 million vectors for SIFT and Deep, respectively. (The full set is used in our scalability test.) We set m = 3, as in [5,12,29], so each object has three attributes. For each attribute, we employed the power law distribution, as used in [5], because it is commonly obse… view at source ↗
Figure 3
Figure 3. Figure 3: QPS vs. recall@10 for query filters with two attributes. “×” shows Ours and “◦” shows UNG. 0 10000 20000 30000 40000 50000 60000 0.98 0.985 0.99 0.995 1 QPS Recall@10 SIFT1M - 3 attributes (a) SIFT 0 2000 4000 6000 8000 10000 12000 14000 16000 0.92 0.94 0.96 0.98 1 QPS Recall@10 GIST1M - 3 attributes (b) GIST 0 5000 10000 15000 20000 25000 30000 0.94 0.95 0.96 0.97 0.98 0.99 1 QPS Recall@10 Deep10M - 3 att… view at source ↗
Figure 4
Figure 4. Figure 4: QPS vs. recall@10 for query filters with three attributes. “×” shows Ours and “◦” shows UNG. Query filter of two attributes case [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Impact of n on SIFT under recall@10 = 0.99 10 100 1000 1 10 100 QPS Data size x106 Deep (1 attribute): recall@10 = 0.99 (a) 1 attribute 10 100 1000 1 10 100 QPS Data size x106 Deep (2 attributes): recall@10 = 0.99 (b) 2 attributes 1000 10000 100000 1 10 100 QPS Data size x106 Deep (3 attributes): recall@10 = 0.99 (c) 3 attributes [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Impact of n on Deep under recall@10 = 0.99 Scalability test. Last, we investigate the scalability of our algorithm by using 1, 10, and 100 million vectors. When scaling to 100M vectors, we were unable to run UNG successfully using the authors’ public implementation under our experimental setup. (It terminated with a runtime failure, i.e., a segmentation fault.) Hence, we only report the scalability results… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 5 linked inside Pith

  1. [1]

    In: IEEE Big Data

    Amagata,D.:Scalableandaccuratedensity-peaksclusteringonfullydynamicdata. In: IEEE Big Data. pp. 445–454 (2022)

    2022

  2. [2]

    In: SIGMOD

    Amagata, D., Onizuka, M., Hara, T.: Fast and exact outlier detection in metric spaces: A proximity graph-based approach. In: SIGMOD. pp. 36–48 (2021)

    2021

  3. [3]

    The VLDB Journal 31(4), 797–821 (2022)

    Amagata, D., Onizuka, M., Hara, T.: Fast, exact, and parallel-friendly outlier de- tection algorithms with proximity graph in metric spaces. The VLDB Journal 31(4), 797–821 (2022)

    2022

  4. [4]

    Proceedings of the ACM on Management of Data 3(1), 1–31 (2025)

    Azizi, I., Echihabi, K., Palpanas, T.: Graph-based vector search: An experimental evaluation of the state-of-the-art. Proceedings of the ACM on Management of Data 3(1), 1–31 (2025)

    2025

  5. [5]

    Proceedings of the ACM on Management of Data2(6), 1–27 (2024)

    Cai, Y., Shi, J., Chen, Y., Zheng, W.: Navigating labels and vectors: A unified approach to filtered approximate nearest neighbor search. Proceedings of the ACM on Management of Data2(6), 1–27 (2024)

    2024

  6. [6]

    In: Asilomar Conference on Signals, Systems and Computers

    Dearholt, D.W., Gonzales, N., Kurup, G.: Monotonic search networks for computer vision databases. In: Asilomar Conference on Signals, Systems and Computers. vol. 2, pp. 548–553 (1988)

    1988

  7. [7]

    In: World Wide Web

    Dong, W., Moses, C., Li, K.: Efficient k-nearest neighbor graph construction for generic similarity measures. In: World Wide Web. pp. 577–586 (2011)

    2011

  8. [8]

    In: ICML (2024)

    Engels, J., Landrum, B., Yu, S., Dhulipala, L., Shun, J.: Approximate nearest neighbor search with window filters. In: ICML (2024)

    2024

  9. [9]

    IEEE Transac- tions on Pattern Analysis and Machine Intelligence44(8), 4139–4150 (2021)

    Fu, C., Wang, C., Cai, D.: High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transac- tions on Pattern Analysis and Machine Intelligence44(8), 4139–4150 (2021)

    2021

  10. [10]

    Proceedings of the VLDB Endowment 12(5), 461–474 (2019)

    Fu, C., Xiang, C., Wang, C., Cai, D.: Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment 12(5), 461–474 (2019)

    2019

  11. [11]

    In: Web Conference

    Gollapudi, S., Karia, N., Sivashankar, V., Krishnaswamy, R., Begwani, N., Raz, S., Lin, Y., Zhang, Y., Mahapatro, N., Srinivasan, P., et al.: Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters. In: Web Conference. pp. 3406–3416 (2023)

    2023

  12. [12]

    arXiv preprint arXiv:2308.15014 (2023)

    Gupta, G., Yi, J., Coleman, B., Luo, C., Lakshman, V., Shrivastava, A.: Caps: A practical partition index for filtered similarity search. arXiv preprint arXiv:2308.15014 (2023)

    Pith/arXiv arXiv 2023

  13. [13]

    Proceedings of the ACM on Management of Data3(3), 1–26 (2025) Simple and Fast Algorithm for Graph-based Filtered ANNS 13

    Jiang, M., Yang, Z., Zhang, F., Hou, G., Shi, J., Zhou, W., Li, F., Wang, S.: Digra: A dynamic graph indexing for approximate nearest neighbor search with range filter. Proceedings of the ACM on Management of Data3(3), 1–26 (2025) Simple and Fast Algorithm for Graph-based Filtered ANNS 13

    2025

  14. [14]

    In: PAKDD

    Kido, K., Amagata, D., Hara, T.: Fast approximation algorithm for euclidean min- imum spanning tree building in high dimensions. In: PAKDD. pp. 432–443 (2025)

    2025

  15. [15]

    Proceedings of the ACM on Management of Data3(6), 1–26 (2025)

    Li, M., Yan, X., Lu, B., Zhang, Y., Cheng, J., Ma, C.: Attribute filtering in ap- proximate nearest neighbor search: An in-depth experimental study. Proceedings of the ACM on Management of Data3(6), 1–26 (2025)

    2025

  16. [16]

    IEEE Transactions on Knowledge and Data Engineering32(8), 1475–1488 (2019)

    Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., Lin, X.: Approxi- mate nearest neighbor search on high dimensional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering32(8), 1475–1488 (2019)

    2019

  17. [17]

    arXiv preprint arXiv:2505.06501 (2025)

    Lin, Y., Zhang, K., He, Z., Jing, Y., Wang, X.S.: Survey of filtered approxi- mate nearest neighbor search over the vector-scalar hybrid data. arXiv preprint arXiv:2505.06501 (2025)

    Pith/arXiv arXiv 2025

  18. [18]

    IEEE Transactions on Pattern Analysis and Machine Intelligencee42(4), 824–836 (2018)

    Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neigh- bor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligencee42(4), 824–836 (2018)

    2018

  19. [19]

    Information Systems 45, 61–68 (2014)

    Malkov, Y., Ponomarenko, A., Logvinov, A., Krylov, V.: Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45, 61–68 (2014)

    2014

  20. [20]

    Proceedings of the ACM on Management of Data2(3), 1–27 (2024)

    Patel, L., Kraft, P., Guestrin, C., Zaharia, M.: Acorn: Performant and predicate- agnostic search over vector embeddings and structured data. Proceedings of the ACM on Management of Data2(3), 1–27 (2024)

    2024

  21. [21]

    Proceedings of the ACM on Man- agement of Data1(1), 1–27 (2023)

    Peng, Y., Choi, B., Chan, T.N., Yang, J., Xu, J.: Efficient approximate nearest neighbor search in multi-dimensional databases. Proceedings of the ACM on Man- agement of Data1(1), 1–27 (2023)

    2023

  22. [22]

    arXiv preprint arXiv:2509.07789 (2025)

    Shi, J., Cai, Y., Zheng, W.: Filtered approximate nearest neighbor search: A uni- fied benchmark and systematic experimental study [experiment, analysis & bench- mark]. arXiv preprint arXiv:2509.07789 (2025)

    Pith/arXiv arXiv 2025

  23. [23]

    In: NeurIPS

    Subramanya, S.J., Devvrit, Kadekodi, R., Krishaswamy, R., Simhadri, H.V.: Diskann: Fast accurate billion-point nearest neighbor search on a single node. In: NeurIPS. pp. 13766–13776 (2019)

    2019

  24. [24]

    Pattern Recognition12(4), 261–268 (1980)

    Toussaint, G.T.: The relative neighbourhood graph of a finite planar set. Pattern Recognition12(4), 261–268 (1980)

    1980

  25. [25]

    In: IEEE International Conference on Big Data

    Uemura, R., Amagata, D.: Ivf++: A flexible and efficient algorithm for approxi- mate nearest neighbor search under attribute constraint. In: IEEE International Conference on Big Data. pp. 7444–7451 (2025)

    2025

  26. [26]

    In: SISAP (2024)

    Uemura, R., Amagata, D., Hara, T.: An efficient framework for approximate near- est neighbor search on high-dimensional multi-metric data. In: SISAP (2024)

    2024

  27. [27]

    In: SISAP (2026)

    Uemura, R., Kido, K., Amagata, D.: Simple and fast algorithm for graph-based filtered approximate nearest neighbor search. In: SISAP (2026)

    2026

  28. [28]

    In: SIGMOD

    Wang, J., Yi, X., Guo, R., Jin, H., Xu, P., Li, S., Wang, X., Guo, X., Li, C., Xu, X., et al.: Milvus: A purpose-built vector data management system. In: SIGMOD. pp. 2614–2627 (2021)

    2021

  29. [29]

    arXiv preprint arXiv:2203.13601 (2022)

    Wang, M., Lv, L., Xu, X., Wang, Y., Yue, Q., Ni, J.: Navigable proximity graph- driven native hybrid queries with structured and unstructured constraints. arXiv preprint arXiv:2203.13601 (2022)

    Pith/arXiv arXiv 2022

  30. [30]

    In: NeurIPS

    Wang, M., Lv, L., Xu, X., Wang, Y., Yue, Q., Ni, J.: An efficient and robust framework for approximate nearest neighbor search with attribute constraint. In: NeurIPS. pp. 15738–15751 (2023)

    2023

  31. [31]

    In: CIKM

    Wu, W., He, J., Qiao, Y., Fu, G., Liu, L., Yu, J.: Hqann: Efficient and robust similarity search for hybrid queries with structured and unstructured constraints. In: CIKM. pp. 4580–4584 (2022) 14 Uemura et al

    2022

  32. [32]

    Proceedings of the ACM on Management of Data2(6), 1–26 (2024)

    Xu, Y., Gao, J., Gou, Y., Long, C., Jensen, C.S.: irangegraph: Improvising range- dedicated graphs for range-filtering nearest neighbor search. Proceedings of the ACM on Management of Data2(6), 1–26 (2024)

    2024

  33. [33]

    Yamashita, T., Amagata, D., Matsui, Y.: How should we evaluate data deletion in graph-based ann indexes? arXiv preprint arXiv:2512.06200 (2025)

    arXiv 2025

  34. [34]

    Yu, S., Engels, J., Huang, Y., Shun, J.: Pecann: Parallel efficient clustering with graph-basedapproximatenearestneighborsearch.arXivpreprintarXiv:2312.03940 (2023)

    Pith/arXiv arXiv 2023

  35. [35]

    Proceedings of the VLDB Endowment19(2), 183–195 (2025)

    Zhu, J., Yuan, J., Yang, K., Chen, X., Yu, S., Lv, H., Li, Y., Zheng, B.: An ex- perimental evaluation of hybrid querying on vectors. Proceedings of the VLDB Endowment19(2), 183–195 (2025)

    2025

  36. [36]

    Proceedings of the ACM on Man- agement of Data2(1), 1–26 (2024)

    Zuo, C., Qiao, M., Zhou, W., Li, F., Deng, D.: Serf: Segment graph for range- filtering approximate nearest neighbor search. Proceedings of the ACM on Man- agement of Data2(1), 1–26 (2024)

    2024

This paper was first reviewed by grok-4.5 on July 31, 2026.