Pith. sign in

REVIEW 1 cited by

Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2402.04713 v1 pith:ZZI5PN2V submitted 2024-02-07 cs.IR cs.DBcs.LG

classification cs.IRcs.DBcs.LG
keywords entrypointadaptivegraph-basedselectionanalysisannsapproximate
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We present a theoretical and empirical analysis of the adaptive entry point selection for graph-based approximate nearest neighbor search (ANNS). We introduce novel concepts: $b\textit{-monotonic path}$ and $B\textit{-MSNET}$, which better capture an actual graph in practical algorithms than existing concepts like MSNET. We prove that adaptive entry point selection offers better performance upper bound than the fixed central entry point under more general conditions than previous work. Empirically, we validate the method's effectiveness in accuracy, speed, and memory usage across various datasets, especially in challenging scenarios with out-of-distribution data and hard instances. Our comprehensive study provides deeper insights into optimizing entry points for graph-based ANNS for real-world high-dimensional data applications.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table

    cs.CV 2025-06 conditional novelty 6.0 of 10

    A fast post-processing method for approximate nearest neighbor search uses a precomputed cutoff table to greedily prune candidates and guarantee a minimum pairwise distance among the returned results.

Pith tools