{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T20:10:30Z","timestamp":1741983030417,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642255908"},{"type":"electronic","value":"9783642255915"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-25591-5_58","type":"book-chapter","created":{"date-parts":[[2011,12,3]],"date-time":"2011-12-03T00:32:34Z","timestamp":1322872354000},"page":"564-573","source":"Crossref","is-referenced-by-count":1,"title":["Edit Distance to Monotonicity in Sliding Windows"],"prefix":"10.1007","author":[{"given":"Ho-Leung","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lap-Kei","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiangwei","family":"Pan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hing-Fung","family":"Ting","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"58_CR1","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"157","author":"F. Ablayev","year":"1996","unstructured":"Ablayev, F.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science\u00a0157(2), 139\u2013159 (1996)","journal-title":"Theoretical Computer Science"},{"key":"58_CR2","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, pp. 370\u2013379 (2002)","DOI":"10.1145\/509961.509964"},{"key":"58_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Moshe, S., Kanza, Y., Fischer, E., Matsliah, A., Fischer, M., Staelin, C.: Detecting and exploiting near-sortedness for efficient relational query evaluation. In: Proc. ICDT, pp. 256\u2013267 (2011)","DOI":"10.1145\/1938551.1938584"},{"issue":"1-7","key":"58_CR4","first-page":"107","volume":"30","author":"S. Brin","year":"1998","unstructured":"Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Computer Networks\u00a030(1-7), 107\u2013117 (1998)","journal-title":"Computer Networks"},{"key":"58_CR5","unstructured":"Chakrabarti, A.: A note on randomized streaming space bounds for the longest increasing subsequence problem. In: ECCC, p. 100 (2010)"},{"key":"58_CR6","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., Tirthapura, S.: Time-decaying aggregates in out-of-order streams. In: Proc. PODS, pp. 89\u201398 (2008)","DOI":"10.1145\/1376916.1376930"},{"key":"58_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/3-540-48224-5_40","volume-title":"Automata, Languages and Programming","author":"G. Cormode","year":"2001","unstructured":"Cormode, G., Muthukrishnan, S.M., \u015eahinalp, S.C.: Permutation Editing and Matching via Embeddings. In: Yu, Y., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 481\u2013492. Springer, Heidelberg (2001)"},{"key":"58_CR8","unstructured":"Ergun, F., Jowhari, H.: On distance to monotonicity and longest increasing subsequence of a data stream. In: Proc. SODA, pp. 730\u2013736 (2008)"},{"key":"58_CR9","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1145\/146370.146381","volume":"24","author":"V. Estivill-Castro","year":"1992","unstructured":"Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Computing Surveys\u00a024, 441\u2013476 (1992)","journal-title":"ACM Computing Surveys"},{"key":"58_CR10","doi-asserted-by":"crossref","unstructured":"G\u00e1l, A., Gopalan, P.: Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence. In: Proc. FOCS, pp. 294\u2013304 (2007)","DOI":"10.1109\/FOCS.2007.4389501"},{"key":"58_CR11","unstructured":"Gopalan, P., Jayram, T.S., Krauthgamer, R., Kumar, R.: Estimating the sortedness of a data stream. In: Proc. SODA, pp. 318\u2013327 (2007)"},{"key":"58_CR12","unstructured":"Gopalan, P., Krauthgamer, R., Thathachar, J.: Method of obtaining data samples from a data stream and of estimating the sortednesss of the data stream based on the samples. United States Patent 7,797,326 B2 (2010)"},{"key":"58_CR13","doi-asserted-by":"crossref","unstructured":"Lin, X., Lu, H., Xu, J., Yu, J.X.: Continuously maintaining quantile summaries of the most recent n elements over a data stream. In: Proc. ICDE, pp. 362\u2013374 (2004)","DOI":"10.1109\/ICDE.2004.1320011"},{"key":"58_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1007\/978-3-642-03685-9_42","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"T.S. Jayram","year":"2009","unstructured":"Jayram, T.S.: Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 562\u2013573. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25591-5_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T19:31:59Z","timestamp":1741980719000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25591-5_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642255908","9783642255915"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25591-5_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}