{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T15:48:19Z","timestamp":1768924099953,"version":"3.49.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p>\n            Set reconciliation is a fundamental algorithmic problem that arises in many networking, system, and database applications. In this problem, two large sets\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            of objects (bitcoins, files, records, etc.) are stored respectively at two different network-connected hosts, which we name Alice and Bob respectively. Alice and Bob communicate with each other to learn\n            <jats:italic>A<\/jats:italic>\n            \u0394\n            <jats:italic>B<\/jats:italic>\n            , the difference between\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            , and as a result the reconciled set\n            <jats:italic>A<\/jats:italic>\n            \u222a\n            <jats:italic>B.<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            Current set reconciliation schemes are based on either invertible Bloom filters (IBF) or error-correction codes (ECC). The former has a low computational complexity of\n            <jats:italic>O(d)<\/jats:italic>\n            , where\n            <jats:italic>d<\/jats:italic>\n            is the cardinality of\n            <jats:italic>A<\/jats:italic>\n            \u0394\n            <jats:italic>B<\/jats:italic>\n            , but has a high communication overhead that is several times larger than the theoretical minimum. The latter has a low communication overhead close to the theoretical minimum, but has a much higher computational complexity of\n            <jats:italic>O(d<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ). In this work, we propose Parity Bitmap Sketch (PBS), an ECC-based set reconciliation scheme that gets the better of both worlds: PBS has both a low computational complexity of\n            <jats:italic>O(d)<\/jats:italic>\n            just like IBF-based solutions and a low communication overhead of roughly twice the theoretical minimum. A separate contribution of this work is a novel rigorous analytical framework that can be used for the precise calculation of various performance metrics and for the near-optimal parameter tuning of PBS.\n          <\/jats:p>","DOI":"10.14778\/3436905.3436906","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T17:23:50Z","timestamp":1614014630000},"page":"458-470","source":"Crossref","is-referenced-by-count":6,"title":["Space- and computationally-efficient set reconciliation via parity bitmap sketch (PBS)"],"prefix":"10.14778","volume":"14","author":[{"given":"Long","family":"Gong","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}]},{"given":"Ziheng","family":"Liu","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"given":"Liang","family":"Liu","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]},{"given":"Jun","family":"Xu","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"given":"Mitsunori","family":"Ogihara","sequence":"additional","affiliation":[{"name":"University of Miami"}]},{"given":"Tong","family":"Yang","sequence":"additional","affiliation":[{"name":"University of Miami"}]}],"member":"320","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Dropbox Smart Sync. https:\/\/www.dropbox.com\/smart-sync. [Online","year":"2020","unstructured":"[n.d.]. Dropbox Smart Sync. https:\/\/www.dropbox.com\/smart-sync. [Online ; accessed 23- July - 2020 ]. [n.d.]. Dropbox Smart Sync. https:\/\/www.dropbox.com\/smart-sync. [Online; accessed 23-July-2020]."},{"key":"e_1_2_1_2_1","volume-title":"Ethereum: A secure decentralised generalised transaction ledger. https:\/\/ethereum.org\/., 32 pages. [Online","year":"2020","unstructured":"[n.d.]. Ethereum: A secure decentralised generalised transaction ledger. https:\/\/ethereum.org\/., 32 pages. [Online ; accessed 10- July - 2020 ]. [n.d.]. Ethereum: A secure decentralised generalised transaction ledger. https:\/\/ethereum.org\/., 32 pages. [Online; accessed 10-July-2020]."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(60)90287-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.836103"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-40061-5_12"},{"key":"e_1_2_1_8_1","unstructured":"Yann Collet. [n.d.]. xxHash - Extremely fast hash algorithm. https:\/\/github.com\/Cyan4973\/xxHash.  Yann Collet. [n.d.]. xxHash - Extremely fast hash algorithm. https:\/\/github.com\/Cyan4973\/xxHash."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/060651380"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043164.2018462"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Long Gong Ziheng Liu Liang Liu Jun Xu Mitsunori Ogihara and Tong Yang. 2020. Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS). arXiv e-prints arXiv:2007.14569.  Long Gong Ziheng Liu Liang Liu Jun Xu Mitsunori Ogihara and Tong Yang. 2020. Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS). arXiv e-prints arXiv:2007.14569.","DOI":"10.14778\/3436905.3436906"},{"key":"e_1_2_1_13_1","volume-title":"Goodrich and Michael Mitzenmacher","author":"Michael","year":"2011","unstructured":"Michael T. Goodrich and Michael Mitzenmacher . 2011 . Invertible Bloom Lookup Tables . arXiv e-prints, arXiv:1101.2245. arXiv:1101.2245 http:\/\/arxiv.org\/abs\/1101.2245 Michael T. Goodrich and Michael Mitzenmacher. 2011. Invertible Bloom Lookup Tables. arXiv e-prints, arXiv:1101.2245. arXiv:1101.2245 http:\/\/arxiv.org\/abs\/1101.2245"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.215"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.813498"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1946251261"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/646975.711402"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3358065"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646752.704751"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Annual Allerton Conference on Communication, Control, and Computing","volume":"248","author":"Minsky Yaron","year":"2002","unstructured":"Yaron Minsky and Ari Trachtenberg . 2002 . Practical set reconciliation . In Proceedings of the Annual Allerton Conference on Communication, Control, and Computing , Vol. 248 . Yaron Minsky and Ari Trachtenberg. 2002. Practical set reconciliation. In Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, Vol. 248."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.815784"},{"key":"e_1_2_1_23_1","volume-title":"Bitcoin: A peer-to-peer electronic cash system. Technical Report. Manubot. https:\/\/bitcoin.org\/bitcoin.pdf.","author":"Nakamoto Satoshi","year":"2019","unstructured":"Satoshi Nakamoto . 2019 . Bitcoin: A peer-to-peer electronic cash system. Technical Report. Manubot. https:\/\/bitcoin.org\/bitcoin.pdf. Satoshi Nakamoto. 2019. Bitcoin: A peer-to-peer electronic cash system. Technical Report. Manubot. https:\/\/bitcoin.org\/bitcoin.pdf."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354237"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342082"},{"key":"e_1_2_1_26_1","unstructured":"Pieter Wuille. [n.d.]. Minisketch: an optimized library for BCH-based set reconciliation. https:\/\/github.com\/sipa\/minisketch.  Pieter Wuille. [n.d.]. Minisketch: an optimized library for BCH-based set reconciliation. https:\/\/github.com\/sipa\/minisketch."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3436905.3436906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:24:07Z","timestamp":1672223047000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3436905.3436906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.14778\/3436905.3436906"],"URL":"https:\/\/doi.org\/10.14778\/3436905.3436906","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}