Threshold phenomena in k-dominant skylines of random samples

DOI10.1137/110856952zbMATH Open1268.68072arXiv1111.6224OpenAlexW2038640416MaRDI QIDQ2840977FDOQ2840977

Authors: Hsien-Kuei Hwang, Tsung-Hsi Tsai, Wei-Mei Chen 

Publication date: 24 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: Skylines emerged as a useful notion in database queries for selecting representative groups in multivariate data samples for further decision making, multi-objective optimization or data processing, and the $k$-dominant skylines were naturally introduced to resolve the abundance of skylines when the dimensionality grows or when the coordinates are negatively correlated. We prove in this paper that the expected number of $k$-dominant skylines is asymptotically zero for large samples when $1lekled-1$ under two reasonable (continuous) probability assumptions of the input points, $d$ being the (finite) dimensionality, in contrast to the asymptotic unboundedness when $k=d$. In addition to such an asymptotic zero-infinity property, we also establish a sharp threshold phenomenon for the expected ($d-1$)-dominant skylines when the dimensionality is allowed to grow with $n$. Several related issues such as the dominant cycle structures and numerical aspects, are also briefly studied.

Full work available at URL: https://arxiv.org/abs/1111.6224

Recommendations

• K-Dominance in Multidimensional Data: Theory and Applications
• K-dominance in multidimensional data: theory and applications
• Towards estimating expected sizes of probabilistic skylines
• \(k\)-dominant skyline queries on incomplete data
• The most-likely skyline problem for stochastic points

zbMATH Keywords

computational geometrymultiobjective optimizationPareto optimalitymaximadominanceasymptotic approximationsskylinerandom samplesthreshold phenomenaaveragecase analysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Zero-one laws (60F20) Database theory (68P15) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Cited In (5)

• K-Dominance in Multidimensional Data: Theory and Applications
• Towards estimating expected sizes of probabilistic skylines
• From proximity to utility: a Voronoi partition of Pareto optima
• K-dominance in multidimensional data: theory and applications
• \(k\)-dominant skyline queries on incomplete data

This page was built for publication: Threshold phenomena in \(k\)-dominant skylines of random samples

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840977)