{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:28Z","timestamp":1750219828982,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,18]],"date-time":"2023-06-18T00:00:00Z","timestamp":1687046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["2106888,2045590,2046235"],"award-info":[{"award-number":["2106888,2045590,2046235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,18]]},"DOI":"10.1145\/3584372.3588679","type":"proceedings-article","created":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T22:21:22Z","timestamp":1685744482000},"page":"169-181","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5486-4641","authenticated-orcid":false,"given":"Aline","family":"Bessa","sequence":"first","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4001-4346","authenticated-orcid":false,"given":"Majid","family":"Daliri","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3915-7075","authenticated-orcid":false,"given":"Juliana","family":"Freire","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2197-6806","authenticated-orcid":false,"given":"Cameron","family":"Musco","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3118-4848","authenticated-orcid":false,"given":"Christopher","family":"Musco","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5124-7770","authenticated-orcid":false,"given":"A\u00e9cio","family":"Santos","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6939-6591","authenticated-orcid":false,"given":"Haoxiang","family":"Zhang","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,18]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Noga Alon Phillip B. Gibbons Yossi Matias and Mario Szegedy. 1999 a. Tracking Join and Self-Join Sizes in Limited Storage. In \u00b6ODS1999.","DOI":"10.1145\/303976.303978"},{"key":"e_1_3_2_1_3_1","volume-title":"Optimal Compression of Approximate Inner Products and Dimension Reduction. In FOCS2017","author":"Alon Noga","year":"2017","unstructured":"Noga Alon and Bo'az Klartag. 2017. Optimal Compression of Approximate Inner Products and Dimension Reduction. In FOCS2017. 639--650."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-6265-7"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"volume-title":"Foundations of Data Science","author":"Blum Avrim","key":"e_1_3_2_1_7_1","unstructured":"Avrim Blum, John Hopcroft, and Ravindran Kannan. 2020. Foundations of Data Science. Cambridge University Press."},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings. Compression and Complexity of SEQUENCES","author":"Broder A.Z.","year":"1997","unstructured":"A.Z. Broder. 1997. On the resemblance and containment of documents. In Proceedings. Compression and Complexity of SEQUENCES 1997. 21--29."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276781"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_3_2_1_12_1","volume-title":"Finding Frequent Items in Data Streams. In ICALP2002","author":"Charikar Moses","year":"2002","unstructured":"Moses Charikar, Kevin Chen, and Martin Farach-Colton. 2002. Finding Frequent Items in Data Streams. In ICALP2002. 693--703."},{"key":"e_1_3_2_1_13_1","volume-title":"ACM Comput. Surv.","volume":"50","author":"Chi Lianhua","year":"2017","unstructured":"Lianhua Chi and Xingquan Zhu. 2017. Hashing Techniques: A Survey and Taxonomy. ACM Comput. Surv. , Vol. 50, 1 (2017)."},{"key":"e_1_3_2_1_14_1","volume-title":"DartMinHash: Fast Sketching for Weighted Sets. arXiv2005.11547","author":"Christiani Tobias","year":"2020","unstructured":"Tobias Christiani. 2020. DartMinHash: Fast Sketching for Weighted Sets. arXiv2005.11547 (2020)."},{"key":"e_1_3_2_1_15_1","unstructured":"City of New York. 2022. Open Data NYC. https:\/\/opendata.cityofnewyork.us\/."},{"volume-title":"Springer New York","author":"Cohen Edith","key":"e_1_3_2_1_16_1","unstructured":"Edith Cohen. 2016. Min-Hash Sketches. Springer New York, New York, NY, 1282--1287."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Edith Cohen and Haim Kaplan. 2007. Summarizing Data Using Bottom-k Sketches. In \u00b6ODC2007. 225--234.","DOI":"10.1145\/1281100.1281133"},{"key":"e_1_3_2_1_18_1","volume-title":"What You Can Do with Coordinated Samples. In APPROX2013","author":"Cohen Edith","year":"2013","unstructured":"Edith Cohen and Haim Kaplan. 2013. What You Can Do with Coordinated Samples. In APPROX2013. 452--467."},{"volume-title":"Histograms, Wavelets, Sketches","author":"Cormode Graham","key":"e_1_3_2_1_19_1","unstructured":"Graham Cormode, Minos Garofalakis, Peter Haas, and Chris Jermaine. 2011. Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches. NOW publishers."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"e_1_3_2_1_21_1","volume-title":"BagMinHash - Minwise Hashing Algorithm for Weighted Sets. In KDD2018","author":"Ertl Otmar","year":"2018","unstructured":"Otmar Ertl. 2018. BagMinHash - Minwise Hashing Algorithm for Weighted Sets. In KDD2018. 1368--1377."},{"key":"e_1_3_2_1_22_1","volume-title":"ICDE2019","author":"Fernandez Raul Castro","year":"2019","unstructured":"Raul Castro Fernandez, Jisoo Min, Demitri Nava, and Samuel Madden. 2019. Lazo: A cardinality-based method for coupled estimation of Jaccard similarity and containment. In ICDE2019. 1190--1201."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_3_2_1_25_1","volume-title":"Exploiting Asymmetry in Hierarchical Topic Extraction. In CIKM2006","author":"Gollapudi Sreenivas","year":"2006","unstructured":"Sreenivas Gollapudi and Rina Panigrahy. 2006. Exploiting Asymmetry in Hierarchical Topic Extraction. In CIKM2006. 475--482."},{"key":"e_1_3_2_1_26_1","volume-title":"Consistent Weighted Sampling Made Fast, Small, and Easy. arXiv1410.4266","author":"Haeupler Bernhard","year":"2014","unstructured":"Bernhard Haeupler, Mark Manasse, and Kunal Talwar. 2014. Consistent Weighted Sampling Made Fast, Small, and Easy. arXiv1410.4266 (2014)."},{"key":"e_1_3_2_1_27_1","volume-title":"Scalable Document Fingerprinting. In USENIX Workshop on Electronic Commerce.","author":"Heintze Nevin","year":"1996","unstructured":"Nevin Heintze. 1996. Scalable Document Fingerprinting. In USENIX Workshop on Electronic Commerce."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.80"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2453355"},{"key":"e_1_3_2_1_30_1","volume-title":"Woodruff","author":"Kane Daniel M.","year":"2010","unstructured":"Daniel M. Kane, Jelani Nelson, and David P. Woodruff. 2010. An Optimal Algorithm for the Distinct Elements Problem. In \u00b6ODS2010. 41--52."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSAA.2015.7344858"},{"key":"e_1_3_2_1_32_1","volume-title":"Optimality of the Johnson-Lindenstrauss Lemma. In FOCS2017","author":"Larsen Kasper Green","year":"2017","unstructured":"Kasper Green Larsen and Jelani Nelson. 2017. Optimality of the Johnson-Lindenstrauss Lemma. In FOCS2017. 633--638."},{"key":"e_1_3_2_1_33_1","volume-title":"Feature Hashing and the Median of Three. In ICML2021","author":"Larsen Kasper Green","year":"2021","unstructured":"Kasper Green Larsen, Rasmus Pagh, and Jakub Tve tek. 2021. CountSketches, Feature Hashing and the Median of Three. In ICML2021. 6011--6020."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2015.05.001"},{"key":"e_1_3_2_1_35_1","volume-title":"Linearized GMM Kernels and Normalized Random Fourier Features. In KDD2017","author":"Li Ping","year":"2017","unstructured":"Ping Li. 2017. Linearized GMM Kernels and Normalized Random Fourier Features. In KDD2017. 315--324."},{"key":"e_1_3_2_1_36_1","volume-title":"Conditional Random Sampling: A Sketch-based Sampling Technique for Sparse Data. In NIPS2006","volume":"19","author":"Li Ping","year":"2006","unstructured":"Ping Li, Kenneth Church, and Trevor Hastie. 2006. Conditional Random Sampling: A Sketch-based Sampling Technique for Sparse Data. In NIPS2006, Vol. 19."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772759"},{"key":"e_1_3_2_1_38_1","volume-title":"Quantized Random Projections and Non-Linear Estimation of Cosine Similarity. In NIPS2016","volume":"29","author":"Li Ping","year":"2016","unstructured":"Ping Li, Michael Mitzenmacher, and Martin Slawski. 2016. Quantized Random Projections and Non-Linear Estimation of Cosine Similarity. In NIPS2016, Vol. 29."},{"key":"e_1_3_2_1_39_1","volume-title":"One Permutation Hashing. In NIPS2012","author":"Li Ping","year":"2012","unstructured":"Ping Li, Art Owen, and Cun-hui Zhang. 2012. One Permutation Hashing. In NIPS2012."},{"key":"e_1_3_2_1_40_1","volume-title":"NIPS2011","volume":"24","author":"Li Ping","year":"2011","unstructured":"Ping Li, Anshumali Shrivastava, Joshua Moore, and Arnd K\u00f6nig. 2011. Hashing algorithms for large-scale learning. NIPS2011 , Vol. 24 (2011)."},{"key":"e_1_3_2_1_42_1","volume-title":"USENIX","author":"Manber Udi","year":"1994","unstructured":"Udi Manber. 1994. Finding Similar Files in a Large File System. In USENIX Winter 1994 Technical Conference."},{"key":"e_1_3_2_1_43_1","unstructured":"Tom Mitchell. 1997. 20 Newsgroups Dataset. https:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.datasets.fetch_20newsgroups.html."},{"key":"e_1_3_2_1_44_1","volume-title":"Woodruff","author":"Pagh Rasmus","year":"2014","unstructured":"Rasmus Pagh, Morten St\u00f6ckel, and David P. Woodruff. 2014. Is Min-Wise Hashing Optimal for Summarizing Set Intersection?. In \u00b6ODS2014. 109--120."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386121"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/361219.361220"},{"key":"e_1_3_2_1_47_1","volume-title":"Correlation Sketches for Approximate Join-Correlation Queries. In SIGMOD2021","author":"Santos A\u00e9cio","year":"2021","unstructured":"A\u00e9cio Santos, Aline Bessa, Fernando Chirigati, Christopher Musco, and Juliana Freire. 2021. Correlation Sketches for Approximate Join-Correlation Queries. In SIGMOD2021. 199--210."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00264"},{"key":"e_1_3_2_1_49_1","volume-title":"Simple and Efficient Weighted Minwise Hashing. In NIPS2016","author":"Shrivastava Anshumali","year":"2016","unstructured":"Anshumali Shrivastava. 2016. Simple and Efficient Weighted Minwise Hashing. In NIPS2016. 1506--1514."},{"key":"e_1_3_2_1_50_1","volume-title":"AISTATS2014","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li. 2014. In Defense of Minhash over Simhash. In AISTATS2014."},{"key":"e_1_3_2_1_51_1","unstructured":"World Bank. 2022. World Bank Group Finances. https:\/\/finances.worldbank.org\/"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3021067"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2876250"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00048"},{"volume-title":"JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. In SIGMOD2019","author":"Zhu Erkang","key":"e_1_3_2_1_55_1","unstructured":"Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Ren\u00e9e J. Miller. 2019. JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. In SIGMOD2019. 847--864."},{"key":"e_1_3_2_1_56_1","volume-title":"Miller","author":"Zhu Erkang","year":"2016","unstructured":"Erkang Zhu, Fatemeh Nargesian, Ken Q Pu, and Ren\u00e9e J. Miller. 2016. LSH Ensemble: Internet-Scale Domain Search. Proceedings of the VLDB Endowment , Vol. 9, 12 (2016). io"}],"event":{"name":"SIGMOD\/PODS '23: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Seattle WA USA","acronym":"SIGMOD\/PODS '23"},"container-title":["Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588679","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3584372.3588679","content-type":"text\/html","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3588679","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3588679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:29Z","timestamp":1750178789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,18]]},"references-count":55,"alternative-id":["10.1145\/3584372.3588679","10.1145\/3584372"],"URL":"https:\/\/doi.org\/10.1145\/3584372.3588679","relation":{},"subject":[],"published":{"date-parts":[[2023,6,18]]},"assertion":[{"value":"2023-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}