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)
Incoming Non-self Citations Over Time
Authors
- 1. C. Heeren
- 2. H. V. Jagadish
- 3. L. Pitt
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,475 | Optimizing Index for Taxonomy Keyword Search | 2012 | SIGMOD | 4.7191809e-05 |
Previous
Page 1 / 1
Next
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.0011708144 |
| 158 | Automated Selection of Materialized Views and Indexes for SQL Databases | 2000 | VLDB | 0.00040071492 |
| 237 | An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server | 1997 | VLDB | 0.00031726304 |
| 391 | Indexing and Querying XML Data for Regular Path Expressions | 2001 | VLDB | 0.00024564567 |
| 516 | AutoAdmin "What-if" Index Analysis Utility | 1998 | SIGMOD | 0.00021196031 |
| 817 | Covering Indexes for Branching Path Queries | 2002 | SIGMOD | 0.00016352717 |
| 869 | APEX: An Adaptive Path Index for XML Data | 2002 | SIGMOD | 0.00015788339 |
| 3,074 | On the Complexity of the View-Selection Problem | 1999 | PODS | 7.6110034e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,003 | Indexing for Data Models with Constraints and Classes (Extended Abstract) | 1993 | PODS | 9.8126082e-05 |
| 7,475 | Optimizing Index for Taxonomy Keyword Search | 2012 | SIGMOD | 4.7191809e-05 |
| 1,766 | Indexing Moving Points (Extended Abstract) | 2000 | PODS | 0.000106236 |
| 8,767 | Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes | 2009 | PODS | 4.456315e-05 |
| 11,554 | On the I/O Complexity of the k-Nearest Neighbors Problem | 2020 | PODS | 4.1945683e-05 |
| 1,488 | On the Analysis of Indexing Schemes | 1997 | PODS | 0.00011699446 |
| 12,295 | Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes | 2009 | PODS | 4.1945683e-05 |
| 7,985 | Secondary Index Optimization | 1975 | SIGMOD | 4.613363e-05 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |
| 8,919 | Efficient Indexes for Diverse Top-k Range Queries | 2020 | PODS | 4.427232e-05 |