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,474 | Optimizing Index for Taxonomy Keyword Search | 2012 | SIGMOD | 4.7146619e-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.0011695087 |
| 160 | Automated Selection of Materialized Views and Indexes for SQL Databases | 2000 | VLDB | 0.00040053897 |
| 237 | An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server | 1997 | VLDB | 0.00031727601 |
| 392 | Indexing and Querying XML Data for Regular Path Expressions | 2001 | VLDB | 0.00024546229 |
| 517 | AutoAdmin "What-if" Index Analysis Utility | 1998 | SIGMOD | 0.00021193179 |
| 812 | Covering Indexes for Branching Path Queries | 2002 | SIGMOD | 0.00016343476 |
| 864 | APEX: An Adaptive Path Index for XML Data | 2002 | SIGMOD | 0.00015781693 |
| 3,079 | On the Complexity of the View-Selection Problem | 1999 | PODS | 7.6036669e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,010 | Indexing for Data Models with Constraints and Classes (Extended Abstract) | 1993 | PODS | 9.8046157e-05 |
| 7,474 | Optimizing Index for Taxonomy Keyword Search | 2012 | SIGMOD | 4.7146619e-05 |
| 1,764 | Indexing Moving Points (Extended Abstract) | 2000 | PODS | 0.0001062234 |
| 8,764 | Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes | 2009 | PODS | 4.4520434e-05 |
| 11,558 | On the I/O Complexity of the k-Nearest Neighbors Problem | 2020 | PODS | 4.1905499e-05 |
| 1,485 | On the Analysis of Indexing Schemes | 1997 | PODS | 0.00011698762 |
| 12,303 | Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes | 2009 | PODS | 4.1905499e-05 |
| 7,988 | Secondary Index Optimization | 1975 | SIGMOD | 4.6089395e-05 |
| 1,183 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013444058 |
| 8,921 | Efficient Indexes for Diverse Top-k Range Queries | 2020 | PODS | 4.4229886e-05 |