Journal of Frontiers of Computer Science and Technology ›› 2010, Vol. 4 ›› Issue (11): 1027-1038.DOI: 10.3778/j.issn.1673-9418.2010.11.008

• 学术研究 • Previous Articles     Next Articles

Research on Novel Method for Forecasting Aggregate Queries over Data Streams in Road Networks*

FENG Jun+;LU Chunyan


  1. College of Computer & Information, Hohai University, Nanjing 210098, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-11-01 Published:2010-11-01
  • Contact: FENG Jun


冯 钧+;陆春燕


  1. 河海大学 计算机与信息学院, 南京 210098
  • 通讯作者: 冯 钧

Abstract: The technologies of spatial-temporal data streams have been the hotspot in the research field of databases. However, there is not an efficient index applied to aggregate queries over data streams in two-dimensional non-Euclidean spatial road networks until now. In order to implement aggregate queries over moving objects in road networks about the past, present, and future, it needs to solve the problems as follows: (1) the non-Euclidean spatial problem of road networks; (2) the problem of distinct counting, non-uniform of moving objects, and predictive ag-gregate queries over moving objects in road networks. Sketch RR-tree solves the problem of distinct counting and non-Euclidean spatial. In order to solve the problem of non-uniform moving objects, using sketching-partition idea for reference, this paper proposes dynamic sketch index: DynSketch by using AMH(adaptive multi-dimen¬sional histogram) to intelligently partition static sketch, making the data in every part uniform, and to improve the approximate quality of aggregate queries in road networks. Then, based on DynSketch index, it proposes predictive aggregate queries over data streams in road networks using ES (exponential smoothing) methods.

Key words: road network, data stream, aggregate query, predictive aggregate, DynSketch index

摘要: 时空数据流的聚集查询技术已经成为数据库领域的研究热点。到目前为止, 还没有一种有效的全时态聚集索引适用于非欧氏空间的路网数据流聚集查询。实现路网数据流的全时态聚集查询, 必须解决: (1) 路网的非欧氏空间特性问题; (2) 路网上移动对象的重复计数、非均匀分布以及预测聚集问题。Sketch RR-tree解决了非欧氏空间特性和重复计数问题; 为解决非均匀分布问题, 借鉴草图划分思想, 提出动态草图索引结构DynSketch:采用AMH智能划分Sketch RR-tree, 使每个划分区域内车辆均匀分布, 以提高聚集查询质量; 同时, 基于DynSketch, 结合ES预测模型, 提出了路网数据流的预测聚集查询算法。

关键词: 道路网, 数据流, 聚集查询, 预测聚集, DynSketch索引

CLC Number: