On the Complexity of the View-Selection Problem
Summary: Shows greedy can be Ω(n) (≥n/12) suboptimal, and unless P=NP any poly-time algorithm is n^{1−ε}-inapproximable for infinitely many n, even for bounded-degree/depth posets. Bicriteria (αk) algorithms also fail; view-selection essentially inapproximable, so focus on restricted practical cases and empirical heuristics. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Howard Karloff
- 2. Milena Mihail
Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,048 | Graph Cube: On Warehousing and OLAP Multidimensional Networks | 2011 | SIGMOD | 9.6914395e-05 |
| 5,682 | Optimal Indexing Using Near-Minimal Space [Extended Abstract] | 2003 | PODS | 5.372736e-05 |
| 7,081 | The Polynomial Complexity of Fully Materialized Coalesced Cubes | 2004 | VLDB | 4.8413336e-05 |
| 7,475 | Optimizing Index for Taxonomy Keyword Search | 2012 | SIGMOD | 4.7191809e-05 |
| 9,964 | Classifier Construction Under Budget Constraints | 2022 | SIGMOD | 4.2269436e-05 |
| 10,116 | Stochastic Submodular Data Forgetting | 2026 | SIGMOD | 4.1945683e-05 |
| 11,595 | Minimization of Classifier Construction Cost for Search Queries | 2020 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 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 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,933 | Answering Top-k Queries Using Views | 2006 | VLDB | 7.8679669e-05 |
| 1,112 | Materialized View Selection and Maintenance Using Multi-Query Optimization | 2001 | SIGMOD | 0.00013917776 |
| 584 | Answering Queries with Aggregation Using Views | 1996 | VLDB | 0.0001971526 |
| 8,295 | View Selection over Knowledge Graphs in Triple Stores | 2021 | VLDB | 4.5435639e-05 |
| 5,144 | Scalable Query Rewriting: A Graph-Based Approach | 2011 | SIGMOD | 5.6651982e-05 |
| 9,259 | Materializing Views with Minimal Size To Answer Queries | 2003 | PODS | 4.3690661e-05 |
| 82 | Answering Queries Using Views (Extended Abstract) | 1995 | PODS | 0.00054402763 |
| 13,754 | The View-Selection Problem Has an Exponential-Time Lower Bound for Conjunctive Queries and Views | 2002 | PODS | - |
| 4,194 | On the Complexity of Approximate Query Optimization | 2002 | PODS | 6.3697822e-05 |
| 3,583 | A Formal Perspective on the View Selection Problem | 2001 | VLDB | 6.9463532e-05 |