Graph-based algorithms for nearest neighbor search with multiple filters

W2: I found the theoretical analysis and the proposed algorithms are not aligned well though there are several raised issues (i.e. lessons) to connect them together. In the end, the proposed algorithm is a combination between FilteredDiskANN (Gollapudi et al. 2023) with new fused distance measure (inherited in NHQ - Wang et al. 2023).

We thank the reviewer for the feedback. The lessons learned from our theoretical algorithm (lessons 1-4) directly translate into our empirical algorithm design process.

Lesson 1 is saying graph based algorithms can also be used for our main theoretical result of Theorems 4.1 and 4.2. Thus, we do not lose any theoretical power by using graph based approaches.

For Lesson 2, query planning refers to appropriately routing the query to a small part of the dataset so that we can guarantee a subset match exists while only comparing to a tiny fraction of data for efficiency. Both the theoretical algorithms and our practical variant make use of this meta-idea.

Lastly, Lesson 3 highlights that popular prior approaches for our problem, which use clustering based methods, are too ‘local.’ In a simple one dimensional example, clustering based methods spend too much time focusing on the ‘distance’ part of the problem and ignore the subset match constraint. This forces them to iterate over many irrelevant points in the local vicinity of the query. In contrast, graph based methods allow us to skip many local points automatically since we consider both the distances and subset matches together.

We thank the reviewer for the detailed response and concerns. Below, we address the reviewer's listed weaknesses in our submission (split over multiple comments):

W1: On theoretical side, the SQ problem only determines that there exists $S_x$ such that $S_q \subset S_x$. It does not report all $S_x$ such that $S_q \ subset S_x$. Therefore, I think the claim of Theorem 4.1 and 4.2 are not correct.

A simple case for LSH is follows. Assume that there exists an cr instance $x$ that is not in the reported group of the SQ's data structure, then LSH will report empty at the certain radius $r$. The algorithm then continues with larger $c$. In this case, you cannot guarantee $(1+ \epsilon)$-ANNS. Another sanity check is that all instances $x$ \in $X$ satisfies the constraint. Hence, reporting a group of $n^\delta$ points by CIP (Charikar et al. 02) clearly affects the $(1+\epsilon)$ guarantees. Since SQ's data structure cannot guarantee to report all elements $x$ such that $S_q \subset S_x$, there will be an uncontrolled probability that DIC & LSH fail to guarantee $(1 + \epsilon)$-ANNS. Unfortunately, I do not think the used technique CIP & LSH (or graph-based index) can fix this issue without increasing the time and space complexity.

The reviewer may have missed a crucial definition. We do not require reporting all $x$ such that $S_q \subseteq S_x$. Rather, we need to report one $x$ that satisfies this guarantee, under the constraint that the $\ell_2$ distances are also minimized.

However, we note that we can easily turn our data structure to reporting all such $x$ such that $S_q \subseteq S_x$. The CIP datastructure actually does, with probability 0.5, return a pointer to groups such that every single feasible point for the query is in some group. Of course, the groups may collectively contain every single point, but performing ANN in sublinear time on each group enables us to find a solution in $o(n)$ time. We will edit the paper to make this clearer. Moreover, we stress that all prior work on multifiltered-NN has been purely empirical in nature. We provide the first meaningful theoretical guarantees for this problem and show that we can achieve almost the same space-time tradeoffs as the best known for subset query.

W4. There are two new fused distances including $dist'$ and $\hat{dist}$, which use $S_q$ in the querying phase. Though it is not clear to me which measure are used for querying, it seems that the proof of Theorem 6.1 with $dist'$ in the appendix is not correct. Given a large $\lambda$, the contribution of second term dominates $dist'$. How could it guarantee to answer MFANN according the distance in the first term? It looks to me the proof is an heuristic argument since given the graph index, filtering out point $y$ such that $S_q \notsubset S_y$ cannot bring you to the closet point $x$ such that $S_q \subset S_x$.

We thank the reviewer for the comment. The $\lambda$ term has the same value ($C$) for all datapoints that are feasible for the query. Moreover, for any infeasible point, the lambda term is larger than ($C+$Diameter). Therefore, any nearest neighbor with the new distance is a nearest feasible neighbor in vanilla distance.

W3: Since the proposed graph-based data structure is very similar to FilteredDiskANN and NHQ, these methods should be used as baselines. Unfortunate, there are no comparison with these works in the experiment sections. The key parameter \lambda used in the proposed penalty distance has not been investigated (the value setting, sensitivity).

While our method does use ideas from these works, both FilterDiskANN and NHQ cannot handle the multi-filter problem. They are designed for very different usecases: FilterDiskANN can only handle one label. Of course, we can reduce the multi-filter problem to the one filter setting, this incurs an exponential blowup in the number of labels, which is prohibitive and impractical for all of our datasets.

NHQ on the other hand can easily be shown to give incorrect answers; we kindly refer the reviewer to our lower bound in Line 286.

We also thank the reviewer for the additional questions, and address them below.

Q1) What is the definition of space-time tradeoff of MultiFilterANN?

Intuitively, the less storage space you have for your datastructure, the less powerful the structure is and the worse the query time will be. Therefore, the spacetime tradeoff can be defined as the curve of possible query times for a given amount of storage space.

Q2) What are lower bounds of space or time complexity of algorithms for MultiFilterANN?

Since the problem is a generalization of subset query, the theoretical guarantees we give almost match the best known for subset query. Improving further on these has been a significant open problem for decades.

Q3) In the query phase, the algorithm only uses $\hat{dist}$. The proposed $dist'$ is only for theoretical interest. Is this correct?

During search, we only use the hat distance.

Q4) Could you report a sensitivity analysis for the λ parameter?

Lambda just needs to be larger than the diameter of the dataset, as the proof of Theorem 6.1 shows.

W5. There are significant room to improve the paper.

For example, Related work need to be rewritten. First half of the content is just listing the citations without any discussions. The second half includes only claims. E.g. CAPS seems to suffer significantly as m increase --> By how it suffers? SERF works with range queries --> MFANN is not designed for range queries as well These ideas do not generalize to multi filters --> Reasons? ACORN do not scale well to even simple AND predicates --> By how?

We thank the reviewer for the feedback on our related works section. We will include an expanded discussion of related approaches and clean up our related works section in our final submission.

Thank for detailed feedbacks.

Regarding W1 and W4:

From what I understand, Theorem 4.1 and 4.2 are both for worst-case scenarios. My raised issue is that if the found x from CIP does not satisfy the filtering condition but there is another y that satisfies the filtering condition, then your theoretical guarantees are not correct. If you cannot find all points (e.g. x and y) from CIP then you cannot guarantee any (1 + \eps)-ANNS.

If you search for all points, then the running time of CIP component will be the bottleneck, and I do not think applying LSH on each CIP group will reduce the total running time to $o(n)$.

Even \lambda is fixed for every point, the Euclidean squared distance $|q - x|^2$ varies for each points, so I do not think your argument is convincing.

Given the raised weakness (potential errors) in theory and lack of comparison with key competitors (e.g. NHQ - in practice the proposed solution is similar to NHQ, only different from the heuristic fused distance), I maintain the rating.

We thank the reviewer for their thoughtful comments regarding the weaknesses of our submission. All presentation issues will be corrected in a final version.

Below, we try to give a high-level explanation of our theoretical framework, and its relevance to our empirically supported algorithms. To put it concisely, our theoretical contributions are two-fold: first, we give the first mathematical formalization of the practically important MultiFilterANN problem by connecting it with subset query and the classical ANNS problems. Second, and more importantly, our results show that the difficulty of the MultifilterANN problem is mostly dominated by the subset query requirement. This is why the stated bounds of Theorem 4.2 generalize Theorem 4.1. Indeed, the subset query problem (i.e. given n base subsets of some universe U, and a query subset Sq, find at least one base subset Sv which is a superset of Sq) is very challenging from a theoretical perspective, and Theorem 4.1 is the state-of-art for the problem. In the proof of Theorem 4.2, we show that it is possible to combine a good ANN structure cleverly with the CIP-based partitioning data-structure for subset query to solve MultifilterANN.

But how does this translate to real-world algorithms?

