不确定时态数据Top-k查询

摘要

时态数据在医疗、经济和电子商务等领域有着广泛的应用.由于时间的测量技术不精确等因素,时态数据具有不确定性.文中针对该数据进行研究,处理Top-k查询,即返回与查询点相交的k个权值最大的数据,该权值是根据数据权值和相交概率按一定规则组合计算所得.为有效解决该查询问题,提出了一个基于关系模型和辅助结构的2D R-tree结构,其中关系模型用于管理所有区间数据的R-tree,辅助结构用于管理R-tree中每个节点内部数据权值的大小关系.基于该结构,提出了按权值的降序访问数据的查询算法.从根节点开始遍历R-tree,对于与查询点相交的节点,根据辅助结构中存储的信息找到数据权值最大的项,将它确定为下一个访问对象.实验使用数据规模在30万到1000万的合成数据集,以及包括大约320万条的航班信息的真实数据集.在可扩展数据库SECONDO系统下,将所提方法与无索引方法、R-tree和区间树方法在性能上进行比较,并以平均I/O访问次数和CPU时间作为性能的评判指标.实验结果表明,在1000万条的数据规模下,所提方法优于对比方法2～3个数量级.通过将实验返回的k个结果的概率与权值和实际相交数据的概率和权值作比较可以发现,实验返回的k个结果的概率与权值均靠近实际相交数据的概率和权值的最大值,因此所提算法可行且有效.