arXiv CSopen access

MCI: A Maximal Clique Index for Efficient Arbitrary-Filtered Approximate Nearest Neighbor Search

arXiv:2604.22171v1 [cs.DB] 24 Apr 2026

MCI: A Maximal Clique Index for Efficient Arbitrary-Filtered Approximate Nearest Neighbor Search Xiaowei Ye

Rong-Hua Li

Guoren Wang

Beijing Institute of Technology Beijing, China [email protected]

Beijing Institute of Technology Beijing, China [email protected]

Beijing Institute of Technology Beijing, China [email protected]

Kaiwen Xue

Daiyin Wang

Xubin Li

Huawei Dongguan, China [email protected]

Huawei Dongguan, China [email protected]

Huawei Dongguan, China [email protected]

Abstract Approximate Nearest Neighbor Search with arbitrary filtering predicates (AFANNS) is essential for modern data applications, yet existing methods often incur substantial storage and computational costs. In this work, we introduce the Maximal Clique Index (MCI), a novel graph-based index designed for robust and efficient AFANNS. The core idea of MCI is to approximate a dense Nearest Neighbor Graph (NNG) through a compact, clique-based representation. We propose two key techniques: (1) Maximal Clique Cover (MCC), which exploits the geometric transitivity of highdimensional spaces to encode dense neighborhoods as maximal cliques, achieving an index with high compression and connectivity; and (2) Local Neighborhood Graph Geometric Densification, a strategy that constructs an index approximating a large NNG from a sparse initial NNG, recovers global connectivity by progressively increasing distance thresholds to locally densify the structure. The index is built in a lock-free parallel manner for scalability and queried via a carefully-designed multi-seed strategy to handle fragmented predicate-induced subgraphs. Extensive experiments on 10 datasets show that MCI significantly outperforms state-of-the-art methods by up to one order of magnitude in QPS at high recall while using substantially smaller space, and remains competitive even on range/keyword filtering tasks, demonstrating robust generalpurpose performance. ACM Reference Format: Xiaowei Ye, Rong-Hua Li, Guoren Wang, Kaiwen Xue, Daiyin Wang, and Xubin Li. 2026. MCI: A Maximal Clique Index for Efficient ArbitraryFiltered Approximate Nearest Neighbor Search. In . ACM, New York, NY, USA, 16 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

1

Introduction

With the proliferation of powerful vector embeddings, Approximate Nearest Neighbor Search (ANNS) has become a foundational Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference’17, Washington, DC, USA © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-x-xxxx-xxxx-x/YYYY/MM https://doi.org/10.1145/nnnnnnn.nnnnnnn

component in numerous real-world applications, including multimedia retrieval [4, 42], recommendation systems [9], and RetrievalAugmented Generation (RAG) [14]. In this landscape, Arbitrary Filtered Approximate Nearest Neighbor Search (AFANNS) is particularly crucial. For instance, in a RAG system, a user may need to retrieve a document chunk that satisfies specific metadata constraints (e.g., keywords, publication date) while simultaneously relying on vector similarity for semantic matching. State-of-the-art (SOTA) ANNS methods predominantly rely on proximity graphs such as the Relative Neighborhood Graph (RNG) [52]. A fundamental requirement for effective search in such graphs is connectivity, ensuring a traversal path exists from any starting node to the target. However, this property is inherently compromised in AFANNS due to query-specific predicates. Proximity graphs limit each node to a small, fixed number of out-neighbors (e.g., 𝑀 in HNSW [40] or NSG [17]). Under a predicate with selectivity 𝑠 (the fraction of vectors that satisfy the predicate), the expected number of valid neighbors per node reduces to 𝑀 · 𝑠. When 𝑠 is small (e.g., 𝑠 = 0.01, 𝑀 = 32), many nodes are likely to have zero valid out-neighbors, fragmenting the induced subgraph and halting traversal. Consequently, traditional proximity-graph indexes with limited neighbor lists are fundamentally ill-suited for AFANNS. To address this, the state-of-the-art ACORN algorithm [45] proposes a predicate-agnostic proximity graph index, extending the Hierarchical Navigable Small World (HNSW) structure. While standard HNSW maintains 𝑀 neighbors per node, ACORN expands this list to 𝑀 · 𝛾, with 𝛾 ≈ 1/𝑠, to statistically preserve 𝑀 valid neighbors after filtering. To mitigate the resulting memory explosion, ACORN approximates the expanded neighborhood via 2-hop connections. Despite this optimization, ACORN still suffers from significant storage overhead and suboptimal search performance in practice [5, 32, 67]. Alternative strategies like pre-filtering (filter first, search after) and post-filtering (search first, filter after) also exhibit well-known efficiency bottlenecks, especially under varying selectivity [32] (detailed in Section 2.3). The limitations of existing approaches reveal that traditional graph structures are inadequate for AFANNS. We therefore propose a fundamentally new index: the Maximal Clique Index (MCI). The core idea is to approximate a dense 𝑘-Nearest Neighbor Graph (𝑘-NNG)—where 𝑘 is large enough to ensure connectivity under filtering (e.g., 𝑘 ≈ 𝑀/𝑠)—but to do so efficiently via a much smaller 𝑘 ′ -NNG (𝑘 ′ < 𝑘). This is made possible by a key geometric insight:

Conference’17, July 2017, Washington, DC, USA

in high-dimensional spaces, neighbors of a node tend to be neighbors of each other. Formally, we prove that nodes within a local neighborhood of a sparse 𝑘 ′ -NNG are highly likely to form dense cliques (Theorem 3.4). Thus, a large 𝑘-NNG’s connectivity can be inferred from the maximal cliques within a sparse 𝑘 ′ -NNG. Based on this observation, we propose two pivotal techniques for constructing MCI from a sparse 𝑘 ′ -NNG: (1) Maximal Clique Cover (MCC), which selects a covering set of maximal cliques (via a lineartime greedy algorithm [69]) to avoid redundancy and ensure every node is covered; and (2) Geometric Densification of Neighborhood Graphs, which iteratively expands local neighborhood graphs by increasing a distance threshold, mining cliques progressively until full coverage is achieved. This prioritizes the early discovery of tight, high-quality cliques. For query processing, we design a beamsearch algorithm augmented with a carefully-designed multiple seeds selection strategy, ensuring robust traversal even when the predicate-induced subgraph is fragmented. MCI offers three key advantages over prior work. First, it eliminates the need for impractically large neighbor lists (e.g., 𝑀 · 𝛾 in ACORN), constructing instead from a modest 𝑘 ′ -NNG (e.g., 𝑘 ′ ≤ 200), which remains computationally tractable at scale. Notably, the final index discards the original 𝑘 ′ -NNG, incurring no dependency overhead. Second, it achieves a superior QPS–Recall trade-off. Our experiments show that MCI can deliver up to an order of magnitude higher QPS at high recall (e.g., recall@10 > 0.95) under mixed selectivity regimes. Third, our index is storage-efficient, with a footprint comparable to the highly compact IVFPQ algorithm and up to 10× smaller than ACORN. In summary, our main contributions are:

• A novel maximal clique index (MCI): We introduce the first clique-based index for AFANNS, which compactly approximates a dense 𝑘-NNG via a maximal clique cover mined from a sparse 𝑘 ′ -NNG, grounded in a formal geometric theorem. To the best of our knowledge, our work pioneers the use of maximal cliques for indexing in high-dimensional vector retrieval. • Efficient construction algorithm: We design an algorithm that geometrically expands local neighborhood graphs to efficiently mine a covering set of cliques, ensuring complete node coverage with near-linear practical complexity. • Robust search algorithm: We develop a search algorithm combining beam search with a multi-seed initialization, guaranteeing robust performance even over disconnected predicate subgraphs. • Comprehensive evaluation: We conduct extensive experiments on 10 benchmark datasets. Results demonstrate that MCI consistently outperforms SOTA methods (ACORN, HNSW, IVFPQ, and specialized filters) in QPS at high recall, maintains compact index size, and exhibits robustness across all selectivity regimes. • Reproducibility : Our source code is available at the anonymous repository https://anonymous.4open.science/r/MCI_ ANNS.

Rong-Hua Li et al.

2 Preliminaries 2.1 Notations and problem definition Let 𝐷 = {(𝑣𝑖 , 𝑓𝑖 )}𝑛𝑖=1 be a dataset of 𝑛 vector-feature pairs, where each vector 𝑣𝑖 ∈ R𝐷 is associated with a corresponding feature 𝑓𝑖 . Denote by 𝑉 = {𝑣𝑖 }𝑛𝑖=1 and 𝐹 = {𝑓𝑖 }𝑛𝑖=1 . A query 𝑄 = (𝑣𝑞 , 𝑓𝑞 , 𝑃𝑞 ) contains a query vector 𝑣𝑞 , a feature 𝑓𝑞 , and a predicate 𝑃𝑞 . For a data pair (𝑣𝑖 , 𝑓𝑖 ), the predicate evaluates 𝑃𝑞 (𝑓𝑖 , 𝑓𝑞 ) ∈ {True, False}. The pair (𝑣𝑖 , 𝑓𝑖 ) is valid to 𝑄 if and only if 𝑃𝑞 (𝑓𝑖 , 𝑓𝑞 ) holds. We denote the Euclidean distance between two vectors by 𝑑 (·, ·). The selectivity of a query on the dataset, denoted as 𝑠 (𝐷, 𝑄), is the fraction of elements that satisfy the predicate: Í𝑛 𝑖=1 1[𝑃𝑞 (𝑓𝑖 , 𝑓𝑞 ) = 𝑇𝑟𝑢𝑒] 𝑠 (𝐷, 𝑄) = . (1) 𝑛 Note that 0 ≤ 𝑠 (𝐷, 𝑄) ≤ 1. We use 𝑠 instead of 𝑠 (𝐷, 𝑄) when the context is clear. Let 𝐺 (𝑈 , 𝐸) be a graph where 𝑈 is the set of nodes and 𝐸 ⊆ 𝑈 ×𝑈 is the set of edges. A clique is a subgraph of 𝐺 that all pairs of nodes are connected by an edge. A maximal clique is a clique that cannot add any other node to reach a larger clique. A 𝑘-nearest neighbor graph (𝑘-NNG) is a directed graph where an edge exists from 𝑢 to 𝑣 if 𝑣 is among the 𝑘 nearest neighbors of 𝑢 [11, 59]. Here, the 𝑘-nearest neighbors of 𝑢 with respect to 𝑉 , denoted N𝑘 (𝑢), is a set N𝑘 (𝑢) ⊆ 𝑉 of size 𝑘 that satisfies: max 𝑑 (𝑢, 𝑣) ≤ 𝑣 ∈ N𝑘 (𝑢 )

min 𝑣 ′ ∈ V\N𝑘 (𝑢 )

𝑑 (𝑢, 𝑣 ′ ).

(2)

Arbitrary-Filtered Approximate Nearest Neighbor Search (AFANNS). Given a dataset 𝐷 = (𝑉 , 𝐹 ), a query 𝑄 (𝑣𝑞 , 𝑓𝑞 , 𝑃𝑞 ), and an integer 𝑘, the goal is to find the 𝑘 nearest neighbors of 𝑣𝑞 that satisfy the predicate 𝑃𝑞 (𝑓𝑖 , 𝑓𝑞 ) = 𝑇𝑟𝑢𝑒. Let 𝑅 be the set of the exact 𝑘 closest True elements to 𝑣𝑞 . The AFANNS problem aims to retrieve a set 𝑅 ′ of 𝑘 True elements to maximize recall and efficiency, where ′| Recall@𝑘 = |𝑅∩𝑅 𝑘 .

2.2

Challenges of AFANNS

The arbitrary filtering nature of AFANNS brings two basic challenges that together make it hard to design efficient indexing and query methods, as discussed below. C1: Heterogeneous feature types rule out specialized indexing. Specialized ANNS variants use specific feature properties: keyword- or tag-based filtering (𝑓𝑖 is a set of labels, attributes, or tags) relies on discrete set membership [5, 22, 38, 58], while rangebased filtering (𝑓𝑖 is a numeric scalar) uses the order of numerical attributes [13, 29, 35, 47, 67, 72, 75]. In addition, some recent rangefiltering indexes also support dynamic feature updates, such as DSG, DIGRA, and RangePQ+ [29, 47, 72]. In contrast, AFANNS must handle a mix of data types (e.g., integers, floats, strings, and timestamps), which may also change over time. No single indexing paradigm can take advantage of the different properties of such diverse types at the same time, since the discrete or order-based assumptions behind specialized indexes do not always hold. As a result, general-purpose indexes often index only the vectors 𝑉 , and treat the feature space 𝐹 as a generic metadata store. C2: Ad-hoc predicates break distribution assumptions. Several existing ANNS methods design indexing strategies under the

