{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T20:01:06Z","timestamp":1770753666344,"version":"3.50.0"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319677286","type":"print"},{"value":"9783319677293","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-67729-3_15","type":"book-chapter","created":{"date-parts":[[2017,9,16]],"date-time":"2017-09-16T01:04:04Z","timestamp":1505523844000},"page":"248-265","source":"Crossref","is-referenced-by-count":11,"title":["PTrie: Data Structure for Compressing and Storing Sets via Prefix Sharing"],"prefix":"10.1007","author":[{"given":"Peter Gj\u00f8l","family":"Jensen","sequence":"first","affiliation":[]},{"given":"Kim Guldstrand","family":"Larsen","sequence":"additional","affiliation":[]},{"given":"Ji\u0159\u00ed","family":"Srba","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,17]]},"reference":[{"key":"15_CR1","unstructured":"Askitis, N., Sinha, R.: HAT-trie: a cache-conscious trie-based data structure for strings. In: Proceedings of the Thirtieth Australasian Conference on Computer Science, vol. 62, pp. 97\u2013105. Australian Computer Society Inc. (2007)"},{"key":"15_CR2","unstructured":"Bagwell, P.: Ideal hash trees. Es Grands Champs, vol. 1195 (2001)"},{"issue":"8","key":"15_CR3","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"C\u201335","author":"RE Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C\u201335(8), 677\u2013691 (1986)","journal-title":"IEEE Trans. Comput."},{"key":"15_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-04761-9_7","volume-title":"Automated Technology for Verification and Analysis","author":"J Byg","year":"2009","unstructured":"Byg, J., J\u00f8rgensen, K.Y., Srba, J.: TAPAAL: editor, simulator and verifier of timed-arc petri nets. In: Liu, Z., Ravn, A.P. (eds.) ATVA 2009. LNCS, vol. 5799, pp. 84\u201389. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-04761-9_7"},{"key":"15_CR5","unstructured":"Jones, D.C.: HAT-trie implementation. https:\/\/github.com\/dcjones\/hat-trie . Accessed 19 Apr 2017"},{"key":"15_CR6","unstructured":"cplusplus.com. C++ map implementation reference. http:\/\/www.cplusplus.com\/reference\/map\/map\/ . Accessed 20 Jan 2017"},{"key":"15_CR7","unstructured":"cplusplus.com. C++ set implementation reference. http:\/\/www.cplusplus.com\/reference\/set\/set\/ . Accessed 20 Jan 2017"},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1007\/978-3-642-28756-5_36","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"A David","year":"2012","unstructured":"David, A., Jacobsen, L., Jacobsen, M., J\u00f8rgensen, K.Y., M\u00f8ller, M.H., Srba, J.: TAPAAL 2.0: integrated development environment for timed-arc petri nets. In: Flanagan, C., K\u00f6nig, B. (eds.) TACAS 2012. LNCS, vol. 7214, pp. 492\u2013497. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-28756-5_36"},{"key":"15_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/11537328_7","volume-title":"Model Checking Software","author":"S Evangelista","year":"2005","unstructured":"Evangelista, S., Pradat-Peyre, J.-F.: Memory efficient state space storage in explicit software model checking. In: Godefroid, P. (ed.) SPIN 2005. LNCS, vol. 3639, pp. 43\u201357. Springer, Heidelberg (2005). doi: 10.1007\/11537328_7"},{"key":"15_CR10","unstructured":"Evans, J.: A scalable concurrent malloc (3) implementation for FreeBSD. In: Proceedings of the BSDCan Conference Ottawa (2006)"},{"issue":"9","key":"15_CR11","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E Fredkin","year":"1960","unstructured":"Fredkin, E.: Trie memory. Commun. ACM 3(9), 490\u2013499 (1960)","journal-title":"Commun. ACM"},{"issue":"1\u20136","key":"15_CR12","first-page":"223","volume":"10","author":"G Gwehenberger","year":"1968","unstructured":"Gwehenberger, G.: Anwendung einer bin\u00e4ren verweiskettenmethode beim aufbau von listen\/use of a binary tree structure for processing files. IT Inf. Technol. 10(1\u20136), 223\u2013226 (1968)","journal-title":"IT Inf. Technol."},{"key":"15_CR13","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1145\/506309.506312","volume":"20","author":"S Heinz","year":"2002","unstructured":"Heinz, S., Zobel, J., Williams, H.E.: Burst tries: a fast, efficient data structure for string keys. ACM Trans. Inf. Syst. 20, 192\u2013223 (2002)","journal-title":"ACM Trans. Inf. Syst."},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-662-53401-4_16","volume-title":"Transactions on Petri Nets and Other Models of Concurrency XI","author":"JF Jensen","year":"2016","unstructured":"Jensen, J.F., Nielsen, T., Oestergaard, L.K., Srba, J.: TAPAAL and reachability analysis of P\/T nets. In: Koutny, M., Desel, J., Kleijn, J. (eds.) Transactions on Petri Nets and Other Models of Concurrency XI. LNCS, vol. 9930, pp. 307\u2013318. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-53401-4_16"},{"key":"15_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-319-06200-6_26","volume-title":"NASA Formal Methods","author":"PG Jensen","year":"2014","unstructured":"Jensen, P.G., Larsen, K.G., Srba, J., S\u00f8rensen, M.G., Taankvist, J.H.: Memory efficient data structures for explicit verification of timed systems. In: Badger, J.M., Rozier, K.Y. (eds.) NFM 2014. LNCS, vol. 8430, pp. 307\u2013312. Springer, Cham (2014). doi: 10.1007\/978-3-319-06200-6_26"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Kordon, F., Garavel, H., Hillah, L.M., Hulin-Hubard, F., Chiardo, G., Hamez, A., Jezequel, L., Miner, A., Meijer, J., Paviot-Adet, E., Racordon, D., Rodriguez, C., Rohr, C., Srba, J., Thierry-Mieg, Y., Tri\u0323nh, G., Wolf, K.: Complete Results for the 2016 Edition of the Model Checking Contest, June 2016. http:\/\/mcc.lip6.fr\/2016\/results.php","DOI":"10.1007\/978-3-662-53401-4_12"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-642-22306-8_4","volume-title":"Model Checking Software","author":"A Laarman","year":"2011","unstructured":"Laarman, A., van de Pol, J., Weber, M.: Parallel recursive state compression for free. In: Groce, A., Musuvathi, M. (eds.) SPIN 2011. LNCS, vol. 6823, pp. 38\u201356. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-22306-8_4"},{"issue":"4","key":"15_CR18","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"DR Morrison","year":"1968","unstructured":"Morrison, D.R.: Patriciapractical algorithm to retrieve information coded in alphanumeric. J. ACM (JACM) 15(4), 514\u2013534 (1968)","journal-title":"J. ACM (JACM)"},{"issue":"8","key":"15_CR19","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/2370036.2145836","volume":"47","author":"A Prokopec","year":"2012","unstructured":"Prokopec, A., Bronson, N.G., Bagwell, P., Odersky, M.: Concurrent tries with efficient non-blocking snapshots. ACM SIGPLAN Not. 47(8), 151\u2013160 (2012). ACM","journal-title":"ACM SIGPLAN Not."},{"key":"15_CR20","unstructured":"Renaud, M.: Trie (aka. prefix tree). https:\/\/github.com\/m-renaud\/trie . Accessed 19 Apr 2017"},{"key":"15_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-319-22969-0_19","volume-title":"Software Engineering and Formal Methods","author":"P Ro\u010dkai","year":"2015","unstructured":"Ro\u010dkai, P., \u0160till, V., Barnat, J.: Techniques for memory-efficient model checking of C and C++ code. In: Calinescu, R., Rumpe, B. (eds.) SEFM 2015. LNCS, vol. 9276, pp. 268\u2013282. Springer, Cham (2015). doi: 10.1007\/978-3-319-22969-0_19"},{"key":"15_CR22","unstructured":"Timonk. Big memory, part 3.5: Google sparsehash! (2011). https:\/\/research.neustar.biz\/2011\/11\/27\/big-memory-part-3-5-google-sparsehash\/ . Accessed 20 Jan 2017"},{"key":"15_CR23","unstructured":"Welch, N.: Hash table benchmarks. http:\/\/incise.org\/hash-table-benchmarks.html . Accessed 20 Jan 2017"},{"key":"15_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/978-3-662-53401-4_13","volume-title":"Transactions on Petri Nets and Other Models of Concurrency XI","author":"K Wolf","year":"2016","unstructured":"Wolf, K.: Running LoLA 2.0 in a model checking competition. In: Koutny, M., Desel, J., Kleijn, J. (eds.) Transactions on Petri Nets and Other Models of Concurrency XI. LNCS, vol. 9930, pp. 274\u2013285. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-53401-4_13"},{"key":"15_CR25","unstructured":"Yang, J.: An implementation of two-trie and tail-trie using double array. https:\/\/github.com\/jianingy\/libtrie . Accessed 19 Apr 2017"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2017"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-67729-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T18:43:16Z","timestamp":1659465796000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67729-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319677286","9783319677293"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67729-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}