| 摘要: |
| 给出一种基于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结构可以极大地提高索引结构的存储利用率,并且可以用于大端点值域下的区间索引. |
| 关键词: 数据流 持续查询 区间索引 CEI (containment-encoded intervals) ACEI |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Basic Research Program of China under Grant No.2007CB311100 (国家重点基础研究发展计划(973)) |
|
| Storage Optimized Containment-Encoded Intervals Indexing for Data Stream Querying |
|
YAO Qiu-Lin,WANG Ying,LIU Ping,GUO Li
|
| 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. |
| Key words: data stream continual query interval indexing CEI (containment-encoded intervals) ACEI |