MCI: A Maximal Clique Index for Efficient Arbitrary-Filtered Approximate Nearest Neighbor Search

assumption that future queries follow past distributions of both features and their predicates [25, 34, 55, 61]. This assumption does not hold for AFANNS, where predicates are ad-hoc and unknown at index construction time. In particular, even for the same query vector, different predicates can produce very different valid subsets. This unpredictability breaks the assumption of stable query patterns, and makes distribution-based optimizations ineffective for arbitrary filtering workloads.

2.3

Existing methods and their defects

Existing methods related to AFANNS can be broadly grouped into four categories: pre-filtering, post-filtering, predicate-subgraph traversal (represented by ACORN [45]), and specialized filtering methods tailored to specific predicate families. In the following discussion, the time complexity for the first three categories is measured by the number of distance computation operations during search. Pre-filtering. This strategy first identifies all elements that satisfy the predicate 𝑃𝑞 , then performs similarity search (often via bruteforce scanning or simple structures like IVF) over this filtered set. It guarantees high recall and is effective for queries with very low selectivity (small filtered sets). However, its time complexity is 𝑂 (𝑠𝑛), where 𝑠 is the selectivity of 𝑃𝑞 , making it non-scalable for moderate or large selectivity on large datasets. Post-filtering. This approach performs an unfiltered ANNS to retrieve 𝑂 (𝑘/𝑠) candidates, then filters out those that do not satisfy 𝑃𝑞 . Its time complexity is 𝑂 (log 𝑛 + 𝑘/𝑠), making it efficient for highly selective queries (large 𝑠). However, when selectivity is low (i.e., 𝑠 is small), the number of candidates 𝑂 (𝑘/𝑠) may become impractically large, leading to poor efficiency. Predicate-subgraph traversal (ACORN). ACORN [45] extends the HNSW [40] index to support predicate filtering by enlarging the neighbor candidate pool during graph construction. Specifically, it scales the construction parameter 𝑒 𝑓𝑐 to 𝑀 · 𝛾 (where 𝛾 > 1 is a scaling factor) to ensure sufficient valid neighbors exist for traversal under arbitrary predicates. To control memory overhead, it stores only the first 𝑀𝛽 candidates explicitly and approximates the remainder via 2-hop neighbors. ACORN achieves time complexity of 𝑂 ((𝑀 · 𝛾 · 𝑠 + 𝛾) · log(𝑠𝑛) + log( 𝑠1 )) and requires 𝑂 (𝑛(𝑀𝛽 + 𝑀 + 𝑀𝛾 ln 𝑀 )) index storage. While more scalable than pure pre- or postfiltering, ACORN still incurs significant storage costs and may suffer from suboptimal recall in complex selectivity scenarios, limiting its applicability in high-performance arbitrary-filtering ANNS [67]. Specific filtering methods. Several methods are designed for specific predicate types, such as keyword-based filtering [5, 22, 38, 58], range-based filtering [13, 29, 35, 47, 67, 72, 75], and categorical/numerical attribute filtering [66]. While they can achieve superior performance within their specialized domains, their underlying assumptions about feature types and predicate logic render them inapplicable to the general AFANNS setting, which must accommodate heterogeneous features and ad-hoc predicates. Table 1 summarizes the key characteristics of these methods.

3

A novel Maximal Clique Index

To overcome the limitations of existing methods, we propose the Maximal Clique Index (MCI), a novel index designed for efficient

Conference’17, July 2017, Washington, DC, USA

Table 1: Characteristics of representative filtered ANNS methods. “Upd.” indicates whether the feature values attached to indexed vectors can be updated after index construction without rebuilding. Method

𝐹 type

𝑓𝑞

𝑃𝑞 (𝑓𝑖 , 𝑓𝑞 )

interval [𝑙, 𝑟 ] interval [𝑙, 𝑟 ] interval [𝑙, 𝑟 ] interval [𝑙, 𝑟 ] interval [𝑙, 𝑟 ] interval [𝑙, 𝑟 ] interval [𝑙, 𝑟 ]

𝑓𝑖 ∈ [𝑙, 𝑟 ] 𝑓𝑖 ∈ [𝑙, 𝑟 ] 𝑓𝑖 ∈ [𝑙, 𝑟 ] 𝑓𝑖 ∈ [𝑙, 𝑟 ] 𝑓𝑖 ∈ [𝑙, 𝑟 ] 𝑓𝑖 ∈ [𝑙, 𝑟 ] 𝑓𝑖 ∈ [𝑙, 𝑟 ]

Upd.

Range-filtering methods SeRF [75] iRangeGraph [67] DSG [47] UNIFY [35] Engels et al. [13] DIGRA [29] RangePQ+ [72]

scalar (float) scalar (float) scalar (float) scalar (float) scalar (float) scalar (float) scalar (float)

✗ ✗ ✓ ✗ ✗ ✓ ✓

Keyword/label-filtering methods Filtered-DiskANN [22] NHQ [58]

label set label set

✗ ✗

label(s) label(s)

UNG [5]

label set

✗

label(s)

TFANNS [38]

label set

✗

label(s)

𝑓𝑞 ⊆ 𝑓𝑖 𝑓𝑞 = 𝑓𝑖 𝑓𝑞 ∈ 𝑓𝑖 , 𝑓𝑖 ∈ 𝑓𝑞 , 𝑓𝑖 = 𝑓𝑞 , 𝑓𝑖 ∩ 𝑓𝑞 ≠ ∅ 𝑓𝑞 ∈ 𝑓𝑖

Range plus label-filtering methods scalar (float) or label set

Xie et al. [66]

✗

[𝑙, 𝑟 ] or label(s)

𝑓𝑖 ∈ [𝑙, 𝑟 ] or 𝑓𝑖 ∈ 𝑓𝑞

Arbitrary-filtering methods Pre-/Post-filtering ACORN [45] MCI (ours)

1

0

3

2

5

4

arbitrary arbitrary arbitrary

✓ ✓ ✓

arbitrary arbitrary arbitrary

arbitrary arbitrary arbitrary

kNN

Acorn Index Clique Index

0: [1, 2, 3] 1: [0, 2, 3] 2: [0, 3, 1] 3: [2, 1, 0] 4: [2, 3, 5] 5: [2, 3, 4]

0: [1, 2] 1: [0, 2] 2: [0, 3] 3: [2, 1] 4: [2, 5] 5: [2, 4]

(a) A kNN Graph

[0, 1, 2, 3] [2, 3, 4, 5]

(b) Three different indexes

Figure 1: Illustration of 𝑘-NNG, ACORN index with two-hop pruning (𝑀𝛽 = 1), and our maximal clique index. and robust AFANNS. Below, we first present the key design principles of MCI, then detail its construction algorithm and analyze its complexity.

3.1

Key ideas of MCI

Traditional proximity graphs optimize for unfiltered search by controlling node degree and neighbor distribution. A common technique is Relative Neighborhood Graph (RNG) pruning [52], widely used in indexes like HNSW [40] and NSG [17]. For a node 𝑢 and candidate neighbor 𝑣, the edge (𝑢, 𝑣) is retained only if no other node 𝑤 satisfies both 𝑑 (𝑢, 𝑤) ≤ 𝑑 (𝑢, 𝑣) and 𝑑 (𝑤, 𝑣) ≤ 𝑑 (𝑢, 𝑣). This ensures sparse, well-distributed edges, accelerating traversal in standard settings [59]. However, in AFANNS, query-specific predicates can invalidate neighbors selected by RNG, fragmenting the induced subgraph over valid nodes and halting search prematurely [45]. To maintain connectivity under arbitrary filters, a fundamental approach is to increase the average degree of nodes in the proximity graph. With a sufficiently large average degree, the index can preserve reachability within the filtered subset with high probability, even when many edges are invalidated by ad-hoc predicates.

Conference’17, July 2017, Washington, DC, USA

Unfortunately, naively increasing the degree by explicitly storing more neighbors incurs prohibitive storage overhead and index construction time. A key challenge, therefore, is to effectively amplify the graph’s connectivity without explicitly storing a dense adjacency structure. To this end, we propose a novel solution based on maximal cliques. Our method, the Maximal Clique Index (MCI), achieves high effective connectivity through a compact, clique-based representation, which we detail in the following. Maximal Clique Cover (MCC). Our approach exploits a fundamental property of high-dimensional vector spaces: spatial proximity exhibits strong transitivity, meaning that neighbors of neighbors are highly likely to be neighbors themselves [11]. Formally, if 𝑑 (𝑎, 𝑏) and 𝑑 (𝑏, 𝑐) are small, then 𝑑 (𝑎, 𝑐) is also likely small. Consequently, mutually proximate nodes in a 𝑘-NNG tend to form cliques. Cliques offer inherent compression benefits. In a standard adjacencylist representation, a clique of size 𝑐 requires storing 𝑐 (𝑐 −1)/2 edges. By representing the clique implicitly via its 𝑐 member nodes, we achieve a space reduction from 𝑂 (𝑐 2 ) to 𝑂 (𝑐), corresponding to a compression factor of (𝑐 − 1)/2. This property enables a dense graph index to be compactly represented as a collection of cliques. However, mining all maximal cliques is inefficient because their number can be exponential (up to 𝑂 (3𝑛/3 )) and they often overlap heavily [51]. Storing every maximal clique would lead to significant redundancy. Therefore, we focus on a subset that captures the essential connectivity: the Maximal Clique Cover. Definition 3.1 (Maximal Clique Cover (MCC)). A set of maximal cliques is a Maximal Clique Cover if every node in the graph is contained in at least one maximal clique in the set. A MCC compactly represents all maximal cliques, providing full node coverage without redundancy. However, small maximal cliques (e.g., of size 3) often carry limited structural information and may introduce noise into the graph index by linking weakly associated nodes. To prioritize meaningful connectivity, we introduce a size threshold 𝜏 and define a refined structure: Definition 3.2 (𝜏-Maximal Clique Cover (𝜏-MCC)). Let 𝜏 be a positive integer. A MCC is a 𝜏-MCC if every maximal clique in the set has a size |𝐶 | ≥ 𝜏. Note that Definition 3.2 guarantees each node participates in at least one clique of size at least 𝜏, implying a lower bound of (𝜏 − 1) on its degree within that clique. In practice, a node often belongs to multiple cliques, which collectively yield a high effective degree in the compressed index. By filtering out small cliques, the 𝜏-MCC retains only cohesive, information-rich subgraphs, thereby enhancing both search precision and traversal efficiency. Our MCI is formally a 𝜏-MCC, and the neighborhood of a node 𝑢 is defined as the union of the node sets of all maximal cliques containing 𝑢. The following example illustrates the concept. Example 3.3. Consider a 𝑘-NNG with 𝑛 = 6 and 𝑘 = 3, as shown in Figure 1(a). Storing this graph via an adjacency list requires 18 integers (Figure 1(b), left). For comparison, methods like ACORN approximate two-hop neighborhoods; e.g., node 0’s effective neighbors include {1, 2} plus the neighbors of 1 and 2. In contrast, our MCI encodes the graph using only two maximal cliques: 𝐶 1 = {0, 1, 2, 4}

Rong-Hua Li et al.