We conduct a rigorous undertaking by studying two plausible candidate algorithms for MultifilterANN, namely ParlayIVF2 (a clustering-based algorithm for MultifilterANN) and Filtered-Vamana (a graph-based algo that apparently only works for queries coming with single filters as opposed to AND predicates). We demonstrate different bad examples for both in worst-case guarantees. These examples motivate our final algorithm, which a) combines clustering and graph-based methods to avoid these bad examples, and b) modifies the graph search algorithm (which has invariably been a greedy algorithm in prior work) to escape the bad examples we constructed. Finally, we note that prior work on the 1 filter case, such as FilteredDiskANN, is not directly applicable to the multi-filter setting. While it is true that we can reduce the multi-filter problem to the one filter setting, this incurs an exponential blowup in the number of labels, which is prohibitive and impractical for all of our datasets.

We also thank the reviewer for the raised questions. We address them below:

• Is your theory only applicable to ℓ2 as the proof of Theorem 4.1 would imply?

No, Theorem 4.1 also holds for many other distances that have efficient underlying nearest neighbor data structures, such as $\ell_1$ and $\ell_p$ norms between $1$ and $2$. However the most practically motivated setting is $\ell_2$.

• How do you select the cut-offs for your proposed query planning method? Are they the same for each dataset?

The cutoffs are based on the data dimension and the selectivity of the query filter's predicate (i.e. how often the predicate appears in the document data). In general, around 30,000 vectors in 100 dimensions can be brute-forced in a few milliseconds, and so we scale it depending on the dimension (e.g., 10000 for 300 dims). For the clustering threshold, we use a slightly larger number (50000) to ensure that only the queries with commonly occurring predicates get routed to the graph algorithm.

• How difficult are the hyperparameters $\lambda$ and $\tau$ to set?

We have used only one set of fixed values in the paper – $\lambda$ depends on the scale of distances, and we set it to 10, since the norms were all close to the unit scale. The value of $\tau$ was fixed to 1 in this paper, to allow one filter mismatch. This we suspect depends on the number of clauses in the query predicate. Our algorithm is quite robust to $\lambda$ value, and we could not test other $\tau$ values due to lack of datasets with multiple query clauses. We will add some ablation studies by varying these parameters which will indicate how robust they are.

• Which data set is used for the ablation study on removing the penalty search?

We used the Wikipedia dataset, and will state it clearly in a final submission. We thank the reviewer for pointing this out.

• Why does ParlayIVF2 only have one instance on the Pareto frontier in two of the experiments?

We ran a large parameter sweep for ParlayIVF2 and ACORN, and in these cases described by the reviewer, their code simply resulted in a cluster of points all in the same latency-recall regime, so we simply reported one of these numbers.

It is also not clear how relevant the studied problem (MultiFilterANN) is. I am not deeply familiar with literature on filtered ANN search, but it seems that the recent related works cited by the authors only consider the special cases of one or two filters. In particular, I suspect that when there are multiple filters (for instance, |Sq|≥3), the simplest possible ad hoc approach (brute force search after finding the database points with correct labels) would often outperform more complicated filtered ANN methods, since in this case the set of database points matching all of query labels is probably quite small.

We thank the reviewer for raising a fair and reasonable concern. For MultifilterANN, the filter predicates that come with queries also come with a specificity, which denotes how common the valid documents are for that predicate within the document corpus. For small-scale demonstration experiments in research, the document corpus rarely exceeds a size of 10-50 million, and for |S_q| \geq 3, it would not be uncommon to expect 100-200 valid documents, for which a simple brute-force search is more than enough. However, in practice, the document corpus can easily reach a size in the magnitude of billions; here, valid documents for a sufficiently large predicate would now likely range in the millions. This is the primary use-case for a graph-based MFANNS approach (see FilteredDiskANN and ACORN), and we believe that our overall approach would shine here. The problem is very relevant [1, 2, 3, 4], and almost all real-world use-cases of ANN now come with additional filtering, and all the vector database services are forced to add this feature.

An analogous claim about scale has been made for multiple variants of the broader ANNS problem: for example, DiskANN, FilteredDiskANN, FreshDiskANN, and OOD-DiskANN [5, 6, 7, 8] each have sections devoted to performance on large-scale datasets. However, there is not enough publicly available data to support a similar claim for the multifilter setting – this remains a major open problem within the space in order to further research. With that said, this warrants additional discussion, and we can include it in a final version of our submission.

