Sort-based query-adaptive loading of R-trees
Sort-based query-adaptive loading of R-trees
复制标题
DOI：
10.1145/2396761.2398577
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Daniar Achakeev;B. Seeger;P. Widmayer
中科院分区：
文献类型：
--
作者：
Daniar Achakeev;B. Seeger;P. Widmayer
二十多年来，R 树的批量加载一直是学术界和工业界的一个重要问题。当前算法创建 R 树，但没有任何有关预期查询配置文件的信息。然而，查询配置文件对于设计高效索引非常有用。在本文中，我们解决了这一缺陷，并提出了查询自适应算法，用于构建针对给定查询配置文件优化设计的 R 树。由于最佳 R 树加载是 NP 困难的（即使没有将结构调整为查询配置文件），因此我们提供高效、易于实现的启发式方法。我们用于查询自适应加载的基于排序的算法包括两个步骤：首先，识别排序顺序，从而产生比从标准空间填充曲线获得的 R 树更好的 R 树。其次，对于给定的排序顺序，我们提出了一种在线性运行时生成 R 树的动态编程算法。我们的实验结果证实，即使查询配置文件未知，我们的算法通常也会创建比标准的基于排序的加载算法获得的 R 树更好的 R 树。
Bulk-loading of R-trees has been an important problem in academia and industry for more than twenty years. Current algorithms create R-trees without any information about the expected query profile. However, query profiles are extremely useful for the design of efficient indexes. In this paper, we address this deficiency and present query-adaptive algorithms for building R-trees optimally designed for a given query profile. Since optimal R-tree loading is NP-hard (even without tuning the structure to a query profile), we provide efficient, easy to implement heuristics. Our sort-based algorithms for query-adaptive loading consist of two steps: First, sorting orders are identified resulting in better R-trees than those obtained from standard space-filling curves. Second, for a given sorting order, we propose a dynamic programming algorithm for generating R-trees in linear runtime. Our experimental results confirm that our algorithms generally create significantly better R-trees than the ones obtained from standard sort-based loading algorithms, even when the query profile is unknown.