Efficient Distance-based Representative Skyline Computation in 2D Space
Article
Article Title | Efficient Distance-based Representative Skyline Computation in 2D Space |
---|---|
ERA Journal ID | 32110 |
Article Category | Article |
Authors | Mao, Rui, Cai, Taotao, Li, Rong-Hua, Yu, Jeffery Xu and Li, Jianxin |
Journal Title | World Wide Web |
Journal Citation | 20 (4), pp. 621-638 |
Number of Pages | 18 |
Year | Jul 2017 |
Publisher | Springer |
Place of Publication | United States |
ISSN | 1386-145X |
1573-1413 | |
Digital Object Identifier (DOI) | https://doi.org/10.1007/s11280-016-0406-0 |
Web Address (URL) | https://link.springer.com/article/10.1007/s11280-016-0406-0 |
Abstract | Representative skyline computation is a fundamental issue in database area, which has attracted much attention in recent years. A notable definition of representative skyline is the distance-based representative skyline (DBRS). Given an integer k, a DBRS includes k representative skyline points that aims at minimizing the maximal distance between a non-representative skyline point and its nearest representative. In the 2D space, the state-of-the-art algorithm to compute the DBRS is based on dynamic programming (DP) which takes O(k m 2) time complexity, where m is the number of skyline points. Clearly, such a DP-based algorithm cannot be used for handling large scale datasets due to the quadratic time cost. To overcome this problem, in this paper, we propose a new approximate algorithm called ARS, and a new exact algorithm named PSRS, based on a carefully-designed parametric search technique. We show that the ARS algorithm can guarantee a solution that is at most 𝜖 larger than the optimal solution. The proposed ARS and PSRS algorithms run in O(klog2mlog(T/𝜖)) and O(k 2 log3m) time respectively, where T is no more than the maximal distance between any two skyline points. We also propose an improved exact algorithm, called PSRS+, based on an effective lower and upper bounding technique. We conduct extensive experimental studies over both synthetic and real-world datasets, and the results demonstrate the efficiency and effectiveness of the proposed algorithms. |
Keywords | Representative skyline; Dynamic programming; Parametric search |
Contains Sensitive Content | Does not contain sensitive content |
ANZSRC Field of Research 2020 | 4605. Data management and data science |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Byline Affiliations | Shenzhen University, China |
Chinese University of Hong Kong, China | |
University of Western Australia |
https://research.usq.edu.au/item/y67q0/efficient-distance-based-representative-skyline-computation-in-2d-space
20
total views0
total downloads4
views this month0
downloads this month