AI Paper Atlas

Research map / Graph learning / Graph algorithms and clustering

High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility

Cong Fu, Changxu Wang, Deng Cai

TPAMI 2021 · Graph learning › Graph algorithms and clustering · approach: Graph distance and retrieval · 126 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
replace NSG with NSSG (angle-based pruning)graph index · GIST1M, Crawl, GloVe at 95% precisionqueries per second: 35%, 15%, and 20% speed-up on Crawl, GloVe, and GIST1MImproved
replace NSG with NSSGgraph index · SIFT1Msearch performance: almost the sameNo clear effect
replace NSG with NSSGgraph index · Deep100Mqueries per second: 5% to 15% speed-up over NSGImproved
replace NSG with NSSG edge selectiongraph index · GIST1Medge selection time: 620+735 (s) -> 620+144 (s)Improved
replace NSG with NSSGgraph index · Deep100M (single thread)indexing time: 16 hours -> 11 hoursImproved
replace NSG with NSSG, parallel 16-subgraphgraph index · Deep100Mindexing time: 3.53 hours -> 2.6 hoursImproved
compute KNN neighbors on the fly instead of storing KNN graphNSSG · Deep100Mmemory: 37 GB less than the NSG; 56 GB at mostImproved
use SSG with alpha=60 instead of MRNGgraph · SIFT10Ksearch path length (unindexed): 4.98 -> 3.91Improved
use SSG with alpha=30 instead of alpha=60 (ablation)SSG · SIFT10Kaverage out-degree: 40 -> 121Hurt
truncate SSG alpha=60 to limit degree (ablation)SSG · SIFT10Kaverage out-degree: 40 -> 19Improved
use alpha=60 instead of smaller alpha (ablation)NSSG · GIST1M, Crawl, GloVesearch performance: 60 best on all except SIFT1M where 55 is bestImproved
use alpha=55 instead of 60 (ablation)NSSG · SIFT1Msearch performance: 55 slightly betterNo clear effect

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy