时态拟序数据结构研究及应用  

Study and Application of Temporal Quasi-Order Data Structure

作　　者：叶小平[1] 汤庸[1] 林衍崇 陈钊滢 张智博[1] 

机构地区：[1]华南师范大学计算机学院,广东广州510631

出　　处：《软件学报》2014年第11期2587-2601,共15页Journal of Software

基　　金：国家高技术研究发展计划(863)(2013AA01A212);国家自然科学基金(60970044;61272067);广东省自然科学基金(S2011010003409;S2012030006242)

摘　　要：时态数据索引是实现时态数据有效管理的关键技术之一.讨论了一种时态数据结构及其在时态数据索引上的应用.常规的时态数据管理技术多基于代数框架.提出了一种基于拟序关系的时态数据结构,该结构能够像常规关系数据那样实现"一次一集合"的数据操作,并可通过多线程提高查询效率.在此基础上,研究了一种时态数据索引TQOindex.首先,提出时间期间集合上拟序关系和线序划分概念,讨论了线序划分的最优(最小)性质和构建算法,并在最小线序划分框架内研究时态拟序结构基于增量式更新的插入和删除算法.其次,研究了时态拟序结构应用——引入基于拟序扩展集的时态数据索引TQOindex.该索引适用于磁盘(外存)数据管理,可在常规数据库平台上有效使用.其增量式更新机制可应用于"大数据"的动态索引技术.另外,对TQOindex进行了基本仿真,实验结果表明了该工作的可行性和有效性.提出的时态拟序数据结构着眼于新型数据,如语义数据、XML数据和移动对象数据中时态处理与整合机制,相应的工作具有较为广泛的应用扩展性.Temporal index is one of key technologies for temporal data managements. This paper discusses a temporal data structure and its application for temporal data index. Most of existing temporal data methods are based on algebra framework. This paper presents a temporal data structure using quasi-order relation which can achieve multithreading data operations, and puts forward temporal index TQOindex supported by the structure. Firstly, it proposes the conception of quasi-order relationship of temporal data and studies the construct algorithm of linear order partition and its optimal property. Secondly, it dedicates application on temporal data structure with building TQOindex on expand quasi-order set which manages data on disks and can be used in common databases platform. TQOindex can dynamically index ＂big data＂ by its querying schema of ＂one time, one set＂ as well as incremental update mechanism. Finally, the simulations in the paper show the feasibility and validity for TQOindex. In conclusion, temporal quasi-order data structure pays attention to the mechanism of the processing and integration between time and application scene information for new kinds of data such as semantic data, XML data and moving objects data, and the works in this paper offers remarkable extendibility.

关 键 词：时态拟序 基于线序划分数据结构 “一次一集合”查询 增量式更新 TQOindex 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]