{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T04:22:17Z","timestamp":1781151737836,"version":"3.54.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2006,3]]},"DOI":"10.1007\/s10878-006-7125-x","type":"journal-article","created":{"date-parts":[[2006,5,4]],"date-time":"2006-05-04T16:10:21Z","timestamp":1146759021000},"page":"155-175","source":"Crossref","is-referenced-by-count":19,"title":["Finding longest increasing and common subsequences in streaming data"],"prefix":"10.1007","volume":"11","author":[{"given":"David","family":"Liben-Nowell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erik","family":"Vee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"An","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"7125_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai M, Jayram TS, Kumar R, Sivakumar D (2002) Approximate counting of inversions in a data stream. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 370\u2013379","DOI":"10.1145\/509907.509964"},{"issue":"1","key":"7125_CR2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N Alon","year":"1999","unstructured":"Alon N, Matias Y, Szegedy M (1999) The space complexity of approximating the frequency moments, Journal of Computer and System Sciences 58(1):137\u2013147","journal-title":"Journal of Computer and System Sciences"},{"key":"7125_CR3","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ (1990) Basic local alignment search tool, Journal of Molecular Biology 215:403\u2013410","journal-title":"Journal of Molecular Biology"},{"key":"7125_CR4","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A Apostolico","year":"1987","unstructured":"Apostolico A, Guerra C (1987) The longest common subsequence problem revisited, Algorithmica 2:315\u2013336","journal-title":"Algorithmica"},{"key":"7125_CR5","unstructured":"Banerjee A, Ghosh J (2001) Clickstream clustering using weighted longest common subsequence. In: SIAM International Conference on Data Mining Workshop on Web Mining"},{"issue":"4","key":"7125_CR6","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z Bar-Yossef","year":"2004","unstructured":"Bar-Yossef Z, Jayram TS, Kumar R, Sivakumar D (2004) An information statistics approach to data stream and communication complexity, Journal of Computer and System Sciences 68(4):702\u2013732","journal-title":"Journal of Computer and System Sciences"},{"key":"7125_CR7","doi-asserted-by":"crossref","unstructured":"Bender MA, Cole R, Demaine ED, Farach-Colton M (2002) Scanning and traversing: Maintaining data for traversals in a memory hierarchy. In: Proceedings of the European Symposium on Algorithms (ESA) pp. 139\u2013151","DOI":"10.1007\/3-540-45749-6_16"},{"key":"7125_CR8","doi-asserted-by":"crossref","unstructured":"Bespamyatnikh S, Segal M (2000) Enumerating longest increasing subsequences and patience sorting, Information Processing Letters 76(1\u20132):7\u201311","DOI":"10.1016\/S0020-0190(00)00124-1"},{"issue":"1","key":"7125_CR9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","volume":"312","author":"M Charikar","year":"2004","unstructured":"Charikar M, Chen K, Farach-Colton M (2004) Finding frequent items in data streams, Theoretical Computer Science 312(1):3\u201315","journal-title":"Theoretical Computer Science"},{"key":"7125_CR10","unstructured":"Cormen T, Leiserson C, Rivest R, Stein C (2002) Introduction to Algorithms, 2nd edition. McGraw-Hill"},{"key":"7125_CR11","doi-asserted-by":"crossref","unstructured":"Cormode G, Muthukrishnan S (2006) What's new: Finding significant differences in network data streams. Transactions on Networking","DOI":"10.1109\/TNET.2005.860096"},{"issue":"11","key":"7125_CR12","doi-asserted-by":"crossref","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","volume":"27","author":"AL Delcher","year":"1999","unstructured":"Delcher AL, Kasif S, Fleischmann RD, Peterson J, White O, Salzberg SL (1999) Alignment of whole genomes, Nucleic Acids Research 27(11):2369\u20132376","journal-title":"Nucleic Acids Research"},{"key":"7125_CR13","doi-asserted-by":"crossref","unstructured":"Demaine ED, L\u00f3pez-Ortiz A, Ian Munro J (2002) Frequency estimation of internet packet streams with limited space. In: Proceedings of the European Symposium on Algorithms (ESA), pp. 348\u2013360","DOI":"10.1007\/3-540-45749-6_33"},{"key":"7125_CR14","unstructured":"Erd\u0151s P, Szekeres, G (1935) A combinatorial problem in geometry, Compositio Mathematica 463\u2013470"},{"key":"7125_CR15","unstructured":"Farach-Colton M, Ferragina P, Muthukrishnan S (1998) Overcoming the memory bottleneck in suffix tree construction. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 174\u2013185"},{"issue":"1","key":"7125_CR16","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/S0097539799361701","volume":"32","author":"J Feigenbaum","year":"2002","unstructured":"Feigenbaum J, Kannan S, Strauss M, Viswanathan M (2002) An approximate $L_1$-difference algorithm for massive data streams, SIAM Journal on Computing 32(1):131\u2013151","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"7125_CR17","first-page":"301","volume":"4","author":"JH Fong","year":"2001","unstructured":"Fong JH, Strauss M (2001) An approximate $L_p$-difference algorithm for massive data streams, Discrete Mathematics & Theoretical Computer Science 4(2):301\u2013322","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"7125_CR18","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"ML Fredman","year":"1975","unstructured":"Fredman ML (1975) On computing the length of longest increasing subsequences, Discrete Mathematics 11:29\u201335","journal-title":"Discrete Mathematics"},{"key":"7125_CR19","doi-asserted-by":"crossref","unstructured":"Gilbert A, Guha S, Indyk P, Kotidis Y, Muthukrishnan S, Strauss M (2002) Fast, small-space algorithms for approximate histogram maintenance. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 389\u2013398","DOI":"10.1145\/509907.509966"},{"key":"7125_CR20","doi-asserted-by":"crossref","unstructured":"Guha S, Koudas N, Shim K (2001) Data-streams and histograms. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 471\u2013475","DOI":"10.1145\/380752.380841"},{"key":"7125_CR21","doi-asserted-by":"crossref","unstructured":"Guha S, Mishra N, Motwani R, O'Callaghan L (2000) Clustering data streams. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 359\u2013366","DOI":"10.1109\/SFCS.2000.892124"},{"key":"7125_CR22","unstructured":"Henzinger MR, Raghavan P, Rajagopalan S (1998) Computing on data streams. Technical Report 1998-011, Digital Equipment Corporation, Systems Research Center"},{"key":"7125_CR23","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1145\/322033.322044","volume":"24","author":"DS Hirschberg","year":"1977","unstructured":"Hirschberg DS (1977) Algorithms for the longest common subsequence problem, Journal of the ACM 24:644\u2013675","journal-title":"Journal of the ACM"},{"key":"7125_CR24","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J Hunt","year":"1977","unstructured":"Hunt J, Szymanski T (1977) A fast algorithm for computing longest common subsequences, Communications of the ACM 20:350\u2013353","journal-title":"Communications of the ACM"},{"key":"7125_CR25","doi-asserted-by":"crossref","unstructured":"Indyk P (2000) Stable distributions, pseudorandom generators, embeddings, and data stream computations. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 189\u2013197","DOI":"10.1109\/SFCS.2000.892082"},{"issue":"5","key":"7125_CR26","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram B, Schnitger G (1992) The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics 5(5):545\u2013557","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"7125_CR27","doi-asserted-by":"crossref","unstructured":"Manku G, Rajagopalan S, Lindsay B (1998) Approximate medians and other quantiles in one pass and with limited memory. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 426\u2013435","DOI":"10.1145\/276305.276342"},{"key":"7125_CR28","unstructured":"Razborov A (1984) On the distributional complexity of disjointness. Journal of Computer and System Sciences 28(2)"},{"key":"7125_CR29","doi-asserted-by":"crossref","unstructured":"Saks ME, Sun X (2002) Space lower bounds for distance approximation in the data stream model. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 360\u2013369","DOI":"10.1145\/509907.509963"},{"key":"7125_CR30","unstructured":"Sankoff D, Kruskal J (1983) Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley"},{"key":"7125_CR31","doi-asserted-by":"crossref","first-page":"179","DOI":"10.4153\/CJM-1961-015-3","volume":"13","author":"C Schensted","year":"1961","unstructured":"Schensted C (1961) Longest increasing and decreasing subsequences, Canadian Journal of Mathematics 13:179\u2013191","journal-title":"Canadian Journal of Mathematics"},{"issue":"3","key":"7125_CR32","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P van Emde Boas","year":"1977","unstructured":"van Emde Boas P (1977) Preserving order in a forest in less than logarithmic time and linear space, Information Processing Letters 6(3):80\u201382","journal-title":"Information Processing Letters"},{"issue":"2","key":"7125_CR33","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard DE (August 1983) Log-logarithmic worst-case range queries are possible in space \u0398 N, Information Processing Letters 17(2):81\u201384","journal-title":"Information Processing Letters"},{"issue":"11","key":"7125_CR34","doi-asserted-by":"crossref","first-page":"1391","DOI":"10.1093\/bioinformatics\/btg168","volume":"19","author":"H Zhang","year":"2003","unstructured":"Zhang H (2003) Alignment of BLAST high-scoring segment pairs based on the longest increasing subsequence algorithm, Bioinformatics 19(11):1391\u20131396","journal-title":"Bioinformatics"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-7125-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-006-7125-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-7125-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:09Z","timestamp":1559261889000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-006-7125-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["7125"],"URL":"https:\/\/doi.org\/10.1007\/s10878-006-7125-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]}}}