dc.contributor.author | Arge, Lars | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2014-05-28T21:14:52Z | |
dc.date.available | 2014-05-28T21:14:52Z | |
dc.date.issued | 2003 | |
dc.identifier.citation | L. Arge and J.S. Vitter. "Optimal External Memory Interval Management," SIAM Journal on Computing, 32(6), 2003, 1488-1508. http://dx.doi.org/10.1137/S009753970240481X | |
dc.identifier.uri | http://hdl.handle.net/1808/13800 | |
dc.description | This is the publisher's version, which is being shared on KU Scholarworks with permission. The original version may be found at the following link: http://dx.doi.org/10.1137/S009753970240481X | |
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 usedin an optimal solution to the dynamic interval management problem, which
is a central problem for object-orientedandtemp oral databases andfor 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. | |
dc.language.iso | en | |
dc.publisher | Society for Industrial and Applied Mathematics | |
dc.subject | Interval management | |
dc.subject | Stabbing queries | |
dc.subject | I/O efficient | |
dc.subject | Data structures | |
dc.title | Optimal External Memory Interval Management | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.kudepartment | Office of the Provost | |
kusw.oastatus | fullparticipation | |
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 | |