and 𝐶 2 = {2, 3, 4, 5}. This representation requires only 8 integers (Figure 1(b), right) to capture all adjacency relationships, while achieving a high average effective degree. For instance, node 3 belongs to both 𝐶 1 and 𝐶 2 , resulting in a high effective degree of 5. While a 𝜏-MCC can be computed efficiently (e.g., via a lineartime greedy algorithm that iteratively extracts and removes a maximal clique until all nodes are covered [69]), a fundamental challenge remains: to guarantee coverage by cliques of size at least 𝜏, the underlying 𝑘-NNG must be sufficiently dense. Constructing such a dense 𝑘-NNG directly is prohibitively expensive. In the following, we address this by showing how to obtain a high-quality 𝜏-MCC from a much sparser 𝑘 ′ -NNG (with 𝑘 ′ ≪ 𝑘). Geometric densification of neighborhood graphs. We construct a 𝜏-MCC from a sparse 𝑘 ′ -NNG (with 𝑘 ′ ≪ 𝑘) by using a geometric densification technique. For each node 𝑢, let 𝑉 ′ = N𝑘 ′ (𝑢) ∪ {𝑢} be its local neighborhood. To obtain cliques of size at least 𝜏 within 𝑉 ′ , we employ a geometric densification strategy: we progressively lower the distance threshold for forming edges, thereby gradually adding connections to 𝐺 (𝑉 ′ ). Formally, let 𝑥 be the top-1 nearest neighbor of 𝑢. For a parameter 𝛼 > 1, we define a distance threshold 𝑡 = 𝛼 ·𝑑 (𝑢, 𝑥) and construct an edge set 𝐸𝛼 = {(𝑣𝑖 , 𝑣 𝑗 ) | 𝑣𝑖 , 𝑣 𝑗 ∈ 𝑉 ′, 𝑑 (𝑣𝑖 , 𝑣 𝑗 ) ≤ 𝑡 }. Maximal cliques are then greedily mined from the induced subgraph 𝐺 (𝑉 ′, 𝐸𝛼 ). A single fixed 𝛼, however, may not yield a subgraph in which every node belongs to a clique of size ≥ 𝜏 (i.e., a valid 𝜏-MCC for 𝑉 ′ ). To maximize coverage, we iteratively increase 𝛼: starting from an initial value (e.g., 𝛼 0 = 1.2), we double 𝛼 in each round, greedily mine cliques from the corresponding denser subgraph 𝐺 (𝑉 ′, 𝐸𝛼 ), and continue until every node in 𝑉 ′ is covered by at least one maximal clique of size ≥ 𝜏. This process is repeated for all nodes 𝑢 in the vector dataset to build the global MCI. Below, we provide a formal analysis of the underlying rationale for this geometric densification strategy. A key property of high-dimensional data is the Distance Concentration Phenomenon: pairwise distances tend to concentrate around their mean with relatively small variance [56]. For analytical clarity, we model this phenomenon using a Gaussian distribution N (𝜇, 𝜎 2 ) with mean 𝜇 and variance 𝜎 2 . Theorem 3.4 leverages this model to establish a strong local transitivity property under high distance concentration. Theorem 3.4 (Local Connectivity under Distance Concentration). Let 𝑉 = {𝑥 1, . . . , 𝑥𝑛 } ⊂ R𝑑 be a vector dataset √ whose 𝜇 pairwise distances are distributed as N (𝜇, 𝜎 2 ), with 𝜎 > 2 ln 𝑛. For a node 𝑢 ∈ 𝑉 , denote its nearest neighbor by 𝑥. If 𝑣, 𝑤 ∈ N𝑘 (𝑢) satisfy 𝑑 (𝑣, 𝑤) ≤ 𝛼 𝑑 (𝑢, 𝑥) for a small constant 𝛼, then, with probability approaching 1 as 𝑛 → ∞, 𝑣 is also a 𝑘-nearest neighbor of 𝑤. Proof. Let 𝑦 ∈ 𝑉 \ {𝑣, 𝑤 } be an arbitrary node. For a value 𝛿 −𝜇 𝛿 < 𝜇, let 𝛿 ′ = 𝜎 . The probability that 𝑑 (𝑦, 𝑤) ≤ 𝛿 is given by the cumulative distribution function (CDF) of the standard Gaussian distribution: 𝑝 (𝛿) = P(𝑑 (𝑦, 𝑤) ≤ 𝛿) = Φ(𝛿 ′ ). First, we bound the distance to the nearest neighbor 𝑑 (𝑢, 𝑥). The probability that the nearest neighbor distance exceeds 𝜇 − 𝑡 (for some 𝑡 > 0) corresponds to the event where all 𝑛 − 1 other nodes

MCI: A Maximal Clique Index for Efficient Arbitrary-Filtered Approximate Nearest Neighbor Search

Conference’17, July 2017, Washington, DC, USA

αmaxd(u, x)

are at a distance greater than 𝜇 − 𝑡 from 𝑢:  𝑡  𝑛−1 P(𝑑 (𝑢, 𝑥) ≥ 𝜇 − 𝑡) = (1 − 𝑝 (𝜇 − 𝑡))𝑛−1 = 1 − Φ − . 𝜎 Consequently, the probability that 𝑑 (𝑢, 𝑥) < 𝜇 − 𝑡 is:   𝑡  𝑛−1 P(𝑑 (𝑢, 𝑥) < 𝜇 − 𝑡) = 1 − 1 − Φ − . 𝜎 We select 𝑡 such that the term Φ(−𝑡/𝜎) is sufficiently large to make the expression approach 1: √ 𝛼 (𝜇 − 𝑡) = 𝜇 − 𝜎 2 ln 𝑛. √ √ 𝜇 𝜇−𝜎 2 ln 𝑛 Solving for 𝑡, we get 𝑡 = 𝜇 − . Note that since 𝜎 > 2 ln 𝑛, 𝛼 we have 𝜇 − 𝑡 > 0. Consider the bound for 𝑑 (𝑢, 𝑥). As 𝑛 grows large, the minimum of 𝑛 Gaussian variables concentrates near the lower tail. Specifically, for our chosen 𝑡, the probability that 𝑑 (𝑢, 𝑥) ≤ 𝜇 − 𝑡 approaches 1. Given the condition 𝑑 (𝑣, 𝑤) ≤ 𝛼𝑑 (𝑢, 𝑥), with high probability we have: √ 𝑑 (𝑣, 𝑤) ≤ 𝛼 (𝜇 − 𝑡) = 𝜇 − 𝜎 2 ln 𝑛. Now, let 𝑝 ′ be the probability that a random node 𝑦 is closer to 𝑤 than 𝑣 is (i.e., 𝑑 (𝑦, 𝑤) ≤ 𝑑 (𝑣, 𝑤)). Using the bound derived above:   √ 𝑝 ′ = P(𝑑 (𝑦, 𝑤) ≤ 𝑑 (𝑣, 𝑤)) ≤ P 𝑑 (𝑦, 𝑤) ≤ 𝜇 − 𝜎 2 ln 𝑛 . √ This is equivalent to evaluating the CDF at 𝑧 = − 2 ln 𝑛:  √  𝑝 ′ ≤ Φ − 2 ln 𝑛 . 

Using Mill’s Inequality [54], which states that Φ(𝑧) ≤ √1 𝑒 −𝑧 /2 |𝑧 | 2𝜋 for 𝑧 < 0, we have: 1 1 − 2 ln 𝑛 𝑝′ ≤ √ . √ 𝑒 2 = √ 2𝑛 𝜋 ln 𝑛 2 ln 𝑛 2𝜋 Finally, let 𝑁𝑐𝑙𝑜𝑠𝑒𝑟 be the number of nodes in 𝑉 \ {𝑣, 𝑤 } that are closer to 𝑤 than 𝑣 is. The expectation is E[𝑁𝑐𝑙𝑜𝑠𝑒𝑟 ] = (𝑛 − 2)𝑝 ′ . As 𝑛 → ∞: 1 1 (𝑛 − 2)𝑝 ′ ≈ 𝑛 · √ = √ → 0. 2𝑛 𝜋 ln 𝑛 2 𝜋 ln 𝑛 Since the expected number of nodes closer to 𝑤 than 𝑣 approaches 0, the probability that 𝑣 is among the top-𝑘 neighbors (i.e., 𝑁𝑐𝑙𝑜𝑠𝑒𝑟 ≤ 𝑘 − 1) approaches 1:

(a) Isolated nodes

(b) Super center nodes

Figure 2: Illustration of handling two special cases. not only by cliques mined from its own local neighborhood 𝑉𝑢′ = N𝑘 ′ (𝑢) ∪ {𝑢}, but also by cliques mined from the neighborhoods 𝑉𝑣′ of other nodes 𝑣 for which 𝑢 ∈ N𝑘 ′ (𝑣). This cooperative coverage enables the MCI to capture rich global connectivity from only local 𝑘 ′ -NN subgraphs. Remark (doubling 𝛼). Doubling 𝛼 at each step is designed to manage the size of the densified subgraph efficiently. In a growthrestricted metric space, the number of points within a ball of radius 2𝑡 is at most a constant factor 𝑐 times the number within radius 𝑡, i.e., |𝐵(𝑢, 2𝑡)| ≤ 𝑐 · |𝐵(𝑢, 𝑡)| [11]. By doubling the distance threshold 𝛼 · 𝑑 (𝑢, 𝑥) in each iteration, we ensure that the edge set 𝐸𝛼 —and hence the graph we mine for cliques—grows in a controlled manner, thereby preserving the efficiency of each clique-mining iteration.

2

P(𝑣 ∈ N𝑘 (𝑤)) = P(𝑁𝑐𝑙𝑜𝑠𝑒𝑟 ≤ 𝑘 − 1)  𝑖=𝑘 −1  ∑︁ 𝑛 − 2 ′𝑖 = 𝑝 (1 − 𝑝 ′ )𝑛−2−𝑖 → 1. 𝑖 𝑖=0 This completes the proof.

□

Theorem 3.4 implies that in high-dimensional spaces, the 𝑘nearest neighbors of a node are highly likely to be mutually proximate. Consequently, these neighbors tend to form cliques within the local neighborhood. This theoretical insight directly supports our geometric densification strategy: by progressively increasing the distance threshold (increasing 𝛼), we systematically induce such cliques, enabling the efficient mining of the 𝜏-MCC from a initially sparse neighborhood graph. More importantly, our local 𝜏-MCC mining strategy produces an index whose average out-degree far exceeds the initial parameter 𝑘 ′ . This is due to a dual coverage mechanism: a node 𝑢 is covered

3.2

The MCI construction algorithm

Based on the key ideas presented previously, we now describe the MCI construction algorithm, outlined in Algorithm 1. The algorithm takes four parameters: the vector dataset 𝑉 , the neighbor count 𝑘 ′ for building an initial 𝑘 ′ -NNG (used only during construction and then discarded), the minimum clique size 𝜏, and the maximum expansion factor 𝛼 max . Its output is a 𝜏-MCC, which constitutes the final MCI index. A key feature of the algorithm is that it relies solely on the vectors 𝑉 for index construction, making it independent of the feature sets 𝐹 and thus fully adaptable to arbitrary filtering queries. The algorithm begins by building an initial 𝑘 ′ -NNG for all vectors using the NN-Descent algorithm [11] (Line 1). It initializes an empty set 𝐼 for covered nodes and an empty set M for the index (Line 2). As described in Section 3.1, the algorithm employs a geometric expansion strategy controlled by a factor 𝛼 (Line 3). The main loop continues while uncovered nodes remain (Line 4). In each iteration, the algorithm processes every uncovered node 𝑣𝑖 (Line 5), invoking the mineCliques(𝑖, 𝛼, 𝐼 ) procedure to greedily mine maximal cliques in its local neighborhood (Line 6). The resulting cliques M ′ are added to the index M, and the covered-node set 𝐼 is updated accordingly (Line 7). After processing all nodes in the current round, 𝛼 is doubled (Line 8), expanding the connection radius for the next iteration and increasing the chance of covering remaining nodes. The mineCliques(𝑖, 𝛼, 𝐼 ) procedure (Lines 10–19) implements the local mining step, grounded in Theorem 3.4. It first retrieves the 𝑘 ′ nearest neighbors of 𝑣𝑖 and includes 𝑣𝑖 itself to form the local node set 𝑉 ′ (Line 11). Let 𝑑 min be the distance from 𝑣𝑖 to its nearest

Conference’17, July 2017, Washington, DC, USA

Rong-Hua Li et al. 1

0

7

0

41.4 36.3 48.7 26.9 50.3 41.9 45.2 27.4

1 41.4

2

45.0 30.6 50.7 31.7 31.9 37.0

3 48.7 53.7 45.0

50.6 27.0 41.2 25.6

5 50.3 54.1 50.7 34.5 50.6

6

2

4

1 2

1 6

2

4

7

7

(b) Local graph of node (c) Local graph of node (d) Local graph of node 0 with 𝛼 = 1.2 1 with 𝛼 = 1.2 2 with 𝛼 = 1.2

46.2 68.3 73.2

6 41.9 19.8 31.7 49.4 27.0 46.2

0

51.5 40.6

7 45.2 33.3 31.9 50.0 41.2 68.3 51.5

29.7

0

6 6 5 2 5

8 27.4 36.8 37.0 66.1 25.6 73.2 40.6 29.7 0 1 2 3 4 5 6 7 8

(a) The distance matrix of example vectors; the 𝑘 ′ -NNs in each row are red.

0

6 5

8 4

4

50.4 34.5 49.4 50.0 66.1

4 26.9 21.2 30.6 50.4

0

3

6

33.7 53.7 21.2 54.1 19.8 33.3 36.8

2 36.3 33.7

5

1

8

4 2

3

3

3

(e) Local graph of node (f) Local graph of node (g) Local graph of node 3 with 𝛼 = 1.2 5 with 𝛼 = 1.2 3 with 𝛼 = 2.4

(h) The final MCI

0: [ 4 8 2 1 6 7 3 5 ] 1: [ 6 4 7 2 8 0 3 5 ] 2: [ 4 6 7 1 0 8 3 5 ] 3: [ 5 2 0 6 7 4 1 8 ] 4: [ 1 8 0 6 2 7 3 5 ] 5: [ 3 6 0 4 2 1 7 8 ] 6: [ 1 4 2 8 0 5 3 7 ] 7: [ 8 2 1 4 0 3 6 5 ] 8: [ 4 0 7 1 2 6 3 5 ] (i) NN (all numbers) / approximated NN by MCI (red numbers)

