###
DOI:
Journal of Software:2009.20(9):2462-2469

一种空间更优的数据流查询包含编码区间索引
姚秋林,王映,刘萍,郭莉
(中国科学院 计算技术研究所,北京 100190;中国科学院 研究生院,北京 100049)
Storage Optimized Containment-Encoded Intervals Indexing for Data Stream Querying
YAO Qiu-Lin,WANG Ying,LIU Ping,GUO Li
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2573   Download 2965
Received:August 07, 2007    Revised:June 03, 2008
> 中文摘要: 给出一种基于CEI(containment-encoded intervals)的存储优化的数据流查询区间索引结构.在数据流处理中涉及到大量的数值型区间查询操作,构造一个基于主存并支持快速查询的区间索引结构十分必要.对CEI索引结构而言,虽然支持高速查询,但存储利用率较低.针对该问题,提出了索引结构ACEI(advanced-CEI).在CEI索引结构的基础上,通过数据结构调整和参数优化,ACEI可在保持原有查询速度的前提下将CEI的空间复杂度由O(R+N·W/L+N·log(L))降为O(sqrt(R·N)+ N·sqrt(W)).实验结果表明,ACEI结构可以极大地提高索引结构的存储利用率,并且可以用于大端点值域下的区间索引.
Abstract:An index structure ACEI (advanced CEI) is proposed in this paper to optimize the storage of CEI (containment-encoded intervals)-based interval index structure for data stream processing which involves a lot of operations of the numerical range query. It is necessary to construct a main memory-based query index with a low storage cost and little search time. The CEI index structure has low storage utilization, although it supports for high-speed query. To solve this problem, index structure ACEI is proposed. Based on CEI, through structural adjustment and optimization of parameters, ACEI can maintain the high speed of query operation and reduce the space complexity from O(R+N·W/L+N·log(L)) to O(sqrt(R·N)+ N·sqrt(W)). Experiments show that ACEI structure can greatly improve the storage utilization and can be used for interval index against a large endpoint range.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Basic Research Program of China under Grant No.2007CB311100 (国家重点基础研究发展计划(973)) Supported by the National Basic Research Program of China under Grant No.2007CB311100 (国家重点基础研究发展计划(973))
Foundation items:
Reference text:

姚秋林,王映,刘萍,郭莉.一种空间更优的数据流查询包含编码区间索引.软件学报,2009,20(9):2462-2469

YAO Qiu-Lin,WANG Ying,LIU Ping,GUO Li.Storage Optimized Containment-Encoded Intervals Indexing for Data Stream Querying.Journal of Software,2009,20(9):2462-2469