Back to papers
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
- 1122
- Venue
- PODS
- Year
- 1997
- Pagerank
- 0.00011699446
- Overall Rank
- 1,488 | 89.65%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 14 of 14 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 79 |
A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces |
1998 |
VLDB |
0.00056242144 |
| 774 |
Algorithms for Mining Distance-Based Outliers in Large Datasets |
1998 |
VLDB |
0.00016865771 |
| 1,182 |
On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) |
1999 |
PODS |
0.00013455963 |
| 3,900 |
Tight bounds for 2-dimensional indexing schemes |
1998 |
PODS |
6.6518011e-05 |
| 4,536 |
Data Series Progressive Similarity Search with Probabilistic Quality Guarantees |
2020 |
SIGMOD |
6.104642e-05 |
| 5,013 |
A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries |
1998 |
PODS |
5.7598528e-05 |
| 5,979 |
External Memory Algorithms |
1998 |
PODS |
5.2450009e-05 |
| 7,433 |
Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse |
1999 |
SIGMOD |
4.7314388e-05 |
| 7,650 |
amdb: An Access Method Debugging Tool |
1998 |
SIGMOD |
4.6882482e-05 |
| 8,767 |
Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes |
2009 |
PODS |
4.456315e-05 |
| 9,601 |
SkyPIE: A Fast & Accurate Oracle for Object Placement |
2024 |
SIGMOD |
4.3177432e-05 |
| 11,434 |
Data-Independent Space Partitionings for Summaries |
2021 |
PODS |
4.1945683e-05 |
| 11,554 |
On the I/O Complexity of the k-Nearest Neighbors Problem |
2020 |
PODS |
4.1945683e-05 |
| 12,106 |
Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility |
2012 |
PODS |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 13 of 13 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,363 |
Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores |
2011 |
VLDB |
8.9580928e-05 |
| 12,564 |
Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases |
2005 |
VLDB |
4.1945683e-05 |
| 3,991 |
Beyond Simple Aggregates: Indexing for Summary Queries |
2011 |
PODS |
6.5553055e-05 |
| 4,108 |
Cracking the Database Store |
2005 |
CIDR |
6.4440088e-05 |
| 2,003 |
Indexing for Data Models with Constraints and Classes (Extended Abstract) |
1993 |
PODS |
9.8126082e-05 |
| 5,682 |
Optimal Indexing Using Near-Minimal Space [Extended Abstract] |
2003 |
PODS |
5.372736e-05 |
| 10,748 |
Benchmarking Adaptive Multidimensional Indices |
2025 |
VLDB |
4.1945683e-05 |
| 1,182 |
On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) |
1999 |
PODS |
0.00013455963 |
| 3,900 |
Tight bounds for 2-dimensional indexing schemes |
1998 |
PODS |
6.6518011e-05 |
| 5,013 |
A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries |
1998 |
PODS |
5.7598528e-05 |