PittsburghV1, Hal, Curation, bibRecord, 000634

Theory and Practice of Chunked Sequences

Identifieur interne : 000634 ( Hal/Curation ); précédent : 000633; suivant : 000635

Theory and Practice of Chunked Sequences

Auteurs : Umut A. Acar [France] ; Arthur Charguéraud [France] ; Mike Rainey [France]

Source :

RBID : Hal:hal-01087245

English descriptors

mix :
- Amortization, Chunk, Data structure, Sequence.

Abstract

Sequence data structures, i.e., data structures that provide operations on an ordered set of items, are heavily used by many applications. For sequence data structures to be efficient in practice, it is important to amortize expensive data-structural operations by chunking a relatively small, constant number of items together, and representing them by using a simple but fast (at least in the small scale) sequence data structure, such as an array or a ring buffer. In this paper, we present chunking techniques, one direct and one based on bootstrapping, that can reduce the practical overheads of sophisticated sequence data structures, such as finger trees, making them competitive in practice with special-purpose data structures. We prove amortized bounds showing that our chunking techniques reduce runtime by amortizing expensive operations over a user-defined chunk-capacity parameter. We implement our techniques and show that they perform well in practice by conducting an empirical evaluation. Our evaluation features comparisons with other carefully engineered and optimized implementations.

Url:

https://hal.inria.fr/hal-01087245

DOI: 10.1007/978-3-662-44777-2_3

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000638

Links to Exploration step

Hal:hal-01087245

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Theory and Practice of Chunked Sequences</title>
<author><name sortKey="Acar, Umut A" sort="Acar, Umut A" uniqKey="Acar U" first="Umut A." last="Acar">Umut A. Acar</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-454410" status="OLD">          <orgName>Programming languages, types, compilation and proofs</orgName>
          <orgName type="acronym">GALLIUM</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/gallium</ref>
          </desc>
          <listRelation>            <relation active="#struct-86790" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-86790" type="direct"><org type="laboratory" xml:id="struct-86790" status="VALID">          <idno type="RNSR">196718247G</idno>
          <orgName>Inria Paris-Rocquencourt</orgName>
          <desc>            <address>              <addrLine>INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex / INRIA Paris - 23 avenue d'Italie 75013 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/centre/paris-rocquencourt</ref>
          </desc>
          <listRelation>            <relation active="#struct-300009" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Chargueraud, Arthur" sort="Chargueraud, Arthur" uniqKey="Chargueraud A" first="Arthur" last="Charguéraud">Arthur Charguéraud</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-2544" status="VALID">          <idno type="RNSR">199812948M</idno>
          <orgName>Laboratoire de Recherche en Informatique</orgName>
          <orgName type="acronym">LRI</orgName>
          <desc>            <address>              <addrLine>LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lri.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-92966" type="direct"></relation>
            <relation active="#struct-300009" type="direct"></relation>
            <relation active="#struct-411575" type="direct"></relation>
            <relation name="UMR8623" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-92966" type="direct"><org type="institution" xml:id="struct-92966" status="VALID">          <orgName>Université Paris-Sud - Paris 11</orgName>
          <orgName type="acronym">UP11</orgName>
          <desc>            <address>              <addrLine>Bâtiment 300 - 91405 Orsay cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.u-psud.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-411575" type="direct"><org type="institution" xml:id="struct-411575" status="VALID"><orgName>CentraleSupélec</orgName>
<desc><address><addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.centralesupelec.fr</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR8623" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Rainey, Mike" sort="Rainey, Mike" uniqKey="Rainey M" first="Mike" last="Rainey">Mike Rainey</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-454410" status="OLD">          <orgName>Programming languages, types, compilation and proofs</orgName>
          <orgName type="acronym">GALLIUM</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/gallium</ref>
          </desc>
          <listRelation>            <relation active="#struct-86790" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-86790" type="direct"><org type="laboratory" xml:id="struct-86790" status="VALID">          <idno type="RNSR">196718247G</idno>
          <orgName>Inria Paris-Rocquencourt</orgName>
          <desc>            <address>              <addrLine>INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex / INRIA Paris - 23 avenue d'Italie 75013 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/centre/paris-rocquencourt</ref>
          </desc>
          <listRelation>            <relation active="#struct-300009" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01087245</idno>
