Modeling High-Dimensional Index Structures using Sampling

Summary: Proposes a sampling-based cost model to predict index-page accesses for high-dimensional structures—dimensionality-agnostic and able to preserve data clusters. Provides a general page-layout estimator with error compensation and a memory-efficient implementation that yields fast predictions, up to 100x faster than building/probing the full index. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3285
Venue: SIGMOD
Year: 2001
Pagerank: 4.6560482e-05
Overall Rank: 7,771 | 45.94%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Christian A. Lang
2. Ambuj K. Singh

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,207	Predicting Cost Amortization for Query Services	2011	SIGMOD	7.3818982e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
4,029	Spatial Online Sampling and Aggregation	2016	VLDB	6.51315e-05
11,446	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD	4.1945683e-05
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
8,079	High-Dimensional Index Structures: Database Support for Next Decade's Applications	1998	SIGMOD	4.5914115e-05
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
1,105	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00013990395
8,605	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4865144e-05
9,346	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD	4.3532026e-05
9,758	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2879116e-05