Figure 3: Illustration of the MCI construction algorithm with 𝑛 = 9, 𝑘 ′ = 4, 𝜏 = 3 Algorithm 1: The MCI Construction Algorithm Input: The set of vectors 𝑉 = {𝑣1 , 𝑣2 , ..., 𝑣𝑛 }, three integers 𝑘 ′ , 𝜏, 𝛼𝑚𝑎𝑥 Output: The maximal clique index M ′ ′ 1 Construct a 𝑘 -NNG with a small 𝑘 by invoking NN-Descent [11]; 2 𝐼 ← ∅; M ← { }; 3 Initialize 𝛼 ← 1.2; 4 while |𝐼 | < 𝑛 do 5 for 𝑖 ∈ [1, 𝑛] s.t. 𝑣𝑖 ∉ 𝐼 do 6 M ′ , 𝐼 ′ ← mineCliques(𝑖, 𝛼, 𝐼 ); 7 M ← M 𝑗 ∪ M′; 𝐼 ← 𝐼 ′; 8

𝛼 ← 𝛼 × 2;

return M; 10 Procedure mineCliques(𝑖, 𝛼, 𝐼 ) 11 𝑉 ′ ← N𝑘 ′ (𝑣𝑖 ) ∪ {𝑣𝑖 } ; 12 𝑔 ← a graph where each edge represents a pair of vectors (𝑣𝑎 ∈ 𝑉 ′ , 𝑣𝑏 ∈ 𝑉 ′ ) such that 𝑑 (𝑣𝑎 , 𝑣𝑏 ) ≤ 𝛼 min𝑣 ∈𝑉 ′ 𝑑 (𝑣, 𝑣𝑖 ); 13 M ′ ← ∅; 14 for 𝑣 𝑗 ∈ 𝑉 ′ s.t. 𝑣 𝑗 ∉ 𝐼 do 15 Find a maximal clique 𝐶 in 𝑔 with 𝑣 𝑗 ∈ 𝐶 using the linear-time greedy algorithm [69]; 16 if |𝐶 | ≥ 𝜏 then 17 M ′ ← M ′ ∪ {𝐶 }; 𝐼 ← 𝐼 ∪ 𝐶; 9

19

if M ′ = ∅ and 𝛼 ≥ 𝛼𝑚𝑎𝑥 then M ′ ← M ′ ∪ {𝑉 ′ }; 𝐼 ← 𝐼 ∪ 𝑉 ′ ;

20

return M ′ , 𝐼 ;

18

neighbor. A local graph 𝑔 is then induced on 𝑉 ′ , where an edge exists between 𝑣 𝑎 and 𝑣𝑏 iff 𝑑 (𝑣 𝑎 , 𝑣𝑏 ) ≤ 𝛼 · 𝑑 min (Line 12). Maximal cliques are mined from 𝑔 to cover the currently uncovered nodes in 𝑉 ′ (Lines 13–17). For each uncovered node 𝑣 𝑗 ∈ 𝑉 ′ (Line 14), the procedure attempts to find a maximal clique 𝐶 in 𝑔 that contains 𝑣 𝑗 and satisfies |𝐶 | ≥ 𝜏 (Lines 15–16). If such a clique is found, it is added to M ′ and the nodes in 𝐶 are marked as covered in 𝐼 (Line 17). The clique mining itself is efficient; we employ a linear-time greedy algorithm [69] to extract a maximal clique for each candidate node.

Finally, if after processing 𝑉 ′ no cliques have been mined and 𝛼 has reached 𝛼 max (Line 18), we add the entire set 𝑉 ′ as a single pseudo-clique to M ′ (Line 19). This case handles isolated nodes that remain uncovered even at the maximum radius. By treating 𝑉 ′ as a bridge, we ensure that nodes in sparse regions are still included in the index, preserving overall connectivity. Example 3.5 (Handling Isolated Nodes). Figure 2(a) illustrates a scenario where a small central cluster is isolated from larger surrounding clusters. The outer circle represents the search boundary at 𝛼 = 𝛼𝑚𝑎𝑥 . The nodes captured within this boundary (the set 𝑉 ′ in Line 11 of Algorithm 1) are distributed across four distinct clusters. Crucially, the node count within any individual cluster is below the threshold 𝜏, and the pairwise distances between nodes in different clusters exceed the edge creation threshold (i.e., ≥ 𝛼𝑚𝑎𝑥 𝑑 (𝑢, 𝑥)). Consequently, the local graph contains no valid maximal cliques. To preserve global connectivity, the early-termination mechanism (Line 18) treats the entire set 𝑉 ′ as a single pseudo-clique, effectively bridging these isolated nodes. Conversely, we encounter “super-center” nodes (or hubs) that belong to an excessively large number of maximal cliques. Such a hub acts as a high-degree connector, linking all nodes across the many cliques it participates in, as detailed in Example 3.6. To mitigate the resulting query-time overhead, we implement a simple pruning rule: if a node is already covered by more than 𝑛/100 cliques, it is excluded from the local candidate set 𝑉 ′ (Line 11). This cap limits the maximum connectivity influence of any single node without harming overall index quality. Example 3.6 (Super-Center Nodes). Figure 2(b) depicts super-center nodes that connect to four distinct clusters (shown as four cycles). Without pruning, these hubs would bridge every node across all four clusters. Consequently, any search traversal passing through a super-center would require distance computations against the entire union of the connected clusters, incurring prohibitive computational cost. Lock-free parallel implementation. Algorithm 1 can be easily designed for efficient lock-free parallel execution. Each thread maintains a private, independent set to store the maximal cliques it discovers (Lines 2, 7). This thread-local storage eliminates write conflicts during parallel processing; the cliques from all threads are

MCI: A Maximal Clique Index for Efficient Arbitrary-Filtered Approximate Nearest Neighbor Search

merged into a unified index only at the final stage (Line 9). The coverage mask 𝐼 (implemented as a bit-array of length 𝑛) is updated via atomic operations rather than locks (Lines 7, 17, 19), which enhances scalability by avoiding lock contention. Our experimental evaluation confirms the high parallel efficiency of this design. Robustness to construction parameters. Regardless of the specific values assigned to 𝑘 ′ and 𝜏, the algorithm guarantees the generation of a valid MCC, thereby ensuring consistent structural integrity. Consequently, the search performance remains relatively stable across different parameter settings. While 𝑘 ′ and 𝜏 naturally govern the trade-off between construction overhead and index quality, MCI exhibits significant robustness to their variations. Experimental results in Section 5 confirm that although larger values of 𝑘 ′ and 𝜏 correlate with marginal gains in precision, the overall system performance is generally insensitive to fine-grained parameter tuning. To facilitate the understanding of Algorithm 1, we provide an illustrative example using a toy dataset below. Example 3.7. Figure 3 illustrates the MCI construction process on a randomly generated dataset with 𝑛 = 9, using parameters 𝑘 ′ = 4 and 𝜏 = 3. The pairwise distance matrix is presented in Figure 3(a), where cells highlighted in red indicate the 𝑘 ′ -nearest neighbors for each node. Figures 3(b)–3(e) depict the local graphs and mined cliques during the first iteration (𝛼 = 1.2). In each subfigure, the depicted nodes correspond to the local candidate set 𝑉 ′ (Line 11 of Algorithm 1), with edges established based on the distance threshold defined in Line 12. Nodes highlighted in red indicate that they have been successfully covered by maximal cliques. For instance, the identification of the clique {0, 4, 8} in Figure 3(b) results in these nodes being marked as covered (red nodes) in subsequent steps. Maximal cliques are distinguished by fill colors; for example, Figure 3(d) identifies two overlapping maximal cliques: {1, 2, 7} and {1, 2, 4, 6}. The final constructed MCI is visualized in Figure 3(h). Figure 3(i) details the connectivity: the full neighbor lists are ordered by distance for each node, with the red numbers denoting the neighbors approximated by the MCI. Storing this connectivity explicitly as an adjacency list would require 40 integers; in contrast, our MCI representation requires only 15 integers. This yields an effective average out-degree of 40/9 ≈ 4.44, which is larger than the construction parameter 𝑘 ′ = 4. This degree amplification is attributable to the dual coverage mechanism discussed in Section 3.1. On larger datasets with higher 𝑘 ′ and 𝜏, the effective degree typically surpasses 𝑘 ′ by a considerably wider margin.

(Lines 4–9) runs for 𝑟 iterations. In each iteration, for every uncovered node 𝑣𝑖 , we construct a local induced subgraph on its 𝑂 (𝑘 ′ ) neighbors (Line 12), which requires 𝑂 ((𝑘 ′ ) 2 ) distance computations. In the worst case, all 𝑛 nodes remain uncovered in every iteration, giving a per-round cost of 𝑂 (𝑛 · (𝑘 ′ ) 2 · 𝐷). Since the expansion factor 𝛼 doubles each round and is capped by 𝛼 max , the number of rounds 𝑟 is 𝑂 (log2 𝛼 max ). In practice, 𝑟 is also limited by the local distance ratio Δ, yielding the combined bound 𝑂 (min(log2 𝛼 max, log Δ)). Summing the two phases gives the total complexity 𝑂 (𝑇 + 𝑟 · 𝑛 · (𝑘 ′ ) 2 · 𝐷). □ Empirical performance. In practice, the first one or two rounds dominate the total runtime. This occurs because dense local structures are quickly identified with small 𝛼, covering the majority of nodes. Subsequent rounds handle only a few remaining isolated nodes, making the observed construction time significantly lower than the worst-case bound. Space complexity. The construction algorithm requires 𝑂 (𝑛𝑘 ′ ) space to store the initial 𝑘 ′ -NNG, which is used only during index building and discarded afterward. The size of the final MCI index is bounded as follows: Theorem 3.9. The worst-case size of the MCI index is 𝑂 (𝑛𝑘 ′ ). Proof. Each maximal clique added to the index covers at least one previously uncovered node, so the total number of cliques is at most 𝑛. Every clique is mined from a local neighborhood of size 𝑂 (𝑘 ′ ), hence its size is also bounded by 𝑂 (𝑘 ′ ). Therefore, the total index size is at most 𝑛 · 𝑂 (𝑘 ′ ) = 𝑂 (𝑛𝑘 ′ ). □ The worst-case bound of 𝑂 (𝑛𝑘 ′ ) arises in the extreme scenario where there are 𝑛 maximal cliques, each of size 𝑘 ′ . However, such a extreme case is rarely encountered in practice. Typically, the number of maximal cliques is far fewer than 𝑛, and their sizes are well below 𝑘 ′ . Our experiments demonstrate that the actual index size is significantly superior to the worst-case theoretical bound (see Exp-2 in Section 5).

4

Complexity analysis

This subsection analyzes the complexity of index construction. Theorem 3.8. The worst-case time complexity of Algorithm 1 is 𝑂 (𝑇 +𝑟 ·𝑛 · (𝑘 ′ ) 2 ·𝐷), where 𝑂 (𝑇 ) is the time to construct the initial 𝑘 ′ NN graph, 𝑟 denotes the number of iterations in the main loop (line 4), 𝑛 is the dataset size, and 𝐷 is the vector dimension. The number of rounds 𝑟 is bounded by 𝑂 (min(log2 𝛼𝑚𝑎𝑥 , log(Δ))), where Δ is the ratio of the maximum to minimum pairwise distance within the local neighborhoods. Proof. The algorithm consists of two phases. First, building the initial 𝑘 ′ -NNG costs 𝑂 (𝑇 ) (Line 1); for NN-Descent [11], 𝑇 is near 𝑂 (𝑛 1.14 ) in practice. Second, the geometric expansion loop

Query processing with MCI

This section describes query processing with MCI for AFANNS. We first introduce a seed-node selection strategy, then present the query processing algorithm and analyze its complexity.

4.1 3.3

Conference’17, July 2017, Washington, DC, USA

Seed nodes selection strategy

Proximity-graph-based search typically starts from a fixed entry node, assuming the graph is well-connected. This assumption fails in AFANNS because arbitrary predicates can invalidate many edges, fragmenting the induced subgraph into disconnected components. A single entry point may trap the search in one component, missing valid candidates in others. To overcome this, we employ a multi-seed initialization. We √ sample 𝜖 𝑛 nodes uniformly at random as candidate seeds. From these, we keep the 𝑙𝑠 closest to the query vector as the actual starting points. This strategy increases the chance of hitting different connected components of the filtered subgraph. The parameter 𝜖 allows adaptation to query selectivity. Our experiments show that even a small 𝜖 (e.g., 0.01) works well for

