基于网格的数据流连续约束Skyline处理技术研究

J4 ›› 2011, Vol. 33 ›› Issue (8): 173-180.

基于网格的数据流连续约束Skyline处理技术研究

张丽，邹鹏，贾焰

(国防科学技术大学计算机学院，湖南长沙 410073)

收稿日期:2009-07-07 修回日期:2009-11-05 出版日期:2011-08-25 发布日期:2011-08-25
作者简介:张丽(1981),女,山东曹县人，博士生，研究方向为数据库和数据流。邹鹏(1957),男,山东青田人，博士，教授，研究方向为操作系统，分布计算、网络与信息安全。贾焰(1961),女,四川成都人，博士，教授，研究方向为网络与信息安全、数据库和数据挖掘。
基金资助:
国家863计划资助项目（2006AA01Z451，2007AA010502，2007AA01Z474）

A Grid Index Based Method for Continuous Constrained Skyline Query over Data Streams

ZHANG Li,ZOU Peng,JIA Yan

(School of Computer Science,National University of Defense Technology,Changsha 410073,China)

Received:2009-07-07 Revised:2009-11-05 Online:2011-08-25 Published:2011-08-25

摘要/Abstract

摘要：

作为数据流上的一种重要查询，skyline对于很多在线应用都非常重要，包括移动运算环境、网络监控、传感器网络、股票交易等。与大多数数据流skyline处理技术不同，本文着重于约束skyline的处理。约束skyline支持用户定义在某些属性上的偏好，系统中存在多个约束skyline查询，为skyline查询处理技术带来了新的挑战。为了在高速数据流上对约束skyline进行高效处理，本文使用了一种网格索引存储元组，并提出两个算法用于计算和维护skyline集合，我们还为每个查询定义了影响区域，以减少在新元组到达和旧元组失效时需要处理的网格数目。理论分析和实验证明了该方法的有效性。

关键词: 约束skyline, 数据流, 网格索引

Abstract:

As an essential query, skyline computation over data streams is very important for many online applications, including mobile environment, network monitoring, communication, sensor network and stock market trading, etc. Different from most popular skyline processing methods that deal with the whole data set, this paper focuses on constrained skyline processing over data streams. We employ a grid based index to store the tuples and put forward two algorithms to compute and maintain the skyline set. We also define Influence Area for every query to minimize the cells needed to be processed when new tuples arrive and old tuples expire. Theoretical analysis and experimental evidences show the efficiency of the proposed approach.

Key words: constrained skyline;data stream;grid index

张丽，邹鹏，贾焰. 基于网格的数据流连续约束Skyline处理技术研究[J]. J4, 2011, 33(8): 173-180.

ZHANG Li,ZOU Peng,JIA Yan. A Grid Index Based Method for Continuous Constrained Skyline Query over Data Streams[J]. J4, 2011, 33(8): 173-180.

[1]	李金熹, 尹首一, 魏少军, 胡杨. 基于MLIR的数据流模型[J]. 计算机工程与科学, 2024, 46(07): 1151-1157.
[2]	张家豪, 邓金易, 尹首一, 魏少军, 胡杨. 基于Actor模型的众核数据流硬件架构探索[J]. 计算机工程与科学, 2024, 46(06): 959-967.
[3]	丁滟, 王闯, 冯了了, 王锋, 常俊胜. 基于区块链监管的联盟数据可信流通[J]. 计算机工程与科学, 2022, 44(10): 1771-1780.
[4]	张喜龙, 韩萌, 陈志强, 武红鑫, 李慕航. 基于Hellinger距离的不平衡漂移数据流Boosting分类算法[J]. 计算机工程与科学, 2022, 44(05): 788-799.
[5]	乔冠杰, 吕高锋, 谭靖, 莫露莎. 大规模数据流统计中冷热流替换策略优化[J]. 计算机工程与科学, 2021, 43(09): 1567-1573.
[6]	朱广林, 吕方, 赖庆宽, 陈华英, 何先波, . 编译器中激进蝴蝶优化方法的研究与实现[J]. 计算机工程与科学, 2021, 43(06): 962-968.
[7]	文凯, 耿小海, 朱璐伟, 许萌萌, . 基于AO算法的数据流频繁项集挖掘[J]. 计算机工程与科学, 2020, 42(12): 2259-2264.
[8]	熊菊霞1,2,3,吴尽昭1,2,3. 异构复杂信息网络敏感数据流动态挖掘[J]. 计算机工程与科学, 2020, 42(04): 628-633.
[9]	张馨予, 安建成, 曹锐. 基于自适应随机森林的数据流分类算法[J]. 计算机工程与科学, 2020, 42(03): 543-549.
[10]	杨杰，张东月，周丽华，黄皓，丁海燕. 基于网格耦合的数据流异常检测[J]. 计算机工程与科学, 2020, 42(01): 25-35.
[11]	袁泉1,2,郭江帆1,赵学华1. 一种基于集成的不均衡数据流分类算法[J]. 计算机工程与科学, 2019, 41(08): 1519-1524.
[12]	李艺煌，马胜，郭阳，陈桂林，徐睿. 基于平铺数据流的可配置神经网络加速器[J]. 计算机工程与科学, 2019, 41(06): 963-972.
[13]	李易1，常成娟1，卢圣健1，江道忠2，范东睿1，叶笑春1. 面向数据流结构的指令映射优化方法[J]. 计算机工程与科学, 2019, 41(01): 9-13.
[14]	杨胜哲，于俊清,唐九飞. 数据流程序动态调度与优化[J]. 计算机工程与科学, 2017, 39(07): 1201-1210.
[15]	梁毅1，侯颖1，陈诚1，金翊2. 面向大数据流式计算的任务管理技术综述[J]. 计算机工程与科学, 2017, 39(02): 215-226.