Efficient Algorithms for Distance-Based Representative Skyline Computation in 2D Space
Presentation
Paper/Presentation Title | Efficient Algorithms for Distance-Based Representative Skyline Computation in 2D Space |
---|---|
Presentation Type | Presentation |
Authors | Cai, Taotao, Li, Rong-Hua, Yu, Jeffrey Xu, Mao, Rui and Cai, Yadi |
Journal or Proceedings Title | Proceedings of 17th Asia-Pacific Web Conference (APWeb2015) |
Journal Citation | 9313, pp. 116-128 |
Number of Pages | 13 |
Year | 2015 |
Publisher | Springer |
Place of Publication | Switzerland |
ISSN | 0302-9743 |
1611-3349 | |
ISBN | 9783319252544 |
9783319252551 | |
Digital Object Identifier (DOI) | https://doi.org/10.1007/978-3-319-25255-1_10 |
Web Address (URL) of Paper | https://link.springer.com/chapter/10.1007/978-3-319-25255-1_10 |
Web Address (URL) of Conference Proceedings | https://link.springer.com/book/10.1007/978-3-319-25255-1 |
Conference/Event | 17th Asia-Pacific Web Conference (APWeb2015) |
Event Details | 17th Asia-Pacific Web Conference (APWeb2015) Parent Asia Pacific Web Conference Delivery In person Event Date 18 to end of 20 Sep 2015 Event Location Guangzhou, China |
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(km 2) time complexity, where m is the number of skyline points. Clearly, such a DP-based algorithm cannot be used for handling large scale dataset 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(klog2 m log(T/ε)) and O(k 2log3 m) time respectively, where T is no more than the maximal distance between any two skyline points. 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 | Computation; algorithms |
Contains Sensitive Content | Does not contain sensitive content |
ANZSRC Field of Research 2020 | 461305. Data structures and algorithms |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Series | Lecture Notes in Computer Science |
Byline Affiliations | Shenzhen University, China |
Chinese University of Hong Kong, China |
https://research.usq.edu.au/item/y67q1/efficient-algorithms-for-distance-based-representative-skyline-computation-in-2d-space
Download files
37
total views15
total downloads12
views this month2
downloads this month