Multi-Entry Generalized Search Trees for Indexing Trajectories

本文介绍了广义索引的概念，这是数据库系统研究的成功案例之一，已经在常见的数据库系统中得到实现。GiST（广义搜索树）和SP-GiST（空间划分广义搜索树）是两种广泛使用的广义索引，通常用于多维数据。目前，广义索引GiST和SP-GiST使用一个索引条目表示一个数据库对象，例如每个时空对象的边界框。然而，当处理复杂对象（例如移动对象轨迹）时，每个对象一个条目的索引不足以创建高效的索引。以前的研究已经强调，将轨迹分成多个边界框进行索引可以提高查询性能，因为它会导致更高的索引过滤。本文介绍了MGiST和MSP-GiST，它们是GiST和SP-GiST的多条目广义搜索树对应物，旨在允许在插入过程中将对象分成多个条目进行划分。将复杂对象分解为多个子对象的方法因数据类型而异，并且可能取决于某些特定领域的参数。因此，MGiST和MSP-GiST旨在允许可插拔模块，以帮助优化将对象拆分为多个子对象的过程。我们使用轨迹索引场景演示了MGiST和MSP-GiST的有用性，其中我们使用MGiST和MSP-GiST实现了多个轨迹索引，并使用轨迹特定的拆分算法实例化了这些搜索树。我们创建并测试了几个广泛使用的空间索引结构的多条目版本的性能，例如R-Tree、Quad-Tree和KD-Tree。我们使用合成数据和真实数据进行评估，并观察到点查询、范围查询和KNN查询的性能提高了一个数量级。

本文旨在解决使用单个索引条目无法有效索引复杂对象（如移动对象轨迹）时的查询性能问题。

本文提出了MGiST和MSP-GiST，这是GiST和SP-GiST的多条目广义搜索树对应物，允许在插入期间将对象分成多个条目。这些新方法允许使用可插拔模块优化对象分解，从而提高查询性能。

本文使用轨迹索引场景演示了MGiST和MSP-GiST的实用性，并使用轨迹特定分割算法实例化这些搜索树。使用合成和真实数据进行评估，并观察到点、范围和KNN查询性能提高了一个数量级。值得关注的是，本文还创建和测试了几个广泛使用的空间索引结构的多条目版本，如R-Tree、Quad-Tree和KD-Tree。

最近的相关研究包括使用多个索引来提高查询性能的工作，如M-tree和TGS-tree。