1. https://www.pinecone.io/learn/vector-search-filtering/
2. https://weaviate.io/developers/weaviate/search/hybrid
3. https://qdrant.tech/articles/hybrid-search/
4. https://docs.trychroma.com/guides#filtering-by-document-contents
5. https://papers.nips.cc/paper_files/paper/2019/file/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Paper.pdf
6. https://harsha-simhadri.org/pubs/Filtered-DiskANN23.pdf
7. https://arxiv.org/pdf/2105.09613
8. https://arxiv.org/pdf/2211.12850

You should include a direct comparison between the proposed graph method and the earlier filtered ANN methods (ParlayIVF and ACORN) (assuming the results of Section 7 are for the hybrid method described in Appendix E).

We thank the reviewer for the comment. ParlayIVF indeed is based on query planning, and has brute force or clustering to route to. Their approach does not use graphs for multiple filters, and resorts to graph-indices only for single filters at query time. As for ACORN, a scan of the code indicates that it does not include a brute-force layer, and relies only on graph indices. That said, the ACORN codebase assumes that the complete filter map of the set of points which satisfy the query predicate is known up front, and that is not counted in their reported latency numbers. While this operation is small at small scales, we suspect that this computation would quickly add to, and even dominate, the overall query latency for large datasets and complex predicates. Our approach, however, is much more forgiving to this filter-evaluation complexity, as it is only done on the fly, as the graph is being searched. We take your point though, and will try to include agnostic comparisons like number of distance comparisons vs recall, between ACORN graph and our graph algorithm in the final version of the paper, to obtain a more apples-to-apples comparison.

Another part that must be clarified significantly is the empirical evaluation in Section 7. In particular, it is unclear whether the results are obtained by using the graph-based method proposed in Section 6 or the hybrid methodology described in Appendix E?

We thank the reviewer for the comment. For the experiments, we do use the hybrid approach described in Appendix E, which is well-motivated by lessons 2 (query planning) and 3 (graph index benefits) from sections 4 and 5. Our experiments are comprehensive and demonstrate the need for all the approaches considered. For example, in The Wikipedia Dataset (Fig 1, left) and YFCC dataset (Fig 1, right), our hybrid algorithm and ParlayIVF perform the best, perhaps because of the need for bruteforce and clustering methods due to the filter specificity being less. On the Amazon Dataset, our approach and ACORN does the best. In terms of baselines, ParlayIVF is a bruteforce+clustering approach, while ACORN is a purely graph-based method. That said, you are correct that as written, the results could entirely be obtained using brute force or clustering-based searches, so we will add a table indicating how the queries are split across the three methods used in the hybrid search. Figure 6 illustrates how our purely-graph algorithm performs as a function of query specificity, with dense predicates (having many base points satisfying the predicate) performing best, and the rare filters are not as great. We have made a nomenclature error with the interpretation of specificity in the figure though, and will fix it. The best-performing curve is for queries whose predicates are satisfied by a large fraction of base points.

We thank the reviewer for their thoughtful comments and concerns. Below, we address their concerns (split over multiple comments).

The authors propose (in Section 6) a graph-based algorithm for MultiFilterANN problem ... The authors should clarify what is the connection between the empirical algorithm and the theoretical discussion of Section 4.

We believe a major contribution of our theoretical results is conceptual: we connect the widely studied nearest neighbor problem to the theoretically challenging problem of subset query, to give the first formalization of the practically important MultiFilterANN problem. A priori, it is not clear how these two separate components (nearest neighbor search and subset query) are connected or interact. Conceptually, our theoretical results show that the difficulty of the problem is dominated by the subset query requirement. This is not an artifact of theory: in our experiments we also observe that as the subset query constraints become more involved, the performance of all methods degrade. Furthermore, the lessons learned from our theoretical algorithm (lessons 1 - 4) directly translate into our empirical algorithm design process, e.g., Theorem 4.1 and Section 4 show that some form of query planning is needed which is a lesson we use in our empirical algorithm design. Furthermore, Theorem 6.1, and Lemma D.1 gives provable guarantees about the specific graph algorithm we use in our experiments. The theorem shows how we can bound the doubling dimension of such a new metric using the original dimension, and DiskANN is the only known graph algorithm which comes with provable guarantees.