The communication and streaming complexity of computing the longest common and increasing subsequences

ABSTRACT

We consider the communication complexity of finding the longest increasing subsequence (LIS) of a string shared between two parties. We prove tight bounds for the space complexity of randomized one-pass streaming algorithms for this problem. Our bounds are parameterized in terms of the LIS of the inputs. This resolves an open question in [19]. We also give the first bounds for approximating the LIS and its length.

Next, we consider the communication complexity of finding the longest common subsequece (LCS) of two strings held by different parties, as well as the problem of approximating its length. We improve the existing lower bounds for these problems, even in the most difficult case when both parties have a permutation of N symbols. Our results yield tight space bounds for multipass deterministic streaming algorithms. For randomized mutlipass algorithms, our bounds are tight up to a logarithmic factor.

REFERENCES

• 1: D. Aldous and P. Diaconis. Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc., 36, 1999, pp. 413--432.
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 3: S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. Journal of Molecular Biology, 215:403--410, 1990.
• 4: A. Apostolico and C. Guerra. The longest common subsequence problem revisited. Algorithmica, 2:315--336, 1987.
• 5: J. Baik, P. Deift, and K. Johansson. On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc. 12 (1999), no. 4, 1119--1178.
• 6: A. Banerjee and J. Ghosh. Clickstream clustering using weighted longest common subsequence. In: ICM Workshop on Web Mining, 2001.
• 7: Sergei Bespamyatnikh , Michael Segal, Enumerating longest increasing subsequences and patience sorting, Information Processing Letters, v.76 n.1-2, p.7-13, Nov. 2000 [doi>10.1016/S0020-0190(00)00124-1]
• 8: P. Deift. Integrable systems and combinatorial theory. Notices Amer. Math. Soc., 47, 2000, pp. 631--640.
• 9: A. L. Delcher, S. Kasif, R. D. Fleischmann, J. Peterson, O. White, and S. L. Salzberg. Alignment of whole genomes. Nucleic Acides Research, 27(11):2369--2376, 1999.
• 10: M. L. Fredman. On computing the length of the longest increasing subsequences.. In Discrete Mathematics 11, 1975, pp. 29--35.
• 11: Lesek Banachowski , Antoni Kreczmar , Wojciech Rytter, Analysis of Algorithms and Data and Structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 12: Parikshit Gopalan , T. S. Jayram , Robert Krauthgamer , Ravi Kumar, Estimating the sortedness of a data stream, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.318-327, January 07-09, 2007, New Orleans, Louisiana
• 13: M. R. Henzinger, P. Raghavan, and S. Rajagopalon. Computing on data streams. Technical Report 1998--011, Digital Equipment Corp., Systems Res. Center, 1998.
• 14: Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977 [doi>10.1145/322033.322044]
• 15: James W. Hunt , Thomas G. Szymanski, A fast algorithm for computing longest common subsequences, Communications of the ACM, v.20 n.5, p.350-353, May 1977 [doi>10.1145/359581.359603]
• 16: Bala Kalyanasundaram , Georg Schintger, The probabilistic communication complexity of set intersection, SIAM Journal on Discrete Mathematics, v.5 n.4, p.545-557, Nov. 1992 [doi>10.1137/0405044]
• 17: Ilan Kremer , Noam Nisan , Dana Ron, On randomized one-round communication complexity, Computational Complexity, v.8 n.1, p.21-49, June 1999 [doi>10.1007/s000370050018]
• 18: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 19: D. Liben-Nowell, E. Vee, and A. Zhu. Finding Longest Increasing and Common Subsequences in Streaming Data. In COCOON, 2005.
• 20: F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
• 21: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, v.57 n.1, p.37-49, Aug. 1998 [doi>10.1006/jcss.1998.1577]
• 22: S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 23: A. Razborov. On the distributional complexity of dis-jointness. JCSS 28, 1984.
• 24: D. Sankoff and J. Kruskal. Time warps, string edits, and macromolecules: The theory and practice of sequence comparison, Addison-Wesley, 1983.
• 25: C. Schensted. Longest increasing and decreasing subsequences. Canadian Journal of Mathematics, 13:179--191, 1961.
• 26: A. C.-C. Yao. Lower bounds by probabilistic arguments. In FOCS, 1983.
• 27: H. Zhang. Alignment of BLAST high-scoring segment pairts based on the longest increasing subsequence algorithm. Bioinformatics, 19(11):1391--1396, 2003.