[C API] Add svs_index_search_range (radius search)

Đang mở
  • Có gì không ổn?
#425 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 5 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
25/100
Loại issue
Tính năng
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
c, cpp
Lĩnh vực
api, search

Hướng nghiên cứu

Start with the existing svs_index_search_topk declaration in svs_c.h (around line 1316) and the CSR svs_search_results_t layout, then compare with DynamicVamanaIndexImpl::range_search in bindings/cpp/src/dynamic_vamana_index_impl.h. The new entry point must follow the same buffer-reuse and threadpool rules, add the max_results cap signal, and honour the per-metric radius contract. Done means a declared and implemented svs_index_search_range with tests for L2, dot product and cosine, including the cap-reached case.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Summary

Please add a radius search to the C API: given a query and a threshold, return every vector within that threshold. Today the only C API search is svs_index_search_topk (svs_c.h:1316). C_API_Design.md (line 300) lists range search as a future extension, and the CSR layout of svs_search_results_t was designed to carry variable per-query result counts for it (svs_c.h:365-368).

Why now

valkey-search added range queries in valkey-io/valkey-search#985, FT.SEARCH ... @v:[VECTOR_RANGE <radius> $blob], merged 2026-10-02. Every vector index now has to implement VectorBase::SearchRange(query, radius, filter).

valkey-search's SVS_VAMANA index uses only the C API. Without a radius search there, it approximates one:

  1. Run svs_index_search_topk with k up to the configured cap, search.max-nonvector-search-results-fetched (100,000 by default).
  2. Keep the results within the radius.
  3. When the cap is reached with its farthest result still in range, scan every stored vector exactly.

This works, but it sizes the search by the cap rather than by how many vectors are actually in range, and the exhaustive scan is O(N).

Ask

A C API entry point alongside svs_index_search_topk, for example:

SVS_API bool svs_index_search_range(
    svs_index_h index,
    const float* queries,
    size_t num_queries,
    float radius,
    size_t max_results,              /* per query; 0 = no limit */
    svs_search_results_t* out_results,
    svs_search_params_h search_params /*=NULL*/,
    svs_id_filter_i id_filter /*=NULL*/,
    svs_error_h out_err /*=NULL*/
);

with this contract:

  1. Results. Per-query counts vary, written in the existing CSR layout (offsets, total_results). Ordering within a row doesn't matter to us.
  2. Radius is in the index metric's own units, and documented per metric. For L2, results have distance <= radius. For dot product and cosine, results have similarity >= radius. A non-positive threshold must be accepted for dot product and cosine: valkey-search's distance radius r maps to the similarity threshold 1 - r, which is <= 0 whenever r >= 1.
  3. max_results cap. When a query has more than max_results vectors in range, return max_results of them and report that the cap was reached, for example through a flag or a per-query count. valkey-search then falls back to an exact scan, so it needs to know the result is incomplete rather than get a silently truncated one.
  4. Threading. Run on the threadpool installed with svs_index_builder_set_threadpool_custom, as svs_index_search_topk does. valkey-search installs a pool that runs on the calling thread so SVS starts no threads of its own.
  5. Filtering. Same svs_id_filter_i contract as svs_index_search_topk with filter_rate() <= 0 (intel/ScalableVectorSearch#415): no sampling, no early exit on hit rate, and return the matches found.

How this differs from the C++ range search

The C++ runtime bindings already provide range search: DynamicVamanaIndex::range_search (bindings/cpp/include/svs/runtime/vamana_index.h:88), implemented in DynamicVamanaIndexImpl::range_search (bindings/cpp/src/dynamic_vamana_index_impl.h:216). It walks batch_iterator in distance order, in batches of the search window size, and stops at the first result outside the radius. That traversal suits this request too. What differs is the contract around it:

C++ range_search This request (C API)
Interface C++ virtual method; results through a ResultsAllocator callback C function; results in svs_search_results_t CSR, with the buffer-reuse and struct_size rules svs_index_search_topk already follows
Radius validation Rejects radius <= 0 for every metric (line 226) Accepts any finite threshold for dot product and cosine (similarity can be <= 0); keeps > 0 for L2
Radius units Not documented per metric Documented per metric: distance <= for L2, similarity >= for dot product and cosine
Threading Runs on default_threadpool() (line 297) Runs on the threadpool installed on the index, like svs_index_search_topk
Result size Unbounded; reserves the search buffer's capacity per query and grows from there Capped by max_results, with a signal when the cap was reached
Filter IDFilter::is_member only svs_id_filter_i, with the filter_rate() <= 0 contract from #415
Errors Status / StatusException svs_error_h, like the other C API calls

Consumer context

  • valkey-search (ALGORITHM SVS_VAMANA) is built on the C API submodule, pinned at 8285340.
  • The current SearchRange fallback is in eshenayo/valkey-search (src/indexes/vector_svs.cc), part of the upstream draft valkey-io/valkey-search#1577.
  • With a native call, VectorSVS::SearchRange would become a single svs_index_search_range call. It would fall back to the exact scan only when SVS reports the cap was reached.
Ngôn ngữ chính
C++
Star
241
Fork
48
Merge trung bình
4 ngày 21 giờ
Pull request đã merge (30 ngày)
11

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của intel/ScalableVectorSearch

Tất cả issue của intel/ScalableVectorSearch

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.