跨信任域的联邦k-支配Sk yline查询算法

doi:10.11959/j.issn.2096-0271.2023047

大数据 ›› 2023, Vol. 9 ›› Issue (4): 32-43.doi: 10.11959/j.issn.2096-0271.2023047

• 专题：跨域数据管理 • 上一篇

跨信任域的联邦k-支配Sk yline查询算法

史烨轩¹^,², 童咏昕¹^,²^,³, 周昊¹^,², 许可¹^,²^,³, 吕卫锋¹^,²

¹ 北京航空航天大学软件开发环境国家重点实验室，北京 100191
² 北京航空航天大学计算机学院，北京 100191
³ 北京航空航天大学未来区块链与隐私计算高精尖创新中心，北京 100191

出版日期:2023-07-01 发布日期:2023-07-01
作者简介:史烨轩（1994- ），男，博士，北京航空航天大学计算机学院博士后，主要研究方向为大数据分析处理、联邦学习和隐私计算
童咏昕（1982- ），男，北京航空航天大学计算机学院教授，主要研究方向为联邦学习、隐私计算、时空大数据分析、数据库技术和群体智能
周昊（1999- ），男，北京航空航天大学计算机学院硕士生，主要研究方向为大数据分析处理、联邦学习和隐私计算
许可（1971- ），男，北京航空航天大学计算机学院教授，主要研究方向为算法与复杂性、数据挖掘和群体智能等
吕卫锋（1972- ），男，北京航空航天大学计算机学院教授，北京航空航天大学副校长，软件开发环境国家重点实验室副主任，主要研究方向为时空大数据分析、智慧城市和群体智能等
基金资助:
国家自然科学基金资助项目(U21A20516);国家自然科学基金资助项目(62076017);北航基础研究建设基金资助项目(YWF-22-L-531);微众学者计划

Cross trust domain federated k-dominant skyline query processing

Yexuan SHI¹^,², Yongxin TONG¹^,²^,³, Hao ZHOU¹^,², Ke XU¹^,²^,³, Weifeng LYU¹^,²

¹ State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China
² School of Computer Science and Engineering, Beihang University, Beijing 100191, China
³ Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, Beihang University, Beijing 100191, China

Online:2023-07-01 Published:2023-07-01
Supported by:
The National Natural Science Foundation of China(U21A20516);The National Natural Science Foundation of China(62076017);Beihang University Basic Research Funding(YWF-22-L-531);WeBank Scholars Program

摘要/Abstract

摘要：

k-支配Skyline查询是一种主流的Skyline查询变种，其在多目标决策与推荐领域有着广泛的应用。随着这些应用规模不断扩大，在由多个参与方组成的数据联邦中进行跨域k-支配Skyline查询的需求日益旺盛。然而，由于数据联邦中的参与方之间彼此不互信，进行跨信任域的查询计算需引入大量安全操作，效率较低。为此提出了一种基于跨域隐私向量聚合的算法，从而实现高效的联邦k-支配Skyline查询，并运用一种密文压缩技术进一步优化查询效率，最后通过充分的实验验证了所提方案的优越性。

关键词: k-支配Skyline查询, 数据联邦, 安全多方计算, 同态加密

Abstract:

k-dominant skyline is a prevailing skyline query which has widespread applications in multi-criteria decision making and recommendation.As these applications continuously scale up, there is an increasing demand to support k-dominant skyline over a data federation which consists of multiple data silos, each holding disjoint columns of the entire dataset.Yet it is challenging to support k-dominant skyline over a data federation.This is because strict security constraints are often imposed to query processing over data federations, whereas naively adopting security techniques leads to unacceptably inefficient queries.In this paper, we presented an efficient and secure k-dominant skyline for a data federation.Specifically, we devised a novel private vector aggregation-based solution with ciphertext compressionbased optimization for efficient k-dominant skyline query processing while providing security guarantees.Extensive evaluations on both synthetic and real datasets showed the superiority of our method.

Key words: k-dominant skyline, data federation, secure multi-party computation, homomorphic encryption

中图分类号:

TP391

史烨轩, 童咏昕, 周昊, 许可, 吕卫锋. 跨信任域的联邦k-支配Sk yline查询算法[J]. 大数据, 2023, 9(4): 32-43.

Yexuan SHI, Yongxin TONG, Hao ZHOU, Ke XU, Weifeng LYU. Cross trust domain federated k-dominant skyline query processing[J]. Big Data Research, 2023, 9(4): 32-43.

图/表 3

参考文献 22

