{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T00:50:46Z","timestamp":1778028646919,"version":"3.51.4"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>\n            Set intersection is a fundamental operation in information retrieval and database systems. This paper introduces linear space data structures to represent sets such that their intersection can be computed in a worst-case efficient way. In general, given\n            <jats:italic>k<\/jats:italic>\n            (preprocessed) sets, with totally\n            <jats:italic>n<\/jats:italic>\n            elements, we will show how to compute their intersection in expected time [EQUATION], where\n            <jats:italic>r<\/jats:italic>\n            is the intersection size and\n            <jats:italic>w<\/jats:italic>\n            is the number of bits in a machine-word. In addition, we introduce a very simple version of this algorithm that has weaker asymptotic guarantees but performs even better in practice; both algorithms outperform the state of the art techniques for both synthetic and real data sets and workloads.\n          <\/jats:p>","DOI":"10.14778\/1938545.1938550","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"255-266","source":"Crossref","is-referenced-by-count":68,"title":["Fast set intersection in memory"],"prefix":"10.14778","volume":"4","author":[{"given":"Bolin","family":"Ding","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnd Christian","family":"K\u00f6nig","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27801-6_30"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_2"},{"key":"e_1_2_1_3_1","first-page":"390","volume-title":"SODA","author":"Barbay J.","year":"2002","unstructured":"J. Barbay and C. Kenyon . Adaptive intersection and t-threshold problems . In SODA , pages 390 -- 399 , 2002 . J. Barbay and C. Kenyon. Adaptive intersection and t-threshold problems. In SODA, pages 390--399, 2002."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_13"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1564507"},{"key":"e_1_2_1_6_1","first-page":"739","volume-title":"ISAAC","author":"Bille P.","year":"2007","unstructured":"P. Bille , A. Pagh , and R. Pagh . Fast Evaluation of Union-Intersection Expressions . In ISAAC , pages 739 -- 750 , 2007 . P. Bille, A. Pagh, and R. Pagh. Fast Evaluation of Union-Intersection Expressions. In ISAAC, pages 739--750, 2007."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277660"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956944"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322127"},{"key":"e_1_2_1_10_1","unstructured":"J. Brutlag. Speed Matters for Google Web Search. http:\/\/code.google.com\/speed\/files\/delayexp.pdf 2009.  J. Brutlag. Speed Matters for Google Web Search. http:\/\/code.google.com\/speed\/files\/delayexp.pdf 2009."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_15"},{"key":"e_1_2_1_12_1","first-page":"743","volume-title":"SODA","author":"Demaine E.","year":"2000","unstructured":"E. Demaine , A. L\u00f3pez-Ortiz , and J. Munro . Adaptive Set Intersections, Unions, and Differences . In SODA , pages 743 -- 752 , 2000 . E. Demaine, A. L\u00f3pez-Ortiz, and J. Munro. Adaptive Set Intersections, Unions, and Differences. In SODA, pages 743--752, 2000."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646679.702301"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"Dubhashi D. P.","year":"2009","unstructured":"D. P. Dubhashi and A. Panconesi . Concentration of Measure for the Analysis of Randomized Algorithms . Cambridge , 2009 . D. P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge, 2009."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201004"},{"key":"e_1_2_1_17_1","unstructured":"G. Linden. http:\/\/glinden.blogspot.com\/2006\/11\/marissa-mayer-at-web-20.html.  G. Linden. http:\/\/glinden.blogspot.com\/2006\/11\/marissa-mayer-at-web-20.html."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1571941.1572104"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972887.1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687722"},{"key":"e_1_2_1_23_1","volume-title":"Managing Gigabytes - Compressing and Indexing Documents and Images","author":"Witten I. H.","year":"1999","unstructured":"I. H. Witten , A. Moffat , and T. C. Bell . Managing Gigabytes - Compressing and Indexing Documents and Images . Morgan Kaufman Publishers , 1999 . I. H. Witten, A. Moffat, and T. C. Bell. Managing Gigabytes - Compressing and Indexing Documents and Images. Morgan Kaufman Publishers, 1999."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1938545.1938550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:46:06Z","timestamp":1672224366000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1938545.1938550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.14778\/1938545.1938550"],"URL":"https:\/\/doi.org\/10.14778\/1938545.1938550","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}