Abstract
Reconstructing an underlying data distribution from a set of query selectivities is a fundamental problem at the intersection of database systems and computational geometry. This paper demonstrates that while finding an exact solution is NP-hard for dimensions $d \ge 2$, a near-linear time approximation algorithm is achievable. By integrating the Multiplicative Weights Update (MWU) method with geometric sampling techniques, the authors present a framework for building compact data synopses that satisfy observed query results within provable error bounds.
Introduction
In modern database systems, selectivity estimation—predicting the fraction of rows a query will return—is critical for efficient query optimization. While databases typically rely on histograms or random sampling of raw data, this paper explores the "inverse" problem: constructing a synthetic data distribution based solely on a workload of previous queries and their observed selectivities. This is particularly relevant in scenarios where raw data is inaccessible due to privacy constraints or massive scale.
The primary challenge lies in the computational complexity of the task. In a $d$-dimensional space, the number of potential "cells" formed by the intersection of $n$ queries grows polynomially as $O(n^d)$. Consequently, finding a distribution that perfectly matches all observations becomes intractable as the number of queries and dimensions increases.
Problem Formulation and Complexity
The authors frame the problem as finding a discrete distribution—a set of points with associated weights—that minimizes the discrepancy between the model's predicted selectivities and the actual observed values.
A key contribution of the paper is the proof that this problem is NP-complete for axis-aligned rectangles in two or more dimensions, regardless of whether the error is measured using $L_1, L_2, \text{ or } L_\infty$ metrics. This hardness result justifies the shift from seeking exact solutions to developing efficient approximation algorithms.
Algorithmic Approach
To overcome the limitations of exact Linear Programming (LP) formulations, which require $O(n^d)$ variables, the authors employ several advanced techniques:
- Multiplicative Weights Update (MWU): This iterative meta-algorithm reduces the global optimization problem into a sequence of simpler decision problems. In each round, the algorithm adjusts the weights of the queries based on how well the current distribution satisfies them.
- Geometric Implicit Representation: Rather than materializing every possible cell in the arrangement, the distribution is represented implicitly. The core task in each MWU iteration becomes finding the "weighted deepest point"—the location covered by the maximum total weight of query regions.
- Sampling and $\epsilon$-Approximations: To accelerate the search for the deepest point, the authors use random sampling. This allows the algorithm to find an approximately deepest point in time that scales primarily with the desired error bound $\delta$ rather than the total number of queries $n$.
Key Results
The theoretical analysis yields several significant findings:
- Efficient Approximation: The developed Monte Carlo algorithm constructs a distribution of size $O(\delta^{-2})$ with an additive error of at most $\delta$.
- Near-Linear Runtime: The algorithm achieves a runtime of $O((n + \delta^{-d})\delta^{-2} \text{polylog } n)$. For a fixed dimension and error tolerance, this performance is nearly linear relative to the number of queries.
- Generality: The framework is not limited to rectangles; it extends to more complex semi-algebraic shapes, including balls and half-spaces.
- Conditional Optimality: Based on the $FPT \neq W[1]$ conjecture, the authors suggest that the exponential dependence on dimension $d$ is likely unavoidable, making their algorithm near-optimal for this class of problems.
Conclusion and Future Work
This research provides a robust theoretical framework for learning data distributions from query feedback. While the algorithm is highly efficient in low-dimensional spaces, the "curse of dimensionality" remains a challenge for high-attribute datasets. Future work may involve extending these geometric techniques to handle more complex database operations, such as joins and aggregations, where query structures are significantly more intricate.
Summary updated