{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:01:38Z","timestamp":1743102098444,"version":"3.40.3"},"publisher-location":"Cham","reference-count":44,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031826962"},{"type":"electronic","value":"9783031826979"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-82697-9_6","type":"book-chapter","created":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:46Z","timestamp":1739614666000},"page":"70-84","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Peeling of\u00a0Invertible Bloom Lookup Tables in\u00a0a\u00a0Constant Number of\u00a0Rounds"],"prefix":"10.1007","author":[{"given":"Michael T.","family":"Goodrich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryuto","family":"Kitagawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,16]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","unstructured":"Adhikari, V.K., Guo, Y., Hao, F., Varvello, M., Hilt, V., Steiner, M., Zhang, Z.L.: Unreeling Netflix: understanding and improving multi-CDN movie delivery. In: IEEE INFOCOM, pp. 1620\u20131628 (2012). https:\/\/doi.org\/10.1109\/INFCOM.2012.6195531","DOI":"10.1109\/INFCOM.2012.6195531"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Adler, M., Dittrich, W., Juurlink, B., Kuty\u0142owski, M., Rieping, I.: Communication-optimal parallel minimum spanning tree algorithms. In: 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 27\u201336 (1998)","DOI":"10.1145\/277651.277662"},{"key":"6_CR3","unstructured":"B. Jenkins: A hash function for hash table lookup. https:\/\/burtleburtle.net\/bob\/hash\/doobs.html (1997)"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Bellare, M.: A note on negligible functions. J. Cryptology 15(4) (2002)","DOI":"10.1007\/s00145-002-0116-x"},{"issue":"1","key":"6_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0196-6774(80)90004-8","volume":"1","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L.: A parallel algorithm for constructing minimum spanning trees. J. Algorithms 1(1), 51\u201359 (1980). https:\/\/doi.org\/10.1016\/0196-6774(80)90004-8","journal-title":"J. Algorithms"},{"issue":"7","key":"6_CR6","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"B Bloom","year":"1970","unstructured":"Bloom, B.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"key":"6_CR7","doi-asserted-by":"publisher","unstructured":"B\u00f6ttger, T., Cuadrado, F., Tyson, G., Castro, I., Uhlig, S.: Open Connect everywhere: a glimpse at the internet ecosystem through the lens of the Netflix CDN. SIGCOMM Comput. Commun. Rev. 48(1), 28\u201334 (2018). https:\/\/doi.org\/10.1145\/3211852.3211857","DOI":"10.1145\/3211852.3211857"},{"issue":"4","key":"6_CR8","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1080\/15427951.2004.10129096","volume":"1","author":"A Broder","year":"2004","unstructured":"Broder, A., Mitzenmacher, M.: Network applications of bloom filters: a survey. Internet Math. 1(4), 485\u2013509 (2004)","journal-title":"Internet Math."},{"key":"6_CR9","doi-asserted-by":"publisher","unstructured":"Brodtkorb, A.R., Hagen, T.R., Schulz, C., Hasle, G.: GPU computing in discrete optimization. Part I: Introduction to the GPU. EURO J. Trans. Logistics 2(1), 129\u2013157 (2013). https:\/\/doi.org\/10.1007\/s13676-013-0025-1, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S2192437620600267","DOI":"10.1007\/s13676-013-0025-1"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Cao, N., Fineman, J.T., Russell, K.: Parallel shortest paths with negative edge weights. In: 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 177\u2013190 (2022)","DOI":"10.1145\/3490148.3538583"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Chang, Y.J., Pettie, S., Zhang, H.: Distributed triangle detection via expander decomposition. In: 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 821\u2013840. SIAM (2019)","DOI":"10.1137\/1.9781611975482.51"},{"issue":"1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51(1), 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"key":"6_CR13","doi-asserted-by":"publisher","unstructured":"Dehne, F., Gotz, S.: Practical parallel algorithms for minimum spanning trees. In: 17th IEEE Symposium on Reliable Distributed Systems, pp. 366\u2013371 (1998). https:\/\/doi.org\/10.1109\/RELDIS.1998.740525","DOI":"10.1109\/RELDIS.1998.740525"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Blelloch, G., Shun, J.: Julienne: a framework for parallel graph algorithms using work-efficient bucketing. In: 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 293\u2013304 (2017)","DOI":"10.1145\/3087556.3087580"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Goodrich, M.T.: Straggler identification in round-trip data streams via Newton\u2019s identities and invertible Bloom filters. IEEE Trans. Knowl. Data Eng. 23(2), 297\u2013306 (2010) (to appear)","DOI":"10.1109\/TKDE.2010.132"},{"issue":"2","key":"6_CR16","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1109\/TKDE.2010.132","volume":"23","author":"D Eppstein","year":"2010","unstructured":"Eppstein, D., Goodrich, M.T.: Straggler identification in round-trip data streams via Newton\u2019s identities and invertible Bloom filters. IEEE Trans. Knowl. Data Eng. 23(2), 297\u2013306 (2010)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"4","key":"6_CR17","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1145\/2043164.2018462","volume":"41","author":"D Eppstein","year":"2011","unstructured":"Eppstein, D., Goodrich, M.T., Uyeda, F., Varghese, G.: What\u2019s the difference? efficient set reconciliation without prior context. ACM SIGCOMM Comput. Commun. Rev. 41(4), 218\u2013229 (2011)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"6_CR18","doi-asserted-by":"publisher","unstructured":"Fagerjord, A., Kueng, L.: Mapping the core actors and flows in streaming video services: what Netflix can tell us about these new media networks. J. Media Bus. Stud. 16(3), 166\u2013181 (2019). https:\/\/doi.org\/10.1080\/16522354.2019.1684717","DOI":"10.1080\/16522354.2019.1684717"},{"key":"6_CR19","doi-asserted-by":"publisher","unstructured":"Fu, W., Abraham, H.B., Crowley, P.: Synchronizing namespaces with invertible Bloom filters. In: ACM\/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), pp. 123\u2013134 (2015). https:\/\/doi.org\/10.1109\/ANCS.2015.7110126","DOI":"10.1109\/ANCS.2015.7110126"},{"key":"6_CR20","unstructured":"Gao, P.: Analysis of the parallel peeling algorithm: a short proof (2014). arxiv.org\/abs\/1402.7326"},{"key":"6_CR21","unstructured":"Gentili, M.: Set Reconciliation and File Synchronization Using Invertible Bloom Lookup Tables. Ph.D. thesis, Harvard Univ. (2015)"},{"key":"6_CR22","unstructured":"Ghaffari, M., Grunau, C., Jin, C.: Improved MPC algorithms for MIS, matching, and coloring on trees and beyond. In: 34th International Symposium on Distributed Computing, pp. 34:1\u201334:18 (2020)"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Invertible bloom lookup tables. In: 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 792\u2013799. IEEE (2011). arxiv.org\/abs\/1101.2245","DOI":"10.1109\/Allerton.2011.6120248"},{"key":"6_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1007\/978-3-642-23719-5_56","volume-title":"Algorithms \u2013 ESA 2011","author":"MT Goodrich","year":"2011","unstructured":"Goodrich, M.T., Pszona, P.: External-memory network analysis algorithms for naturally sparse graphs. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 664\u2013676. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23719-5_56"},{"key":"6_CR25","doi-asserted-by":"publisher","unstructured":"Hijma, P., Heldens, S., Sclocco, A., van Werkhoven, B., Bal, H.E.: Optimization techniques for GPU programming. ACM Comput. Surv. 55(11) (2023). https:\/\/doi.org\/10.1145\/3570638","DOI":"10.1145\/3570638"},{"issue":"4","key":"6_CR26","doi-asserted-by":"publisher","first-page":"38","DOI":"10.3390\/data3040038","volume":"3","author":"A Hussain","year":"2018","unstructured":"Hussain, A., Aleem, M.: GoCJ: Google cloud jobs dataset for distributed and cloud computing infrastructures. Data 3(4), 38 (2018)","journal-title":"Data"},{"key":"6_CR27","doi-asserted-by":"publisher","unstructured":"Jiang, J., Mitzenmacher, M., Thaler, J.: Parallel peeling algorithms. ACM Trans. Parallel Comput. 3(1) (2017). https:\/\/doi.org\/10.1145\/2938412","DOI":"10.1145\/2938412"},{"key":"6_CR28","doi-asserted-by":"publisher","unstructured":"Karloff, H., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 938\u2013948 (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.76, https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611973075.76","DOI":"10.1137\/1.9781611973075.76"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Karloff, H., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In: 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 938\u2013948 (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Mizrahi, A., Bar-Lev, D., Yaakobi, E., Rottenstreich, O.: Invertible Bloom lookup tables with listing guarantees. arXiv:2212.13812 (2022)","DOI":"10.1145\/3626792"},{"key":"6_CR31","unstructured":"Molloy, M.: The pure literal rule threshold and cores in random hypergraphs. In: 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 672\u2013681. Society for Industrial and Applied Mathematics (2004)"},{"issue":"1","key":"6_CR32","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/rsa.20061","volume":"27","author":"M Molloy","year":"2005","unstructured":"Molloy, M.: Cores in random hypergraphs and Boolean formulas. Random Struct. Algorithms 27(1), 124\u2013135 (2005)","journal-title":"Random Struct. Algorithms"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Odun-Ayo, I., Ajayi, O., Akanle, B., Ahuja, R.: An overview of data storage in cloud computing. In: IEEE International Conference on Next Generation Computing and Information Systems (ICNGCIS), pp. 29\u201334. IEEE (2017)","DOI":"10.1109\/ICNGCIS.2017.9"},{"key":"6_CR34","doi-asserted-by":"publisher","unstructured":"Ozisik, A.P., Andresen, G., Levine, B.N., Tapp, D., Bissias, G., Katkuri, S.: Graphene: efficient interactive set reconciliation applied to blockchain propagation. In: ACM SIGCOMM, pp. 303\u2013317 (2019). https:\/\/doi.org\/10.1145\/3341302.3342082","DOI":"10.1145\/3341302.3342082"},{"key":"6_CR35","doi-asserted-by":"publisher","unstructured":"Palankar, M.R., Iamnitchi, A., Ripeanu, M., Garfinkel, S.: Amazon S3 for science grids: a viable solution? In: ACM Int. Workshop on Data-Aware Distributed Computing, pp. 55\u201364 (2008). https:\/\/doi.org\/10.1145\/1383519.1383526","DOI":"10.1145\/1383519.1383526"},{"issue":"4","key":"6_CR36","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.ipl.2013.11.015","volume":"114","author":"S Pontarelli","year":"2014","unstructured":"Pontarelli, S., Reviriego, P., Mitzenmacher, M.: Improving the performance of invertible Bloom lookup tables. Inf. Process. Lett. 114(4), 185\u2013191 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"6_CR37","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BF02289843","volume":"24","author":"F Restle","year":"1959","unstructured":"Restle, F.: A metric and an ordering on sets. Psychometrika 24(3), 207\u2013220 (1959)","journal-title":"Psychometrika"},{"key":"6_CR38","doi-asserted-by":"crossref","unstructured":"Sayood, K.: Introduction to Data Compression. Morgan Kaufmann (2017)","DOI":"10.1016\/B978-0-12-809474-7.00019-7"},{"key":"6_CR39","doi-asserted-by":"publisher","unstructured":"Shi, J., Dhulipala, L., Shun, J.: Parallel clique counting and peeling algorithms. In: SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), pp. 135\u2013146 (2021). https:\/\/doi.org\/10.1137\/1.9781611976830.13, https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611976830.13","DOI":"10.1137\/1.9781611976830.13"},{"key":"6_CR40","doi-asserted-by":"publisher","unstructured":"Shi, J., Shun, J.: Parallel algorithms for butterfly computations. In: Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 16\u201330 (2020). https:\/\/doi.org\/10.1137\/1.9781611976021.2, https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611976021.2","DOI":"10.1137\/1.9781611976021.2"},{"key":"6_CR41","doi-asserted-by":"publisher","unstructured":"V\u00f6cking, B.: How asymmetry helps load balancing. J. ACM 50(4), 568\u2013589 (2003). https:\/\/doi.org\/10.1145\/792538.792546","DOI":"10.1145\/792538.792546"},{"key":"6_CR42","unstructured":"Wilder, B.: Cloud Architecture Patterns: Using Microsoft Azure. \"O\u2019Reilly Media, Inc.\" (2012)"},{"key":"6_CR43","unstructured":"Wittig, M., Wittig, A.: Amazon Web Services in Action. Simon and Schuster (2018)"},{"issue":"9","key":"6_CR44","doi-asserted-by":"publisher","first-page":"1681","DOI":"10.1109\/JPROC.2016.2571298","volume":"104","author":"W Xia","year":"2016","unstructured":"Xia, W., et al.: A comprehensive study of the past, present, and future of data deduplication. Proc. IEEE 104(9), 1681\u20131710 (2016)","journal-title":"Proc. IEEE"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82697-9_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:58Z","timestamp":1739614678000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82697-9_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826962","9783031826979"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82697-9_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"16 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}