<idno type="halId">hal-01087245</idno>
<idno type="halUri">https://hal.inria.fr/hal-01087245</idno>
<idno type="url">https://hal.inria.fr/hal-01087245</idno>
<idno type="doi">10.1007/978-3-662-44777-2_3</idno>
<date when="2014-09-08">2014-09-08</date>
<idno type="wicri:Area/Hal/Corpus">000638</idno>
<idno type="wicri:Area/Hal/Curation">000638</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Theory and Practice of Chunked Sequences</title>
<author><name sortKey="Acar, Umut A" sort="Acar, Umut A" uniqKey="Acar U" first="Umut A." last="Acar">Umut A. Acar</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-454410" status="OLD">          <orgName>Programming languages, types, compilation and proofs</orgName>
          <orgName type="acronym">GALLIUM</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/gallium</ref>
          </desc>
          <listRelation>            <relation active="#struct-86790" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-86790" type="direct"><org type="laboratory" xml:id="struct-86790" status="VALID">          <idno type="RNSR">196718247G</idno>
          <orgName>Inria Paris-Rocquencourt</orgName>
          <desc>            <address>              <addrLine>INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex / INRIA Paris - 23 avenue d'Italie 75013 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/centre/paris-rocquencourt</ref>
          </desc>
          <listRelation>            <relation active="#struct-300009" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Chargueraud, Arthur" sort="Chargueraud, Arthur" uniqKey="Chargueraud A" first="Arthur" last="Charguéraud">Arthur Charguéraud</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-2544" status="VALID">          <idno type="RNSR">199812948M</idno>
          <orgName>Laboratoire de Recherche en Informatique</orgName>
          <orgName type="acronym">LRI</orgName>
          <desc>            <address>              <addrLine>LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lri.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-92966" type="direct"></relation>
            <relation active="#struct-300009" type="direct"></relation>
            <relation active="#struct-411575" type="direct"></relation>
            <relation name="UMR8623" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-92966" type="direct"><org type="institution" xml:id="struct-92966" status="VALID">          <orgName>Université Paris-Sud - Paris 11</orgName>
          <orgName type="acronym">UP11</orgName>
          <desc>            <address>              <addrLine>Bâtiment 300 - 91405 Orsay cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.u-psud.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-411575" type="direct"><org type="institution" xml:id="struct-411575" status="VALID"><orgName>CentraleSupélec</orgName>
<desc><address><addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.centralesupelec.fr</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR8623" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Rainey, Mike" sort="Rainey, Mike" uniqKey="Rainey M" first="Mike" last="Rainey">Mike Rainey</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-454410" status="OLD">          <orgName>Programming languages, types, compilation and proofs</orgName>
          <orgName type="acronym">GALLIUM</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/equipes/gallium</ref>
          </desc>
          <listRelation>            <relation active="#struct-86790" type="direct"></relation>
            <relation active="#struct-300009" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-86790" type="direct"><org type="laboratory" xml:id="struct-86790" status="VALID">          <idno type="RNSR">196718247G</idno>
          <orgName>Inria Paris-Rocquencourt</orgName>
          <desc>            <address>              <addrLine>INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex / INRIA Paris - 23 avenue d'Italie 75013 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inria.fr/centre/paris-rocquencourt</ref>
          </desc>
          <listRelation>            <relation active="#struct-300009" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1007/978-3-662-44777-2_3</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Amortization</term>
