Multi-User Preference Top-<i>k</i> Skyline Query Method Based on Road Network

Li Song; Bin Tingliang; Hao Xiaohong; Zhang Liping; Hao Zhongxiao

doi:10.7544/issn1000-1239.202220455

Journal of Computer Research and Development > 2023 > 60(10): 2348-2358. > DOI: 10.7544/issn1000-1239.202220455

Li Song, Bin Tingliang, Hao Xiaohong, Zhang Liping, Hao Zhongxiao. Multi-User Preference Top-k Skyline Query Method Based on Road Network[J]. Journal of Computer Research and Development, 2023, 60(10): 2348-2358. DOI: 10.7544/issn1000-1239.202220455

Citation:

PDF (1403 KB)

Multi-User Preference Top-k Skyline Query Method Based on Road Network

School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080

Funds: This work was supported by the National Natural Science Foundation of China (61872105, 62072136), the Natural Science Foundation of Heilongjiang Province (LH2023F031), and the National Key Research and Development Program of China (2020YFB1710200).

More Information

Author Bio:
Li Song: born in 1977. PhD, professor. Member of CCF. His main research interests include spatial database，data mining, and data information security

Bin Tingliang: born in 1999. Master candidate. Her main research interests include spatial database and data mining

Hao Xiaohong: born in 1969. Master，senior experimentalist. Her main research interest includes spatial database

Zhang Liping: born in 1976. Master, associate professor. Her main research interests include spatial database and data information security

Hao Zhongxiao: born in 1940. PhD，professor. His main research interests include relational database，null database，acyclic database，active database, and spatial database
Received Date: June 08, 2022
Revised Date: December 08, 2022
Available Online: May 22, 2023

Graphical Abstract

Abstract

Abstract

Existing Skyline query most foucus on single-user scenarios, and caculate Skyline results based on single-user model. But less consideration is given to multi-user model in road network environment. The existing methods cannot solve the Top-k Skyline query problem that comprehensively considers multi-user preference and weight in road network environment. Therefore, we propose a Top-k Skyline query method MUP-TKS, based on multi-user preference in road network environment. In this environment, the different preference and weight of multi-user are considered for Skyline calculation. The result set which conforms to the preference and weight of the query user group can be obtained quickly to make better decision. Firstly, through the proposed algorithm G_DBC, the position relation of data points and query points in the road network, and the new index structure Vor-R^*-DHash are used for pruning the data points. Thus the optimal distance set is obtained. Then taking advantage of the invariable property of the static Skyline set to precompute and save the set. KPRD algorithm is performed on S set, the union of the optimal distance set and static Skyline set. Finally, TK_DC algorithm is used to score the candidate set. According to the score of the data points, the Top-k of the sorted set are returned to the query user group. Theoretical studies and experiments show that the proposed method is efficient and reliable.
- Skyline query,
- Top-k Skyline query,
- multi-user preference,
- road network,
- user weight

FullText(HTML)

References (27)

References

