电子学报 ›› 2021, Vol. 49 ›› Issue (5): 992-1000.DOI: 10.12263/DZXB.20200300

• 学术论文 • 上一篇    下一篇

面向时空数据流的移动对象空间索引构建

杨良怀, 沈东海, 范玉雷, 高楠   

  1. 浙江工业大学计算机科学与技术学院, 浙江杭州 310023
  • 收稿日期:2020-03-25 修回日期:2020-07-19 出版日期:2021-05-25 发布日期:2021-05-25
  • 通讯作者: 范玉雷(通讯作者) 男,1984年出生于内蒙古赤峰.毕业于中国人民大学,获博士学位,浙江工业大学计算机学院讲师,主要研究方向为数据库管理系统、数据流管理系统和数据挖掘.在IEEE Data Eng Bull等英文期刊和计算机学报等中文期刊以及DASFAA和WAIM等数据库领域国际会议发表学术论文20余篇. E-mail:fyl815@zjut.edu.cn
  • 作者简介:杨良怀 男,1967年出生于浙江新昌.毕业于北京大学,获博士学位.浙江工业大学计算机学院教授,主要研究方向为数据库系统、数据挖掘.在VLDB J,J of Info and Soft Tech,J of Sys and Soft,《计算机研究与发展》、《软件学报》等期刊以及VLDB,SIGKDD,CIKM,DASFAA等数据库领域重要会议上发表学术论文80余篇. E-mail:yanglh@zjut.edu.cn;沈东海 男,1995年出生于浙江宁波.浙江工业大学硕士研究生,主要研究方向为时空数据流处理. E-mail:215936795@qq.com
  • 基金资助:
    国家自然科学基金(No.61702456);绍兴柯桥浙工大创新研究院项目(No.2019KQT002)

A Moving Object Spatial Index for Spatio-Temporal Data Stream

YANG Liang-huai, SHEN Dong-hai, FAN Yu-lei, GAO Nan   

  1. School of Computer Science and Technology, Zhejiang University of Technology, Hangzhou, Zhejiang 310023, China
  • Received:2020-03-25 Revised:2020-07-19 Online:2021-05-25 Published:2021-05-25

摘要: 本文针对时空数据流提出了一种基于时间窗口数据排序和批量装载的移动对象空间索引构建方法HSTRCL.该方法用固定长度的时间窗口将连续的时空数据流进行切分,每当一个时间窗口完成数据缓存,采用优化的索引批量装载技术,从传统的构建流程中尽可能分离出耗时的数据划分和排序操作,将数据流的接收及其他构建操作并行执行,避免不必要的加锁同步开销,加快索引的构建效率;同时,采用基于Hash和STR的主、辅索引构建技术,满足高性能且多样化的查询需求.另外,为进一步提高对象查询性能,引入聚合技术划分对象,提出了一种基于时间窗口对象聚合和批量装载的移动对象空间索引构建方法OAHSTRCL,对象查询时间约为HSTRCL的65%,但对空间查询性能会有一定程度的影响.通过理论分析和多种实验验证了所提方法的有效性.

关键词: 时空数据流, 移动对象, 空间索引, R树, 对象聚合

Abstract: In light of the characteristics of spatio-temporal data stream,we propose a moving object spatial index construction method called HSTRCL,which is based on time window data sorting and bulk loading.It segments the continuous spatio-temporal data stream with fixed-length time windows; after finishing caching the data of a time window,by combining parallel processing and optimized bulk loading technology,we isolate as much as possible the time-consuming work of data partitioning and sorting operations from the traditional build process,and parallize them with the reception of data streams and other build operations.Furthermore,we avoid unnecessary locking synchronization overhead.And all these techniques improve the efficiency of index construction.In addition,to meet the performance and diverse query requirements,we also adopt the primary-auxiliary index construction technology based on Hash and STR.To further improve the performance in the object query scenario,we invent another moving object spatial index construction method OAHSTRCL via time window object aggregation and bulk loading,where objects are divided more finely,and the object query time required is about 65% of HSTRCL,though it will affect the performance of spatial query to some extent.Theoretical analysis and experiments have demonstrated the effectiveness of our proposed methods.

Key words: spatio-temporal data stream, moving object, spatial index, R-tree, object aggregation

中图分类号: