Current state: ["Under Discussion"]
ISSUE: #17599
PRs:
Keywords: search, range search, radius, low bound, high bound
Released:
By now, doing "search" in Milvus will return TOPK most similar results for each vector being searched.
This MEP is about to realize a functionality named "range search". User specifies a range scope -- including radius low bound and radius high bound, Milvus does "range search", and also returns TOPK sorted results with distance falling in this range scope.
Many users request Milvus to realize a "range search" functionality. With this capability, user can
We reuse the SDK interface Search() to do "range search". Only add 2 more parameters "radius_low_bound" and "radius_high_bound" into params.
When "radius_low_bound" and "radius_high_bound" are specified, Milvus does range search; otherwise, Milvus does search.
As shown in the following figure, set "radius_low_bound": 1.0, "radius_high_bound": 2.0 in search_ params.params.
default_index = {"index_type": "HNSW", "params":{"M": 48, "efConstruction": 500}, "metric_type": "L2"} collection.create_index("float_vector", default_index) collection.load() search_params = {"metric_type": "L2", "params": {"ef": 32, "radius_low_bound": 1.0, "radius_high_bound": 2.0}} res = collection.search(vectors[:nq], "float_vector", search_params, limit, "int64 >= 0") |
// range search parameter legacy check virtual bool CheckRangeSearch(Config& cfg, const IndexType type, const IndexMode mode); // range search virtual DatasetPtr QueryByRange(const DatasetPtr& dataset, const Config& config, const faiss::BitsetView bitset); // brute force range search static DatasetPtr BruteForce::RangeSearch(const DatasetPtr base_dataset, const DatasetPtr query_dataset, const Config& config, const faiss::BitsetView bitset); |
We add 3 new APIs CheckRangeSearch(), QueryByRange() and BruteForce::RangeSearch() to support range search, these APIs are already available since knowhere-v1.3.0.
This API is used to get all unsorted results with distance "better than radius" (for L2: < radius; for IP: > radius).
PROTO | DatasetPtr QueryByRange(const DatasetPtr&, const Config&, const faiss::BitsetView); |
INPUT | Dataset { Config { knowhere::meta::RADIUS: - // radius for range search } |
OUTPUT | Dataset { |
LIMS is with length "nq+1", it's the offset prefix sum for result IDS and result DISTANSES. The length of IDS and DISTANCES are the same but variable.
Suppose N queried vectors is with label: {0, 1, 2, ..., n-1}
The result counts for each queried vectors are: {r(0), r(1), r(2), ..., r(n-1)}
Then the data in LIMS will be like this: {0, r(0), r(0)+r(1), r(0)+r(1)+r(2), ..., r(0)+r(1)+r(2)+...+r(n-1)}
The total range search result num is: LIMS[nq]
The range search result for each query vector is: IDS[lims[n], lims[n+1]) and DISTANCE[lims[n], lims[n+1])
The memory used for IDS, DISTANCE and LIMS are allocated in Knowhere, they will be auto-freed when Dataset deconstruction.
By new, following index types support QueryByRange():
BinaryIDMAP
BinaryIVF
IDMAP
IVF_FLAT
IVF_PQ
IVF_SQ8
HNSW
Range search completely reuses the call stack from SDK to segcore.
Segcore search flow will be updated as this flow chart, range search related change is marked RED.
In API query::SearchOnSealedIndex() and BruteForceSearch(), when "radius_low_bound" and "radius_high_bound" are set, range search is called; otherwise, search is called.
For API query::SearchOnSealedIndex(), the result returned by knowhere::QueryByRange() will be sorted and filtered, only results with distance falling in the range scope will be returned.
The same as API BruteForceSearch(), the result returned by knowhere::BruteForce::RangeSearch() will be sorted and filtered, only results with distance falling in the range scope will be returned.
The output of range search is exactly as same as the result of search.
There is no compatibility issue.
For Knowhere
There is no public data set for range search. I have created range search data set based on sift1M and glove200.
You can find them in NAS:
test/milvus/ann_hdf5/sift-128-euclidean-range.hdf5
test/milvus/ann_hdf5/glove-200-angular-range.hdf5
test/milvus/ann_hdf5/binary/sift-4096-hamming-range.hdf5
For Milvus
The previous proposal of this MEP is let range search return all results with distances better than a "radius".
The project implementation of the previous proposal will be much more complicated than current proposal.
Cons:
Current proposal is better than the previous one in all respects.