Skip to content

feat: discover duplicate edges with uncapped IVF radius queries - #10304

Open
jackye1995 wants to merge 5 commits into
lance-format:mainfrom
jackye1995:jack/dedup-similarity-search
Open

jackye1995 wants to merge 5 commits into
lance-format:mainfrom
jackye1995:jack/dedup-similarity-search

Conversation

@jackye1995

@jackye1995 jackye1995 commented Oct 24, 2026 •

Copy link
Copy Markdown
Contributor

Add an alternative to comparing only vectors stored in the same IVF partition: use each live source vector as a query against IVF cells in every active index segment, then emit threshold-matching edges.

Execution flow

Pinned dataset + source (segment, partition)
  → live source row IDs → original source vectors
  → for each source, select IVF cells in every target segment
  → uncapped radius scan over stored vector codes
  → verify candidate distances on original vectors
  → stream canonical (min_row_id, max_row_id, distance)

find_similar_pairs_in_partition discovers edges for one source scope. It searches all target segments, so matches may cross the source partition and segment boundary. Radius scans return every qualifying candidate within the scanned cells; no top-k truncation is applied. Self edges are excluded. Discovery can be asymmetric, so matches are retained regardless of which endpoint found the other; repeated canonical edges may be emitted and can be merged by the caller.

Probe selection and distance semantics

  • Automatic probing considers the nearest two centroids by default. Centroid-boundary geometry determines whether an additional cell is within the query's threshold neighborhood.
  • Fixed nprobes selects a fixed number of nearest cells. max_nprobes changes the automatic candidate budget; counts must be positive and fixed probes cannot exceed an explicit maximum. Budgets apply independently to each target segment.
  • Candidate scans use the index metric/quantizer; final distances are verified on original vectors. This removes candidate false positives, while restricted probes and quantization can still omit matches.
  • The scan operates on IVF vector codes independently of HNSW traversal. It does not add HNSW acceleration or claim top-k ANN throughput.

Requires one current-format logical vector index covering the pinned dataset, with stale indexed values rejected. Source/target range blocking is a separate change in #10305.

Coverage includes centroid-boundary matches, more than 100 radius neighbors, nested vector columns and automatic/fixed probe budgets.

@claude claude Bot left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Claude Code Review

This pull request is from a fork — automated review is disabled. A repository maintainer can comment @claude review to run a one-time review.

@github-actions github-actions Bot added A-index Vector index, linalg, tokenizer enhancement New feature or request labels Oct 24, 2026
lance-gatekeeper[bot]

This comment was marked as outdated.

@lance-gatekeeper lance-gatekeeper Bot added K-approved Latest Gatekeeper recommendation permits acceptance. K-risk Latest Gatekeeper recommendation includes a non-blocking risk. labels Oct 24, 2026
@lance-gatekeeper lance-gatekeeper Bot removed K-approved Latest Gatekeeper recommendation permits acceptance. K-risk Latest Gatekeeper recommendation includes a non-blocking risk. labels Oct 24, 2026
lance-gatekeeper[bot]

This comment was marked as outdated.

@lance-gatekeeper lance-gatekeeper Bot added K-approved Latest Gatekeeper recommendation permits acceptance. K-risk Latest Gatekeeper recommendation includes a non-blocking risk. labels Oct 24, 2026
@lance-gatekeeper lance-gatekeeper Bot removed K-risk Latest Gatekeeper recommendation includes a non-blocking risk. K-approved Latest Gatekeeper recommendation permits acceptance. labels Oct 24, 2026
lance-gatekeeper[bot]

This comment was marked as outdated.

@lance-gatekeeper lance-gatekeeper Bot added K-approved Latest Gatekeeper recommendation permits acceptance. K-risk Latest Gatekeeper recommendation includes a non-blocking risk. labels Oct 24, 2026
@lance-gatekeeper lance-gatekeeper Bot removed K-risk Latest Gatekeeper recommendation includes a non-blocking risk. K-approved Latest Gatekeeper recommendation permits acceptance. labels Oct 24, 2026
lance-gatekeeper[bot]

This comment was marked as outdated.

@lance-gatekeeper lance-gatekeeper Bot added K-approved Latest Gatekeeper recommendation permits acceptance. K-risk Latest Gatekeeper recommendation includes a non-blocking risk. labels Oct 24, 2026
@lance-gatekeeper lance-gatekeeper Bot removed K-risk Latest Gatekeeper recommendation includes a non-blocking risk. K-approved Latest Gatekeeper recommendation permits acceptance. labels Oct 24, 2026

@lance-gatekeeper lance-gatekeeper Bot left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

⚠️ Gate recommendation: approve with a non-blocking risk.

Automatic probing now considers at most two centroids per target segment by default, so threshold matches can be omitted even with IVF_FLAT. Raising max_nprobes broadens discovery; quantization retains its separate recall trade-off.

The partition-level approach remains reasonable when partitions fit worker memory. Whole-partition loading and per-query candidate buffering mean the smaller source and verification batches still do not establish a memory budget.

Tests cover L2/IVF_FLAT, including nested projections and the probe-budget behavior. I could not run them because the required Rust 1.98.1 is unavailable and cannot be installed into this environment’s read-only rustup directory. Quantized, other-metric, and multi-segment behavior remains unverified end to end.

@lance-gatekeeper lance-gatekeeper Bot added K-approved Latest Gatekeeper recommendation permits acceptance. K-risk Latest Gatekeeper recommendation includes a non-blocking risk. and removed K-risk Latest Gatekeeper recommendation includes a non-blocking risk. K-approved Latest Gatekeeper recommendation permits acceptance. labels Oct 24, 2026

This branch has not been deployed

No deployments
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

A-index Vector index, linalg, tokenizer enhancement New feature or request K-approved Latest Gatekeeper recommendation permits acceptance. K-risk Latest Gatekeeper recommendation includes a non-blocking risk.

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant