Filtered Range Search in DiskANN

Filtered Range Search

This document covers experimentation on the best algorithms for filtered range search.

Algorithms

Range Search Algorithm

The current range search algorithm is the algorithm described in this paper, modulo the optional early stopping routine. At a high level, it conducts a regular KNN search with a fixed $L_{search}$, and then, if the initial KNN search yields more than some fraction $f$ times $L_{search}$ points within the range, it moves on to a version of greedy search with an unbounded queue length, starting from the in-radius points it discovered during the initial search. The unbounded search can visit unlimited vertices, but it restricts its search frontier to points within some slack factor $s \geq 1.0$ times the range search radius. Then, only points falling within the radius are returned. Range search within DiskANN is implemented here.

Filtered Search Algorithm

DiskANN currently supports two filtered search variants: inline search with optional adaptive $L_{search}$, and multihop search. Since the main use cases for filtered search usually use inline search with adaptive L, we will focus here on that search variant. Inline filtered search executes a regular KNN search, with the addition of recording any filter-satisfying elements encountered during search, and passing only those on as the returned result. If the adaptive L feature is enabled, the inline filtered search will estimate the filter match rate after a certain amount of search, and then increase $L_{search}$ to search for longer if the match rate is low. See this wiki page for more information about filtered search algorithms.

Options for Filtered Range Search

Given that we want to adapt inline filtered search for range search, the presence of filters naturally leads to the following questions:

1. Should the initial KNN search be a regular inline filtered search, or should it use adaptive L?
2. Should the algorithm use matching points only to determine whether to continue search and to seed the starting points for the search, or should it use all points within the radius?

We will choose the best algorithm for filtered range search based on the matrix of these options.

Datasets

Unfortunately there are no natural datasets for filtered range search that I know of. Instead, we will evaluate the options by artificially selecting a radius for two 10000-size query subsets of two existing filtered datasets, Caselaw and YFCC. Since we don't have a radius that is semantically meaningful, we choose a radius by looking at the frequency distribution of filter-matching, in-range results. We want a good number of points to have no results as well of a sizable diversity of result sizes.

For Caselaw, we use two query subsets: "high," with match rate .1-.5, and "medium," with match rate .005-.01. Histograms showing the frequency distribution of the chosen radius are shown below.

For YFCC, we use two query subsets: "high," with match rate .114-.338, and "medium," with match rate .005-.037. Histograms showing the frequency distribution of the chosen radius are shown below.

Experimental Results

We benchmark the following variants:

1. Inline filtered search using all in-radius points to decide whether to continue (labeled Inline + All)
2. Inline filtered search using filter-satisfying in-radius points to decide whether to continue (labeled Inline + Filter)
3. Adaptive L search using all in-radius points to decide whether to continue (labeled Adaptive + All)
4. Adaptive L search using filter-satisfying in-radius points to decide whether to continue (labeled Adaptive + Filter)

Results on Caselaw are shown in the following plots. The left plot shows the entire matrix of options, while the right-hand plot shows the two "All" lines on their own plot to help compare them more closely.

Caselaw, high match rate:

Caselaw, low match rate:

Results on YFCC are shown in the following plots. The left plot shows the entire matrix of options, while the right-hand plot shows the two "All" lines on their own plot to help compare them more closely.

YFCC, high match rate:

YFCC, medium match rate:

Further Experiments and Discussion

The experimental results are a bit strange. Using filter-satisfying results in YFCC to decide to continue follows a strange curve, where increasing the initial $L_{search}$ can sometimes decrease recall. One explanation for why this might happen is as follows: in YFCC, there are many more points within the radius that don't satisfy the filter than which do satisfy the filter. Then, in an initial inline search with a low $L_{build}$, you only have to find a handful of those filter-satisfying, in-range points to decide to continue (in fact, those data points to the left are L values from 1 to 5). For those searches, they will continue on to the exhaustive in-radius search and thus find more filter-satisfying points. On the other hand, if $L_{search}$ is a bit higher, it is harder to find $L_{search}$ points that are filter-satisfying and in-range, and the search will terminate early too often.

If this were true, a way to test it would be to check whether Caselaw has more correlation between distance and filter matching than YFCC. We do this by generating groundtruth without any filters for the radius used for each dataset, and computing the ratio of filter-satisfying points within the radius to all points within the radius. The statistics for this calculation are as follows:

YFCC, medium match rate: 1.4%

YFCC, high match rate: 12.2%

Caselaw, low match rate: 40.3%

Caselaw, high match rate: 97.0%

Indeed, we find that in Caselaw, there is strong correlation between whether a point is within the radius and whether it satisfies the predicate (i.e. the within-radius match rate is higher than the dataset's average match rate). This confirms our assumption that Caselaw is an "easier" dataset for filtering, with more correlation between filter and distance. This also confirms our suspicion about the strange behavior we saw with range search on YFCC when using filter-satisfying points to decide whether to continue the search, and it provides good confidence that the filtered range search algorithm performs well under a wide range of match rates, both within-radius and over the whole dataset.

Overall Discussion. With confirmation that the results on YFCC make sense given the match rate statistics, the experimental results strongly support the conclusion that we should always use all results to decide whether to continue to the next round of search. They also support the conclusion that we do not need to use the optional adaptive L feature of inline search. It has slightly worse performance in some cases, and while it increases the maximum recall in one case, it is already in the realm of three 9s so this is not a significant gain. With those results on adaptive L, combined with the fact that this is not a feature in especially high demand at the moment, we will not use adaptive L in filtered range search.