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,054 | Graph Cube: On Warehousing and OLAP Multidimensional Networks | 2011 | SIGMOD | 9.682102e-05 |
| 5,695 | Optimal Indexing Using Near-Minimal Space [Extended Abstract] | 2003 | PODS | 5.3675705e-05 |
| 7,077 | The Polynomial Complexity of Fully Materialized Coalesced Cubes | 2004 | VLDB | 4.8367109e-05 |
| 7,474 | Optimizing Index for Taxonomy Keyword Search | 2012 | SIGMOD | 4.7146619e-05 |
| 9,963 | Classifier Construction Under Budget Constraints | 2022 | SIGMOD | 4.2229209e-05 |
| 10,116 | Stochastic Submodular Data Forgetting | 2026 | SIGMOD | 4.1905499e-05 |
| 11,599 | Minimization of Classifier Construction Cost for Search Queries | 2020 | SIGMOD | 4.1905499e-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.0011695087 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,936 | Answering Top-k Queries Using Views | 2006 | VLDB | 7.8579393e-05 |
| 1,110 | Materialized View Selection and Maintenance Using Multi-Query Optimization | 2001 | SIGMOD | 0.00013902997 |
| 583 | Answering Queries with Aggregation Using Views | 1996 | VLDB | 0.00019705383 |
| 8,288 | View Selection over Knowledge Graphs in Triple Stores | 2021 | VLDB | 4.5392079e-05 |
| 5,144 | Scalable Query Rewriting: A Graph-Based Approach | 2011 | SIGMOD | 5.6597671e-05 |
| 9,263 | Materializing Views with Minimal Size To Answer Queries | 2003 | PODS | 4.3648789e-05 |
| 82 | Answering Queries Using Views (Extended Abstract) | 1995 | PODS | 0.00054430106 |
| 13,768 | The View-Selection Problem Has an Exponential-Time Lower Bound for Conjunctive Queries and Views | 2002 | PODS | - |
| 4,189 | On the Complexity of Approximate Query Optimization | 2002 | PODS | 6.3681294e-05 |
| 3,586 | A Formal Perspective on the View Selection Problem | 2001 | VLDB | 6.9402014e-05 |