TL;DR
This paper tackles the challenge of finding the maximum coverage of a universe of elements using a fixed number of sets in a streaming setting, specifically optimizing a sublinear-space algorithm. The authors significantly speed up this algorithm by reducing the reliance on complex hashing techniques and removing a computationally expensive sketching component, achieving substantial performance gains without sacrificing approximation quality or space efficiency.
What Problem Does This Paper Address?
The Maximum Set Coverage problem, a classic NP-hard problem, aims to select k sets from a collection of m sets to maximize the total number of unique elements covered. While approximation algorithms exist, they often struggle with large datasets. The "streaming" context, where data arrives sequentially, adds further constraints. A notable prior algorithm, MACH, achieved a good approximation (1-1/e - ε) with sublinear space complexity (poly-logarithmic in m and n, the universe size). However, MACH relied on two computationally expensive techniques: y-independent hash functions for subsampling (reducing the problem's scope) and F₀-sketching for estimating set sizes. This paper addresses the significant runtime bottleneck introduced by these techniques, aiming to accelerate MACH* while maintaining its desirable space and approximation properties.
Methods
The authors build upon the MACH* algorithm, which uses a multi-pass approach with subsampling and thresholding. Their key contributions are:
- Optimized Subsampling: They re-analyze the theoretical bounds and show that the required independence factor for the hash functions can be reduced from Ω(ε⁻²k log m) to Ω(k log m). This means simpler, faster hash functions can be used, leading to a significant speedup.
- Removal of F₀-Sketching: The paper demonstrates that F₀-sketching, used for estimating set sizes, can be entirely removed without asymptotically affecting the approximation guarantees. This eliminates a major computational bottleneck.
- New Algorithm (MACH'): These optimizations lead to a new algorithm, MACH', which is faster and simpler than MACH*.
- Theoretical Analysis: The paper provides rigorous theoretical analysis to support their claims, including new bounds on the probability of achieving the desired approximation factor with reduced independence.
Datasets
The paper evaluates their algorithms on four real-world datasets:
- SocialNet: A collection of individuals linked by a friendship relation.
- UKUnion: Snapshots of webpages from the .uk domain.
- Webbase: A collection of interlinked websites.
- Webdocs: Another collection of interlinked websites.
These datasets are described by their size (n in elements, m in sets) and other characteristics like maximum set size and element frequency.
Key Insights and Ideas
- The Bottleneck Was Hashing: The core insight is that the high independence requirement of the hash functions in MACH* was the primary driver of its slow runtime. Reducing this requirement dramatically improves performance.
- Sketching is Overkill: F₀-sketching, while theoretically sound, proved to be an unnecessary computational burden for the desired approximation quality in this context. Its removal simplifies the algorithm without significant loss.
- Pairwise Independence is Often Enough: Surprisingly, even simple pairwise-independent hash functions (the lowest form of independence) yield competitive results in practice, significantly outperforming the original MACH* in terms of speed.
- Practical vs. Theoretical Trade-offs: The paper highlights that while theoretical guarantees might be slightly weaker with simpler hashing, the practical speedups are substantial, making these "lighter" algorithms more attractive for large-scale applications.
Key Results
- Significant Speedup: The optimized algorithm (MACH') achieves speedups of several orders of magnitude compared to the original MACH algorithm, particularly for larger values of k*. For instance, Figure 1 shows that MACH' with reduced independence is 10x to 1000x faster.
- Reduced Independence Factor: The required independence factor for subsampling hash functions was reduced from Ω(ε⁻²k log m) to Ω(k log m).
- Approximation Quality Maintained: Despite the speed improvements and removal of F₀-sketching, the algorithm maintains a strong approximation factor of 1-1/e - δ(ε). Experimental results (Figure 3) show that the coverage quality is comparable to the greedy algorithm and the original MACH* across various datasets and parameters.
- Space Efficiency Preserved: The sublinear space complexity of O(ε⁻²k) is maintained. Figure 2 demonstrates that MACH' is significantly more space-efficient than other streaming algorithms.
Limitations and Future Work
- Theoretical Guarantees for Pairwise Independence: While experiments show pairwise independence works well, the theoretical guarantees for this specific case are weaker than for higher independence. The paper mentions a new lower bound for pairwise independence, but further theoretical exploration might be beneficial.
- "Bad Guess" Handling: The paper acknowledges that in rare cases (less than 1%), the algorithm might select a "wrong guess" for the optimal coverage, leading to solutions with fewer than k sets. While this is a minor issue in practice, further work could explore more robust methods for guess selection.
- Parallel Implementation: The paper mentions that MACH' is implemented in a way that naturally lends itself to parallelization, but a full parallel implementation was not performed. This is a clear avenue for future work to further exploit the algorithm's structure.
- Exploring Other Submodular Functions: The paper focuses on Maximum Coverage, but the techniques used could potentially be applied to accelerate other submodular maximization problems in streaming settings.
Summary updated