论文标题：Efficient k-dominant skyline query over incomplete data using MapReduce (MapReduce框架下不完整数据的有效k-支配skyline查询)

期刊：Frontiers of Computer Science

作者：Linlin DING , Shu WANG , Baoyan SONG

发表时间：08 May 2021

DOI：10.1007/s11704-020-0122-x

微信链接：点击此处阅读微信文章

编者荐语：

《前沿》系列之《计算机科学前沿》最近研究荐读

导读

Skyline查询能够有效过滤无用的、不感兴趣的数据对象，其被广泛应用到现实生活的很多领域。由于传统skyline查询对查询条件的限制有限，使得skyline查询在面临高维数据集时可能返回过多结果。作为skyline查询的扩展，k-支配skyline查询通过控制参数k的值来降低对维度的控制，进而能够减少skyline查询的查询对象。此外，随着大数据应用程序的不断推广，在实际应用中诸如交付失败、电池电量不足、意外丢失等原因导致可能无法获取人们想要的全部内容，因此数据可能不完整，在某些属性上缺少值。显然，不完全数据的k-支配skyline查询算法在某种程度上取决于用户定义，并且结果无法共享。同时，现有算法不能直接适合用于不完整大数据。基于上述情况，本文主要结合MapReduce分布式框架，研究不完整数据集的k-支配skyline查询问题。首先，我们提出了一种基于不完全数据的索引结构，即基于支配层次树（ID-DHT）的不完全数据索引。应用存储桶策略，根据缺失属性的维度不同，将不完整的数据划分至不同的存储桶。其次，我们还提出了基于MapReduce框架的不完整数据查询算法，即MapReduce环境下基于支配层次树（MR-ID-DHTA）的不完整数据k支配skyline查询算法。通过Map函数根据支配条件将存储桶中的数据分配到不同的子空间。Reduce函数根据键值控制数据并返回k-支配skyline查询结果。大量的实验证明了本文的索引结构以及算法的有效性和实用性。

文章精要

摘要

Skyline queries are extensively incorporated in various real-life applications by filtering uninteresting data objects. Sometimes, a skyline query may return so many results because it cannot control the retrieval conditions especially for highdimensional datasets. As an extension of skyline query, the kdominant skyline query reduces the control of the dimension by controlling the value of the parameter kto achieve the purpose of reducing the retrieval objects. In addition, with the continuous promotion of Bigdata applications, the data we acquired may not have the entire content that people wanted for some practically reasons of delivery failure, no power of battery, accidental loss, so that the data might be incomplete with missing values in some attributes. Obviously, the k-dominant skyline query algorithms of incomplete data depend on the user definition in some degree and the results cannot be shared. Meanwhile, the existing algorithms are unsuitable for directly used to the incomplete big data. Based on the above situations, this paper mainly studies k-dominant skyline query problem over incomplete dataset and combines this problem with the distributed structure like MapReduce environment. First, we propose an index structure over incomplete data, named incomplete data index based on dominate hierarchical tree (ID-DHT). Applying the bucket strategy, the incomplete data is divided into different buckets according to the dimensions of missing attributes. Second, we also put forward query algorithm for incomplete data in MapReduce environment, named MapReduce incomplete data based on dominant hierarchical tree algorithm (MR-ID-DHTA). The data in the bucket is allocated to the subspace according to the dominant condition by Map function. Reduce function controls the data according to the key value and returns the k-dominant skyline query result. The effective experiments demonstrate the validity and usability of our index structure and the algorithm.

相关内容推荐：

基于多任务协调的信息网络融合 2021 15(4): 154608

分布式日志存储结构中的增量连接视图维护 2021 15(4): 154607

基于内容和协同过滤的时间感知混合推荐方案 2021 15(4): 154613

基于kNN的最优位置查询算法 2021 15(2): 152606

如何进行精准高效日志修复？一文阐述日志修复算法 2021 15(2): 152605

【FCS 信息系统专栏】一种基于RkNN的空间位置影响力评价与查询算法 2021 15(2): 152604

【FCS 信息系统专栏】基于结构相似性的对抗网络表示学习方法 2020 14(5): 151603

【FCS 信息系统专栏】多语言社交数据流中的事件检测和演化 2020 14(5): 145612

【FCS 信息系统专栏】一种分布式数据库下自适应统计信息收集策略 2020 14(5): 145610

【FCS 信息系统专栏】一种套牌车检测框架 2020 14(5): 145609

【FCS 信息系统专栏】大数据查询结果多样化 2020 14(4): 144607

【FCS 信息系统专栏】面向主备复制系统的并行事务日志技术 2020 14(4): 144606

【FCS 信息系统专栏】分布式LSM-tree中范围查询的分区修剪策略 2020 14(3): 143604

【FCS Letter专栏】一种抵御基于上下文知识的位置隐私攻击的保护方法 2020 14(3): 143605

一种面向位置服务的空间对象存储优化模型HGeoHashBase 2020 14(1)：208-218

基于轨迹数据的热门路径规划及其消耗估计 2020 14(1)：191-207

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中13种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

高等教育出版社入选“中国科技期刊卓越行动计划”集群化项目。Frontier系列期刊中：13种被SCI收录；1种被A&HCI收录；6种被Ei收录；2种被MEDLINE收录；11种中国科技核心期刊；16种被CSCD收录。

中国学术前沿期刊网

http://journal.hep.com.cn