ZDC-tree:一种支持面向数据流Skyline查询的高效索引结构  

ZDC-tree:An Efficient Index Structure for Supporting Skyline Query on Data Streams

作　　者：彭敦陆[1] 衣少君[1] 段凯[1] 霍欢[1] 

机构地区：[1]上海理工大学光电信息与计算机工程学院,上海200093

出　　处：《小型微型计算机系统》2013年第6期1288-1294,共7页Journal of Chinese Computer Systems

基　　金：上海市自然科学基金项目(10ZR1421100)资助;国家自然科学基金项目(61003031)资助

摘　　要：数据流上的Skyline查询是近年来数据管理与数据挖掘领域的研究热点.该文针对数据流场景下基于滑动窗口Skyline查询问题,采用基于剪枝策略和分而治之思想,并结合Z-order曲线的性质,提出一种可以在一个分支上进行查询和更新操作的ZDC-tree索引结构,并给出可有效维护Skyline查询计算的ZDCSK算法.算法采用自底向上的方式,归并递归返回Skyline结果集,具备较好的Skyline查询效率.论文从理论和实验上证明了在ZDC-tree上进行Skylike查询的高效性、稳定性及可扩展性.Computation of Skyline query on data-stream has become a research hot spot from data management and data mining area in recent years. This work focuses on the sliding window based Skyline query operation on data streams. An index structure called ZDC- tree was proposed based on the idea of pruning and divide-and-conquer strategies and properties of Z-order curve. ZDC-tree can effi- ciently compute Skyline queries and be maintained on a branch. A series of algorithms-ZDCSK algorithms （ including ZDCSK-insert, ZDCSK-update, ZCDSK-delete ） was developed to implement Skyline queries. ZDCSK algorithms improve the efficiency of Skyline computation in a bottom-up way and return the eventual result by recursively merging the intermediate results. Theoretical analysis and experimental results verify the efficiency, stability and expansibility of performing Skyline query operation on ZDC-tree.

关 键 词：SKYLINE计算 剪枝策略 数据流 Z-order曲线 分而治之 

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