dc.contributor.author | Arge, Lars | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2015-11-20T17:28:54Z | |
dc.date.available | 2015-11-20T17:28:54Z | |
dc.date.issued | 2012-02-17 | |
dc.identifier.citation | Arge, Lars, and Jeffrey Scott Vitter. "Optimal External Memory Interval Management." SIAM J. Comput. SIAM Journal on Computing 32.6 (2003): 1488-508. DOI:10.1137/S009753970240481X | en_US |
dc.identifier.uri | http://hdl.handle.net/1808/18954 | |
dc.description | This is the published version. Copyright © 2003 Society for Industrial and Applied Mathematics | en_US |
dc.description.abstract | 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. | en_US |
dc.publisher | Society for Industrial and Applied Mathematics | en_US |
dc.subject | Interval management | en_US |
dc.subject | Stabbing queries | en_US |
dc.subject | I/O efficient | en_US |
dc.subject | Data structures | en_US |
dc.title | Optimal External Memory Interval Management | en_US |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.kudepartment | Electrical Engr & Comp Science | en_US |
dc.identifier.doi | 10.1137/S009753970240481X | |
kusw.oaversion | Scholarly/refereed, publisher version | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess | |