Optimal Indexing Using Near-Minimal Space [Extended Abstract]

Summary: Index selection under space budget B: algorithm builds indices using O(B log m) space w.h.p. and attains average query cost opt_B (the optimum under space ≤B). Prove necessity: unless NP⊆n^{O(log log n)}, no poly-time algorithm using αB space attains cost < M^{1−ε}·opt_B, and quantify sampling error. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1295
Venue: PODS
Year: 2003
Pagerank: 5.7836523e-05
Overall Rank: 6,753 | 53.67%
DOI: 10.1145/773153.773177

Incoming Non-self Citations Over Time

Authors

1. C. Heeren (University of Illinois Urbana-Champaign)
2. H. V. Jagadish (University of Michigan)
3. L. Pitt (University of Illinois Urbana-Champaign)

BibTeX Citation

@inproceedings{heeren_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{Optimal Indexing Using Near-Minimal Space [Extended Abstract]}},
        url = {https://dl.acm.org/doi/10.1145/773153.773177},
        doi = {10.1145/773153.773177},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Heeren, C. and Jagadish, H. V. and Pitt, L.},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,896	Optimizing Index for Taxonomy Keyword Search	2012	SIGMOD	5.5201308e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.00071822821
87	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035281619
156	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00028636811
341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020704572
387	AutoAdmin "What-if" Index Analysis Utility	1998	SIGMOD	0.00019442332
718	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014642961
897	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00013339862
3,188	On the Complexity of the View-Selection Problem	1999	PODS	7.6547735e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
2	7,896	Optimizing Index for Taxonomy Keyword Search	2012	SIGMOD
3	1,611	Indexing Moving Points (Extended Abstract)	2000	PODS
4	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
5	11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
6	1,512	On the Analysis of Indexing Schemes	1997	PODS
7	12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
8	8,302	Secondary Index Optimization	1975	SIGMOD
9	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
10	9,073	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS