On the Analysis of Indexing Schemes

Summary: Introduces a formal framework for indexing workloads (dataset + query set) that quantifies efficiency via storage redundancy and access overhead. Presents upper and lower bounds and trade-offs for multi-dimensional range and set-query indexing. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1121
Venue: PODS
Year: 1997
Pagerank: 0.00010536001
Overall Rank: 1,512 | 89.63%
DOI: 10.1145/263661.263688

Incoming Non-self Citations Over Time

Authors

1. Joseph M. Hellerstein (University of California Berkeley)
2. Elias Koutsoupias (University of California Los Angeles)
3. Christos H. Papadimitriou (University of California Berkeley)

BibTeX Citation

@inproceedings{hellerstein_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{On the Analysis of Indexing Schemes}},
        url = {https://dl.acm.org/doi/10.1145/263661.263688},
        doi = {10.1145/263661.263688},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hellerstein, Joseph M. and Koutsoupias, Elias and Papadimitriou, Christos H.},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
693	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00014918477
1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010482997
3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.9814651e-05
4,212	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.8283344e-05
4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	6.5348792e-05
6,289	External Memory Algorithms	1998	PODS	5.9261616e-05
7,497	amdb: An Access Method Debugging Tool	1998	SIGMOD	5.6037176e-05
7,612	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	5.5834218e-05
8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	5.3483178e-05
9,735	SkyPIE: A Fast & Accurate Oracle for Object Placement	2024	SIGMOD	5.227679e-05
11,632	Data-Independent Space Partitionings for Summaries	2021	PODS	5.093636e-05
11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	5.093636e-05
12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
354	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00020355578
1,129	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00012061727
1,370	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00010997795
2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.3214272e-05
2,135	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.1133971e-05
2,774	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	8.1372328e-05
3,790	OODB Indexing by Class-Division	1995	SIGMOD	7.1239529e-05
4,070	Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension	1996	VLDB	6.9272604e-05
6,053	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.9939282e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,811	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB
2	12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
3	4,285	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS
4	3,876	Cracking the Database Store	2005	CIDR
5	2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
6	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
7	10,984	Benchmarking Adaptive Multidimensional Indices	2025	VLDB
8	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
9	3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS
10	4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS