Efficient distance-based representative skyline computation in 2D space |
| |
Authors: | Rui Mao Taotao Cai Rong-Hua Li Jeffery Xu Yu Jianxin Li |
| |
Affiliation: | 1.College of Computer Science and Software Engineering,Shenzhen University,Shenzhen,China;2.Guangdong Province Key Laboratory of Popular High Performance Computers,Shenzhen University,Shenzhen,China;3.The Chinese University of Hong Kong,Hong Kong,Hong Kong;4.University of Western Australia,Perth,Australia |
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|