Optimal external memory interval management

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 pro...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2003-01, Vol.32 (6), p.1488-1508
Main Authors: ARGE, Lars, VITTER, Jeffrey Scott
Format: Article
Language:English
Subjects:
Alliances
Applied sciences
Computer science
Computer science
control theory
systems
Data processing. List processing. Character string processing
Exact sciences and technology
Information systems. Data bases
Logic programming
Memory organisation. Data processing
Queries
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c343t-33df4a2b753ca29990582dc4c5f866c89ffa09affee794f3bceafb8d2464c5523
cites cdi_FETCH-LOGICAL-c343t-33df4a2b753ca29990582dc4c5f866c89ffa09affee794f3bceafb8d2464c5523
container_end_page 1508
container_issue 6
container_start_page 1488
container_title SIAM journal on computing
container_volume 32
creator ARGE, Lars
VITTER, Jeffrey Scott
description 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.
doi_str_mv 10.1137/S009753970240481X
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_918826333</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2574829531</sourcerecordid><originalsourceid>FETCH-LOGICAL-c343t-33df4a2b753ca29990582dc4c5f866c89ffa09affee794f3bceafb8d2464c5523</originalsourceid><addsrcrecordid>eNplUEtLxDAQDqJgrf4Ab4vgSaqZPJrkKIsvWNiDCt5CmibSpS-Trrj_3pRd8OBcZj6-BzOD0CXgWwAq7l4xVoJTJTBhmEn4OEIZYMULAQDHKJvpYuZP0VmMG4yBMaAZulmPU9OZduF-Jhf6NHSuG8Ju0fQJf8_Y9ObTda6fztGJN210F4eeo_fHh7flc7FaP70s71eFpYxOBaW1Z4ZUaR1riFIKc0lqyyz3siytVN4brIz3zgnFPK2sM76SNWFl0nBCc3S1zx3D8LV1cdKbYTvvFrUCKUlJU-UI9iIbhhiD83oM6ZCw04D1_BL97yXJc30INtGa1gfT2yb-GTkVpeKM_gJFsWBt</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>918826333</pqid></control><display><type>article</type><title>Optimal external memory interval management</title><source>EBSCOhost Business Source Ultimate</source><source>SIAM Journals Archive</source><source>ABI/INFORM Global</source><creator>ARGE, Lars ; VITTER, Jeffrey Scott</creator><creatorcontrib>ARGE, Lars ; VITTER, Jeffrey Scott</creatorcontrib><description>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.</description><identifier>ISSN: 0097-5397</identifier><identifier>EISSN: 1095-7111</identifier><identifier>DOI: 10.1137/S009753970240481X</identifier><language>eng</language><publisher>Philadelphia, PA: Society for Industrial and Applied Mathematics</publisher><subject>Alliances ; Applied sciences ; Computer science ; Computer science; control theory; systems ; Data processing. List processing. Character string processing ; Exact sciences and technology ; Information systems. Data bases ; Logic programming ; Memory organisation. Data processing ; Queries ; Software</subject><ispartof>SIAM journal on computing, 2003-01, Vol.32 (6), p.1488-1508</ispartof><rights>2004 INIST-CNRS</rights><rights>[Copyright] © 2003 Society for Industrial and Applied Mathematics</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c343t-33df4a2b753ca29990582dc4c5f866c89ffa09affee794f3bceafb8d2464c5523</citedby><cites>FETCH-LOGICAL-c343t-33df4a2b753ca29990582dc4c5f866c89ffa09affee794f3bceafb8d2464c5523</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/918826333?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,776,780,3172,11667,27901,27902,36037,44339</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=15376954$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>ARGE, Lars</creatorcontrib><creatorcontrib>VITTER, Jeffrey Scott</creatorcontrib><title>Optimal external memory interval management</title><title>SIAM journal on computing</title><description>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.</description><subject>Alliances</subject><subject>Applied sciences</subject><subject>Computer science</subject><subject>Computer science; control theory; systems</subject><subject>Data processing. List processing. Character string processing</subject><subject>Exact sciences and technology</subject><subject>Information systems. Data bases</subject><subject>Logic programming</subject><subject>Memory organisation. Data processing</subject><subject>Queries</subject><subject>Software</subject><issn>0097-5397</issn><issn>1095-7111</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2003</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNplUEtLxDAQDqJgrf4Ab4vgSaqZPJrkKIsvWNiDCt5CmibSpS-Trrj_3pRd8OBcZj6-BzOD0CXgWwAq7l4xVoJTJTBhmEn4OEIZYMULAQDHKJvpYuZP0VmMG4yBMaAZulmPU9OZduF-Jhf6NHSuG8Ju0fQJf8_Y9ObTda6fztGJN210F4eeo_fHh7flc7FaP70s71eFpYxOBaW1Z4ZUaR1riFIKc0lqyyz3siytVN4brIz3zgnFPK2sM76SNWFl0nBCc3S1zx3D8LV1cdKbYTvvFrUCKUlJU-UI9iIbhhiD83oM6ZCw04D1_BL97yXJc30INtGa1gfT2yb-GTkVpeKM_gJFsWBt</recordid><startdate>20030101</startdate><enddate>20030101</enddate><creator>ARGE, Lars</creator><creator>VITTER, Jeffrey Scott</creator><general>Society for Industrial and Applied Mathematics</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7RQ</scope><scope>7WY</scope><scope>7WZ</scope><scope>7X2</scope><scope>7XB</scope><scope>87Z</scope><scope>88A</scope><scope>88F</scope><scope>88I</scope><scope>88K</scope><scope>8AL</scope><scope>8FE</scope><scope>8FG</scope><scope>8FH</scope><scope>8FK</scope><scope>8FL</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>ATCPS</scope><scope>AZQEC</scope><scope>BBNVY</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>BHPHI</scope><scope>CCPQU</scope><scope>D1I</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>KB.</scope><scope>L.-</scope><scope>L6V</scope><scope>LK8</scope><scope>M0C</scope><scope>M0K</scope><scope>M0N</scope><scope>M1Q</scope><scope>M2O</scope><scope>M2P</scope><scope>M2T</scope><scope>M7P</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PATMY</scope><scope>PDBOC</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>PYCSY</scope><scope>Q9U</scope><scope>S0W</scope><scope>U9A</scope></search><sort><creationdate>20030101</creationdate><title>Optimal external memory interval management</title><author>ARGE, Lars ; VITTER, Jeffrey Scott</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c343t-33df4a2b753ca29990582dc4c5f866c89ffa09affee794f3bceafb8d2464c5523</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2003</creationdate><topic>Alliances</topic><topic>Applied sciences</topic><topic>Computer science</topic><topic>Computer science; control theory; systems</topic><topic>Data processing. List processing. Character string processing</topic><topic>Exact sciences and technology</topic><topic>Information systems. Data bases</topic><topic>Logic programming</topic><topic>Memory organisation. Data processing</topic><topic>Queries</topic><topic>Software</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>ARGE, Lars</creatorcontrib><creatorcontrib>VITTER, Jeffrey Scott</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Career &amp; Technical Education Database</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>Agricultural Science Collection</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Biology Database (Alumni Edition)</collection><collection>Military Database (Alumni Edition)</collection><collection>Science Database (Alumni Edition)</collection><collection>Telecommunications (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>Agricultural &amp; Environmental Science Collection</collection><collection>ProQuest Central Essentials</collection><collection>Biological Science Collection</collection><collection>ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Materials Science Collection</collection><collection>ProQuest Central Korea</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>Materials Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Biological Sciences</collection><collection>ABI/INFORM Global</collection><collection>Agriculture Science Database</collection><collection>Computing Database</collection><collection>Military Database</collection><collection>Research Library</collection><collection>ProQuest Science Journals</collection><collection>Telecommunications Database</collection><collection>Biological Science Database</collection><collection>Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Environmental Science Database</collection><collection>Materials Science Collection</collection><collection>One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>Environmental Science Collection</collection><collection>ProQuest Central Basic</collection><collection>DELNET Engineering &amp; Technology Collection</collection><jtitle>SIAM journal on computing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>ARGE, Lars</au><au>VITTER, Jeffrey Scott</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Optimal external memory interval management</atitle><jtitle>SIAM journal on computing</jtitle><date>2003-01-01</date><risdate>2003</risdate><volume>32</volume><issue>6</issue><spage>1488</spage><epage>1508</epage><pages>1488-1508</pages><issn>0097-5397</issn><eissn>1095-7111</eissn><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.</abstract><cop>Philadelphia, PA</cop><pub>Society for Industrial and Applied Mathematics</pub><doi>10.1137/S009753970240481X</doi><tpages>21</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0097-5397
ispartof SIAM journal on computing, 2003-01, Vol.32 (6), p.1488-1508
issn 0097-5397
1095-7111
language eng
recordid cdi_proquest_journals_918826333
source EBSCOhost Business Source Ultimate; SIAM Journals Archive; ABI/INFORM Global
subjects Alliances
Applied sciences
Computer science
Computer science
control theory
systems
Data processing. List processing. Character string processing
Exact sciences and technology
Information systems. Data bases
Logic programming
Memory organisation. Data processing
Queries
Software
title Optimal external memory interval management
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-30T22%3A31%3A13IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Optimal%20external%20memory%20interval%20management&rft.jtitle=SIAM%20journal%20on%20computing&rft.au=ARGE,%20Lars&rft.date=2003-01-01&rft.volume=32&rft.issue=6&rft.spage=1488&rft.epage=1508&rft.pages=1488-1508&rft.issn=0097-5397&rft.eissn=1095-7111&rft_id=info:doi/10.1137/S009753970240481X&rft_dat=%3Cproquest_cross%3E2574829531%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c343t-33df4a2b753ca29990582dc4c5f866c89ffa09affee794f3bceafb8d2464c5523%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=918826333&rft_id=info:pmid/&rfr_iscdi=true