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: 3347
Venue: SIGMOD
Year: 2001
Pagerank: 5.4102697e-05
Overall Rank: 8,570 | 41.21%
DOI: 10.1145/375663.375716

Incoming Non-self Citations Over Time

Authors

1. Christian A. Lang (University of California Santa Barbara)
2. Ambuj K. Singh (University of California Santa Barbara)

BibTeX Citation

@inproceedings{lang_sigmod01,
        title = {{Modeling High-Dimensional Index Structures using Sampling}},
        author = {Lang, Christian A. and Singh, Ambuj K.},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375716},
        url = {https://dl.acm.org/doi/10.1145/375663.375716},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,176	Predicting Cost Amortization for Query Services	2011	SIGMOD	6.3326746e-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
1	235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
2	3,741	Spatial Online Sampling and Aggregation	2016	VLDB
3	11,644	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD
4	149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD
5	8,359	High-Dimensional Index Structures: Database Support for Next Decade's Applications	1998	SIGMOD
6	1,512	On the Analysis of Indexing Schemes	1997	PODS
7	694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
8	7,419	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB
9	9,411	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD
10	8,790	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD