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

给出一种基于cei(containment-encodedintervals)的存储优化的数据流查询区间索引结构.在数据流处理中涉及到大量的数值型区间查询操作,构造一个基于主存并支持快速查询的区间索引结构十分必要.对cei索引结构而言,虽然支持高速查询,但存储利用率较低.针对该问题,提出了索引结构acei(advanced-cei).在cei索引结构的基础上,通过数据结构调整和参数优化,acei可在保持原有查询速度的前提下将cei的空间复杂度由o(r+n·w/l+n·log(l))降为o(sqrt(r·n)+n·sqrt(w)).实验结果表明,acei结构可以极大地提高索引结构的存储利用率,并且可以用于大端点值域下的区间索引.