Optimal external memory interval management
Optimal external memory interval management
复制标题
DOI：
10.1137/s009753970240481x
复制
发表时间：
2003-01-01
影响因子：
1.6
通讯作者：
Vitter, JS
中科院分区：
文献类型：
--
作者：
Arge, L;Vitter, JS
在本文中，我们提出了外部的间隔树，一个最佳的外部存储器的数据结构，回答刺查询的一组动态维护的时间间隔。外部区间树可以用于动态区间管理问题的最佳解决方案，该问题是面向对象和时态数据库以及约束逻辑编程的核心问题。该结构的一部分使用了权重平衡技术，用于平衡树的有效最坏情况操作，这是独立的利益。外部区间树，以及我们的新的平衡技术，最近被用来开发几个有效的外部数据结构。
In this paper we present the external interval tree, an optimal external memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The external interval tree can be used in an optimal solution to the dynamic interval management problem, which is a central problem for object-oriented and temporal databases and for constraint logic programming. Part of the structure uses a weight-balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest. The external interval tree, as well as our new balancing technique, have recently been used to develop several efficient external data structures.