[1]	Borzsony S, Kossmann D, Stocker K. The Skyline operator[C] //Proc of the 17th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2001: 421−430
[2]	Zeng Yifu, Chen Guo, Li Kenli, et al. M-Skyline: Taking sunk cost and alternative recommendation in consideration for Skyline query on uncertain data[J]. Knowledge-Based Systems, 2019, 163(1): 204−213
[3]	Ren Weilong, Lian Xiang, Ghazinour K. Skyline queries over incomplete data streams[J]. The Very Large Date Bases Journal, 2019, 28(6): 961−985 doi: 10.1007/s00778-019-00577-6
[4]	Wang Weiguo, Li Hui, Peng Yanguo, et al. Scale: An efficient framework for secure dynamic Skyline query processing in the cloud [C]//Proc of the 25th Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2020: 288−305
[5]	Yin Bo, Zhou Siwang, Zhang Shiwen, et al. On efficient processing of continuous reverse Skyline queries in wireless sensor networks[J]. KSII Transactions on Internet and Information Systems, 2017, 11(4): 1931−1953
[6]	Kossmann D, Ramsak F, Rost S. Shooting stars in the sky: An online algorithm for Skyline queries[C] //Proc of the 28th Int Conf on Very Large Databases(VLDB’02). San Francisco, CA: Morgan Kaufmann, 2002: 275−286
[7]	Chomicki J, Godfrey P, Gryz J, et al. Skyline with presorting[C] //Proc of the 19th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2003: 717−719
[8]	李松,窦雅男,郝晓红,等. 道路网环境下K-支配空间Skyline查询方法[J]. 计算机研究与发展,2020,57(1):227−239 doi: 10.7544/issn1000-1239.2020.20190026 Li Song, Dou Yanan, Hao Xiaohong, et al. The method of the K-dominant space Skyline query in road network[J]. Journal of Computer Research and Development, 2020, 57(1): 227−239 (in Chinese) doi: 10.7544/issn1000-1239.2020.20190026
[9]	Fu Xiaoyi, Miao Xiaoye, Xu Jianliang, et al. Continuous range-based Skyline queries in road networks[J]. World Wide Web, 2017, 20(6): 1443−1467 doi: 10.1007/s11280-017-0444-2
[10]	李松, 王冠群, 郝晓红, 等. 面向推荐系统的多目标决策优化算法. 西安交通大学学报, 2022, 56（8）: 104−112 Li Song, Wang Guanqun, Hao Xiaohong, et al. A multi-objective decision optimization algorithm for recommendation system [J]. Journal of xi’an Jiaotong University, 2022, 56(8): 104−112 (in Chinese)
[11]	Zhang Kaiqi, Gao Hong, Han Xixian, et al. Probabilistic Skyline on incomplete data[C] //Proc of the 26th Int Conf on Information and Knowledge Management. New York: ACM, 2017: 427−436
[12]	Abdul Fattah H M, Azharul Hasan K M, Tsuji T. Indexed Top-kdominating queries on highly incomplete data[C] //Proc of the 1st Int Conf on Big Data, IoT, and Machine Learning. Berlin: Springer, 2022: 231−241
[13]	Mouratidis K, Li Keming, Tang Bo. Marrying Top-k with Skyline queries: Relaxing the preference input while producing output of controllable size[C] //Proc of the 47th Int Conf on Management of Data. New York: ACM, 2021: 1317−1330
[14]	Saad N H M, Ibrahim H, Sidi F, et al. Efficient Skyline computation on uncertain dimensions[J]. IEEE Access, 2021, 9: 96975−96994 doi: 10.1109/ACCESS.2021.3094547
[15]	白梅,王京徽,王习特,等. PSP:一种高效的偏序域上 Skyline 查询处理方法[J]. 湖南大学学报:自然科学版,2020,47(8):9−20 Bai Mei, Wang Jinghui, Wang Xite, et al. PSP: An efficient Skyline computation method for partially ordered domains[J]. Journal of Hunan University: Natural Sciences, 2020, 47(8): 9−20 (in Chinese)
[16]	Wang Yan, Shi Zhan, Wang Junlu, et al. Skyline preference query based on massive and incomplete dataset[J]. IEEE Access, 2017, 5: 3183−3192 doi: 10.1109/ACCESS.2016.2639558
[17]	Tai Liangkuang, Wang E T, Chen A L P. Finding the most profitable candidate product by dynamic skyline and parallel processing[J]. Distributed and Parallel Databases, 2021, 39(4): 979−1008 doi: 10.1007/s10619-021-07323-4
[18]	Zheng Zhiyun, Zhang Minghao, Yu Mengyao, et al. User preference-based data partitioning Top-k Skyline query processing algorithm[C]//Proc of the 2nd Int Conf on Industrial Application of Artificial Intelligence. Piscataway, NJ: IEEE, 2021: 436−444
[19]	Cai Zhi, Cui Xuerui, Su Xing, et al. Continuous road network-based Skyline query for moving objects[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 22(12): 7383−7394
[20]	Li Qiyan, Zhu Yuanyuan, Yu J X. Skyline cohesive group queries in large road-social networks[C]//Proc of the 36th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2020: 397−408
[21]	Hidayat A, Cheema M A, Lin Xuemin, et al. Continuous monitoring of moving Skyline and Top-k queries[J]. The VLDB Journal, 2022, 31(3): 459−482 doi: 10.1007/s00778-021-00702-4
[22]	Ding Linlin, Zhang Xiao, Sun Mingxin, et al. Efficient user preferences-based Top-k Skyline using MapReduce[C] //Proc of the 4th Int Conf on Pioneering Computer Scientists, Engineers and Educators. Berlin: Springer, 2018: 74−87
[23]	Awasthi A, Bhattacharya A, Gupta S, et al. K-dominant Skyline join queries: Extending the join paradigm to k-dominant Skylines[C] //Proc of the 33rd Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2017: 99−102
[24]	Zan C T, Yamana H. An improved symbolic aggregate approximation distance measure based on its statistical features[C] //Proc of the 18th Int Conf on Information Integration and Web-based Applicationsand Services. New York: ACM, 2016: 72−80
[25]	Chomicki J, Godfrey P, Gryz J, et al. Skyline with Presorting: Theory and Optimizations[C] //Intelligent Information Processing and Web Mining. Berlin: Springer, 2005: 595−604
[26]	Zou Yonggui, Wang Zhi. User preference based spatial Skyline query method[J]. Applied Mechanics & Materials, 2014, 530: 832−838
[27]	John A, Singh S K, Adimoolam M, et al. Dynamic sorting and average Skyline method for query processing in spatial-temporal data[J]. International Journal of Data Science, 2021, 6(1): 1−18