Efficient Algorithms for Distance-Based Representative Skyline Computation in 2D Space

Presentation


Cai, Taotao, Li, Rong-Hua, Yu, Jeffrey Xu, Mao, Rui and Cai, Yadi. 2015. "Efficient Algorithms for Distance-Based Representative Skyline Computation in 2D Space ." 17th Asia-Pacific Web Conference (APWeb2015). Guangzhou, China 18 - 20 Sep 2015 Switzerland . Springer. https://doi.org/10.1007/978-3-319-25255-1_10
Paper/Presentation Title

Efficient Algorithms for Distance-Based Representative Skyline Computation in 2D Space

Presentation TypePresentation
AuthorsCai, Taotao, Li, Rong-Hua, Yu, Jeffrey Xu, Mao, Rui and Cai, Yadi
Journal or Proceedings TitleProceedings of 17th Asia-Pacific Web Conference (APWeb2015)
Journal Citation9313, pp. 116-128
Number of Pages13
Year2015
PublisherSpringer
Place of PublicationSwitzerland
ISSN0302-9743
1611-3349
ISBN9783319252544
9783319252551
Digital Object Identifier (DOI)https://doi.org/10.1007/978-3-319-25255-1_10
Web Address (URL) of Paperhttps://link.springer.com/chapter/10.1007/978-3-319-25255-1_10
Web Address (URL) of Conference Proceedingshttps://link.springer.com/book/10.1007/978-3-319-25255-1
Conference/Event17th 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.

KeywordsComputation; algorithms
Contains Sensitive ContentDoes not contain sensitive content
ANZSRC Field of Research 2020461305. Data structures and algorithms
Public Notes

Files associated with this item cannot be displayed due to copyright restrictions.

SeriesLecture Notes in Computer Science
Byline AffiliationsShenzhen University, China
Chinese University of Hong Kong, China
Permalink -

https://research.usq.edu.au/item/y67q1/efficient-algorithms-for-distance-based-representative-skyline-computation-in-2d-space

Download files


Other Documentation
peer review.PNG
File access level: Anyone

  • 10
    total views
  • 9
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as

Related outputs