[1]	BORZSONY S , KOSSMANN D , STOCKER K . The skyline operator[C]// Proceedings of Proceedings 17th International Conference on Data Engineering. Piscataway:IEEE Press, 2002: 421-430.
[2]	SHARIFZADEH M , SHAHABI C . The spatial skyline queries[C]// Proceedings of the 32nd International Conference on Very Large Data Bases. New York:ACM Press, 2006: 751-762.
[3]	BATER J , ELLIOTT G , EGGEN C ,et al. SMCQL:secure query processing for private data networks[J]. Proceedings of the VLDB Endowment, 2017,10(6): 673-684.
[4]	TONG Y X , PAN X C , ZENG Y X ,et al. Hu-fu[J]. Proceedings of the VLDB Endowment, 2022,15(6): 1159-1172.
[5]	CHAN C Y , JAGADISH H V , TAN K L ,et al. Finding k-dominant skylines in high dimensional space[C]// Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York:ACM Press, 2006: 503-514.
[6]	AWASTHI A , BHATTACHARYA A , GUPTA S ,et al. k-dominant skyline join queries:extending the join paradigm to K-dominant skylines[C]// Proceedings of 2017 IEEE 33rd International Conference on Data Engineering (ICDE). Piscataway:IEEE Press, 2017: 99-102.
[7]	MIAO X Y , GAO Y J , CHEN G ,et al. k-dominant skyline queries on incomplete data[J]. Information Sciences, 2016,367/368: 990-1011.
[8]	LIU J F , YANG J C , XIONG L ,et al. Secure skyline queries on cloud platform[J]. Proceedings International Conference on Data Engineering, 2017,2017: 633-644.
[9]	DING X F , WANG Z , ZHOU P ,et al. Efficient and privacy-preserving multi-party skyline queries over encrypted data[J]. IEEE Transactions on Information Forensics and Security, 2021,16: 4589-4604.
[10]	ZHANG Y Y , SHI Y X , ZHOU Z M ,et al. Efficient and secure skyline queries over vertical data federation[J]. IEEE Transactions on Knowledge and Data Engineering, 2022(99): 1-12.
[11]	KELLER M . MP-SPDZ:a versatile framework for multi-party computation[C]// Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2020: 1575-1590.
[12]	KATZ J , LINDELL Y . Introduction to modern cryptography[M].[S.l.]: Chapman and Hall/CRC, 2020.
[13]	GAO Y J , MIAO X Y , CUI H Y ,et al. Processing k-skyband,constrained skyline,and group-by skyline queries on incomplete data[J]. Expert Systems With Applications, 2014,41(10): 4959-4974.
[14]	GAO Y J , LIU Q , ZHENG B H ,et al. On efficient reverse skyline query processing[J]. Expert Systems With Applications, 2014,41(7): 3237-3249.
[15]	LIN X M , YUAN Y D , ZHANG Q ,et al. Selecting stars:the k most representative skyline operator[C]// Proceedings of 2007 IEEE 23rd International Conference on Data Engineering. Piscataway:IEEE Press, 2007: 86-95.
[16]	LEE K C K , ZHENG B H , LI H J ,et al. Approaching the skyline in Z order[C]// Proceedings of the 33rd International Conference on Very Large Data Bases. New York:ACM Press, 2007: 279-290.
[17]	SIDDIQUE M A , MORIMOTO Y . k-dominant skyline computation by using sort-filtering method[C]// Pacific-Asia Conference on Knowledge Discovery and Data Mining. Heidelberg:Springer, 2009: 839-848.
[18]	CHEN W X , LIU M J , ZHANG R ,et al. Secure outsourced skyline query processing via untrusted cloud service providers[C]// Proceedings of IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications. Piscataway:IEEE Press, 2016: 1-9.
[19]	LIU X M , CHOO K K R , DENG R H ,et al. PUSC:privacy-preserving user-centric skyline computation over multiple encrypted domains[C]// Proceedings of 2018 17th IEEE International Conference on Trust,Security and Privacy,In Computing and Communications/ 12th IEEE International Conference on Big Data Science and Engineering (TrustCom/BigDataSE). Piscataway:IEEE Press, 2018: 958-963.
[20]	李书缘, 季与点, 史鼎元 ,等. 面向多方安全的数据联邦系统[J]. 软件学报, 2022,33(3): 1111-1127.
	LI S Y , JI Y D , SHI D Y ,et al. Data federation system for multi-party security[J]. Journal of Software, 2022,33(3): 1111-1127.
[21]	VOLGUSHEV N , SCHWARZKOPF M , GETCHELL B ,et al. Conclave:secure multi-party computation on big data[C]// Proceedings of the 14th EuroSys Conference 2019. New York:ACM Press, 2019: 1-18.
[22]	BATER J , PARK Y , HE X ,et al. SAQE:Practical privacy-preserving approximate query processing for data federations[J]. Proceedings of the VLDB Endowment, 2020,13(12): 2691-2705.

跨信任域的联邦k-支配Sk yline查询算法

Cross trust domain federated k-dominant skyline query processing

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 22

相关文章 3

Metrics

推荐阅读 0

[1]	尹虹舒, 周旭华, 周文君. 纵向联邦线性模型在线推理过程中成员推断攻击的隐私保护研究[J]. 大数据, 2022, 8(5): 45-54.
[2]	刘彦松, 夏琦, 李柱, 夏虎, 张小松, 高建彬. 基于区块链的链上数据安全共享体系研究[J]. 大数据, 2020, 6(5): 92-105.
[3]	黄霖, 黎源, 汪星辰, 赵运磊. 数据自治开放的加密技术挑战[J]. 大数据, 2018, 4(2): 50-62.