多维数据流下的top-k支配查询算法研究  

Study on Top-k Dominating Query Algorithm over Multi-dimensional Data Streams

作　　者：陈加付[1] 孟凡荣[1] 闫秋艳[1] 

机构地区：[1]中国矿业大学计算机科学与技术学院,江苏徐州221116

出　　处：《微电子学与计算机》2010年第8期218-221,225,共5页Microelectronics & Computer

基　　金：国家自然科学基金项目(50674086);江苏省博士后科学基金项目(0701045B);中国矿业大学科技基金项目(2007B017)

摘　　要：Top-k支配查询算法返回前k个支配得分最高的数据对象,在多维数据查询中有效地限定了结果集的大小,但是无法直接应用于数据流查询中.文中使用网格索引结构在多维数据流下构建的top-k支配算法,采取动态创建网格,反向遍历一次求支配区点数,剪枝无效单元格等策略,提高了查询的效率.实验结果证明了该方法在多维数据流查询中的有效性.The top-k dominating query returns k data objects which dominate the highest number of objects, which effectively limits the result size in multi-dimensional data query. However, it cannot be applied to data streams query directly. Using the grid index structure,this paper builds a top-k dominating query model over multi-dimensional data streams. The model improves the query efficiency with the strategy of dynamic creation of grid, traversing the grid to get the points number in dominated region in reversed order and pruning invalid cells. Experiment results prove the validity of the method in multi-dimensional data stream query.

关 键 词：数据流 滑动窗口 TOP-K SKYLINE 网格 

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