Page Comparison

Current state: ["Under Discussion"]

...

both radius low bound and radius high bound MUST be set
falling in range scope means

Metric type	Behavior
IP	radius_low_bound < distance <= radius_high_bound
L2 and other metric types	radius_low_bound <= distance < radius_high_bound

Motivation(required)

Many users request the "range search" functionality. With this capability, user can

...

In Knowhere, two new parameters "radius_low_bound" and "radius_high_bound" are passed in via config, and range search will return all un-sorted results with distance falling in this range scope.

Metric type	Behavior
IP	radius_low_bound < distance <= radius_high_bound
L2 or other metric types	radius_low_bound <= distance < radius_high_bound

We add 3 new APIs CheckRangeSearch(), QueryByRange() and BruteForce::RangeSearch() to support range search.

...

This API returns all unsorted results with distance falling in the specified range scope.

PROTO

virtual DatasetPtr
QueryByRange(const DatasetPtr& dataset, const Config& config, const faiss::BitsetView bitset)

INPUT

Dataset {
knowhere::meta::TENSOR: - // query data
knowhere::meta::ROWS: - // rows of queries
knowhere::meta::DIM: - // dimension
}

Config {

knowhere::meta::RADIUS_LOW_BOUND: -

knowhere::meta::RADIUS_HIGH_BOUND: -

}

OUTPUT

Dataset {
knowhere::meta::IDS: - // result IDs with length LIMS[nq]
knowhere::meta::DISTANCE: - // result DISTANCES with length LIMS[nq]
knowhere::meta::LIMS: - // result offset prefix sum with length nq + 1
}

...

This API does range search for no-index dataset, it returns all unsorted results with distance "better than radius" (for IP: > radius; for others: < radius).

PROTO

static DatasetPtr
RangeSearch(const DatasetPtr base_dataset,
            const DatasetPtr query_dataset,
            const Config& config,
            const faiss::BitsetView bitset);

INPUT

Dataset {
knowhere::meta::TENSOR: - // base data
knowhere::meta::ROWS: - // rows of base data
knowhere::meta::DIM: - // dimension
}