基于网格索引的数据流子空间概率轮廓查询

doi:10.3969/j.issn.1000-3428.2013.02.010

计算机工程 ›› 2013, Vol. 39 ›› Issue (2): 50-54. doi: 10.3969/j.issn.1000-3428.2013.02.010

基于网格索引的数据流子空间概率轮廓查询

杨艳艳，赵雷，杨季文

(苏州大学计算机科学与技术学院，江苏苏州 215006)

收稿日期:2012-03-26 修回日期:2012-05-08 出版日期:2013-02-15 发布日期:2013-02-13
作者简介:杨艳艳(1988－)，女，硕士研究生，主研方向：流数据管理与挖掘；赵雷，副教授、博士；杨季文，教授
基金资助:
国家自然科学基金资助项目(61073061)

Probabilistic Skyline Query in Subspaces over Data Streams Based on Grid Index

YANG Yan-yan, ZHAO Lei, YANG Ji-wen

(School of Computer Science and Technology, Soochow University, Suzhou 215006, China)

Received:2012-03-26 Revised:2012-05-08 Online:2013-02-15 Published:2013-02-13

摘要/Abstract

摘要： 在数据流子空间上的连续概率轮廓查询(CPSQS)基础上，提出一种基于网格索引结构的概率轮廓查询算法。采用适合于子空间轮廓计算的网格索引结构，将数据空间划分成若干个格，利用格间的支配关系，减少对象之间的比较次数。同时挖掘全空间与子空间上格的概率上下界关系，设计有效的剪枝策略提高CPSQS算法的性能。理论分析和实验结果表明，该算法能满足实际应用中用户的个性化查询要求，降低查询响应时间。

关键词: 数据流, 子空间, 轮廓查询, 概率查询, 不确定数据

Abstract: This paper proposes Continuous Probabilistic Skyline Query in Subspaces(CPSQS) over sliding window on uncertain data streams. Moreover, a novel algorithm using a regular grid index, which is adaptable for solving subspace skyline issue, is presented to reduce the dominating testing costs. At the same time, based on the subtle relationship between the probabilistic bounds of full space and an arbitrary subspace, a set of pruning strategies are developed to improve the performance of CPSQS. Analytical analysis and experimental results show that this algorithm can meet individuation query of users, reduce query response time.

Key words: data streams, subspace, skyline query, probabilistic query, uncertain data

中图分类号:

TP311

杨艳艳, 赵雷, 杨季文. 基于网格索引的数据流子空间概率轮廓查询[J]. 计算机工程, 2013, 39(2): 50-54.

YANG Yan-Yan, DIAO Lei, YANG Ji-Wen. Probabilistic Skyline Query in Subspaces over Data Streams Based on Grid Index[J]. Computer Engineering, 2013, 39(2): 50-54.

http://www.ecice06.com/CN/Y2013/V39/I2/50

参考文献

[1] Stephan B, Donald K. The Skyline Operator[C]//Proc. of the 17th International Conference on Data Engineering. Heidelberg, Germany: [s. n.], 2001: 421-430.
[2] Jan C, Parke G, Jarek G, et al. Skyline with Presorting[C]// Proc. of the 19th International Conference on Data Engineering. Bangalore, India: [s. n.], 2003: 717-816.
[3] Dimitris P, Tao Yufei, Greg F, et al. An Optimal and Progressive Algorithm for Skyline Queries[C]//Proc. of ACM SIGMOD International Conference on Management of Data. California, USA: [s. n.], 2003: 467-478.
[4] Tao Yufei, Dimitris P. Maintaining Sliding Window Skylines on Data Streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(2): 377-391.
[5] Tao Yufei, Xiao Xiaokui, Pei Jian. SUBSKY: Efficient Computation of Skylines in Subspaces[C]//Proc. of the 22nd International Conference on Data Engineering. Atlanta, USA: [s. n.], 2006: 65-74.
[6] Pei Jian, Ada W F, Lin Xuemin. Computing Compressed Multidimensional Skyline Cubes Efficiently[C]//Proc. of the 23rd International Conference on Data Engineering. Istanbul, Turkey: [s. n.], 2007: 96-105.
[7] 孙圣力, 黄震华, 李金玖, 等. 数据流上高效计算子空间skyline的算法[J]. 计算机学报, 2007, 30(8): 1418- 1428.
[8] Pei Jian, Jiang Bin, Lin Xuemin, et al. Probabilistic Skylines on Uncertain Data[C]//Proc. of the 33rd International Conference on Very Large Data Bases. Vienna, Austria: [s. n.], 2007: 15-26.
[9] Zhang Wenjie, Lin Xuemin, Zhang Ying. Probabilistic Skyline Operator over Sliding Windows[C]//Proc. of the 25th International Conference on Data Engineering. Shanghai, China: [s. n.], 2009: 1060-1071.
[10] 孙圣力, 戴东波, 黄震华, 等. 概率数据流上skyline查询处理算法[J]. 电子学报, 2009, 37(2): 285-293.
[11] 王晓伟, 贾焰, 杨树强, 等. 存在级不确定数据上的概率skyline计算[J]. 计算机研究与发展, 2011, 48(1): 68-76.
[12] Maria K, Apostolos N P, Yannis M. Continuous Top-k Dominating Queries in Subspaces[C]//Proc. of PCI’08. Samos Island, Greece: [s. n.], 2008: 31-35.

