Blog
Unlock Advanced Recommendation Engines with Milvus' New Range Search

Unlock Advanced Recommendation Engines with Milvus' New Range Search

Nov 09, 20236 min read

Introduction

In similarity search, developers often need help with limitations, particularly when balancing the quality and diversity of search results. Enter Milvus' new feature: Range Search. This post will outline what Range Search is, when to use it over traditional Top-K Search, and delve into its technical architecture and usage guide.

What is Range Search?

Range Search in Milvus offers granular control over vector similarity in search results, allowing you to specify a distance range for relevant vectors. This feature addresses the limitations of traditional KNN searches in recommendation systems, where results can be either too similar or too diverse compared to your expectations.

When to choose range search over Top-K search?

Traditional KNN search has two fundamental shortcomings:

Unbalanced Recommendations: It may recommend items that are too similar, affecting recommendation quality. For instance, a sports news aggregator might end up recommending multiple articles about the same football game to a user, simply because they read one article about the game. This could crowd out diverse content, making the recommendations feel repetitive and less engaging.
System Constraints: The Top-K parameter maxes out at 16,384, posing issues for large-scale data queries and resource utilization. Consider a scenario where you're querying a dataset of millions of products. The Top-K limit of 16,384 means you might miss out on thousands of relevant products that could be of interest to the user, while also straining your system resources as it tries to process and transmit this large volume of data.

Range Search solves these problems. It enables a balanced set of results by allowing you to define a distance range for vector similarity. Adding parameters like radius and optional range_filter offers a more nuanced control, eliminating the need for post-query filtering. This nuanced control makes Range Search ideal for applications requiring precise control over search results.

Technical details behind Range Search

Now that we've explored what Range Search is and when to use it let's dive into its architecture and algorithms. This exploration will provide critical insights into its strengths, limitations, and integration with third-party libraries.

The Range Search flow is built upon the existing Search flow, reusing most data pathways at the higher levels. Below is an outline of the steps taken when a search request is received:

SDK Handles Search Request: The SDK receives a user search request containing parameters like radius and range_filter.
Proxy Generates SearchTask: Upon receiving the search request, the proxy creates a SearchTask and passes it to the query node.
Querynode to Segcore: The query node invokes the Search interface in Segcore through a cgo call.
Segcore Parsing: Segcore analyzes the parameters in search_param. If a radius parameter is present, it invokes knowhere::RangeSearch.

Knowhere and Third-Party Libraries: Knowhere (the Milvus core vector execution engine) then routes the call to the corresponding third-party library's range_search function based on the index type.

All the third-party library indexes we support are configured to perform one-sided Range Search. "One-sided" means they only accept a single 'radius' parameter and return all unsorted results within that radius. The table below outlines the Range Search strategies for different index types.

Index Type	Search Strategy
IDMAP / BIN_IDMAP	Brute Force Search
IVF_xxx / SCANN / BIN_IVF_xxx (updated)	Start searching from the bucket closest to the center point. Stop the search when one of the following conditions is met: 1. All buckets have been searched 2. No vectors meeting the condition are found in a bucket.
HNSW (self-developed)	Start the search from the uppermost layer and identify the vector closest to the target, then proceed to the next layer down. Continue this process layer by layer until it reaches the nearest neighbor in the bottommost (1st) layer. From there, conduct a Breadth-First Search (BFS) starting from this nearest neighbor and continuing until all visited points and their outward neighbors fall outside the desired range.
DISKANN	Start with l_search = min_l_search. For each iteration, set l_search = 2 * l_search. Stop the search when one of the following conditions is met: 1. The number of results returned in an iteration is less than l_search / 2 2. l_search > max_l_search.

Both HAMMING and JACCARD metric types offer full support for range search for binary data types. However, the SUBSTRUCTURE/SUPERSTRUCTURE metric types are incompatible with range search, as their semantics are based on a true/false value system. As for float-type indexes, those using L2, IP, and COSINE metrics are fully compatible with range search.

The table below outlines the detailed index and metric types compatible with Range Search.

	L2	IP	COSINE	HAMMING	JACCARD
BIN_IDMAP				√	√
BIN_IVF_FLAT				√	√
IDMAP	√	√	√
IVF_FLAT	√	√	√
IVF_PQ	√	√	√
IVF_SQ8	√	√	√
HNSW	√	√	√	√	√
SCANN	√	√	√
DISKANN	√	√	√

How to use Range Search in Milvus

To use Range Search in Milvus, you'll need to modify the search parameters in your search request. Here's a step-by-step guide, including a sample Python code snippet:

Prerequisites

Ensure that Milvus is installed and running.
Make sure you've created a collection and indexed it.

Important Range Search parameters

radius: This is a mandatory parameter that determines whether the search request will perform a range search or a regular search.
range_filter: This is an optional parameter. If provided, it will perform a secondary filtering on the results. If not specified, the function will return the results directly.

By configuring these two parameters, you can fine-tune the behavior of your Range Search queries for different application needs. With that in mind, let's look at some sample code to help you get started.

default_index = {
    "index_type": "HNSW",
    "metric_type": "L2",
    "params": {"M":48,"efConstruction":500}
}
collection.create_index("float_vector", default_index)
search_params = {
    "metric_type": "L2",
    "limit": TOPK,
    "params": {"ef":32,"range_filter":1.0,"radius":2.0}
}
res = collection.search(vectors[:nq], "float_vector", search_params, limit)

Metrics considerations

Now that you understand how to use Range Search, it's essential to consider the impact of metric types on your queries. Depending on the metric type you choose, you should check the Radius as we suggested in the table below.

Metric Type	Radius	Similar	Not similar
L2	[0.0, inf]	0.0	inf
IP	[-inf, inf]	inf	-inf
COSINE	[-1.0, 1.0]	1.0	-1.0
HAMMING	[0, n]	0	n
JACCARD	[0.0, 1.0]	0.0	1.0

Additionally, the range_filter should follow these rules:

For L2/Hamming/Jaccard, range_filter < radius
For IP/Cosine, range_filter > radius

Conclusion

Range Search in Milvus is not limited to recommendation engines; it has broader applications in areas like content matching, anomaly detection, and NLP search tasks. By leveraging parameters like radius and range_filter, you can precisely tailor your queries to fit these diverse use cases.

Ready to take control of your search requests? Range Search is now available for public preview on Zilliz Cloud. Upgrade to the Zilliz Cloud beta version or download Milvus 2.3.x to give it a try. Your insights are key to its ongoing improvement, so if you encounter any issues or have suggestions, we're all ears. Let's make Range Search better together.

Leon Cai
Senior Software Engineer at Zilliz

Content

Start Free, Scale Easily

Try the fully-managed vector database built for your GenAI applications.

Try Zilliz Cloud for Free