Scaling Package Queries to a Billion Tuples via Hierarchical Partitioning and Customized Optimization
Summary: Progressive Shading scales package-query ILP optimization to billions of tuples via hierarchical refinement, avoiding SketchRefine’s premature pruning under tight constraints. Dynamic Low Variance partitioning and custom Dual Reducer/Parallel Dual Simplex solvers deliver adaptive, orders-of-magnitude faster processing. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Anh L. Mai (New York University)
- 2. Pengyu Wang (New York University)
- 3. Azza Abouzied (New York University)
- 4. Matteo Brucato (Microsoft)
- 5. Peter J. Haas (University of Massachusetts Amherst)
- 6. Alexandra Meliou (University of Massachusetts Amherst)
BibTeX Citation
@article{mai_vldb24,
title = {{Scaling Package Queries to a Billion Tuples via Hierarchical Partitioning and Customized Optimization}},
author = {Mai, Anh L. and Wang, Pengyu and Abouzied, Azza and Brucato, Matteo and Haas, Peter J. and Meliou, Alexandra},
journal = {PVLDB},
series = {{VLDB} '24},
volume = {17},
number = {5},
pages = {1146--1158},
doi = {10.14778/3641204.3641222},
url = {https://doi.org/10.14778/3641204.3641222},
year = {2024}
}Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,389 | Query Refinement for Diverse Top-k Selection | 2024 | SIGMOD | 5.8895166e-05 |
| 8,598 | Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation | 2025 | VLDB | 5.4049137e-05 |
| 10,908 | Stochastic SketchRefine: Scaling In-Database Decision-Making under Uncertainty to Millions of Tuples | 2025 | VLDB | 5.093636e-05 |
| 11,170 | Counterfactual Explanation at Will, with Zero Privacy Leakage | 2024 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,823 | Query Processing on Tensor Computation Runtimes | 2022 | VLDB | 8.0893814e-05 |
| 3,144 | Interactive Data Exploration Using Semantic Windows | 2014 | SIGMOD | 7.7134729e-05 |
| 3,214 | Searchlight: Enabling Integrated Search and Exploration over Large Multidimensional Data | 2015 | VLDB | 7.6325181e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 984 | Analyzing Plan Diagrams of Database Query Optimizers | 2005 | VLDB |
| 2 | 4,596 | Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams | 2004 | SIGMOD |
| 3 | 8,983 | Stochastic Package Queries in Probabilistic Databases | 2020 | SIGMOD |
| 4 | 1,044 | Fine-grained Partitioning for Aggressive Data Skipping | 2014 | SIGMOD |
| 5 | 1,286 | Adaptive Optimization of Very Large Join Queries | 2018 | SIGMOD |
| 6 | 4,481 | Dynamically Optimizing Queries over Large Scale Data Platforms | 2014 | SIGMOD |
| 7 | 9,969 | Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation | 2026 | VLDB |
| 8 | 9,446 | Parallelizing Query Optimization on Shared-Nothing Architectures | 2016 | VLDB |
| 9 | 10,908 | Stochastic SketchRefine: Scaling In-Database Decision-Making under Uncertainty to Millions of Tuples | 2025 | VLDB |
| 10 | 6,853 | Scalable Package Queries in Relational Database Systems | 2016 | VLDB |