[1]	江雨燕, 陶承凤, 李平. 数据增强和自适应自步学习的深度子空间聚类算法[J]. 计算机工程, 2023, 49(8): 96-103, 110.
[2]	胡慧旗, 张维强, 徐晨. 判别性增强的稀疏子空间聚类[J]. 计算机工程, 2023, 49(2): 98-104.
[3]	高峰, 姚光涛, 顾进广. 基于改进多嵌入空间的实时语义数据流推理[J]. 计算机工程, 2022, 48(2): 55-64.
[4]	刘鹏飞, 朱健晨, 万良易, 江波. 低功耗异构计算架构的高光谱遥感图像分类研究[J]. 计算机工程, 2022, 48(12): 9-15,23.
[5]	贾思宇, 路茗, 丁华泽, 陈明, 赵鲁阳. 一种改进的信号子空间聚焦宽带DOA估计算法[J]. 计算机工程, 2022, 48(1): 175-181.
[6]	陶洋, 鲍灵浪, 胡昊. 结构约束的对称低秩表示子空间聚类算法[J]. 计算机工程, 2021, 47(4): 56-61,67.
[7]	郭渝洛, 边浩东, 董润婷, 唐嘉豪, 王晓英, 黄建强. 基于SIMD的并行傅里叶空间图像相似度计算[J]. 计算机工程, 2021, 47(11): 247-253.
[8]	陈会伟, 刘树美, 刘培学, 公茂法. 超尺度自导注意力网络的遥感船舶识别[J]. 计算机工程, 2021, 47(10): 314-320.
[9]	孙登第, 凌媛, 丁转莲, 罗斌. 基于稀疏子空间聚类的多层网络社团检测[J]. 计算机工程, 2021, 47(10): 52-60.
[10]	刘宇航, 马慧芳, 刘海姣, 余丽. 一种可重叠子空间K-Means聚类算法[J]. 计算机工程, 2020, 46(8): 58-63,71.
[11]	赵琪琪, 马慧芳, 刘海姣, 贾俊杰. 融合节点属性与结构信息的子空间异常社区检测方法[J]. 计算机工程, 2020, 46(6): 94-102.
[12]	周胜, 刘三民. 基于动态策略的多源迁移学习数据流分类研究[J]. 计算机工程, 2020, 46(5): 139-143,149.
[13]	马喆康, 迪力亚尔·帕尔哈提, 早克热·卡德尔, 吐尔根·依布拉音, 西尔艾力·色提, 艾山·吾买尔. 一种集成深度学习模型的旅游问句文本分类算法[J]. 计算机工程, 2020, 46(11): 70-76.
[14]	毛亚琼, 田立勤, 王艳, 毛亚萍, 王志刚. 引入局部向量点积密度的数据流离群点快速检测算法[J]. 计算机工程, 2020, 46(11): 132-138,147.
[15]	王少波, 郭英, 眭萍, 李红光, 杨鑫. 欠定条件下同步组网跳频信号盲源分离方法[J]. 计算机工程, 2020, 46(10): 166-172,181.

选择文件类型/文献管理软件名称

选择包含的内容

基于网格索引的数据流子空间概率轮廓查询

Probabilistic Skyline Query in Subspaces over Data Streams Based on Grid Index

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于网格索引的数据流子空间概率轮廓查询

Probabilistic Skyline Query in Subspaces over Data Streams Based on Grid Index

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价