{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T10:16:38Z","timestamp":1768904198095,"version":"3.49.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"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. Algorithms"],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            The\n            <jats:italic>intersection of sorted arrays<\/jats:italic>\n            problem has applications in search engines such as Google. Previous work has proposed and compared deterministic algorithms for this problem, in an adaptive analysis based on the encoding size of a certificate of the result (cost analysis). We define the\n            <jats:italic>alternation analysis<\/jats:italic>\n            , based on the nondeterministic complexity of an instance. In this analysis we prove that there is a deterministic algorithm asymptotically performing as well as any randomized algorithm in the comparison model. We define the\n            <jats:italic>redundancy analysis<\/jats:italic>\n            , based on a measure of the internal redundancy of the instance. In this analysis we prove that any algorithm optimal in the redundancy analysis is optimal in the alternation analysis, but that there is a randomized algorithm which performs strictly better than any deterministic algorithm in the comparison model. Finally, we describe how these results can be extended beyond the comparison model.\n          <\/jats:p>","DOI":"10.1145\/1328911.1328915","type":"journal-article","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T16:08:32Z","timestamp":1207066112000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Alternation and redundancy analysis of the intersection problem"],"prefix":"10.1145","volume":"4","author":[{"given":"J\u00e9r\u00e9my","family":"Barbay","sequence":"first","affiliation":[{"name":"University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Kenyon","sequence":"additional","affiliation":[{"name":"Brown University, Providence, RI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,3,28]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM), S. C. Sahinalp et al., Eds","author":"Baeza-Yates R. A.","unstructured":"Baeza-Yates , R. A. 2004. A fast set intersection algorithm for sorted sequences . In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM), S. C. Sahinalp et al., Eds . Lecture Notes in Computer Science , vol. 3109 . Springer , 400--408. Baeza-Yates, R. A. 2004. A fast set intersection algorithm for sorted sequences. In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM), S. C. Sahinalp et al., Eds. Lecture Notes in Computer Science, vol. 3109. Springer, 400--408."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39816-5_3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Barbay J. and Kenyon C. 2003. Deterministic algorithm for the t-threshold set problem. In Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC) H. O. Toshihide Ibaraki Noki Katoh Eds. Lecture Notes in Computer Science. Springer 575--584.  Barbay J. and Kenyon C. 2003. Deterministic algorithm for the t-threshold set problem. In Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC) H. O. Toshihide Ibaraki Noki Katoh Eds. Lecture Notes in Computer Science. Springer 575--584.","DOI":"10.1007\/978-3-540-24587-2_59"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, 390--399","author":"Barbay J.","unstructured":"Barbay , J. , and Kenyon , C . 2002. Adaptive intersection and t-threshold problems . In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, 390--399 . Barbay, J., and Kenyon, C. 2002. Adaptive intersection and t-threshold problems. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, 390--399."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1822"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 195--207","author":"Bender M. A.","unstructured":"Bender , M. A. , Cole , R. , and Raman , R . 2002. Exponential structures for efficient cache-oblivious algorithms . In Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 195--207 . Bender, M. A., Cole, R., and Raman, R. 2002. Exponential structures for efficient cache-oblivious algorithms. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 195--207."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90071-5"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275492"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.20"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009235"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222019"},{"key":"e_1_2_1_13_1","unstructured":"Demaine E. D. L\u00f3pez-Ortiz A. and Munro J. I. 2001. Experiments on adaptive set intersections for text retrieval systems. In Proceedings of the 3rd Workshop on Algorithm Engineering and Experiments. Lecture Notes in Computer Science. Springer 5--6.   Demaine E. D. L\u00f3pez-Ortiz A. and Munro J. I. 2001. Experiments on adaptive set intersections for text retrieval systems. In Proceedings of the 3rd Workshop on Algorithm Engineering and Experiments. Lecture Notes in Computer Science. Springer 5--6."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), 743--752","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 ACM-SIAM Symposium on Discrete Algorithms (SODA), 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 ACM-SIAM Symposium on Discrete Algorithms (SODA), 743--752."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 285","author":"Frigo M.","unstructured":"Frigo , M. , Leiserson , C. E. , Prokop , H. , and Ramachandran , S . 1999. Cache-Oblivious algorithms . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 285 . Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. 1999. Cache-Oblivious algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 285."},{"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":"crossref","unstructured":"Hwang F. K. and Lin S. 1971. Optimal merging of 2 elements with n elements. Acta Inf. 145--158.  Hwang F. K. and Lin S. 1971. Optimal merging of 2 elements with n elements. Acta Inf. 145--158.","DOI":"10.1007\/BF00289521"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322144"},{"key":"e_1_2_1_19_1","unstructured":"Neumann J. V. and Morgenstern O. 1944. Theory of Games and Economic Behavior 1st ed. Princeton University Press.  Neumann J. V. and Morgenstern O. 1944. Theory of Games and Economic Behavior 1st ed. Princeton University Press."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 233--242","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), 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), 233--242."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Sion M. 1958. On general minimax theorems. Pacific J. Math. 171--176.  Sion M. 1958. On general minimax theorems. Pacific J. Math. 171--176.","DOI":"10.2140\/pjm.1958.8.171"},{"key":"e_1_2_1_22_1","unstructured":"Witten I. H. Moffat A. and Bell T. C. 1994. Managing Gigabytes. VanNostrand Reinhold New York.  Witten I. H. Moffat A. and Bell T. C. 1994. Managing Gigabytes. VanNostrand Reinhold New York."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328915","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1328911.1328915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:00Z","timestamp":1750258320000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1328911.1328915"],"URL":"https:\/\/doi.org\/10.1145\/1328911.1328915","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2006-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}