{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:06:30Z","timestamp":1792155990706,"version":"4.4.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T00:00:00Z","timestamp":1291161600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>\n            Conjunctive Boolean queries are a key component of modern information retrieval systems, especially when Web-scale repositories are being searched. A conjunctive query\n            <jats:italic>q<\/jats:italic>\n            is equivalent to a |\n            <jats:italic>q<\/jats:italic>\n            |-way intersection over ordered sets of integers, where each set represents the documents containing one of the terms, and each integer in each set is an ordinal document identifier. As is the case with many computing applications, there is tension between the way in which the data is represented, and the ways in which it is to be manipulated. In particular, the sets representing index data for typical document collections are highly compressible, but are processed using random access techniques, meaning that methods for carrying out set intersections must be alert to issues to do with access patterns and data representation. Our purpose in this article is to explore these trade-offs, by investigating intersection techniques that make use of both uncompressed \u201cinteger\u201d representations, as well as compressed arrangements. We also propose a simple hybrid method that provides both compact storage, and also faster intersection computations for conjunctive querying than is possible even with uncompressed representations.\n          <\/jats:p>","DOI":"10.1145\/1877766.1877767","type":"journal-article","created":{"date-parts":[[2010,12,22]],"date-time":"2010-12-22T14:41:31Z","timestamp":1293028891000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":89,"title":["Efficient set intersection for inverted indexing"],"prefix":"10.1145","volume":"29","author":[{"given":"J. Shane","family":"Culpepper","sequence":"first","affiliation":[{"name":"RMIT University and The University of Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alistair","family":"Moffat","sequence":"additional","affiliation":[{"name":"The University of Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,12,27]]},"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","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02)","author":"Barbay J.","unstructured":"Barbay , J. and Kenyon , C . 2002. Adaptive intersection and t-threshold problems . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02) . D. Eppstein, Ed., 390--399. Barbay, J. and Kenyon, C. 2002. Adaptive intersection and t-threshold problems. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02). D. Eppstein, Ed., 390--399."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_13"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90071-5"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04)","author":"Blandford D. K.","unstructured":"Blandford , D. K. and Blelloch , G. E . 2004. Compact representations of ordered sets . In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04) . J. I. Munro, Ed., 11--19. Blandford, D. K. and Blelloch, G. E. 2004. Compact representations of ordered sets. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04). J. I. Munro, Ed., 11--19."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294165"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89097-3_18"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00)","author":"Demaine E. D.","unstructured":"Demaine , E. D. , L\u00f3pez-Ortiz , A. , and Munro , J. I . 2000. Adaptive set intersections, unions, and differences . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00) . 743--752. Demaine, E. D., L\u00f3pez-Ortiz, A., and Munro, J. I. 2000. Adaptive set intersections, unions, and differences. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00). 743--752."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055357"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053907"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288534"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_14"},{"key":"e_1_2_1_15_1","volume-title":"Computer Architecture: A Quantitative Approach","author":"Hennessy J. L.","year":"2006","unstructured":"Hennessy , J. L. and Patterson , D. A . 2006 . Computer Architecture: A Quantitative Approach 4 th Ed. Morgan Kaufmann , San Francisco, CA . Hennessy, J. L. and Patterson, D. A. 2006. Computer Architecture: A Quantitative Approach 4th Ed. Morgan Kaufmann, San Francisco, CA.","edition":"4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201004"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 13th Australasian Computer Science Conference. 275--284","author":"Moffat A.","unstructured":"Moffat , A. and Port , G. S . 1990. Splay tree melding: Theme and variations . In Proceedings of the 13th Australasian Computer Science Conference. 275--284 . Moffat, A. and Port, G. S. 1990. Splay tree melding: Theme and variations. In Proceedings of the 13th Australasian Computer Science Conference. 275--284."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013002601898"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Moffat A. and Turpin A. 2002. Compression and Coding Algorithms 1st Ed. Kluwer Academic Publisher Boston.   Moffat A. and Turpin A. 2002. Compression and Coding Algorithms 1st Ed. Kluwer Academic Publisher Boston.","DOI":"10.1007\/978-1-4615-0935-6_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/237496.237497"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 16th Annual Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Munro J. I.","unstructured":"Munro , J. I. 1996. Tables . In Proceedings of the 16th Annual Conference on Foundations of Software Technology and Theoretical Computer Science , V. Chandru and V. Vinay, Eds. Lecture Notes in Computer Science, vol. 1180 . Springer , 37--42. Munro, J. I. 1996. Tables. In Proceedings of the 16th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, V. Chandru and V. Vinay, Eds. Lecture Notes in Computer Science, vol. 1180. Springer, 37--42."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'07)","author":"Okanohara D.","unstructured":"Okanohara , D. and Sadakane , K . 2007. Practical entropy-compressed rank\/select dictionary . In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'07) . 60--70. Okanohara, D. and Sadakane, K. 2007. Practical entropy-compressed rank\/select dictionary. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'07). 60--70."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02)","author":"Raman R.","unstructured":"Raman , R. , Raman , V. , and Rao , S. S . 2002. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02) , D. Eppstein, Ed. SIAM, 233--242. Raman, R., Raman, V., and Rao, S. S. 2002. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), D. Eppstein, Ed. SIAM, 233--242."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109693"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'07)","author":"Sanders P.","unstructured":"Sanders , P. and Transier , F . 2007. Intersection in integer inverted indices . In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'07) . 71--83. Sanders, P. and Transier, F. 2007. Intersection in integer inverted indices. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'07). 71--83."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277774"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'08)","author":"Transier F.","unstructured":"Transier , F. and Sanders , P . 2008. Compressed inverted indexes for in-memory search engines . In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'08) . J. I. Munro and D. Wagner, Eds. 3--12. Transier, F. and Sanders, P. 2008. Compressed inverted indexes for in-memory search engines. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'08). J. I. Munro and D. Wagner, Eds. 3--12."},{"key":"e_1_2_1_30_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"Witten I. H.","year":"1999","unstructured":"Witten , I. H. , Moffat , A. , and Bell , T. C . 1999 . Managing Gigabytes: Compressing and Indexing Documents and Images 2 nd Ed. Morgan Kaufmann , San Francisco . Witten, I. H., Moffat, A., and Bell, T. C. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images 2nd Ed. Morgan Kaufmann, San Francisco.","edition":"2"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1877766.1877767","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1877766.1877767","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:47Z","timestamp":1750243967000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1877766.1877767"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1145\/1877766.1877767"],"URL":"https:\/\/doi.org\/10.1145\/1877766.1877767","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]},"assertion":[{"value":"2009-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}