Research map / Learning theory and algorithms / Prediction and decision losses

On Finding Hubs in High Dimensions with Sampling

AAAI 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Approximate nearest neighbor indexing · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes SamHub, a two-step sampling method that finds top-h hubs in high-dimensional data with O(sn) distance computations and theoretical sample-size guarantees, working for any distance measure.

Problem

Identifying hubs (points frequently appearing in many kNN lists) in high-dimensional data is O(n^2) with exact kNN and ANNS indexes are costly to build and limited to a few metrics.

Approach

Sample s points, compute their kNN over the full set to form a candidate hub set from the most frequent neighbors, then compute kNN of all points over only this candidate set to estimate k-occurrence counts, giving a distance-agnostic linear-cost hub detector with a probabilistic guarantee for the top hub.

Key results

• SamHub with 10% sampling achieves about 85% top-10 hub accuracy on L2 across studied datasets.
• On Gisette (L2), SamHub reaches 70% accuracy in 0.85s vs Hnswlib 60% at 2.38s index plus 1.29s query.
• On ADL1 with dot product, SamHub attains 100% top-10 hub accuracy in 0.25s versus 34.78s for exact kNN.

Measured effects reported in the paper

Surprising findings

• Hnswlib achieves 0% hub accuracy on Mutants and ADL1 with dot product despite its index cost, per the comparison table.

Limitations

• Accuracy depends on skewness; low-skewness data (e.g., DTW time series) needs larger sample ratios.
• The practical verifying step lacks the rigorous guarantee; only the validating-step variant is proven.
• Experiments are limited to top-10 hubs and a single CPU setup.

Experimental setup

Datasets: ADL1 Arr CNAE Dexter Diabetes DNA Gisette Heart Isolet Mini-ngs Mutants Optdigits

Benchmarks: ADL1 Arr CNAE Dexter Diabetes DNA Gisette Heart Isolet Mini-ngs Mutants Optdigits

Metrics: top-h hub accuracy running time skewness estimate kNN classification accuracy speedup

Baselines: Hnswlib Faiss-IVFPQ ScaNN Exact kNN Nicdm Dsl Lcent

Builds on: hubness reduction (local scaling, DSL, NICDM) Chernoff bounds approximate nearest neighbor search

Closest papers by meaning

• A Hubness Perspective on Representation Learning for Graph-Based Multi-View Clustering (CVPR 2025 · similarity 0.83)
• MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search (NeurIPS 2026 · similarity 0.83)
• Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.83)
• Efficient Precision and Recall Metrics for Assessing Generative Models using Hubness-aware Sampling (ICML 2024 · similarity 0.83)
• Hubness Change Point Detection (AAAI 2025 · similarity 0.83)
• Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.82)