<![CDATA[Group Skyline (G-Skyline) queries identify Pareto-optimal groups of k objects that are not dominated by any other group of the same size, extending skyline analysis from individual objects to combinatorial group selection. Existing streaming algorithms, including the sliding-window methods of Dong et al. and the incremental candidate-maintenance approach of Guo et al., explicitly enumerate and materialize candidate groups, making their scalability dependent on output cardinality. Under anti-correlated attribute distributions, the number of qualifying groups can grow combinatorially, exceeding practical memory and computation limits before an exact result is obtained. This paper introduces DC3-GSky, an exact algorithm that reformulates G-Skyline group counting as a frontier decision-diagram traversal over the dominance poset, merging structurally equivalent intermediate states rather than enumerating groups individually. On a streaming benchmark of 10,000 active sensor readings under correlated, independent, and anti-correlated distributions, DC3-GSky remains within 3.3% of the fastest enumeration baseline for small outputs (0.0251 s vs. 0.0243 s on independent data) and computes the exact count of 166,616,670,000 groups, matching C(10,000,3), in 0.0752 s. Uncapped small-scale validation further indicates that enumeration would require approximately 27 hours and 27 TB of memory for the linear baseline and roughly 12 million years for the quadratic baseline. These results show that the exact G-Skyline scalability depends critically on the output cardinality and representation strategy, not the input size alone.]]>
Copyrights © 2026
