计算SKY的预排序分组算法

doi:10.3969/j.issn.1006-2475.2014.02.016

计算机与现代化

计算SKY的预排序分组算法

（甘肃民族师范学院计算机科学系，甘肃合作 747000）

收稿日期:2013-06-14 出版日期:2014-02-14 发布日期:2014-02-14
作者简介:刘萍(1978-)，女，青海西宁人，甘肃民族师范学院计算机科学系讲师，硕士，研究方向：计算机算法与数据库。

Presorting Grouping Algorithm for Skyline Computation

(Department of Computer Science, Gansu Normal University for Nationalities, Hezuo 747000, China)

Received:2013-06-14 Online:2014-02-14 Published:2014-02-14

摘要/Abstract

摘要： 在SFS算法的预排序思想基础上，借助数据集R上的单调分值函数，将R的点分组，提出计算Skyline的迭代算法。算法有效地支持用户的偏爱。给出证明：若R的点的个数为n，R的Skyline的点的个数为m，则在计算R的Skyline的过程中，需要对点之间所做的支配比较的次数不超过m(n-m/2-1/2)；如果分组的组数为k，则分组算法比SFS减少比较次数不少于m(m-k)/2k。

关键词: 多元目标优化, 预排序, 轮廓, 分组算法

Abstract: In this paper, we proposed the presorting grouping algorithm for skyline computation. This algorithm was based on SFS algorithm, and efficiently supported the preference of users. We proved that, for computing skyline, the number required comparisons between two points does not exceed m(n-m/2-1/2), where n being the number of points, and m being the number of skyline points; if the number of groups being k, then the number required comparisons used in the presorting grouping algorithm reduced m(m-k)/2k.

Key words: multi-objective optimization, presorting, skyline, grouping algorithm

中图分类号:

TP311

刘萍. 计算SKY的预排序分组算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2014.02.016.

LIU Ping.

Presorting Grouping Algorithm for Skyline Computation

[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2014.02.016.

参考文献 15

[1]	Borzsony S, Kossmann D, Stocker K. The skyline operator[C]// Proceedings of the 17th IEEE International Conference on Data Engineering. 2001:421-430.
[2]	Chomicki J, Godfrey P, Gryz J, et al. Skyline with Presorting[R]. York University, 2002.
[3]	Chomicki J, Godfrey P, Gryz J, et al. Skyline with presorting[C]// Proceedings of the 19th IEEE International Conference on Data Engineering. 2003:717-719.
[4]	Kung H T, Luccio F, Preparata F P. On finding the maxima of a set of vectors[J]. Journal of the Association for Computing Machinery, 1975,22(4):469-476.
[5]	Bentley J L, Kung H T, Schkolnick M, et al. On the average number of maxima in a set of vectors and applications[J]. Journal of the Association for Computing Machinery, 1978,25(4):536-543.
[6]	Tan K L, Eng P K, Ooi B C. Efficient progressive skyline computation[C]// Proceedings of the 27th IEEE International Conference on Very Large Data Bases. Rome, Italy, 2001:301-310.
[7]	Papadias D, Tao Y, Fu G, et al. Progressive skyline computation in database systems[J]. ACM Transactions on Database Systems, 2005,30(1):41-82.
[8]	Balke W-T, Guntzer U, Zheng J X. Efficient distributed skylining for Web information systems[C]// Proceedings of the 9th IEEE International Conference on Extending Database Technology. Crete, Greece, 2004:256-273.
[9]	Hose K. Processing skyline queries in P2P systems[C]// Proceedings of VLDB 2005 PhD Workshop. Trondheim, Norway, 2005:36-40.
[10]	Pei J, Jiang B, Lin X, et al. Probabilistic skylines on uncertain data[C]// Proceedings of the 33rd IEEE International Conference on Very Large Data Bases. Vienna, Austria, 2007:15-26.
[11]	Vlachou A, Doulkeridis C, Kotidis Y, et al. SKYPEER: Efficient subspace skyline computation over distributed data[C]// Proceedings of the 23rd IEEE International Conference on Data Engineering. 2007:416-425.
[12]	Tao Y, Xiao X, Pei J. SUBSKY: Efficient computation of skylines in subspaces[C]// Proceedings of the 22nd IEEE International Conference on Data Engineering. 2006.
[13]	Pei J, Yuan Y, Lin X, et al. Towards multidimensional subspace skyline analysis[J]. ACM Transactions on Database Systems, 2006,31(4):1335-1381.
[14]	Tao Y, Papadias D. Maintaining sliding window skylines on data streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2006,18(3):377-391.
[15]	Lin X, Yuan Y, Wang W, et al. Stabbing the skyline: Efficient skyline computation over sliding windows[C]// Proceedings of the 21st IEEE International Conference on Data Engineering. 2005:502-513.

计算SKY的预排序分组算法

Presorting Grouping Algorithm for Skyline Computation

可视化

摘要/Abstract

引用本文

使用本文

参考文献 15

相关文章 15

编辑推荐

Metrics

本文评价

[1]	贺璇, 刘怡欣, 何小海, 卿粼波, 陈洪刚. 基于改进残差网络的联合损失步态特征识别[J]. 计算机与现代化, 2022, 0(04): 27-32.
[2]	马云龙1,高云玲1,卿黎飞1,熊悠然2. 基于单目视觉的助航灯具定位及发光口识别[J]. 计算机与现代化, 2018, 0(08): 51-.
[3]	孔倩倩，赵辽英，张莉. 基于图像轮廓分析的室内窗户检测[J]. 计算机与现代化, 2018, 0(04): 56-.
[4]	汪洋1,2，许映秋1,2，彭艳兵1,2. 基于KNN技术的校内网验证码识别[J]. 计算机与现代化, 2017, 0(2): 93-97.
[5]	陈泓佑，李郁峰. 一种精确的运动目标外轮廓提取方法[J]. 计算机与现代化, 2016, 0(3): 74-77.
[6]	王美阳1，唐学文2，杨正益3. 基于膨胀系数的正则表达式分组算法[J]. 计算机与现代化, 2014, 0(7): 129-132.
[7]	吴震菊. 基于S变换融合Canny算子的汽车轮廓提取[J]. 计算机与现代化, 2014, 0(4): 29-32.
[8]	关永洪. 基于非抽样轮廓波变换和矩阵F-范数的旋转不变纹理图像检索方法[J]. 计算机与现代化, 2013, 1(9): 95-97,1.
[9]	杨平，刘在英 . 基于相对链码和改进LCS算法的图形匹配实现[J]. 计算机与现代化, 2013, 12(12): 106-109.
[10]	蒲新华;李永久. 基于CV模型的目标检测与提取[J]. 计算机与现代化, 2013, 1(11): 25-27.
[11]	吴勇;徐峰. 一种适用于短消息文本的聚类算法[J]. 计算机与现代化, 2012, 198(2): 31-34.
[12]	]陈康;黄影平;张仁杰. 基于主动轮廓模型的行人边缘检测应用研究[J]. 计算机与现代化, 2012, 208(12): 66-68,7.
[13]	于若飞. 背景提取和水平集相结合的运动目标轮廓提取方法[J]. 计算机与现代化, 2011, 7(7): 40-44.
[14]	郭同华;谭守标;徐超. 彩色漫画轮廓提取研究[J]. 计算机与现代化, 2010, 1(3): 12-4.
[15]	赵文胜尹升爱. 基于单目视频图像序列的三维表面重建研究[J]. 计算机与现代化, 2010, 1(02): 88-90.