一种空间更优的数据流查询包含编码区间索引

• 作者: 刘萍 姚秋林 王映 郭莉
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 数据流 持续查询 区间索引 CEI(containment-encoded intervals) ACEI
• 年，卷（期）: 2009,（9）
• 所属期刊栏目: 数据库技术
• 页码范围: 2462-2469
• 页数: 8页
• 分类号: TP311
• 字数: 5279字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2009.03402

摘要

给出一种基于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结构可以极大地提高索引结构的存储利用率,并且可以用于大端点值域下的区间索引.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘萍	中国科学院计算技术研究所	35	435	11.0	19.0
2	郭莉	中国科学院计算技术研究所	64	788	14.0	26.0
3	王映	中国科学院计算技术研究所	3	23	2.0	3.0