Conference’17, July 2017, Washington, DC, USA

Algorithm 2: Query Processing Algorithm with MCI Input: 𝐷 = (𝑉 , 𝐹 ), 𝑄 = (𝑣𝑞 , 𝑓𝑞 , 𝑃𝑞 ), Maximal Clique Index M, an integer 𝑘, an integer 𝑙𝑠 , and a parameter 𝜖 Output: 𝑘 ANNs of 𝑄 1 𝑅 ← ∅, 𝐸 ← ∅, 𝐼 ← ∅; /*Results, Explored, Inserted*/ √ 2 𝑠𝑒𝑒𝑑𝑠 ← sample 𝜖 𝑛 vectors that ∀𝑣𝑖 ∈ 𝑠𝑒𝑒𝑑𝑠, 𝑃𝑞 ( 𝑓𝑖 , 𝑓𝑞 ) = 𝑇 𝑟𝑢𝑒; 3 for 𝑣 ∈ 𝑠𝑒𝑒𝑑𝑠 do 4 𝐼 ← 𝐼 ∪ {𝑣 }; insert(𝑅, 𝑣); M ′ ← ∅; /*visted maximal cliques*/ 6 while 𝑅 \ 𝐸 ≠ ∅ do 7 Let 𝑝 be the vector in 𝑅 \ 𝐸 closest to 𝑣𝑞 ; 8 𝐸 ← 𝐸 ∪ {𝑝 }; 9 for 𝐶 ∈ M s.t. 𝑝 ∈ 𝐶, 𝐶 ∉ M ′ do 10 M ′ ← M ′ ∪ {𝐶 }; 11 for 𝑣𝑖 ∈ 𝐶 do 12 if 𝑃𝑞 ( 𝑓𝑖 , 𝑓𝑞 ) and 𝑣𝑖 ∉ 𝐼 then 13 𝐼 ← 𝐼 ∪ {𝑣𝑖 }; insert(𝑅, 𝑣𝑖 ); 5

return the closest 𝑘 vector of 𝑣𝑞 in 𝑅; Procedure insert(𝑅, 𝑣) 16 𝑅 ← 𝑅 ∪ {𝑣 }; 17 if |𝑅 | > 𝑙𝑠 then 18 Update 𝑅 with the closest 𝑙𝑠 vectors to 𝑣𝑞 ;

14

15

high-selectivity queries, as the giant component dominates. For low-selectivity queries, a larger 𝜖 (e.g., 1) helps locate seeds in scattered components, thereby improving recall. √ √ Why 𝜖 𝑛 Seeds? The 𝑛 term is motivated by the observation that in most practical scenarios, query selectivity is typically at least √ √ 𝑂 (1/ 𝑛). Under this condition, 𝑛 seeds provide a good balance: enough to cover the main components, yet sub-linear to avoid √ excessive overhead. While the seed sampling adds 𝜖 𝑛 distance computations, this cost becomes negligible in high-recall regimes where the total number of distance evaluations is much larger. The law of diminishing returns in ANNS means that achieving the last few percentage points of recall often dominates the overall cost [16, 17, 40, 58, 59]; the modest seed-selection overhead is therefore justified by the substantial gains in robustness and final recall.

4.2

The query processing algorithm

Nodes belonging to the same maximal clique as a reference node 𝑢 exhibit strong semantic or structural correlations, rendering them high-potential candidates for the nearest neighbor search. Accordingly, for any node 𝑢 visited during the traversal, we identify M𝑢 as the set of all maximal cliques containing 𝑢. The union of nodes Ð across these cliques, defined as 𝐶 ∈ M𝑢 𝐶, constitutes the candidate set for the subsequent expansion step. Algorithm 2 outlines the pseudo-code for the MCI search procedure. It employs a greedy strategy like beam search [17], customized for the clique-based structure. The algorithm takes as input the dataset 𝐷 = (𝑉 , 𝐹 ), a query 𝑄 = (𝑣𝑞 , 𝑓𝑞 , 𝑃𝑞 ), the index M, and three parameters: the beam width 𝑙𝑠 (where 𝑙𝑠 ≥ 𝑘), the target result count 𝑘, and the sampling factor 𝜖. The process begins by initializing three sets: 𝑅, the top-𝑙𝑠 valid (𝑇𝑟𝑢𝑒) candidates found so far; 𝐸, the set of nodes within 𝑅 that

Rong-Hua Li et al.

have already been expanded; and 𝐼 , the set of visited nodes for which the distance to 𝑣𝑞 has been computed (Line 1). The algorithm √ first samples 𝜖 𝑛 random seeds (Line 2) and attempts to insert them into 𝑅 (Lines 3–4). The core loop proceeds by iteratively selecting the closest unexplored node 𝑝 ∈ 𝑅 \ 𝐸 (Lines 6–8). For each 𝑝, the algorithm retrieves its associated maximal cliques and expands the search to all unvisited neighbors that satisfy the predicate 𝑃𝑞 (lines 9–13). The priority queue 𝑅 is dynamically updated to retain only the top-𝑙𝑠 closest valid vectors (lines 15–18). Finally, the algorithm terminates when no further candidates can be explored, returning the top-𝑘 results (line 14). The search parameters 𝑙𝑠 and 𝜖 enable a flexible trade-off between search quality and efficiency: larger values of 𝜖 and 𝑙 search yield more accurate retrieval results, but at the cost of increased computational latency. Implementation details. To ensure efficient query performance, we adopt the optimized data structure framework established in Vamana [22]. Specifically, the candidate sets 𝑅 and 𝐸 are maintained as ordered vectors, where each element is stored as a tuple (𝑣𝑖 , 𝑑 (𝑣𝑖 , 𝑣𝑞 ), flag𝑖 ) containing the node identifier, its distance to the query, and a boolean validity indicator. The visited set 𝐼 is implemented as a bit-vector of length 𝑛 supporting 𝑂 (1) membership tests. √ We utilize the reservoir sampling algorithm to sample the 𝜖 𝑛 seeds. This sampling algorithm needs a computation of predicates 𝑃𝑞 (𝑓𝑖 , 𝑓𝑞 ) for all nodes. Generally, the predicate computation cost is quite smaller than the search process. Thus, like previous works [32, 45], we pre-compute the predicates as a boolean vector for sampling (Line 2) and searching (Line 12). Additionally, when the predicates cost can not be ignored, we can keeps sampling without √ replacement until 𝜖 𝑛 seeds are reached, where the total sample √ size is expected to be 𝜖 𝑛/𝑠 (𝑠 is the query selectivity). Complexity analysis. The search procedure comprises two distinct phases: seed initialization and greedy traversal. First, the al√ gorithm samples 𝜖 𝑛 seeds to ensure coverage across potentially disconnected components within the predicate-induced subgraph. √ This initialization incurs a computational cost of 𝑂 (𝜖 𝑛) distance comparisons. Second, the greedy traversal operates within the subgraph of valid elements (of size 𝑠𝑛). In high-dimensional vector spaces, the total search overhead is dominated by distance computations. Prior literature on 𝑘-NNG-based ANNS characterizes the empirical search complexity as ranging from 𝑂 (𝑁 0.52 ) to 𝑂 (𝑁 0.55 ) [15, 30, 39, 59]. Given that MCI approximates a 𝑘-NNG structure, we estimate the expected traversal complexity to be 𝑂 ((𝑠𝑛) 0.55 ). Consequently, the total average-case complexity is dominated by the combination of seed sampling and graph traversal, yielding √ 𝑂 (𝜖 𝑛 + (𝑠𝑛) 0.55 ).

5

Experiments

We present a comprehensive evaluation of our method and several state-of-the-art baselines for AFANNS.

5.1

Experimental setup

Datasets. We use ten publicly available datasets from diverse domains, widely adopted in prior ANNS and AFANNS studies

MCI: A Maximal Clique Index for Efficient Arbitrary-Filtered Approximate Nearest Neighbor Search

2

10

80

85

90

95 100

3

80

recall@10

(a) sift1M

3

10

2

10

80

85

90

95

10

3

80

100

3

10

2

10

1

95 100

10

(f) nuswide

10 10

80

recall@10

85

90

85

90

95 100

IVFPQ

10

4

10

3

10

2

10

1

80

recall@10

(c) audio

QPS

4

10

90

recall@10

4

(b) movielens

QPS

QPS

10

85

10

Milvus-HNSW

95

recall@10

2 1

(g) tripclick

85

90

85

90

10

3

10

2

10

1

95 100

80

recall@10

(d) deep1M

3

80

100

pre-filter

QPS

4

Faiss-HNSW

95

recall@10

(h) gist1M

100

10

3

10

2

10

1

80

85

90

85

90

95

100

95

100

recall@10

(e) glove2.2m

QPS

10

10

ACORN

QPS

3

5

QPS

10

10

QPS

10

QPS

QPS

Clique 4

Conference’17, July 2017, Washington, DC, USA

95

recall@10

100

(i) wit

10

3

10

2

10

1

80

85

90

recall@10

(j) spacev10M

Figure 4: Recall@10 vs QPS of different methods under mixed selectivity Í Table 2: Summary of datasets ( C∈ M |C| is the total number • ACORN [45]: configured with 𝑀 = 40, 𝑀𝛽 = 80, 𝛾 = 24, and of nodes contained in MCI) 𝑒 𝑓construction = 500, which ensures sufficient graph density Í C∈M |C| and convergence for most datasets [32, 45]. Datasets 𝑛 Dim #Q Type n HNSW: two implementations (Faiss [12] and Milvus [57]), • sift1M 1,000,000 128 10,000 Image 15.87 both with 𝑀 = 50, 𝑒 𝑓construction = 200. 10,677 150 1,000 Latent Factor 18.57 movielens • IVFPQ: Faiss version with 4000 coarse clusters and 8-bit audio 53,387 192 200 audio 25.75 product quantization. deep1M 1,000,000 256 1,000 Image 17.09 2,196,017 268,643 1,000,000 1,000,000 1,000,000 10,000,000

Clique

ACORN

Memory (G)

glove2.2m nuswide tripclick gist1M wit spacev10M

10

1

10

0

10

300 500 768 960 2,048 100

1,000 200 1,000 1,000 1,000 1,000

Faiss-HNSW

Text Image passages Scenes image Document

45.90 32.01 46.29 35.66 29.60 25.43

Milvus-HNSW

IVFPQ

All methods use Euclidean (𝐿2 ) distance. For specialized filtering tasks, we also include domain-specific baselines: • Range filtering: iRange [67], SuperPF [13], Unify [35], and SeRF [75]. • Keyword filtering: NHQ (NHQ-Kgraph variant [32]) and UNG [5] (with the number of cross edges 𝛿 = 6 and entry vectors 𝜎 = 16 as recommended [5]). All sequential baselines are parallelized for fair latency comparison. General parameter settings follow [32].

−1

sift1M deep1Mglove2.2mnuswide tripclick gist1M

wit

0M

spacev1

Implementation. All experiments run on a Linux server with an AMD Ryzen Threadripper 3990X CPU and 256GB RAM (CentOS 7). Our code is written in C++ and compiled with -O3. Index construction and query processing use 16 threads for all algorithms.

Figure 5: Index size of different methods

5.2 [32, 45, 59]. Detailed characteristics of these datasets are summarized in Table 2. For experiments involving mixed selectivity, we adopt the label (feature) generation method proposed in [5]. The selectivity of the generated labels follows a Zipf distribution, where a higher selectivity indicates a larger number of nodes included in the query result set [5]. For experiments that require precise control of selectivity, we use the selectivity control method in [32]. Algorithms. We implement our construction (Algorithm 1) and search (Algorithm 2) algorithms in C++. Default parameters are 𝜏 = 50, 𝑘 ′ = 200 (construction) and 𝜖 = 1 (search). For the large-scale spacev10M dataset, we increase 𝑘 ′ to 300 to ensure sufficient connectivity. We compare MCI against four general AFANNS baselines, following the evaluation protocol of [32]:

Performance studies

