{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T06:43:55Z","timestamp":1767422635948,"version":"3.44.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T00:00:00Z","timestamp":1701907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2023,12,7]]},"abstract":"<jats:p>The Invertible Bloom Lookup Table (IBLT) is a probabilistic concise data structure for set representation that supports a listing operation as the recovery of the elements in the represented set. Its applications can be found in network synchronization and traffic monitoring as well as in error-correction codes. IBLT can list its elements with probability affected by the size of the allocated memory and the size of the represented set, such that it can fail with small probability even for relatively small sets. While previous works only studied the failure probability of IBLT, this work initiates the worst case analysis of IBLT that guarantees successful listing for all sets of a certain size. The worst case study is important since the failure of IBLT imposes high overhead. We describe a novel approach that guarantees successful listing when the set satisfies a tunable upper bound on its size. To allow that, we develop multiple constructions that are based on various coding techniques such as stopping sets and the stopping redundancy of error-correcting codes, and Steiner systems as well as new methodologies we develop. We analyze the sizes of IBLTs with listing guarantees obtained by the various methods as well as their mapping memory and runtime overheads. Lastly, we study lower bounds on the achievable sizes of IBLT with listing guarantees and verify the results in the paper by simulations.<\/jats:p>","DOI":"10.1145\/3626792","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T15:20:29Z","timestamp":1702394429000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Invertible Bloom Lookup Tables with Listing Guarantees"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5715-724X","authenticated-orcid":false,"given":"Avi","family":"Mizrahi","sequence":"first","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6766-1450","authenticated-orcid":false,"given":"Daniella","family":"Bar-Lev","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9851-5234","authenticated-orcid":false,"given":"Eitan","family":"Yaakobi","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4064-1238","authenticated-orcid":false,"given":"Ori","family":"Rottenstreich","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Allerton Conference on Communication, Control, and Computing","author":"Michael","year":"2011","unstructured":"Michael T. Goodrich and Michael Mitzenmacher. Invertible bloom lookup tables. In Allerton Conference on Communication, Control, and Computing, 2011."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2999572.2999609"},{"key":"e_1_2_1_3_1","volume-title":"USENIX Symposium on Networked Systems Design and Implementation (NSDI)","author":"Li Yuliang","year":"2016","unstructured":"Yuliang Li, Rui Miao, Changhoon Kim, and Minlan Yu. Flowradar: A better netflow for data centers. In USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2016."},{"key":"e_1_2_1_4_1","volume-title":"IEEE International Symposium on Information Theory (ISIT)","author":"Mitzenmacher Michael","year":"2012","unstructured":"Michael Mitzenmacher and George Varghese. Biff (Bloom filter) codes: Fast error correction for large data sets. In IEEE International Symposium on Information Theory (ISIT), 2012."},{"key":"e_1_2_1_5_1","volume-title":"ACM SIGCOMM","author":"Eppstein David","year":"2011","unstructured":"David Eppstein, Michael T. Goodrich, Frank Uyeda, and George Varghese. What's the difference?: Efficient set reconciliation without prior context. In ACM SIGCOMM, 2011."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0316-0"},{"key":"e_1_2_1_7_1","volume-title":"ACM SIGCOMM","author":"Ozisik A. Pinar","year":"2019","unstructured":"A. Pinar Ozisik, Gavin Andresen, Brian Neil Levine, Darren Tapp, George Bissias, and Sunny Katkuri. Graphene: Efficient interactive set reconciliation applied to blockchain propagation. In ACM SIGCOMM, 2019."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.1003839"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.864441"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8486415"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373360.3380845"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.883542"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2023736"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2006.888633"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511808968"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198535768.001.0001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90015-2"},{"key":"e_1_2_1_19_1","volume-title":"Finite length analysis on listing failure probability of invertible Bloom lookup tables. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 97-A(12):2309--2316","author":"Yugawa Daichi","year":"2014","unstructured":"Daichi Yugawa and Tadashi Wadayama. Finite length analysis on listing failure probability of invertible Bloom lookup tables. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 97-A(12):2309--2316, 2014."},{"key":"e_1_2_1_20_1","volume-title":"Failure probability analysis for partial extraction from invertible Bloom filters. arXiv preprint arXiv:2008.00879","author":"Kubjas Ivo","year":"2020","unstructured":"Ivo Kubjas and Vitaly Skachek. Failure probability analysis for partial extraction from invertible Bloom filters. arXiv preprint arXiv:2008.00879, 2020."},{"key":"e_1_2_1_21_1","volume-title":"Irregular invertible Bloom look-up tables. CoRR, abs\/2107.02573","author":"L\u00e1zaro Francisco","year":"2021","unstructured":"Francisco L\u00e1zaro and Bal\u00e1zs Matuz. Irregular invertible Bloom look-up tables. CoRR, abs\/2107.02573, 2021."},{"key":"e_1_2_1_22_1","volume-title":"Parallel peeling algorithms. ACM Transactions on Parallel Computing (TOPC), 3(1):1--27","author":"Jiang Jiayang","year":"2017","unstructured":"Jiayang Jiang, Michael Mitzenmacher, and Justin Thaler. Parallel peeling algorithms. ACM Transactions on Parallel Computing (TOPC), 3(1):1--27, 2017."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1964.1053689"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/050631847"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2011.010411.100240"},{"key":"e_1_2_1_26_1","volume-title":"Marcel Adrian Ambroze, and Martin Tomlinson. On the minimum\/stopping distance of array low-density parity-check codes","author":"Rosnes Eirik","year":"2014","unstructured":"Eirik Rosnes, Marcel Adrian Ambroze, and Martin Tomlinson. On the minimum\/stopping distance of array low-density parity-check codes. IEEE transactions on information theory, 60(9):5204--5214, 2014."},{"key":"e_1_2_1_27_1","volume-title":"Bounds on unique-neighbor codes. arXiv preprint arXiv:2203.10330","author":"Linial Nati","year":"2022","unstructured":"Nati Linial and Idan Orzech. Bounds on unique-neighbor codes. arXiv preprint arXiv:2203.10330, 2022."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2003.1228136"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388385"},{"volume-title":"Colloq. Math., 3: 146--163","year":"1954","key":"e_1_2_1_30_1","unstructured":"Tur\u00e1n. Peter. On the theory of graphs. Colloq. Math., 3:146--163, 1954."},{"key":"e_1_2_1_31_1","unstructured":"Austin Appleby. Murmurhash3 2016. https:\/\/github.com\/aappleby\/smhasher\/blob\/ master\/src\/MurmurHash3.cpp."},{"key":"e_1_2_1_32_1","volume-title":"Bitcoin: A peer-to-peer electronic cash system. Bitcoin white paper","author":"Nakamoto Satoshi","year":"2008","unstructured":"Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Bitcoin white paper, 2008."},{"key":"e_1_2_1_33_1","volume-title":"Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper","author":"Gavin Wood","year":"2014","unstructured":"Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 2014."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308897.3308956"},{"key":"e_1_2_1_35_1","volume-title":"Collective dynamics of \"small-world'networks. nature, 393(6684):440--442","author":"Watts Duncan J","year":"1998","unstructured":"Duncan J Watts and Steven H Strogatz. Collective dynamics of \"small-world'networks. nature, 393(6684):440--442, 1998."},{"key":"e_1_2_1_36_1","volume-title":"Projective geometry over finite fields. Oxford Math. Monographs","author":"Hirschfeld JWP","year":"1979","unstructured":"JWP Hirschfeld. Projective geometry over finite fields. Oxford Math. Monographs, 1979."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626792","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626792","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:14:58Z","timestamp":1755908098000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626792"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,7]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,12,7]]}},"alternative-id":["10.1145\/3626792"],"URL":"https:\/\/doi.org\/10.1145\/3626792","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2023,12,7]]},"assertion":[{"value":"2023-12-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}