Range Search

A range search query is defined by a query vector and a search radius (epsilon, ε). The system retrieves every database vector whose distance from the query vector is less than or equal to ε. This is expressed as: {x in DB | distance(q, x) ≤ ε}. The result set size is variable and depends entirely on the data distribution and the chosen epsilon, unlike k-NN search which always returns a fixed number k of results.

Range search can be executed in two primary modes:

• Exhaustive (Linear) Scan: Computes the distance from the query to every vector in the database. This guarantees 100% recall but has O(N) time complexity, making it impractical for large-scale databases.
• Approximate Range Search: Uses an index (e.g., HNSW, IVF) to prune the search space, only exploring regions of the vector space likely to contain points within the radius. This trades perfect recall for sub-linear query latency. The approximation error manifests as missing some vectors that are within the radius (false negatives).

Range search is critical for applications requiring all items meeting a similarity threshold:

• Deduplication: Finding all near-duplicate images or documents within a tolerance.
• Anomaly Detection: Identifying all system logs or transactions that are 'far' from normal behavior (using a large radius).
• Clustering Seed Discovery: Finding dense regions by using a point as a query and a small radius to discover core points for algorithms like DBSCAN.
• Regulatory Compliance Retrieval: In legal or medical contexts, finding all records semantically related to a query beyond a certain confidence threshold.

The search radius (ε) is the most critical tuning parameter. Its optimal value is highly data-dependent and tied to the distance metric.

• Too Small: Returns very few or zero results, missing relevant items (low recall).
• Too Large: Returns an overwhelming number of results, including irrelevant ones (low precision), and increases query latency. Tuning involves analyzing the distance distribution in the dataset. A common method is to run k-NN queries for a sample, observe the distances to the k-th neighbor, and set ε based on a percentile of those distances.

Range search is often combined with metadata filtering in a hybrid query pattern. For example: 'Find all product images within a visual similarity radius of ε and where category = 'shoes' and price < 100.' Execution strategies include:

• Pre-filtering: Apply metadata filters first, then perform range search on the filtered subset. Risk: may exclude vectors whose metadata is filtered out but whose vectors are within range.
• Post-filtering: Perform the approximate range search first, then apply metadata filters to the results. Risk: if the filter is highly selective, few final results may remain. Advanced databases perform query planning to choose the optimal strategy dynamically.

Implementing efficient approximate range search requires specialized support within vector indices.

• Graph-based indices (HNSW): Can be adapted by traversing the graph and collecting all nodes within the radius, using the efSearch parameter to control the depth of the candidate list.
• Cluster-based indices (IVF): Search is confined to a subset of Voronoi cells whose centroids are within ε + cell_radius. The cell radius must be known or estimated.
• Tree-based indices (Annoy, KD-Tree): Prune branches of the tree where the minimum possible distance to any point in the branch exceeds ε. The primary trade-off is between recall, query latency, and memory overhead from the index structure.

Range search is used to identify outliers by finding data points that fall outside a normal operational radius. In fraud detection, legitimate transaction embeddings cluster tightly; any new transaction vector outside a small epsilon radius from known clusters is flagged for review.

• Financial Security: Detects novel fraud patterns not seen in training data.
• System Monitoring: Identifies server metrics or log embeddings deviating from a healthy baseline cluster.

Ensures data integrity by finding all items that are nearly identical. By setting a very small epsilon (search radius), the system retrieves all vectors representing near-duplicate content.

• Media Libraries: Identifies duplicate or highly similar images, videos, or documents.
• Customer Records: Finds database entries with highly similar user profile embeddings to merge records.
• Content Moderation: Flags user-generated content that is nearly identical to known prohibited material.

Directly maps to physical world queries when vectors represent latitude/longitude coordinates (e.g., 2D or 3D embeddings). A range search with a radius epsilon finds all points within a physical distance.

• Location-Based Services: "Find all restaurants within 5 miles."
• IoT & Logistics: "Find all sensors or vehicles within a geofenced area."
• Real-Estate Platforms: Retrieve all property listings within a specific neighborhood boundary.

Used in legal and financial contexts where retrieval must be complete and verifiable within a defined conceptual scope. Unlike top-K search, range search guarantees all relevant documents within a similarity threshold are returned for audit trails.

• eDiscovery: Retrieve all case law documents semantically related to a legal concept above a certainty threshold.
• Patent Search: Find all prior art within a specific technical similarity boundary to assess novelty.