Exp-1: Recall@10 vs. QPS under mixed selectivity. Figure 4 shows the Recall@10–QPS trade-off across datasets under mixed selectivity. ACORN cannot be evaluated on movielens and audio due to segmentation faults in its original implementation. As can be seen, MCI consistently dominates the high-recall regime. On the wit dataset (Figure 4(i)), at recall at 95%, our MCI outperforms the baselines by an order of magnitude in QPS. On deep1M (Figure 4(d)), it sustains > 99.5% recall at 739.7 QPS, whereas the best baseline (Milvus-HNSW) reaches only 197.8 QPS at the same recall—a 3.7× speedup. At lower recall targets, ACORN occasionally achieves higher QPS. For example, on spacev10M (Figure 4(j)) at 85% recall, ACORN attains 2221 QPS vs. 1799 QPS for MCI. This √ gap stems from our fixed seed-sampling overhead (𝜖 𝑛 distance

Conference’17, July 2017, Washington, DC, USA

Time (s)

Clique Clique+KNNG 10

4

10

3

10

2

sift1M

nuswide

ACORN faiss-HNSW

glove2.2m

tripclick

Rong-Hua Li et al. Milvus-HNSW IVFPQ

wit

spacev10M

Figure 6: Index construction time of different methods computations), which becomes noticeable when the total search budget is small (i.e., a small 𝑙𝑠 ). Notably, ACORN fails to reach 99% recall on several datasets, a result that differs from findings in prior studies [32, 45]. This discrepancy arises from our adoption of the query generation method from [5], which includes queries with extremely low selectivity (e.g., 𝑠 ≈ 0.001). ACORN struggles to navigate the sparse subgraphs induced by these strict predicates. In contrast, MCI successfully attains over > 98% recall across all tested datasets, demonstrating superior robustness to selectivity variations. The glove2.2m dataset poses a particular challenge due to its complex topology (many small clusters, hub nodes, and imbalanced distribution) [18]. In such settings, graph-based indices usually degrade, allowing IVFPQ to lead in recall (Figure 4(e)). Nevertheless, MCI still outperforms IVFPQ even under these adverse scenarios. Impact of beam width (𝑙𝑠 ). As the search parameter 𝑙𝑠 increases, recall improves with diminishing returns. Analyzing deep1M specifically (Figure 4(d)): at 𝑙𝑠 = 10, the system achieves 88% recall at 4557 QPS. Increasing 𝑙𝑠 to 20 boosts recall to 93% (3570 QPS), and further to 160 yields 99.08% recall (1391 QPS). However, bridging the final gap to 99.9% recall requires increasing 𝑙𝑠 drastically to 2640, causing QPS to drop to 348. This non-linear trade-off highlights that queries with very low selectivity require extensive graph traversal to ensure near-perfect retrieval. Exp-2: Comparison of index size. Figure 5 compares the index storage requirements of our proposed MCI against the baselines. Note that the index size for the Milvus implementation is not directly measurable [32] and is thus approximated by the official sizing tool https://milvus.io/zh-hant/tools/sizing. Our MCI demonstrates significant storage efficiency, requiring at most 23% of the space consumed by ACORN or HNSW across all datasets. When compared to the quantization-based IVFPQ, MCI achieves the smallest index size on 6 out of 8 datasets. On the remaining two, its size is within a factor of 1.6× that of IVFPQ. This reduction stems from the fundamental difference in structure: while proximity graph-based indices (like HNSW and ACORN) must store a neighbor list for every node, MCI stores only the 𝜏Maximal Clique Cover (𝜏-MCC), which inherently compresses the topological information. Table 2 presents the ratio of the number of integers in MCI and 𝑛, which not surpass 46.29 for all datasets. These results highlight the storage superiority of MCI, reinforcing its practical viability for large-scale AFANNS deployments. Exp-3: Comparison of index construction time (ICT). Figure 6 compares index construction times of different methods. For MCI, we report two indexing times: “Clique” (building MCI from a pre-built 𝑘-NNG) and “Clique+KNNG” (end-to-end time, including 𝑘-NNG construction via NN-Descent [11]). The end-to-end

construction of MCI is faster than ACORN, requiring only 43% of ACORN ’s time on average. Although HNSW builds more quickly, MCI ’s one-time indexing overhead is justified by its substantially better query performance—especially in challenging low-selectivity and high-recall regimes—delivering a favorable trade-off between construction cost and query efficiency. Exp-4: Results under varying query selectivity. To evaluate robustness across selectivity, we tested three representative datasets (Figure 7); trends on other datasets are similar. Compared to ACORN, MCI is particularly stronger in high-recall, low-selectivity regimes. ACORN remains competitive when 𝑠 ≥ 0.05 and target recall < 90%. However, for Recall@10 ≥ 95% and 𝑠 ≤ 0.01, MCI consistently outperforms ACORN on every dataset and achieves a higher overall recall ceiling. Against Milvus-HNSW, MCI delivers higher throughput at comparable recall, especially at higher selectivities. On glove2.2m with 𝑠 = 0.5 (Figure 7(a)), MCI reaches > 95% recall, a level Milvus-HNSW cannot attain. At low selectivity (𝑠 ≤ 0.01), Milvus-HNSW can achieve extremely high recall (≥ 99.9%) but at a high latency cost. For example, on tripclick with 𝑠 = 0.01, Milvus-HNSW reaches 99.98% recall at 614 QPS, while MCI offers more practical trade-offs: 96% recall at 3147 QPS (5× faster) and 98.8% recall at 1499 QPS (2.4× faster). In summary, MCI adapts robustly across a wide selectivity range, offering an efficient balance between high recall and high throughput, especially in challenging low-selectivity, high-recall scenarios. Exp-5: Results on range filtering. Figure 8 shows the range-filtering performance. Each data vector has a numeric feature, and each query specifies a range; query selectivities are controlled at values {0.3, 0.15, 0.07, 0.03, 0.015, 0.007, 0.003, 0.001} using the method in [32]. We report results on three representative datasets. On sift1M (Figure 8(a)), MCI delivers competitive performance, closely matching the state-of-the-art specialized baselines (iRange and SuperPF) in the high-recall regime—a trend observed across most datasets. On more challenging datasets like glove2.2m (Figure 8(b)) and nuswide (Figure 8(c)), MCI not only remains competitive but also shows a slight advantage at high recall. Despite the fact that the baseline methods build indexes specifically optimized for numerical range filtering, our general-purpose MCI achieves comparable or better efficiency, especially when high recall is required. This underscores the robustness and wide applicability of our approach. Exp-6: Results on keyword filtering. Figure 9 shows the keyword filtering performance of different methods. In this experiment, each data vector has a set of keywords, and queries require exactly matching keywords. Among the baselines, UNG achieves the best overall performance, as its index is specifically designed for the sparsity patterns of keyword filtering [5]. Despite this specialization, our general-purpose MCI remains highly competitive, especially in the high-recall regime on datasets like deep1M and wit, demonstrating its effectiveness even without domain-specific optimizations. Exp-6: no filtering. We compare the methods in a standalone ANNS setting. The HNSW and IVFPQ are implemented in the Faiss library [12]. The results are summarized in Figure 10. On the deep1M dataset (Figure 10(a)), HNSW achieves the highest query throughput, followed by our method MCI, with IVFPQ exhibiting the lowest performance. A similar ranking is observed on

MCI: A Maximal Clique Index for Efficient Arbitrary-Filtered Approximate Nearest Neighbor Search

90

recall@10

10

3

10

2

10

2

95 100

80

90

recall@10

95

80

100

(b) glove2.2m, s=0.1

10

4

10

4

10

3

10

3

10

3

10

2

10

2

10

2

85

90

95

recall@10

QPS

4

80

80

100

(f) tripclick, s=0.5

95

80

100

90

95

10

2

80

100

recall@10

85

90

95

10

3

10

2

80

80

85

90

95

10

2

80

100

recall@10

(k) gist1M, s=0.5

85

90

95

10

3

10

2

100

recall@10

QPS

2

3

80

(l) gist1M, s=0.1

85

90

90

95

80

100

recall@10

85

90

95

recall@10

10

4

10

3

10

2

80

100

95

10

3

10

2

100

recall@10

(m) gist1M, s=0.05

85

90

85

90

95

recall@10

100

(e) glove2.2m, s=0.005

80

(i) tripclick, s=0.01

3

10

85

2

(d) glove2.2m, s=0.01

100

recall@10

10

(h) tripclick, s=0.05

QPS

10

90

recall@10

(g) tripclick, s=0.1

QPS

QPS

10

85

85

3

(c) glove2.2m, s=0.05

10

QPS

QPS

(a) glove2.2m, s=0.5

85

10

QPS

3

IVFPQ

QPS

85

10

Milvus-HNSW

85

90

95

recall@10

100

(j) tripclick, s=0.005

QPS

80

10

4

QPS

10

1

Faiss-HNSW

10

QPS

10

2

ACORN

4

QPS

10

QPS

QPS

Clique 3

Conference’17, July 2017, Washington, DC, USA

10

3

10

2

95 100

80

recall@10

(n) gist1M, s=0.01

85

90

95

recall@10

100

(o) gist1M, s=0.005

Figure 7: Recall@10 vs QPS of different methods under various selectivity

80

85

90

10 10

2

95 100

80

recall@10

(a) sift1M

85

90

recall@10

95

10 10

2

80

100

(b) glove2.2m

85

90

95

recall@10

Clique

100

10

4

10

3

10

2

85

(c) nuswide

10

3

10

2

80

85

90

95

recall@10

(a) deep1M

100

10

4

10

3

10

2

UNG

NHQ 4 10 QPS

10

QPS

QPS

Clique

80

85

90

95

recall@10

(b) glove2.2m

95

recall@10

100

10

3

10

2

80

10

3

10

2

100

85

(a) deep1M

Figure 8: Results of different methods on range filtering 4

90

HNSW

IVFPQ

10

2

10

1

QPS

3

3

SeRF

QPS

10

3

Unify

QPS

4

SupperPF

QPS

10

iRange

QPS

QPS

Clique

90

95

recall@10

85

100

(b) gist1M

90

95

recall@10

100

(c) glove2.2m

Figure 10: No filtering

85

90

95

recall@10

100

10

4

10

3

(c) wit

Figure 9: Results of different methods for keywords filtering gist1M. The trend differs on glove2.2m (Figure 10(c)), where IVFPQ demonstrates superior efficiency at moderate recall rates, outperforming both MCI and HNSW. In the high-recall regime (e.g., >98%), MCI surpasses IVFPQ, while HNSW lags significantly. These results highlight that MCI provides a more robust and balanced performance, consistently remaining competitive across diverse datasets. This demonstrates the general effectiveness of our approach. Exp-7: recall vs distance computation times. To further analyze the efficiency of the search process, we compare the recall achieved against the number of distance computations required.

Clique ACORN

80 85 90 95 100 recall@10

(a) deep1M

10

5

10

4

Clique ACORN

80 85 90 95 100 recall@10

(b) glove2.2m

10

4

10

3

Clique ACORN

80 85 90 95 100 recall@10

(c) tripclick

Figure 11: Recall vs distance computation times (y-axis is the times of distance computation)

This comparison, shown in Figure 11, is conducted under queries with mixed selectivities. Similar trends were observed across other datasets. We primarily compare our method, MCI, with ACORN. Algorithms such as Faiss-HNSW, Milvus-HNSW, and IVFPQ are

Conference’17, July 2017, Washington, DC, USA

3

10

2

10

Faiss-HNSW

10

1

80

85

90

95

recall@50

2

10

1

80

(a) deep1M, k=50

IVFPQ

3

10

100

Milvus-HNSW

QPS

10

ACORN

QPS

QPS

Clique

Rong-Hua Li et al.

85

90

95

recall@50

10

3

10

2

10

1

80

85

90

95 100

recall@50

(c) gist1M, k=50

Figure 12: Recall vs QPS of various methods for 𝑘 = 50

95 96 97 98 99100

QPS

QPS

10

2

(b) glove2.2m, s=0.05

95 96 97 98 99100 recall@10

(d) tripclick, s=0.5

10

4

10

3

10

2

10

1.0

2 6 × 10

1

4 × 10

1

3 × 10

1

95 96 97 98 99100

recall@10

(a) glove2.2m, s=0.5 3

2

0.5

95 96 97 98 99100

recall@10

10

0.2

QPS

1

10

0.1

recall@10

(c) glove2.2m, s=0.005

QPS

10

QPS

QPS

0.01

95 96 97 98 99100 recall@10

(e) tripclick, s=0.05

𝑘 ′ = 100

Datasets

100

(b) tripclick, k=50

Table 3: Average out-degree of MCI

pre-filter

2

10 95 96 97 98 99100 recall@10

(f) tripclick, s=0.005

