论文部分内容阅读
时态数据用于表示数据的时间属性，在医疗、交通、经济和电子商务等领域有着广泛的应用。由于时间测量不精确、设备误差等因素，时态数据往往具有不确定性。本文针对不确定时态数据Top-k查询进行研究，该查询根据用户设定的评分函数返回具有最高（或最低）分数的k个查询结果，这对于在海量数据中返回最符合查询条件的目标数据有重要意义。已有的研究工作主要在确定时态数据查询和不确时态数据表示，针对不确定时态数据的Top-k 查询较少。该查询需要考虑不确定性和权值两方面因素，对时态数据索引和查询处理提出了新的要求，现有时态数据索引很少涉及权值管理。本文主要工作具体如下：
(1) 定义带权值不确定时态数据和不确定时态数据Top-k区间查询，设计并实现一种计算不确定数据相交概率的方法，给出Top-k查询的评分函数。提出一种不确定性时态数据索引结构RR-tree，该结构包含一棵2D R-tree和一个辅助结构。在此基础上设计并实现了相应的查询算法，实现按权值降序访问索引节点，采用真实和合成数据进行实验测试。实验结果验证所提方法可行有效。
(2) 定义不确定时态数据连续Top-k区间查询并设计相应的查询算法。由于时间区间存在有效期，传统的Top-k查询只考虑在查询范围内评分最高的对象，并不考虑返回的对象是否在整个查询区间内都有效。针对不确定时态数据连续Top-k区间查询，提出一种区间划分构建的双索引DR-tree，基于该索引可以实现查询时减少访问索引中非叶子节点信息来提高查询效率。同时为管理查询区间每个点上的k个结果，提出了一个树状结构，给出连续Top-k查询算法，采用真实和合成数据进行实验。通过对比实验，表明本文所提方法在不确定时态数据连续Top-k区间查询上有较好的查询性能。
(3) 高效更新时态数据索引。时态数据库系统不仅要管理历史数据，还要支持处理更新数据。首先基于已有的批量加载更新算法，结合区间划分更新本文提出的DR-Tree。将新加入的时态数据分为两部分，分别批量加载构建DR-Tree子树，再将DR-Tree子树分别插入对应的历史DR-Tree中。然后，将基于DR-tree提出的批量加载更新方法扩展至区间树，实现区间树批量更新。采用真实数据集和合成数据集，与删除重建索引和逐个插入更新索引算法进行对比，实验结果表明本文所提批量更新时态数据索引对于两种结构都有较好的性能，当数据规模较大时，所提方法在更新效率上优于对比方法2倍以上。
(1) 定义带权值不确定时态数据和不确定时态数据Top-k区间查询，设计并实现一种计算不确定数据相交概率的方法，给出Top-k查询的评分函数。提出一种不确定性时态数据索引结构RR-tree，该结构包含一棵2D R-tree和一个辅助结构。在此基础上设计并实现了相应的查询算法，实现按权值降序访问索引节点，采用真实和合成数据进行实验测试。实验结果验证所提方法可行有效。
(2) 定义不确定时态数据连续Top-k区间查询并设计相应的查询算法。由于时间区间存在有效期，传统的Top-k查询只考虑在查询范围内评分最高的对象，并不考虑返回的对象是否在整个查询区间内都有效。针对不确定时态数据连续Top-k区间查询，提出一种区间划分构建的双索引DR-tree，基于该索引可以实现查询时减少访问索引中非叶子节点信息来提高查询效率。同时为管理查询区间每个点上的k个结果，提出了一个树状结构，给出连续Top-k查询算法，采用真实和合成数据进行实验。通过对比实验，表明本文所提方法在不确定时态数据连续Top-k区间查询上有较好的查询性能。
(3) 高效更新时态数据索引。时态数据库系统不仅要管理历史数据，还要支持处理更新数据。首先基于已有的批量加载更新算法，结合区间划分更新本文提出的DR-Tree。将新加入的时态数据分为两部分，分别批量加载构建DR-Tree子树，再将DR-Tree子树分别插入对应的历史DR-Tree中。然后，将基于DR-tree提出的批量加载更新方法扩展至区间树，实现区间树批量更新。采用真实数据集和合成数据集，与删除重建索引和逐个插入更新索引算法进行对比，实验结果表明本文所提批量更新时态数据索引对于两种结构都有较好的性能，当数据规模较大时，所提方法在更新效率上优于对比方法2倍以上。