Show simple item record

dc.contributor.authorArge, Lars
dc.contributor.authorVitter, Jeffrey Scott
dc.date.accessioned2014-05-28T21:14:52Z
dc.date.available2014-05-28T21:14:52Z
dc.date.issued2003
dc.identifier.citationL. 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.urihttp://hdl.handle.net/1808/13800
dc.descriptionThis 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.abstractIn 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.isoen
dc.publisherSociety for Industrial and Applied Mathematics
dc.subjectInterval management
dc.subjectStabbing queries
dc.subjectI/O efficient
dc.subjectData structures
dc.titleOptimal External Memory Interval Management
dc.typeArticle
kusw.kuauthorVitter, Jeffrey Scott
kusw.kudepartmentOffice of the Provost
kusw.oastatusfullparticipation
dc.identifier.doi10.1137/S009753970240481X
kusw.oaversionScholarly/refereed, publisher version
kusw.oapolicyThis item meets KU Open Access policy criteria.
dc.rights.accessrightsopenAccess


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record