Acts as a high-recall first-stage retriever in multi-stage search pipelines. A broad range search fetches a comprehensive candidate set, which is then passed to a slower, more precise model (e.g., a cross-encoder) for final reranking.

• Recommendation Systems: Generates all potentially relevant products or content for a user query before applying business logic filters.
• Retrieval-Augmented Generation (RAG): Ensures no relevant document is missed before the LLM synthesizes an answer, improving factual grounding.

In research domains, scientists need to explore all data points within a similarity bound to a prototype. Range search facilitates density-based clustering and region-of-interest analysis.

• Bioinformatics: Find all protein sequences within an evolutionary distance epsilon from a reference sequence.
• Astronomy: Identify all celestial objects with spectral signatures within a defined range of a known star type.
• Material Science: Retrieve all compounds with molecular embedding vectors similar to a target compound.

k-Nearest Neighbors (k-NN) Search is the most common vector query, retrieving the 'k' vectors most similar to a query point. Unlike Range Search, which uses a fixed radius (epsilon), k-NN returns a fixed number of results. The two are related: a Range Search can be seen as a variable-result k-NN query where 'k' is determined by the data density within epsilon. Many databases implement Range Search by performing a k-NN search and filtering results by distance.

• Primary Use: Retrieving a predictable number of top matches.
• Contrast with Range Search: Returns fixed count vs. variable count within fixed distance.

The Search Radius, denoted by epsilon (ε), is the core parameter defining a Range Search. It is the maximum allowable distance from the query vector for a result to be included. Setting epsilon requires domain knowledge of the distance metric and data distribution.

• Impact on Results: A small epsilon yields precise, high-similarity results but may return an empty set. A large epsilon increases recall but adds less relevant, noisy vectors.
• Tuning Challenge: Optimal epsilon is often data-dependent and may require calibration against a ground truth set to achieve desired recall/precision trade-offs.

Approximate Nearest Neighbor (ANN) Search refers to algorithms that find similar vectors with sub-linear time complexity by trading perfect accuracy for speed. Range Search is often implemented using underlying ANN indices (like HNSW or IVF). The ANN index quickly generates candidate vectors, and their exact distances are computed and compared to epsilon.

• Foundation for Scale: Enables fast Range Search over billion-scale vector collections.
• Accuracy Trade-off: The approximation can cause false negatives (vectors within epsilon are missed) and false positives (candidates outside epsilon are checked, adding overhead).

Filtered Search combines a vector similarity search (like Range or k-NN) with conditional metadata filters (e.g., category = 'news' AND date > '2024-01-01'). A Filtered Range Search retrieves all vectors within epsilon that also satisfy the metadata constraints.

• Implementation Strategies:
  • Pre-filtering: Apply metadata filters first, then perform Range Search on the subset. Efficient if filter is highly selective but can miss relevant vectors filtered out early.
  • Post-filtering: Perform Range Search first, then filter results by metadata. Guarantees all vectors within epsilon are considered but may return fewer final results than requested.
• Use Case: Scoping a semantic search to a specific tenant, time period, or product category.

A Distance Metric is the mathematical function that defines similarity between vectors. The choice of metric directly determines the shape and scale of the "range" in a Range Search. Common metrics include:

• Euclidean (L2) Distance: Measures straight-line distance. A range forms a hypersphere.
• Cosine Similarity: Measures angular separation. Often converted to a distance (e.g., 1 - cosine). A range forms a cone.
• Inner Product: For normalized vectors, correlates with cosine. Requires careful thresholding for ranges.

Critical Note: The epsilon value is meaningless without reference to the specific distance metric used for indexing and querying. An epsilon of 0.1 implies very different similarity thresholds for L2 versus cosine distance.

In production systems, a Range Search is often part of a multi-stage retrieval pipeline. A fast Candidate Generation phase uses an ANN index to produce a likely set of matches. These candidates are then re-ranked by computing their exact distances and applying the epsilon cutoff.

• Pipeline Example:
  1. ANN Probe: HNSW graph retrieves 1000 approximate nearest neighbors.
  2. Exact Distance Compute: Calculate precise L2 distance for all 1000 candidates.
  3. Range Filter: Apply epsilon, returning only candidates where distance <= ε.
• Performance: This architecture avoids a prohibitively slow exact search over the entire database while ensuring the final results are accurate with respect to the defined radius.