Finding k-Dominant G-Skyline Groups on High Dimensional Data
Lists
Only you see this
Abstract
Skyline query retrieves a set of skyline points which are not dominated by any other point and has attracted wide attention in database community. Recently, an important variant G-Skyline is developed. It aims to return optimal groups of points. However, when data dimensionality is high, G-Skyline result has too many groups, which makes that users cannot determine which groups are satisfactory. To find less but more representative groups of points, in this paper, we propose a novel concept of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -dominant G-Skyline, which first adopts <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -dominance to retrieve more representative points and then computes the groups not <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -dominated by others. In addition, we present a two-phase algorithm to efficiently compute <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -dominant G-Skyline groups. In the first phase, we construct a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$lk$ </tex-math></inline-formula> DG structure while pruning the points never included in any <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -dominant G-Skyline group as much as possible. In the second phase, using <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$lk$ </tex-math></inline-formula> DG, we propose two efficient <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -dominant G-Skyline searching methods SM-P and SM-G, which generate new candidate groups from single points and ancestor groups, respectively. Our experimental results indicate that our proposed algorithms are more efficient than the baseline methods on real and synthetic data sets.
BibTeX
@article{zhang2018finding,
author = {Kaiqi Zhang and Hong Gao and Xixian Han and Jinbao Wang},
title = {{Finding k-Dominant G-Skyline Groups on High Dimensional Data}},
journal = {IEEE Access},
year = {2018},
doi = {10.1109/access.2018.2873719},
}Loading related content...