{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:24:20Z","timestamp":1740108260321,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T00:00:00Z","timestamp":1653091200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T00:00:00Z","timestamp":1653091200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","award":["SFRH\/BPD\/108018\/2015","UIDB\/50014\/2020"],"award-info":[{"award-number":["SFRH\/BPD\/108018\/2015","UIDB\/50014\/2020"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00607-022-01085-2","type":"journal-article","created":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T08:02:46Z","timestamp":1653120166000},"page":"2279-2305","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the correctness of a lock-free compression-based elastic mechanism for a hash trie design"],"prefix":"10.1007","volume":"104","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1589-3174","authenticated-orcid":false,"given":"Miguel","family":"Areias","sequence":"first","affiliation":[]},{"given":"Ricardo","family":"Rocha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,21]]},"reference":[{"key":"1085_CR1","doi-asserted-by":"crossref","unstructured":"Areias M, Rocha R (2012) An efficient and scalable memory allocator for multithreaded tabled evaluation of logic programs. In: International conference on parallel and distributed systems. IEEE Computer Society, pp 636\u2013643","DOI":"10.1109\/ICPADS.2012.91"},{"key":"1085_CR2","doi-asserted-by":"crossref","unstructured":"Areias M, Rocha R (2018) On extending a fixed size, persistent and lock-free hash map design to store sorted keys. In: International symposium on parallel and distributed processing with applications. IEEE Computer Society, Melbourne, pp 415\u2013422","DOI":"10.1109\/BDCloud.2018.00070"},{"key":"1085_CR3","unstructured":"Bagwell P (2001) Ideal hash trees. Es Grands Champs, 1195"},{"key":"1085_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R Bayer","year":"1972","unstructured":"Bayer R, Mccreight EM (1972) Organization and maintenance of large ordered indexes. Acta Inf 1:173\u2013189","journal-title":"Acta Inf"},{"key":"1085_CR5","doi-asserted-by":"crossref","unstructured":"Brown T (2017) A template for implementing fast lock-free trees using HTM. In: Proceedings of the ACM symposium on principles of distributed computing, PODC 2017. ACM, pp 293\u2013302","DOI":"10.1145\/3087801.3087834"},{"key":"1085_CR6","unstructured":"Brown T (2017) Techniques for constructing efficient lock-free data structures. Ph.D. thesis, University of Toronto"},{"key":"1085_CR7","doi-asserted-by":"crossref","unstructured":"Brown T, Prokopec A, Alistarh D (2020) Non-blocking interpolation search trees with doubly-logarithmic running time. Association for Computing Machinery, New York, pp 276\u2013291","DOI":"10.1145\/3332466.3374542"},{"issue":"10","key":"1085_CR8","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1145\/3156695.3122973","volume":"52","author":"C Chen","year":"2017","unstructured":"Chen C, Choudhury V, Newton R (2017) Adaptive lock-free data structures in haskell: a general method for concurrent implementation swapping. SIGPLAN Not 52(10):197\u2013211","journal-title":"SIGPLAN Not"},{"issue":"6","key":"1085_CR9","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"EF Codd","year":"1970","unstructured":"Codd EF (1970) A relational model for large shared data banks. Commun ACM 13(6):377\u2013387","journal-title":"Commun ACM"},{"key":"1085_CR10","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D Comer","year":"1979","unstructured":"Comer D (1979) Ubiquitous b-tree. ACM Comput Surv 11:121\u2013137","journal-title":"ACM Comput Surv"},{"key":"1085_CR11","unstructured":"Drepper U (2007) What every programmer should know about memory - version 1.0. Technical report, Red Hat, Inc"},{"key":"1085_CR12","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E Fredkin","year":"1962","unstructured":"Fredkin E (1962) Trie memory. Commun ACM 3:490\u2013499","journal-title":"Commun ACM"},{"key":"1085_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2656332","volume":"19","author":"R Grossi","year":"2015","unstructured":"Grossi R, Ottaviano G (2015) Fast compressed tries through path decompositions. J Exp Algorithmics 19:1","journal-title":"J Exp Algorithmics"},{"key":"1085_CR14","doi-asserted-by":"crossref","unstructured":"Harris TL (2001) A pragmatic implementation of non-blocking linked-lists. In: International conference on distributed computing, DISC \u201901. Springer, pp 300\u2013314","DOI":"10.1007\/3-540-45414-4_21"},{"issue":"3","key":"1085_CR15","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M Herlihy","year":"1990","unstructured":"Herlihy M, Wing JM (1990) Linearizability: a correctness condition for concurrent objects. ACM Trans Program Lang Syst 12(3):463\u2013492","journal-title":"ACM Trans Program Lang Syst"},{"key":"1085_CR16","unstructured":"Herlihy M, Lev Y, Luchangco V, Shavit N (2006) A provably correct scalable concurrent skip list. In: International conference on principles of distributed systems. Technical report, Bordeaux"},{"key":"1085_CR17","doi-asserted-by":"crossref","unstructured":"Herlihy M, Shavit N (2011) On the nature of progress. In: Principles of distributed systems. LNCS, vol 7109. Springer, pp 313\u2013328","DOI":"10.1007\/978-3-642-25873-2_22"},{"key":"1085_CR18","doi-asserted-by":"crossref","unstructured":"Herlihy M, Wing JM (1987) Axioms for concurrent objects. In: ACM symposium on principles of programming languages. ACM, pp 13\u201326","DOI":"10.21236\/ADA200584"},{"issue":"4","key":"1085_CR19","doi-asserted-by":"publisher","first-page":"22:1","DOI":"10.1145\/2043652.2043655","volume":"36","author":"C Kim","year":"2011","unstructured":"Kim C, Chhugani J, Satish N, Sedlar E, Nguyen AD, Kaldewey T, Lee VW, Brandt SA, Dubey P (2011) Designing fast architecture-sensitive tree search on modern multicore\/many-core processors. ACM Trans Database Syst 36(4):22:1-22:34","journal-title":"ACM Trans Database Syst"},{"key":"1085_CR20","unstructured":"Knuth DE (1998) The art of computer programming, volume 3: sorting and searching, 2nd ed. Addison-Wesley Longman"},{"key":"1085_CR21","doi-asserted-by":"crossref","unstructured":"Lehman TJ, Carey MJ (1986) Query processing in main memory database management systems. In: Proceedings of the 1986 ACM SIGMOD international conference on management of data, SIGMOD \u201986. ACM, pp 239\u2013250","DOI":"10.1145\/16894.16878"},{"key":"1085_CR22","unstructured":"Mauchly J (1946) Theory and techniques for design of electronic digital computers"},{"issue":"3","key":"1085_CR23","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1145\/174130.174139","volume":"40","author":"K Mehlhorn","year":"1993","unstructured":"Mehlhorn K, Tsakalidis A (1993) Dynamic interpolation search. J ACM 40(3):621\u2013634","journal-title":"J ACM"},{"key":"1085_CR24","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035179","volume-title":"Handbook of data structures and applications","author":"DP Mehta","year":"2004","unstructured":"Mehta DP, Sahni S (2004) Handbook of data structures and applications. Chapman & Hall\/CRC, Boca Raton"},{"key":"1085_CR25","doi-asserted-by":"crossref","unstructured":"Michael MM (2002) High performance dynamic lock-free hash tables and list-based sets. In: ACM symposium on parallel algorithms and architectures. ACM, pp 73\u201382","DOI":"10.1145\/564870.564881"},{"key":"1085_CR26","doi-asserted-by":"crossref","unstructured":"Moreno P, Areias M, Rocha R (2020) A compression-based design for higher throughput in a lock-free hash map. In: Proceedings of the 26th international European conference on parallel and distributed computing (Euro-Par 2020), LNCS. Springer, Warsaw, pp 458\u2013473","DOI":"10.1007\/978-3-030-57675-2_29"},{"issue":"2","key":"1085_CR27","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1147\/rd.12.0130","volume":"1","author":"WW Peterson","year":"1957","unstructured":"Peterson WW (1957) Addressing for random-access storage. IBM J Res Dev 1(2):130\u2013146","journal-title":"IBM J Res Dev"},{"key":"1085_CR28","doi-asserted-by":"crossref","unstructured":"Prokopec A (2018) Cache-tries: concurrent lock-free hash tries with constant-time operations. In: Proceedings of the 23rd ACM SIGPLAN symposium on principles and practice of parallel programming, PPoPP \u201918. ACM, pp 137\u2013151","DOI":"10.1145\/3178487.3178498"},{"key":"1085_CR29","doi-asserted-by":"crossref","unstructured":"Prokopec A (2018) Efficient lock-free removing and compaction for the cache-trie data structure. In: Euro-Par 2018: Parallel processing-24th International conference on parallel and distributed computing. Lecture notes in computer science, vol 11014. Springer, pp 575\u2013589","DOI":"10.1007\/978-3-319-96983-1_41"},{"key":"1085_CR30","doi-asserted-by":"crossref","unstructured":"Prokopec A, Bronson NG, Bagwell P, Odersky M (2012) Concurrent tries with efficient non-blocking snapshots. In: ACM symposium on principles and practice of parallel programming. ACM, pp 151\u2013160","DOI":"10.1145\/2370036.2145836"},{"issue":"2","key":"1085_CR31","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0022-0000(86)90021-8","volume":"33","author":"Y Sagiv","year":"1986","unstructured":"Sagiv Y (1986) Concurrent operations on B*-trees with overtaking. J Comput Syst Sci 33(2):275\u2013296","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"1085_CR32","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1145\/1147954.1147958","volume":"53","author":"O Shalev","year":"2006","unstructured":"Shalev O, Shavit N (2006) Split-ordered lists: lock-free extensible hash tables. J ACM 53(3):379\u2013405","journal-title":"J ACM"},{"key":"1085_CR33","doi-asserted-by":"crossref","unstructured":"Skarlatos D, Kokolis A, Xu T, Torrellas J (2020) Elastic cuckoo page tables: rethinking virtual memory translation for parallelism. In: Proceedings of the twenty-fifth international conference on architectural support for programming languages and operating systems, ASPLOS \u201920. ACM, pp 1093\u20131108","DOI":"10.1145\/3373376.3378493"},{"key":"1085_CR34","unstructured":"The Java Concurrency Package (JSR-166)"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-022-01085-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00607-022-01085-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-022-01085-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T18:14:11Z","timestamp":1663265651000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00607-022-01085-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,21]]},"references-count":34,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["1085"],"URL":"https:\/\/doi.org\/10.1007\/s00607-022-01085-2","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"type":"print","value":"0010-485X"},{"type":"electronic","value":"1436-5057"}],"subject":[],"published":{"date-parts":[[2022,5,21]]},"assertion":[{"value":"16 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}