<term>Chunk</term>
<term>Data structure</term>
<term>Sequence</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Sequence data structures, i.e., data structures that provide operations on an ordered set of items, are heavily used by many applications. For sequence data structures to be efficient in practice, it is important to amortize expensive data-structural operations by chunking a relatively small, constant number of items together, and representing them by using a simple but fast (at least in the small scale) sequence data structure, such as an array or a ring buffer. In this paper, we present chunking techniques, one direct and one based on bootstrapping, that can reduce the practical overheads of sophisticated sequence data structures, such as finger trees, making them competitive in practice with special-purpose data structures. We prove amortized bounds showing that our chunking techniques reduce runtime by amortizing expensive operations over a user-defined chunk-capacity parameter. We implement our techniques and show that they perform well in practice by conducting an empirical evaluation. Our evaluation features comparisons with other carefully engineered and optimized implementations.</div>
</front>
</TEI>
<hal api="V3">          <titleStmt>            <title xml:lang="en">Theory and Practice of Chunked Sequences</title>
            <author role="aut">              <persName>                <forename type="first">Umut A.</forename>
                <surname>Acar</surname>
              </persName>
              <idno type="halauthorid">1113713</idno>
              <affiliation ref="#struct-454410"></affiliation>
              <affiliation ref="#struct-67135"></affiliation>
            </author>
            <author role="aut">              <persName>                <forename type="first">Arthur</forename>
                <surname>Charguéraud</surname>
              </persName>
              <idno type="halauthorid">699337</idno>
              <affiliation ref="#struct-2544"></affiliation>
              <affiliation ref="#struct-212219"></affiliation>
            </author>
            <author role="aut">              <persName>                <forename type="first">Mike</forename>
                <surname>Rainey</surname>
              </persName>
              <idno type="halauthorid">888794</idno>
              <affiliation ref="#struct-454410"></affiliation>
            </author>
            <editor role="depositor">              <persName>                <forename>Arthur</forename>
                <surname>Charguéraud</surname>
              </persName>
              <email type="md5">0b0f23497a6fd17293ac1511596e4062</email>
              <email type="domain">inria.fr</email>
            </editor>
            <funder ref="#projeurop-98758"></funder>
          </titleStmt>
          <editionStmt>            <edition n="v1" type="current">              <date type="whenSubmitted">2014-11-25 16:08:18</date>
              <date type="whenWritten">2014-09-08</date>
              <date type="whenModified">2017-02-09 15:52:58</date>
              <date type="whenReleased">2014-11-25 16:15:16</date>
              <date type="whenProduced">2014-09-08</date>
              <date type="whenEndEmbargoed">2014-11-25</date>
              <ref type="file" target="https://hal.inria.fr/hal-01087245/document">                <date notBefore="2014-11-25"></date>
              </ref>
              <ref type="file" subtype="author" n="1" target="https://hal.inria.fr/hal-01087245/file/chunkedseq.pdf">                <date notBefore="2014-11-25"></date>
              </ref>
            </edition>
            <respStmt>              <resp>contributor</resp>
              <name key="181471">                <persName>                  <forename>Arthur</forename>
                  <surname>Charguéraud</surname>
                </persName>
                <email type="md5">0b0f23497a6fd17293ac1511596e4062</email>
                <email type="domain">inria.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>            <distributor>CCSD</distributor>
            <idno type="halId">hal-01087245</idno>
            <idno type="halUri">https://hal.inria.fr/hal-01087245</idno>
            <idno type="halBibtex">acar:hal-01087245</idno>
            <idno type="halRefHtml">Schulz, AndreasS. and Wagner, Dorothea. European Symposium on Algorithms, Sep 2014, Wrocław, Poland. Springer Berlin Heidelberg, Algorithms - ESA 2014, pp.25 - 36, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-44777-2_3〉</idno>
            <idno type="halRef">Schulz, AndreasS. and Wagner, Dorothea. European Symposium on Algorithms, Sep 2014, Wrocław, Poland. Springer Berlin Heidelberg, Algorithms - ESA 2014, pp.25 - 36, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-44777-2_3〉</idno>
          </publicationStmt>
          <seriesStmt>            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
            <idno type="stamp" n="GALLIUM">Collection HAL Gallium</idno>
            <idno type="stamp" n="UMR8623">Laboratoire de Recherche en Informatique</idno>
            <idno type="stamp" n="OPENAIRE">OpenAIRE</idno>
            <idno type="stamp" n="LORIA2">Publications du LORIA</idno>
            <idno type="stamp" n="INRIA2">INRIA 2</idno>
            <idno type="stamp" n="LRI-VALS" p="UMR8623">Laboratoire de Recherche en Informatique. Équipe: Vérification d'Algorithmes, Langages et Systèmes</idno>
            <idno type="stamp" n="INRIA-SACLAY">INRIA Saclay - Ile de France</idno>
            <idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
            <idno type="stamp" n="TESTANNE">Anne</idno>
            <idno type="stamp" n="CENTRALESUPELEC">Ecole CentraleSupélec</idno>
            <idno type="stamp" n="UNIV-PSUD">Université Paris Sud - Paris XI</idno>
          </seriesStmt>
          <notesStmt>            <note type="audience" n="2">International</note>
            <note type="invited" n="0">No</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
            <note type="proceedings" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>            <biblStruct>              <analytic>                <title xml:lang="en">Theory and Practice of Chunked Sequences</title>
                <author role="aut">                  <persName>                    <forename type="first">Umut A.</forename>
                    <surname>Acar</surname>
                  </persName>
                  <idno type="halauthorid">1113713</idno>
                  <affiliation ref="#struct-454410"></affiliation>
                  <affiliation ref="#struct-67135"></affiliation>
                </author>
                <author role="aut">                  <persName>                    <forename type="first">Arthur</forename>
                    <surname>Charguéraud</surname>
                  </persName>
                  <idno type="halauthorid">699337</idno>
                  <affiliation ref="#struct-2544"></affiliation>
                  <affiliation ref="#struct-212219"></affiliation>
                </author>
                <author role="aut">                  <persName>                    <forename type="first">Mike</forename>
                    <surname>Rainey</surname>
                  </persName>
                  <idno type="halauthorid">888794</idno>
                  <affiliation ref="#struct-454410"></affiliation>
                </author>
              </analytic>
              <monogr>                <title level="m">Algorithms - ESA 2014</title>
                <meeting>                  <title>European Symposium on Algorithms</title>
                  <date type="start">2014-09-08</date>
                  <date type="end">2014-09-10</date>
                  <settlement>Wrocław</settlement>
                  <country key="PL">Poland</country>
                </meeting>
                <editor>Schulz, AndreasS. and Wagner, Dorothea</editor>
                <imprint>                  <publisher>Springer Berlin Heidelberg</publisher>
                  <biblScope unit="serie">Lecture Notes in Computer Science</biblScope>
                  <biblScope unit="issue">8737</biblScope>
                  <biblScope unit="pp">25 - 36</biblScope>
                  <date type="datePub">2014-09-08</date>
                </imprint>
              </monogr>
              <idno type="doi">10.1007/978-3-662-44777-2_3</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>            <langUsage>              <language ident="en">English</language>
            </langUsage>
            <textClass>              <keywords scheme="author">                <term xml:lang="en">Data structure</term>
                <term xml:lang="en">Sequence</term>
                <term xml:lang="en">Chunk</term>
                <term xml:lang="en">Amortization</term>
              </keywords>
              <classCode scheme="halDomain" n="info.info-ds">Computer Science [cs]/Data Structures and Algorithms [cs.DS]</classCode>
              <classCode scheme="halTypology" n="COMM">Conference papers</classCode>
            </textClass>
            <abstract xml:lang="en">Sequence data structures, i.e., data structures that provide operations on an ordered set of items, are heavily used by many applications. For sequence data structures to be efficient in practice, it is important to amortize expensive data-structural operations by chunking a relatively small, constant number of items together, and representing them by using a simple but fast (at least in the small scale) sequence data structure, such as an array or a ring buffer. In this paper, we present chunking techniques, one direct and one based on bootstrapping, that can reduce the practical overheads of sophisticated sequence data structures, such as finger trees, making them competitive in practice with special-purpose data structures. We prove amortized bounds showing that our chunking techniques reduce runtime by amortizing expensive operations over a user-defined chunk-capacity parameter. We implement our techniques and show that they perform well in practice by conducting an empirical evaluation. Our evaluation features comparisons with other carefully engineered and optimized implementations.</abstract>
          </profileDesc>
        </hal>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/Hal/Curation

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000634 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Hal/Curation/biblio.hfd -nk 000634 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    Hal
   |étape=   Curation
   |type=    RBID
   |clé=     Hal:hal-01087245
   |texte=   Theory and Practice of Chunked Sequences
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

Theory and Practice of Chunked Sequences

Theory and Practice of Chunked Sequences

Source :

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri