Alternation and redundancy analysis of the intersection problem

ABSTRACT

The intersection of sorted arrays 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 alternation analysis, 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 redundancy analysis, 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.

REFERENCES

• 1: 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.
• 2: Barbay, J. 2004. Index-Trees for descendant tree queries in the comparison model. Tech. Rep. TR-2004-11, University of British Columbia. July.
• 3: Barbay, J. 2003. Optimality of randomized algorithms for the intersection problem. In Proceedings of the 2nd International Symposium on Stochastic Algorithms, Foundations and Applications (SAGA), A. Albrecht, Ed. Lecture Notes in Computer Science, vol. 2827. Springer, Heidelberg, 26--38. 3-540-20103-3.
• 4: 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.
• 5: Jérémy Barbay , Claire Kenyon, Adaptive intersection and t-threshold problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.390-399, January 06-08, 2002, San Francisco, California
• 6: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002 [doi>10.1006/jcss.2002.1822]
• 7: Michael A. Bender , Richard Cole , Rajeev Raman, Exponential Structures for Efficient Cache-Oblivious Algorithms, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.195-207, July 08-13, 2002
• 8: Bentley, J. L., and Yao, A. C.-C. 1976. An almost optimal algorithm for unbounded searching. Inf. Proc. Lett. 5, 3, 82--87.
• 9: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 10: Christen, C. 1978. Improving the bound on optimal merging. In Proceedings of 19th Annual Symposium on Foundations of Computer Science (FOCS). 259--266.
• 11: de la Vega, W. F., Frieze, A. M., and Santha, M. 1998. Average-Case analysis of the merging algorithm of Hwang and Lin. Algorithmica 22, 4, 483--489.
• 12: Wenceslas Fernandez de la Vega , Sampath Kannan , Miklos Santha, Two probabilistic results on merging, SIAM Journal on Computing, v.22 n.2, p.261-271, April 1993 [doi>10.1137/0222019]
• 13: Erik D. Demaine , Alejandro López-Ortiz , J. Ian Munro, Experiments on Adaptive Set Intersections for Text Retrieval Systems, Revised Papers from the Third International Workshop on Algorithm Engineering and Experimentation, p.91-104, January 05-06, 2001
• 14: Erik D. Demaine , Alejandro López-Ortiz , J. Ian Munro, Adaptive set intersections, unions, and differences, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.743-752, January 09-11, 2000, San Francisco, California, United States
• 15: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 16: Hwang, F. K., and Lin, S. 1972. A simple algorithm for merging two disjoint linearly ordered sets. SIAM J. Comput. 1, 1, 31--39.
• 17: Hwang, F. K., and Lin, S. 1971. Optimal merging of 2 elements with n elements. Acta Inf. 145--158.
• 18: Glenn K. Manacher, Significant Improvements to the Hwang-Lin Merging Algorithm, Journal of the ACM (JACM), v.26 n.3, p.434-440, july 1979 [doi>10.1145/322139.322144]
• 19: Neumann, J. V., and Morgenstern, O. 1944. Theory of Games and Economic Behavior, 1st ed. Princeton University Press.
• 20: Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.233-242, January 06-08, 2002, San Francisco, California
• 21: Sion, M. 1958. On general minimax theorems. Pacific J. Math. 171--176.
• 22: Witten, I. H., Moffat, A., and Bell, T. C. 1994. Managing Gigabytes. VanNostrand Reinhold, New York.
• 23: Yao, A. C. 1977. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS), 222--227.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Theory

Keywords:
Adaptive analysis, alternation analysis, intersection, intersection of sorted arrays, randomized algorithm, redundancy analysis