This paper addresses the challenge of computing Pareto sums in high-dimensional spaces or with large inputs, presenting an adaptive (1+ )-approximation scheme that leverages the monotone structure of skylines for sublinear time complexity. The algorithm provides provable error bounds and demonstrates significant speedup versus accuracy trade-offs on synthetic benchmarks.
Key findings
An adaptive (1+ )-approximation scheme for Pareto sum computation is presented.
The algorithm exploits the monotonicity of Pareto frontiers for recursive partitioning.
Theoretical guarantees on approximation error and time complexity are provided.
Experimental results show up to 4× speedup while maintaining low approximation errors.
Limitations & open questions
The algorithm's effectiveness is highly dependent on the exploitable skyline structure.
Performance on datasets without clear clustering or correlation may be less pronounced.