FRAMU: Attention-based Machine Unlearning using Federated Reinforcement Learning
Shaik, Thanveer, Tao, Xiaohui, Li, Lin, Xie, Haoran, Cai, Taotao, Zhu, Xiaofeng and Li, Qing. 2024. "FRAMU: Attention-based Machine Unlearning using Federated Reinforcement Learning ." IEEE Transactions on Knowledge and Data Engineering. https://doi.org/10.1109/TKDE.2024.3382726
Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks
Cai, Taotao, Lei, Qi, Sheng, Quan Z., Cui, Ningning, Yang, Shuiqiao, Yang, Jian, Zhang, Wei Emma and Mahmood, Adnan. 2024. "Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks." IEEE Transactions on Knowledge and Data Engineering. 36 (5), pp. 2151-2165. https://doi.org/10.1109/TKDE.2023.3316268
Dynamic Correlation Adjacency Matrix Based Graph Neural Network for Traffic Flow Prediction
Gu, Junhua, Jia, Zhihao, Cai, Taotao, Song, Xiangyu and Mahmood, Adnan. 2023. "Dynamic Correlation Adjacency Matrix Based Graph Neural Network for Traffic Flow Prediction." Sensors. 23 (6). https://doi.org/10.3390/s23062897
Top-k socio-spatial co-engaged location selection for social users
Hasan Haldar, Nur Al, Li, Jianxin, Ali, Mohammed Eunus, Cai, Taotao, Chen, Yunliang, Sellis, Timos and Reynolds, Mark. 2023. "Top-k socio-spatial co-engaged location selection for social users." IEEE Transactions on Knowledge and Data Engineering. 35 (5), pp. 5325-5340. https://doi.org/10.1109/TKDE.2022.3151095
Towards Multi-User, Secure, and Verifiable kNN Query in Cloud Database
Cui, Ningning, Qian, Kang, Cai, Taotao, Li, Jianxin, Yang, Xiaochun, Cui, Jie and Zhong, Hong. 2023. "Towards Multi-User, Secure, and Verifiable kNN Query in Cloud Database." IEEE Transactions on Knowledge and Data Engineering. 35 (9), pp. 9333-9349. https://doi.org/10.1109/TKDE.2023.3237879
Incremental graph computation: Anchored Vertex Tracking in Dynamic Social Networks
Cai, Taotao, Yang, Shuiqiao, Li, Jianxin, Sheng, Quan Z., Yang, Jian, Wang, Xin, Zhang, Wei Emma and Gao, Longxiang. 2023. "Incremental graph computation: Anchored Vertex Tracking in Dynamic Social Networks." IEEE Transactions on Knowledge and Data Engineering. 35 (7), pp. 7030-7044. https://doi.org/10.1109/TKDE.2022.3199494
Robust cross-network node classification via constrained graph mutual information
Yang, Shuiqiao, Cai, Borui, Cai, Taotao, Song, Xiangyu, Jiang, Jiaojiao, Li, Bing and Li, Jianxin. 2022. "Robust cross-network node classification via constrained graph mutual information." Knowledge-Based Systems. 257. https://doi.org/10.1016/j.knosys.2022.109852
A survey on deep learning based knowledge tracing
Song, Xiangyu, Li, Jianxin, Cai, Taotao, Yang, Shuiqiao, Yang, Tingting and Liu, Chengfei. 2022. "A survey on deep learning based knowledge tracing." Knowledge-Based Systems. 258. https://doi.org/10.1016/j.knosys.2022.110036
Target-Aware Holistic Influence Maximization in Spatial Social Networks
Cai, Taotao, Li, Jianxin, Mian, Ajmal, Li, Rong-Hua, Sellis, Timos and Yu, Jeffrey Xu. 2022. "Target-Aware Holistic Influence Maximization in Spatial Social Networks ." IEEE Transactions on Knowledge and Data Engineering. 34 (4), pp. 1993-2007. https://doi.org/10.1109/TKDE.2020.3003047
Community-diversity Driven Influence Maximization on Social Networks
Li, Jianxin, Cai, Taotao, Ke, Deng, Wang, Xinjue, Sellis, Timos and Xia, Feng. 2020. "Community-diversity Driven Influence Maximization on Social Networks." Information Systems. 92. https://doi.org/10.1016/j.is.2020.101522
Anchor vertex selection for enhanced reliability of traffic offloading service in edge-enabled mobile P2P social networks
Zhang, Hengda, Wang, Xiaofei, Fan, Hao, Cai, Taotao, Li, Jianxin, Li, Xiuhua and Leung, Victor C. M.. 2020. "Anchor vertex selection for enhanced reliability of traffic offloading service in edge-enabled mobile P2P social networks." Journal of Communications and Information Networks. 5 (2), pp. 217-224. https://doi.org/10.23919/JCIN.2020.9130437
Anchored Vertex Exploration for Community Engagement in Social Networks
Cai, Taotao, Li, Jianxin, Hasan Haldar, Nur Al, Mian, Ajmal, Yearwood, John and Sellis, Timos. 2020. "Anchored Vertex Exploration for Community Engagement in Social Networks ." 2020 IEEE 36th International Conference on Data Engineering (ICDE). Dallas, United States 20 - 24 Apr 2020 United States. IEEE (Institute of Electrical and Electronics Engineers). https://doi.org/10.1109/ICDE48307.2020.00042
Correlate Influential News Article Events to Stock Quote Movement
Mandalapu, Arun Chaitanya, Gunabalan, Saranya, Sadineni, Avinash, Cai, Taotao, Hasan, Nur Al Hasan and Li, Jianxin. 2019. "Correlate Influential News Article Events to Stock Quote Movement ." Li, Jianxin, Wang, Sen, Qin, Shaowen, Li, Xue and Wang, Shuliang (ed.) 15th International Conference on Advanced Data Mining and Applications. Dalian, China 21 - 23 Nov 2019 Switzerland. Springer. https://doi.org/10.1007/978-3-030-35231-8_24
Holistic Influence Maximization for Targeted Advertisements in Spatial Social Networks
Li, Jianxin, Cai, Taotao, Mian, Ajmal, Li, Rong-Hua, Sellis, Timos and Yu, Jeffrey Xu. 2018. "Holistic Influence Maximization for Targeted Advertisements in Spatial Social Networks ." 2018 IEEE 34th International Conference on Data Engineering (ICDE). Paris, France 16 - 19 Apr 2018 United States. IEEE (Institute of Electrical and Electronics Engineers). https://doi.org/10.1109/ICDE.2018.00145
Efficient Distance-based Representative Skyline Computation in 2D Space
Mao, Rui, Cai, Taotao, Li, Rong-Hua, Yu, Jeffery Xu and Li, Jianxin. 2017. "Efficient Distance-based Representative Skyline Computation in 2D Space." World Wide Web. 20 (4), pp. 621-638. https://doi.org/10.1007/s11280-016-0406-0