摘要: 在移动对象数据库领域中，索引是一个重要的研究方向。由于其动态特性，移动对象的各种索引结构更加不可或缺。移动对象索引存储的是移动对象的位置，可以在已有的空间索引的方法上扩展来得到，这些扩展包括修改或增加额外数据结构以适应特定的动态需求或新查询类别。例如，有很多移动对象索引使用了R-树，一种著名的空间索引结构，将其作为一个基本框架或是作为一个结构块，并对一些内部节点进行重组。在本文中，我们主要关注基于R-树的对移动对象进行索引的方案。在移动对象索引的其他类别中，我们主要考虑在特定的道路网络上对移动对象的历史轨迹进行索引。根据应用选择最合适的方法来索引数据，这要求对所关注的索引进行仔细的比较研究。我们选择了四种索引结构来进行比较：3DR-树，MV3DR-树，映射方法和MON-树。前两种索引是通用的索引方案，其中的移动对象没有任何限制，进行自由移动；而后两种是为移动对象在道路网络上的运动而专门设计的。
3DR-树是个非常简单的解决方案，而MV3DR-树是一种复杂的组织结构，它能够高效地支持各种类型的范围查询。第三个被选择的技术，我们在本文中成为“映射方法”，它的基本方法是将网络，轨迹和时空查询简单映射到低维空间中。最后，MON-树是个组织良好的2级结构，第一级索引的是道路网络中其上有运动的边，而在下一级索引中，R-树用2维矩形对每条边上的运动进行索引。本文的主要贡献在于评估基于网络的索引结构（映射和MON-树）相对于众所周知的自由移动的索引方案（3DR-树和MV3DR树）的性能。我们在本研究中的假设是：在道路网络的运动中，基于网络的解决方案并不总优于自由移动的解决方案。这个假说基于以下事实：基于网络的解决方案带来了如高复杂度和高存储开销等关键问题。
在这样的目的下，我们在公平的环境中对现有方法的存储消耗以及时空查询的执行性能进行了评估。为此，我们基于对上述四种索引的原型实现来设置比较环境。为公平起见，我们的模拟环境在加载所有的索引时采用从同一个交通中生成的相同更新，这样插入每个索引的项数目是相等的。在我们的比较中，我们讨论了结构对于查询的空间和/或时间范围的敏感度，以及在可靠性和磁盘存取性能方面道路网络和自由移动两组索引的情况。
从我们的研究中可以得到如下一些重要的发现。在大部分情况下，我们发现3DR-树相比其他组织结构在查询执行性能上表现出更为稳定的结果。这个结论来自于对查询结果可靠性的比较。虽然MON-树对于查询特征变化的相应表现符合预期；但它的性能在几乎所有条件中是最差的。主要原因在于它的底层体系是基于边的，这显著地增加了MON-树中的网络R-树的负载。可以预期，在不同的更新模型下，如果维持其对于空间范围和时间范围变化的相应表现，MON-树在查询执行和存储消耗将表现出更好的结果。
据我们所知，目前还没有其他对我们在本文中所选结构的比较研究。最后，我们相信我们的研究揭示了一些基于网络的结构的弱点，特别是映射和MON-树，这将激发我们去设计更健壮的组织结构。