PSP:一种高效的偏序域上skyline查询处理方法

2020-12-21 03:38:27白梅王京徽王习特朱斌李冠宇
湖南大学学报·自然科学版 2020年8期

白梅 王京徽 王习特 朱斌 李冠宇

摘   要:为解决偏序域上的skyline查询问题,本文提出一种高效的偏序域上的skyline查询处理方法,来满足人们对查询效率日益增长的需求. 首先,为提高偏序域上skyline的查询效率,将倒排索引引入skyline查询,提出一种基于倒排的索引结构. 其次,提出基础算法 (Basic Partially-ordered Skyline Processing based on inverted index,PSP_B),PSP_B包含两个阶段:第一阶段,能够通过映射将偏序域转化成全序域,并建立倒排索引;第二阶段,通过倒排索引提前找到扫描结束点,得到最终的skyline结果. 再次,在PSP_B的基础上,进一步提出优化算法 (Improved Partially-ordered Skyline Processing based on inverted index,PSP_I). PSP_I通過先分组再建索引的方法能够进一步提高计算效率. 最后,用大量的实验证明本文所提算法的正确性和高效性.

关键词:skyline查询;倒排索引;偏序域;查询优化;算法

中图分类号:TP391                             文献标志码:A          文章编号:1674—2974(2020)08—0009—12

Abstract:In order to solve the skyline query problem in partial order domain, this paper proposes an efficient query processing method for the skyline query in the partial order domain to meet people's increasing demand for query efficiency. Firstly, in order to improve the query efficiency of skyline on partially ordered domains, this paper introduces the inverted index into the skyline query and proposes an index structure based on the inverted index. Secondly, the basic algorithm PSP_B (Basic Partially-ordered Skyline Processing based on inverted index, PSP_B) is proposed. The PSP_B consists of two phases: in the first step, each partially ordered domain is converted into two fully ordered domains through mapping function, and then each fully ordered dimension is managed through the inverted index; in the second step, the scan end point is found through scanning the inverted index and the result set is obtained. Thirdly, based on the PSP_B, this paper further proposes an optimization algorithm PSP_I (Improved Partially-ordered Skyline Processing based on inverted index, PSP_I). The PSP_I can further improve the computational efficiency by grouping the data in advance and then indexing them. Finally, a large number of experiments prove the correctness and efficiency of the proposed algorithm.

Key words:skyline query;inverted index;partial order domain;query optimization;algorithm

近年来,随着互联网技术的发展以及信息获取设备的进步,数据库收集处理的数据量增多,进一步,数据库中存储的数据量也急剧增加. 但是,人们却很难从这些海量、庞杂的信息中挖掘出自己最想要的有价值的信息. 因此,如何快速高效地从海量数据中返回给用户最为关心的数据,成为学术界的研究热点.

skyline查询根据用户在各个维度的偏好,利用“支配”的概念,将数值间的大小比例作为“好坏”的评价标准,直观而准确地返回给用户最为关心的结果集. 具体地,给定两个点p1和p2,p1支配p2指的是在所有维度上p1都不比p2差,并且至少在一个维度上p1要严格好于p2. 如图1所示,共有20条图书信息记录{p1,p2,…,p20},每一条……

登录APP查看全文