数据流上Ad Hoc查询的自适应处理算法

doi:10.3969/j.issn.1000-3428.2013.09.016

计算机工程

数据流上Ad Hoc查询的自适应处理算法

黄浩，杨卫东

(复旦大学计算机科学技术学院，上海 201203)

收稿日期:2012-09-03 出版日期:2013-09-15 发布日期:2013-09-13
作者简介:黄浩(1989－)，男，硕士，主研方向：数据流，复杂事件处理；杨卫东，副教授、博士
基金资助:
国家“863”计划基金资助项目(2008AA121705)；上海市重点基础研究基金资助项目(08JC1402500)；上海市科技创新基金资助项目(Xiao-34-1)

Adaptive Processing Algorithm of Ad Hoc Query in Data Streams

HUANG Hao, YANG Wei-dong

(School of Computer Science, Fudan University, Shanghai 201203, China)

Received:2012-09-03 Online:2013-09-15 Published:2013-09-13

摘要/Abstract

摘要： 对数据流上的Ad Hoc查询进行自适应处理，需要保证已有查询计划快速在线更新和迁移，但现有方法实现新旧查询计划的更新需要大量的滑动窗口状态转换。为此，提出一种Ad Hoc查询自适应处理算法。该算法基于数据流概要分布特性和自定义评分模型，快速计算出现有查询计划的最佳增量更新，以实现新到达的Ad Hoc查询处理，降低新旧查询计划切换时间。在数据流benchmark Linear Road提供的高速公路数据集上进行实验，结果表明，与MS、PT方法相比，该算法可较快完成新旧查询计划的切换。

关键词: 数据流, 查询计划, Ad Hoc查询, 自适应算法, 查询计划更新

Abstract: The adaptive processing of non-stop coming Ad Hoc queries over data stream concerns much on the fast on-the-fly plan updating and migration. Existing methods implementing the shifting from old plan to new plan need amounts of work to move the state maintained in operators’ sliding time window leading to large time delay. This paper proposes a highly efficient Ad Hoc query processing algorithm called AQU, which can compute the best incremental updating based on the summary view of data stream characteristics and a slef-defined model, handle the newly arriving Ad Hoc queries. This algorithm reduces the time shifting from old plan to new one and is also adaptive to non-top incoming queries. Experiments on the high way data generated by data stream benchmark Linear Road shows the efficiency of this algorithm.

Key words: data stream, query plan, Ad Hoc query, adaptive algorithm, query plan updating

中图分类号:

TP311

黄浩，杨卫东. 数据流上Ad Hoc查询的自适应处理算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2013.09.016.

HUANG Hao, YANG Wei-dong. Adaptive Processing Algorithm of Ad Hoc Query in Data Streams[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2013.09.016.

http://www.ecice06.com/CN/Y2013/V39/I9/74

参考文献

[1] Zou Qiong, Wang Huayong, Soulé R, et al. From a Stream of Relational Queries to Distributed Stream Processing[C]//Proc. of Internet Conf. on Very Large Data Base[S. 1.]: View Publication, 2010: 1394-1405. [2] Arasu A, Babcock B, Babu S, et al. STREAM: The Stanford Stream Data Manager(Demonstration Description)[C]//Proc. of 2003 ACM SIGMOD International Conference on Manage- ment of Data. [S. 1.]: ACM Press, 2003: 665-665. [3] Kr?mer J, Seeger B. PIPES: A Public Infrastructure for Processing and Exploring Streams[C]//Proc. of 2004 ACM SIGMOD International Conference on Management of Data. [S. 1.]: ACM Press, 2004: 925-926. [4] Rundensteiner E K, Ding Luping, Sutherland T, et al. CAPE: Continuous Query Engine with Heterogeneous-grained Adaptivity[C]//Proc. of the 30th International Conference on Very Large Data Bases. Worcester, USA: [s. n.], 2004: 1353-1356. [5] Chandrasekaran S, Franklin M J. PSoup: A System for Strea- ming Queries over Streaming Data[J]. The VLDB Journal, 2003, 12(2): 140-156. [6] Lerner A, Shasha D. The Virtues and Challenges of Ad Hoc+ Streams Querying in Finance[J]. IEEE Data Engineering Bulletin, 2003, 26(1): 49-56. [7] Moonjung C, Jian P, Ke W. Answering Ad Hoc Aggregate Queries from Data Streams Using Prefix Aggregate Trees[J]. Knowledge and Information Systems, 2007, 2(3): 301-329. [8] Babcock B, Babu S, Datar M, et al. Models and Issues in Data Stream Systems[C]//Proc. of the 21st ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Systems. [S. 1.]: ACM Press, 2002: 1-16. [9] Yang Yin, Kramer J, Papadias D, et al. HybMig: A Hybrid Approach to Dynamic Plan Migration for Continuous Queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(3): 398-411. [10] Zhu Yali, Rundensteiner E A, Heineman G T. Dynamic Plan Migration for Continuous Queries over Data Streams[C]//Proc. of 2004 ACM SIGMOD International Conference on Management of Data. [S. 1.]: ACM Press, 2004: 431-442. [11] Das G, Gunopulos D, Koudas N, et al. Ad Hoc Top-k Query Answering for Data Streams[C]//Proc. of the 33rd Inter- national Conference on Very Large Data Bases. [S. 1.]: ACM Press, 2007: 183- 194. [12] Arasu A, Cherniack M, Galvez E, et al. Linear Road: A Stream Data Management Benchmark[C]//Proc. of the 30th Inter- national Conference on Very Large Data Bases. [S. 1.]: ACM Press, 2004: 480-491. [13] Mousavi H, Zaniolo C. Fast and Accurate Computation of Equi-depth Histograms over Data Streams[C]//Proc. of the 14th International Conference on Extending Database Technology. [S. 1.]: ACM Press, 2011: 69-80. 编辑索书志

[1]	王博, 张远, 杨咏蓓. 基于模仿学习的决策树码率自适应算法研究[J]. 计算机工程, 2023, 49(5): 206-214.
[2]	高峰, 姚光涛, 顾进广. 基于改进多嵌入空间的实时语义数据流推理[J]. 计算机工程, 2022, 48(2): 55-64.
[3]	章俊伟, 卞金来, 丁良辉, 支琤, 杨峰, 钱良. 慢衰落信道下并行HARQ系统的速率自适应算法[J]. 计算机工程, 2021, 47(2): 201-205,211.
[4]	陈梓晗, 叶进, 肖庆宇. 一种基于视频分类的码率自适应算法[J]. 计算机工程, 2021, 47(12): 118-121,130.
[5]	郭渝洛, 边浩东, 董润婷, 唐嘉豪, 王晓英, 黄建强. 基于SIMD的并行傅里叶空间图像相似度计算[J]. 计算机工程, 2021, 47(11): 247-253.
[6]	周胜, 刘三民. 基于动态策略的多源迁移学习数据流分类研究[J]. 计算机工程, 2020, 46(5): 139-143,149.
[7]	崔艳, 李庆华. 二阶多智能体系统参数自适应的有限时间一致性算法[J]. 计算机工程, 2020, 46(4): 273-278,286.
[8]	康雁, 杨其越, 李浩, 梁文韬, 李晋源, 崔国荣, 王沛尧. 基于主题相似性聚类的自适应文本分类[J]. 计算机工程, 2020, 46(3): 93-98.
[9]	施元昊, 张健铭, 徐正蓺, 滕国伟. 多运动模式下的累积误差修正行人航位推算算法[J]. 计算机工程, 2020, 46(12): 305-312.
[10]	毛亚琼, 田立勤, 王艳, 毛亚萍, 王志刚. 引入局部向量点积密度的数据流离群点快速检测算法[J]. 计算机工程, 2020, 46(11): 132-138,147.
[11]	杜诗语, 韩萌, 申明尧, 张春砚, 孙蕊. 概念漂移数据流集成分类算法综述[J]. 计算机工程, 2020, 46(1): 15-24,30.
[12]	刘建航, 李大伟, 黄庭培, 姜忠泰, 李世宝. 联合动态聚合帧长机制的速率自适应算法[J]. 计算机工程, 2019, 45(12): 91-97.
[13]	高嘉伟,刘建敏. 一种面向轨迹信息的时序数据流异常检测算法[J]. 计算机工程, 2018, 44(5): 25-32,46.
[14]	储光,胡学钢,张玉红. 基于语义的文本数据流概念漂移检测算法[J]. 计算机工程, 2018, 44(2): 24-30.
[15]	王炜,徐凌泽,周语宁,潘鹏. MIMO干扰信道中基于非线性预编码的收发机设计[J]. 计算机工程, 2018, 44(10): 136-140.

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

选择包含的内容

数据流上Ad Hoc查询的自适应处理算法

Adaptive Processing Algorithm of Ad Hoc Query in Data Streams

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

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

选择包含的内容

数据流上Ad Hoc查询的自适应处理算法

Adaptive Processing Algorithm of Ad Hoc Query in Data Streams

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价