PTrie: Data Structure for Compressing and Storing Sets via
Prefix Sharing

D 2017

PTrie: Data Structure for Compressing and Storing Sets via Prefix Sharing

JENSEN, Peter G., Kim G. LARSEN a Jiří SRBA

Základní údaje

Originální název

PTrie: Data Structure for Compressing and Storing Sets via Prefix Sharing

Autoři

JENSEN, Peter G. (208 Dánsko), Kim G. LARSEN (208 Dánsko) a Jiří SRBA (203 Česká republika, garant, domácí)

Vydání

Holland, Proceedings of the 14th International Colloquium on Theoretical Aspects of Computing (ICTAC'17), od s. 248-265, 18 s. 2017

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/17:00100449

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-67728-6

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-67729-3_15

UT WoS

000516829800015

Klíčová slova anglicky

data structure; set; prefix sharing; model checking

Štítky

core_B, firank_B

Změněno: 16. 5. 2022 14:38, Mgr. Michal Petr

Anotace

V originále

Sets and their efficient implementation are fundamental in all of computer science, including model checking, where sets are used as the basic data structure for storing (encodings of) states during a state-space exploration. In the quest for fast and memory efficient methods for manipulating large sets, we present a novel data structure called PTrie for storing sets of binary strings of arbitrary length. The PTrie data structure distinguishes itself by compressing the stored elements while sharing the desirable key characteristics with conventional hash-based implementations, namely fast insertion and lookup operations. We provide the theoretical foundation of PTries, prove the correctness of their operations and conduct empirical studies analysing the performance of PTries for dealing with randomly generated binary strings as well as for state-space exploration of a large collection of Petri net models from the 2016 edition of the Model Checking Contest (MCC'16). We experimentally document that with a modest overhead in running time, a truly significant space-reduction can be achieved. Lastly, we provide an efficient implementation of the PTrie data structure under the GPL version 3 license, so that the technology is made available for memory-intensive applications such as model-checking tools.

Citovat

JENSEN, Peter G., Kim G. LARSEN a Jiří SRBA. PTrie: Data Structure for Compressing and Storing Sets via Prefix Sharing. In Proceedings of the 14th International Colloquium on Theoretical Aspects of Computing (ICTAC'17). Holland: Springer, 2017, s. 248-265. ISBN 978-3-319-67728-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-67729-3_15.

@inproceedings{1412003,
   author = {Jensen, Peter G. and Larsen, Kim G. and Srba, Jiří},
   address = {Holland},
   booktitle = {Proceedings of the 14th International Colloquium on Theoretical Aspects of Computing (ICTAC'17)},
   doi = {http://dx.doi.org/10.1007/978-3-319-67729-3_15},
   keywords = {data structure; set; prefix sharing; model checking},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Holland},
   isbn = {978-3-319-67728-6},
   pages = {248-265},
   publisher = {Springer},
   title = {PTrie: Data Structure for Compressing and Storing Sets via Prefix Sharing},
   year = {2017}
}

TY  - JOUR
ID  - 1412003
AU  - Jensen, Peter G. - Larsen, Kim G. - Srba, Jiří
PY  - 2017
TI  - PTrie: Data Structure for Compressing and Storing Sets via Prefix Sharing
PB  - Springer
CY  - Holland
SN  - 9783319677286
KW  - data structure
KW  - set
KW  - prefix sharing
KW  - model checking
N2  - Sets and their efficient implementation are fundamental in all of computer science, including model checking, where sets are used as the basic data structure for storing (encodings of) states during a state-space exploration. In the quest for fast and memory efficient methods for manipulating large sets, we present a novel data structure called PTrie for storing sets of binary strings of arbitrary length. The PTrie data structure distinguishes itself by compressing the stored elements while sharing the desirable key characteristics with conventional hash-based implementations, namely fast insertion and lookup operations. We provide the theoretical foundation of PTries, prove the correctness of their operations and conduct empirical studies analysing the performance of PTries for dealing with randomly generated binary strings as well as for state-space exploration of a large collection of Petri net models from the 2016 edition of the Model Checking Contest (MCC'16). We experimentally document that with a modest overhead in running time, a truly significant space-reduction can be achieved. Lastly, we provide an efficient implementation of the PTrie data structure under the GPL version 3 license, so that the technology is made available for memory-intensive applications such as model-checking tools.
ER  -

JENSEN, Peter G., Kim G. LARSEN a Jiří SRBA. PTrie: Data Structure for Compressing and Storing Sets via Prefix Sharing. In \textit{Proceedings of the 14th International Colloquium on Theoretical Aspects of Computing (ICTAC'17)}. Holland: Springer, 2017, s.~248-265. ISBN~978-3-319-67728-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-67729-3\_{}15.

Podrobný výpis o publikaci