Figure 13: Results of our method with varying 𝜖 built upon the Faiss and Milvus libraries, which internally manage index traversal and distance calculations. Consistent with the trends observed in prior results (e.g., Figure 4), ACORN demonstrates an advantage in scenarios requiring lower recall. Conversely, our method MCI consistently achieves a significantly higher final recall rate. This indicates that MCI is suitable for high-recall retrieval tasks. Exp-7: Sensitivity to result set size (𝑘). To evaluate the impact of the target number of nearest neighbors (𝑘), we extended our evaluation to 𝑘 = 50, as shown in Figure 12. The overall trend indicates that the relative performance of all evaluated algorithms remains consistent across different 𝑘 values. Our method, MCI, maintains nearly identical performance profiles regardless of 𝑘. In contrast, ACORN exhibits minor degradation as 𝑘 increases. For instance, on the deep1M dataset at a throughput of 103 QPS, the recall for ACORN drops slightly from approximately 93% at 𝑘 = 10 (Figure 4(d)) to about 92% at 𝑘 = 50 (Figure 12(a)). These results confirm that the performance characteristics of AFANNS are generally robust with varying 𝑘. Exp-8: Sensitivity to sampling parameter 𝜖. We investigate the √ impact of 𝜖, which controls the initial seed count 𝜖 𝑛 (Algorithm 2). Figure 13 reveals a clear pattern: the optimal seed count is inversely correlated with query selectivity 𝑠. For high selectivity, a small 𝜖 suffices because the filtered subgraph is dense and well-connected. For low selectivity, increasing 𝜖 yields significant gains. On tripclick with 𝑠 = 0.005, raising 𝜖 from 0.01 to 1 lifts Recall@10 from 97.06% to 97.8%—a non-trivial improvement in the challenging high-recall regime. These results suggest a practical tuning heuristic: set 𝜖 inversely proportional to the expected selectivity.

sift1M deep1M glove2.2m gist1M wit

𝑘 ′ = 200

𝜏 = 14

𝜏 = 32

𝜏 = 50

𝜏 = 14

𝜏 = 32

𝜏 = 50

297.1 415.2 512.8 657.2 553.4

405.4 644.2 535.5 782.2 636.1

454.2 616.8 561.9 892.9 715.7

532.8 726.3 1953.2 1457.8 1192.4

797.5 1176.2 2067.8 1676.7 1329.5

908.9 1305.7 1093.7 1871.3 1453.7

Exp-9: Sensitivity to construction parameters (𝑘 ′ and 𝜏). Figure 14 analyzes the impact of the construction parameters 𝑘 ′ (initial neighborhood size) and 𝜏 (clique overlap threshold). In the plots, varying 𝑘 ′ values (50, 100, 200) are represented by red, blue, and green lines, respectively, while different 𝜏 thresholds (14, 32, 50) are distinguished by circular, square, and triangular markers. The results indicate that performance is primarily determined by 𝑘 ′ . As illustrated, the green curves (𝑘 ′ = 200) consistently yield better recall/QPS trade-offs than the blue curves (𝑘 ′ = 100), which in turn outperform the red curves (𝑘 ′ = 50). In contrast, MCI demonstrates significant robustness to the parameter 𝜏. For instance, on the wit dataset (Figure 14(e)), trajectories with the same color (constant 𝑘 ′ ) exhibit nearly identical performance profiles despite differences in 𝜏. This implies that 𝑘 ′ is the critical determinant of index quality, while the algorithm is relatively insensitive to the precise tuning of 𝜏. Exp-10: Average out-degree of MCI. Table 3 reports the average out-degree of the MCI graph structure across various parameter settings. A key strength of MCI is its ability to produce an NNG whose effective average degree far exceeds the initial parameter 𝑘 ′ . For 𝑘 ′ = 100, the average out-degree consistently surpasses 300 across all datasets, reaching over 600 in some configurations. This structural densification is pivotal for search performance, particularly in low-selectivity scenarios. Even when a significant fraction of neighbors are pruned by the query predicate, the expanded neighborhood ensures that a sufficient number of valid neighbors remain. Consequently, this high connectivity directly contributes to the algorithm’s robustness and high recall. Exp-11: 𝛼 vs. percentage of uncovered nodes. Figure 15 illustrates how the percentage of uncovered nodes decreases as 𝛼 increases (with 𝛼 max = 10). At 𝛼 = 2, over 60% of nodes are already covered across all datasets; the remaining uncovered nodes belong to small, isolated clusters. Full coverage is achieved when 𝛼 ≥ 𝛼 max , as guaranteed by the fallback mechanism in Lines 17–18 of Algorithm 1. These results highlight two important properties: (1) the construction algorithm converges in few iterations, and (2) the first two iterations are sufficient to cover the dense clusters, leaving only sparse outliers for later rounds. Exp-12: Parallel speedup of index construction. Figure 16 plots the parallel speedup of MCI and ACORN. With 16 or fewer threads, both algorithms exhibit similar speedup ratios. However, at 32 and 64 threads on the sift1M dataset, the speedup of ACORN drops to 13.10 and 10.91, respectively, whereas MCI achieves 17.31 and 22.76. The reduced parallel efficiency of ACORN at higher thread counts stems from its reliance on locks in the HNSW structure [40]. In contrast, MCI benefits from a lock-free design, allowing it to scale

MCI: A Maximal Clique Index for Efficient Arbitrary-Filtered Approximate Nearest Neighbor Search

10

200 14

50 32

100 32

200 32

3

3

10

90 92 94 96 98 100

90 92 94 96 98 100

recall@10

recall@10

(a) sift1M

(b) deep1M

100 50

10

3

10

2

200 50

10

3

10

2

2

QPS

10

QPS

QPS

QPS

10

100 14

4

90 92 94 96 98 100 recall@10

(c) glove2.2m

QPS

50 14

Conference’17, July 2017, Washington, DC, USA

90 92 94 96 98 100 recall@10

(d) gist1M

90 92 94 96 98 100 recall@10

(e) wit

uncovered percentage (%)

Figure 14: Results of our method with varying (𝑘 ′ , 𝜏) 100 80 60

sift1M deep1M glove2.2m tripclick

gist1M wit spacev10M

2

8

40 20 0

0

1

4

α (multiply 1.2)

16

64 32 16 8 4 2 1

Clique ACORN

Speedup

Speedup

Figure 15: Results of 𝛼 vs. the percentage of uncovered nodes

1 2 4 8 16 32 64 threads

(a) sift1M

64 32 16 8 4 2 1

Clique ACORN

1 2 4 8 16 32 64 threads

(b) deep1M

Figure 16: Parallel performance of index building algorithms

better with available resources. These results confirm our analysis in Section 3.2.

5.3

Summary of experimental results

Table 4 presents a systematic comparison of MCI and state-of-theart methods across key performance metrics, rated using a star system (★: more stars = better performance). The analysis reveals MCI’s distinctive advantages: First, MCI matches the storage efficiency of quantization-based methods (like IVFPQ), a notable achievement for a graph-based index. This compact representation reduces memory overhead while preserving rich connectivity. Second, in index construction time (ICT), MCI significantly outperforms ACORN (43% of ACORN’s time) and remains competitive with HNSW. This efficiency stems from our lock-free parallel design and the geometric expansion strategy. Most importantly, MCI delivers the best query performance—achieving the highest recall at given latency levels, especially under low selectivity. This addresses a critical limitation of existing filtered-ANNS methods. Together, these strengths give MCI the highest overall robustness rating, demonstrating its suitability for diverse real-world workloads where no single dimension can be sacrificed.

6

Related work

Unfiltered ANNS. Approximate Nearest Neighbor Search (ANNS) is a well-studied problem, with methods falling into four main categories: tree-based structures [1, 3, 6, 28, 48], proximity graphs (PG) [7, 17, 18, 24, 27, 31, 33, 39, 43, 46, 62, 68, 70], learning-based methods [25, 55, 61], and Locality-Sensitive Hashing (LSH) [50, 65, 73, 74]. Among these, PG-based indexes have shown the best recall-latency trade-off in practice [59]. A key design principle is approximating ideal geometric structures. Many top-performing graphs (e.g., HNSW [40], NSG [17], Vamana [27]) are efficient approximations of the Relative Neighborhood Graph (RNG) [53]. Some methods (e.g., 𝜏-MNG [46], FANNG [24]) provide theoretical routing guarantees, while others (e.g., HNSW [40], DPG [33]) prioritize empirical efficiency. Complementary research focuses on reducing the distance-computation bottleneck via quantization [8, 10, 19– 21, 23, 26, 36, 37, 63, 64, 71] and hardware-aware optimizations (CPU pipelining [41], SIMD [2], GPU [44], I/O [49, 60]). Filtered ANNS. Incorporating filtering predicates makes ANNS substantially more challenging because the index must preserve both geometric proximity and predicate reachability. As summarized in Table 1, most prior work is specialized to one predicate family. For range filtering on numerical attributes, static indexes such as SeRF [75], SuperPF/the 𝛽-WST framework of Engels et al. [13], iRangeGraph [67], and UNIFY [35] exploit attribute order through range-aware graph structures or hybrid trees. More recent dynamic RFANNS methods, including DSG [47], DIGRA [29], and RangePQ+ [72], further support online updates while still assuming scalar attributes and interval predicates. For keyword, label, or tag filtering, Filtered-DiskANN [22], NHQ [58], UNG [5], and TFANNS [38] leverage discrete set-membership semantics via label-aware graphs, attribute indexes, DAG-style inclusion structures, or tag-frequency-aware graph construction; these methods are highly effective in their target settings but typically assume static categorical metadata. For arbitrary filtering, the classical baselines are pre-filtering and post-filtering, which are effective only in favorable selectivity regimes. General systems such as FAISS [12] and Milvus [57] usually implement filtered search through these heuristics or lightweight variants, often sacrificing robustness across mixed workloads. Learning-based methods such as SIEVE [34] assume stable historical query distributions, which limits applicability in dynamic or cold-start settings. ACORN [45] is the main predicate-agnostic

Conference’17, July 2017, Washington, DC, USA

Rong-Hua Li et al.

Table 4: Summary of performance comparison Method

Index Size

ICT

Query

Overall

ACORN [45] Faiss-HNSW [12] Milvus-HNSW [57] IVFPQ [12] MCI (Ours)

★★★ ★★★ ★★ ★★★★★ ★★★★★

★★★ ★★★★★ ★★★★★ ★ ★ ★★ ★ ★ ★★

★★★ ★★★ ★★★ ★★ ★★★★★

★★★ ★★★ ★★★ ★★ ★★★★★

graph index in this line, extending HNSW with enlarged predicaterobust neighborhoods; however, as also confirmed by our experiments, it still incurs substantial memory overhead and can struggle to maintain high recall under low selectivity. This gap motivates MCI, which seeks to retain the generality of arbitrary filtering without relying on predicate-specific structures or workload-specific assumptions.

7

Conclusion

This work addresses the Arbitrary Filtered Approximate Nearest Neighbor Search (AFANNS) problem. We present the Maximal Clique Index (MCI), a novel graph-based index designed for AFANNS. By employing a Maximal Clique Cover strategy and a neighborhood graphs geometric densification strategy, MCI exploits the inherent clique structure of the graph to achieve high compression and connectivity. Our results demonstrate that MCI significantly outperforms state-of-the-art baselines in both highrecall regimes and storage efficiency, offering a robust solution for the complex filtering requirements of modern vector databases.

References [1] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015. Practical and Optimal LSH for Angular Distance. In NIPS. 1225– 1233. [2] Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2017. Accelerated Nearest Neighbor Search with Quick ADC. In ICMR. ACM, 159–166. [3] Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. HDIndex: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces. Proc. VLDB Endow. 11, 8 (2018), 906–919. [4] Fedor Borisyuk, Siddarth Malreddy, Jun Mei, Yiqun Liu, Xiaoyi Liu, Piyush Maheshwari, Anthony Bell, and Kaushik Rangadurai. 2021. VisRel: Media Search at Scale. In SIGKDD. ACM, 2584–2592. [5] Yuzheng Cai, Jiayang Shi, Yizhuo Chen, and Weiguo Zheng. 2024. Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 6 (2024), 246:1–246:27. [6] Manos Chatzakis, Panagiota Fatourou, Eleftherios Kosmas, Themis Palpanas, and Botao Peng. 2023. Odyssey: A Journey in the Land of Distributed Data Series Similarity Search. Proc. VLDB Endow. 16, 5 (2023), 1140–1153. [7] Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X. Sean Wang. 2024. RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search. Proc. VLDB Endow. 17, 11 (2024), 2735–2749. [8] Patrick H. Chen, Wei-Cheng Chang, Jyun-Yu Jiang, Hsiang-Fu Yu, Inderjit S. Dhillon, and Cho-Jui Hsieh. 2023. FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search. In WWW. ACM, 3225–3235. [9] Abhinandan Das, Mayur Datar, Ashutosh Garg, and Shyamsundar Rajaram. 2007. Google news personalization: scalable online collaborative filtering. In WWW. ACM, 271–280. [10] Liwei Deng, Penghao Chen, Ximu Zeng, Tianfu Wang, Yan Zhao, and Kai Zheng. 2024. Efficient Data-aware Distance Comparison Operations for HighDimensional Approximate Nearest Neighbor Search. Proc. VLDB Endow. 18, 3 (2024), 812–821. [11] Wei Dong, Moses Charikar, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW 2011. ACM, 577–586. [12] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. (2024). arXiv:2401.08281 [cs.LG] [13] Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters. In Fortyfirst International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net.

[14] Wenqi Fan, Yujuan Ding, Liangbo Ning, Shijie Wang, Hengyun Li, Dawei Yin, Tat-Seng Chua, and Qing Li. 2024. A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Models. In SIGKDD. ACM, 6491–6501. [15] Cong Fu and Deng Cai. 2016. EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. CoRR abs/1609.07228 (2016). [16] Cong Fu, Changxu Wang, and Deng Cai. 2022. High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE Trans. Pattern Anal. Mach. Intell. 44, 8 (2022), 4139–4150. [17] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. Proc. VLDB Endow. 12, 5 (2019), 461–474. [18] Yujian Fu, Cheng Chen, Yao Chen, Weng-Fai Wong, and Bingsheng He. 2025. Vista: Vector Indexing and Search for Large-Scale Imbalanced Datasets. In ICDE. IEEE, 543–556. [19] Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong. 2025. Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 3 (2025), 202:1–202:26. [20] Jianyang Gao and Cheng Long. 2023. High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations. Proc. ACM Manag. Data 1, 2 (2023), 137:1–137:27. [21] Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 3 (2024), 167. [22] Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. 2023. FilteredDiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In WWW. ACM, 3406–3416. [23] Yutong Gou, Jianyang Gao, Yuexuan Xu, and Cheng Long. 2025. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 1 (2025), 80:1–80:26. [24] Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713–5722. [25] Ville Hyvönen, Elias Jääsaari, and Teemu Roos. 2024. A Multilabel Classification Framework for Approximate Nearest Neighbor Search. J. Mach. Learn. Res. 25 (2024), 46:1–46:51. [26] Elias Jääsaari, Ville Hyvönen, and Teemu Roos. 2024. LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search. In NIPS. [27] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Advances in Neural Information Processing Systems, Vol. 32. Curran Associates, Inc. [28] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (2011), 117–128. [29] Mengxu Jiang, Zhi Yang, Fangyuan Zhang, Guanhao Hou, Jieming Shi, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter. Proc. ACM Manag. Data 3, 3 (2025), 148:1–148:26. doi:10.1145/3725399 [30] Zhongming Jin, Debing Zhang, Yao Hu, Shiding Lin, Deng Cai, and Xiaofei He. 2014. Fast and Accurate Hashing Via Iterative Nearest Neighbors Expansion. IEEE Trans. Cybern. 44, 11 (2014), 2167–2177. [31] Sungjun Jung, Yongsang Park, Haeun Lee, Young H. Oh, and Jae W. Lee. 2025. Angular Distance-Guided Neighbor Selection for Graph-Based Approximate Nearest Neighbor Search. In WWW. ACM, 4014–4023. [32] Mocheng Li, Xiao Yan, Baotong Lu, Yue Zhang, James Cheng, and Chenhao Ma. 2025. Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study. Proc. ACM Manag. Data 3, 6 (2025), 1–26. [33] 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. TKDE 32, 8 (2020), 1475–1488. [34] Zhaoheng Li, Silu Huang, Wei Ding, Yongjoo Park, and Jianjun Chen. 2025. SIEVE: Effective Filtered Vector Search with Collection of Indexes. Proc. VLDB Endow. 18, 11 (2025), 4723–4736. [35] Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search. Proc. VLDB Endow. 18, 4 (2024), 1118–1130. [36] Zihan Liu, Wentao Ni, Jingwen Leng, Yu Feng, Cong Guo, Quan Chen, Chao Li, Minyi Guo, and Yuhao Zhu. 2024. JUNO: Optimizing High-Dimensional Approximate Nearest Neighbour Search with Sparsity-Aware Algorithm and Ray-Tracing Core Mapping. In ASPLOS. ACM, 549–565. [37] Kejing Lu, Chuan Xiao, and Yoshiharu Ishikawa. 2024. Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search. In ICML. OpenReview.net. [38] Jiarui Luo, Miao Qiao, Chaoji Zuo, and Dong Deng. 2025. Tag-Filtered Approximate Nearest Neighbor Search. In 41st IEEE International Conference on Data Engineering, ICDE.

MCI: A Maximal Clique Index for Efficient Arbitrary-Filtered Approximate Nearest Neighbor Search

[39] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Inf. Syst. 45 (2014), 61–68. [40] Yury A. Malkov and Dmitry A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42, 4 (2020), 824–836. [41] Magdalen Dobson Manohar, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms. In PPoPP. ACM, 270–285. [42] Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Ali Mousavi, Ihab F. Ilyas, Umar Farooq Minhas, Jeffrey Pound, and Theodoros Rekatsinas. 2023. HighThroughput Vector Similarity Search in Knowledge Graphs. Proc. ACM Manag. Data 1, 2 (2023), 197:1–197:25. [43] Javier Alvaro Vargas Muñoz, Marcos André Gonçalves, Zanoni Dias, and Ricardo da Silva Torres. 2019. Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search. Pattern Recognit. 96 (2019). [44] Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. 2024. CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs. In ICDE. IEEE, 4236–4247. [45] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. Proc. ACM Manag. Data 2, 3 (2024), 120. [46] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proc. ACM Manag. Data 1, 1 (2023), 54:1–54:27. [47] Zhencan Peng, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2025. Dynamic Range-Filtering Approximate Nearest Neighbor Search. Proc. VLDB Endow. 18, 10 (2025), 3256–3268. [48] Chanop Silpa-Anan and Richard I. Hartley. 2008. Optimised KD-trees for fast image descriptor matching. In CVPR. IEEE Computer Society. [49] Bing Tian, Haikun Liu, Zhuohui Duan, Xiaofei Liao, Hai Jin, and Yu Zhang. 2024. Scalable Billion-point Approximate Nearest Neighbor Search Using SmartSSDs. In USENIX ATC. USENIX Association, 1135–1150. [50] Yao Tian, Xi Zhao, and Xiaofang Zhou. 2024. DB-LSH 2.0: Locality-Sensitive Hashing With Query-Based Dynamic Bucketing. IEEE Trans. Knowl. Data Eng. 36, 3 (2024), 1000–1015. [51] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363, 1 (2006), 28–42. [52] Godfried T. Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern Recognit. 12, 4 (1980), 261–268. [53] Godfried T. Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern Recognit. 12, 4 (1980), 261–268. [54] R. v. Mises. 1942. On the Correct Use of Bayes’ Formula. The Annals of Mathematical Statistics 13, 2 (1942), 156 – 165. [55] Thomas Vecchiato, Claudio Lucchese, Franco Maria Nardini, and Sebastian Bruch. 2024. A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search. In SIGIR. ACM, 2261–2265. [56] Roman Vershynin. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press. [57] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A Purpose-Built Vector Data Management System. In Proceedings of the 2021 International Conference on Management of Data. 2614–2627. [58] Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2023. An Efficient and Robust Framework for Approximate Nearest

Conference’17, July 2017, Washington, DC, USA

Neighbor Search with Attribute Constraint. In NIPS. [59] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. Proc. VLDB Endow. 14, 11 (2021), 1964–1978. [60] Yitu Wang, Shiyu Li, Qilin Zheng, Linghao Song, Zongwang Li, Andrew Chang, Hai Li, and Yiran Chen. 2024. NDSEARCH: Accelerating Graph-Traversal-Based Approximate Nearest Neighbor Search through Near Data Processing. In ISCA. IEEE, 368–381. [61] Yi Wang, Huan Liu, Jianan Yuan, Jiaxian Chen, Tianyu Wang, Chenlin Ma, and Rui Mao. 2024. Leanor: A Learning-Based Accelerator for Efficient Approximate Nearest Neighbor Search via Reduced Memory Access. In DAC. ACM, 61:1–61:6. [62] Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, and Wei Wang. 2024. Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes. Proc. VLDB Endow. 17, 13 (2024), 4668–4682. [63] Zeyu Wang, Haoran Xiong, Qitong Wang, Zhenying He, Peng Wang, Themis Palpanas, and Wei Wang. 2024. Dimensionality-Reduction Techniques for Approximate Nearest Neighbor Search: A Survey and Evaluation. IEEE Data Eng. Bull. 48, 3 (2024), 63–80. [64] Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng. 2025. Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 1 (2025), 79:1–79:29. [65] Jiuqi Wei, Botao Peng, Xiaodong Lee, and Themis Palpanas. 2024. DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search. Proc. VLDB Endow. 17, 9 (2024), 2241–2254. [66] Jiadong Xie, Jeffrey Xu Yu, Siyi Teng, and Yingfan Liu. 2025. Beyond Vector Search: Querying With and Without Predicates. Proc. ACM Manag. Data 3, 6 (2025), 1–26. doi:10.1145/3769765 [67] Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S. Jensen. 2024. iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search. Proc. ACM Manag. Data 2, 6 (2024), 239:1–239:26. [68] Ming Yang, Yuzheng Cai, and Weiguo Zheng. 2024. CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search. In NIPS. [69] Xiaowei Ye, Rong-Hua Li, and Guoren Wang. 2025. The Power of Core Clique Removal for Exact Clique Enumeration. Proc. ACM Manag. Data 3, 4 (2025), 269:1–269:27. [70] Ziqi Yin, Jianyang Gao, Pasquale Balsebre, Gao Cong, and Cheng Long. 2025. DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph. Proc. ACM Manag. Data 3, 1 (2025), 29:1–29:28. [71] Qiang Yue, Xiaoliang Xu, Yuxiang Wang, Yikun Tao, and Xuliyuan Luo. 2024. Routing-Guided Learned Product Quantization for Graph-Based Approximate Nearest Neighbor Search. In ICDE. IEEE, 4870–4883. [72] Fangyuan Zhang, Mengxu Jiang, Guanhao Hou, Jieming Shi, Hua Fan, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 3 (2025), 152:1–152:26. doi:10.1145/3725401 [73] Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards Efficient Index Construction and Approximate Nearest Neighbor Search in HighDimensional Spaces. Proc. VLDB Endow. 16, 8 (2023), 1979–1991. [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 J. 31, 6 (2022), 1339–1363. [75] Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 1 (2024), 69:1–69:26.

Conference’17, July 2017, Washington, DC, USA

Rong-Hua Li et al.

10

3

80

QPS

QPS

mine a new maximal clique from 𝑅 ∪ {𝑢} using the mineCliques procedure in Algorithm 1. 6 8 10 12

85

90

95

recall@10

100

(a) Various quality of 𝑘 ′ -NNG

10

3

80

1.25 1.5 1.75 2.0

85

90

recall@10

95

100

(b) Various 𝛼 expansion ratio

Figure 17: Additional experiments on deep1M

A

Discussion on dynamic updates

Although our current implementation focuses on static construction, MCI is designed to support efficient dynamic operations without global re-indexing. We propose the following lightweight strategies, which we leave for future work. Insertion. We utilize a heuristic grounded in geometric transitivity (Theorem 3.4). To insert a node 𝑢, we first retrieve its approximate nearest neighbors 𝑅 using the existing index (cost ≈ 𝑂 (𝑛 0.55 )). We then append 𝑢 to√︁any maximal clique 𝐶 satisfying the overlap condition |𝐶 ∩ 𝑅| ≥ |𝐶 |. This overlap serves as a proxy for full connectivity, leveraging distance concentration to avoid expensive verification. If 𝑢 is an outlier (i.e., no such clique exists), we locally

Deletion. Deletion is straightforward: the target node is simply removed from all maximal cliques containing it. If a clique’s size drops below the threshold 𝜏, locally mine the maximal cliques for remaining nodes using the mineCliques procedure in Algorithm 1.

B

Additional experiments

Exp-13: Sensitivity to the quality of 𝑘 ′ -NNG. The NN-Descent algorithm relies on iterations to converge; generally, a higher number of iterations yields a higher-quality 𝑘 ′ -NNG. We measure the quality of a 𝑘 ′ -NNG using Recall@𝑘 ′ . At 6, 8, 10, and 12 iterations, the quality (Recall@𝑘 ′ ) is 0.39, 0.67, 0.81, and 0.91, respectively. Although iterations 8, 10, and 12 produce 𝑘 ′ -NNGs of varying qualities, the query performance (Recall-QPS) of MCI remains stable, as shown in Figure 17(a). These results demonstrate that MCI is not sensitive to the quality of the underlying 𝑘 ′ -NNG. Exp-14: Sensitivity to 𝛼 expansion ratio. In the default setting, 𝛼 doubles at each step (Line 8 of Algorithm 1). Figure 17(b) plots the performance under various expansion ratios: 1.25, 1.5, 1.75, and 2.0. An expansion ratio of 1.25 implies the update 𝛼 ← 𝛼 × 1.25 at Line 8 of Algorithm 1. The results in Figure 17(b) indicate that MCI is insensitive to the specific choice of expansion ratio.

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181