{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:23Z","timestamp":1759638443177},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_28","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T09:34:13Z","timestamp":1127813653000},"page":"263-272","source":"Crossref","is-referenced-by-count":2,"title":["Finding Longest Increasing and Common Subsequences in Streaming Data"],"prefix":"10.1007","author":[{"given":"David","family":"Liben-Nowell","sequence":"first","affiliation":[]},{"given":"Erik","family":"Vee","sequence":"additional","affiliation":[]},{"given":"An","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","unstructured":"Henzinger, M.R., Raghavan, P., Rajagopalon, S.: Computing on data streams. Technical Report 1998-011, Digital Equipment Corp., Systems Res. Center (1998)"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: What\u2019s new: Finding significant differences in network data streams. In: Proc. INFOCOM (2004)","DOI":"10.1109\/INFCOM.2004.1354567"},{"key":"28_CR3","unstructured":"Banerjee, A., Ghosh, J.: Clickstream clustering using weighted longest common subsequence. In: Workshop, I.C.M. (ed.) ICM Workshop on Web Mining (2001)"},{"key":"28_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/3-540-45465-9_59","volume-title":"Automata, Languages and Programming","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, p. 693. Springer, Heidelberg (2002)"},{"key":"28_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/3-540-45749-6_33","volume-title":"Algorithms - ESA 2002","author":"E.D. Demaine","year":"2002","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Frequency estimation of Internet packet streams with limited space. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 348\u2013360. Springer, Heidelberg (2002)"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"Guha, S., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams. In: Proc. FOCS, pp. 359\u2013366 (2000)","DOI":"10.1109\/SFCS.2000.892124"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Manku, G., Rajagopalan, S., Lindsay, B.: Approximate medians and other quantiles in one pass and with limited memory. In: Proc. SIGMOD (1998)","DOI":"10.1145\/276304.276342"},{"key":"28_CR8","first-page":"137","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. JCSS\u00a058, 137\u2013147 (1999)","journal-title":"JCSS"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. In: Proc. FOCS (2002)","DOI":"10.1109\/SFCS.2002.1181944"},{"key":"28_CR10","unstructured":"Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.: An approximate L1- difference algorithm for massive data streams. In: Proc. FOCS (1999)"},{"key":"28_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-46541-3_16","volume-title":"STACS 2000","author":"J. Fong","year":"2000","unstructured":"Fong, J., Strauss, M.: An approximate L-difference algorithm for massive data streams. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, p. 193. Springer, Heidelberg (2000)"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings, and data stream computations. In: Proc. FOCS (2000)","DOI":"10.1109\/SFCS.2000.892082"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"Saks, M., Sun, X.: Space lower bounds for distance approximation in the data stream model. In: Proc. STOC (2002)","DOI":"10.1145\/509907.509963"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Jayram, T.S., Kumar, R., Sivakumar, D.: Approximate counting of inversions in a data stream. In: Proc. STOC (2002)","DOI":"10.1145\/509907.509964"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., Strauss, M.: Fast, small-space algorithms for approximate histogram maintenance. In: STOC (2002)","DOI":"10.1145\/509907.509966"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"Guha, S., Koudas, N., Shim, K.: Data-streams and histograms. In: STOC (2001)","DOI":"10.1145\/380752.380841"},{"key":"28_CR17","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"M.L. Fredman","year":"1975","unstructured":"Fredman, M.L.: On computing the length of longest increasing subsequences. Discrete Mathematics\u00a011, 29\u201335 (1975)","journal-title":"Discrete Mathematics"},{"key":"28_CR18","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. IPL\u00a06, 80\u201382 (1977)","journal-title":"IPL"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \u0398(N). IPL\u00a017, 81\u201384 (1983)","journal-title":"IPL"},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/S0020-0190(00)00124-1","volume":"76","author":"S. Bespamyatnikh","year":"2000","unstructured":"Bespamyatnikh, S., Segal, M.: Enumerating longest increasing subsequences and patience sorting. IPL\u00a076, 7\u201311 (2000)","journal-title":"IPL"},{"key":"28_CR21","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2002","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. McGraw-Hill, New York (2002)"},{"key":"28_CR22","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Disc. Math\u00a05, 545\u2013557 (1992)","journal-title":"SIAM J. Disc. Math"},{"key":"28_CR23","unstructured":"Razborov, A.: On the distributional complexity of disjointness. JCSS\u00a028 (1984)"},{"key":"28_CR24","unstructured":"Erd\u00f6s, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica, 463\u2013470 (1935)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,25]],"date-time":"2019-03-25T22:54:07Z","timestamp":1553554447000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11533719_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}