{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T19:18:41Z","timestamp":1722885521097},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2014,9,10]],"date-time":"2014-09-10T00:00:00Z","timestamp":1410307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s00493-014-3035-1","type":"journal-article","created":{"date-parts":[[2014,9,11]],"date-time":"2014-09-11T03:43:56Z","timestamp":1410407036000},"page":"641-653","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the monotonicity of a data stream"],"prefix":"10.1007","volume":"35","author":[{"given":"Funda","family":"Ergun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hossein","family":"Jowhari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,10]]},"reference":[{"key":"3035_CR1","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1002\/rsa.20167","volume":"31","author":"N. Ailon","year":"2007","unstructured":"N. Ailon, B. Chazelle, S. Comandur and D. Liu: Estimating the distance to a monotone function, Random Struct. Algorithms 31 (2007), 371\u2013383.","journal-title":"Random Struct. Algorithms"},{"key":"3035_CR2","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1090\/S0273-0979-99-00796-X","volume":"36","author":"D. Aldous","year":"1999","unstructured":"D. Aldous and P. Diaconis: Longest increasing subsequences: from patience sorting to the baik-deift-johansson theorem, Bull. Amer. Math. Soc. 36 (1999), 413\u2013432.","journal-title":"Bull. Amer. Math. Soc."},{"key":"3035_CR3","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/j.ipl.2011.12.008","volume":"112","author":"A. Chakrabarti","year":"2012","unstructured":"A. Chakrabarti: A note on randomized streaming space bounds for the longest increasing subsequence problem, Inf. Process. Lett. 112 (2012), 261\u2013263.","journal-title":"Inf. Process. Lett."},{"key":"3035_CR4","doi-asserted-by":"crossref","first-page":"3463","DOI":"10.1137\/090770801","volume":"39","author":"A. G\u00e1l","year":"2010","unstructured":"A. G\u00e1l and P. Gopalan: Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence, SIAM J. Comput. 39 (2010), 3463\u20133479.","journal-title":"SIAM J. Comput."},{"key":"3035_CR5","first-page":"318","volume-title":"SODA","author":"P. Gopalan","year":"2007","unstructured":"P. Gopalan, T. S. Jayram, R. Krauthgamer and R. Kumar: Estimating the sortedness of a data stream, SODA (2007), 318\u2013327."},{"key":"3035_CR6","first-page":"760","volume":"1","author":"S. Guha","year":"2008","unstructured":"S. Guha and A. McGregor: Tight lower bounds for multi-pass stream computation via pass elimination, ICALP 1 (2008), 760\u2013772.","journal-title":"ICALP"},{"key":"3035_CR7","doi-asserted-by":"crossref","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"E. Kushilevitz and N. Nisan: Communication complexity, Cambridge University Press, 1997."},{"key":"3035_CR8","first-page":"362","volume-title":"ICDE","author":"X. Lin","year":"2004","unstructured":"X. Lin, H. Lu, J. Xu and J. X. Yu: Continuously maintaining quantile summaries of the most recent n elements over a data stream, ICDE (2004), 362\u2013373."},{"key":"3035_CR9","first-page":"263","volume-title":"COCOON","author":"D. Liben-Nowell","year":"2005","unstructured":"D. Liben-Nowell, E. Vee and An Zhu: Finding longest increasing and common subsequences in streaming data, COCOON (2005), 263\u2013272."},{"key":"3035_CR10","first-page":"458","volume-title":"FOCS","author":"M. Saks","year":"2010","unstructured":"M. Saks and C. Seshadhri: Estimating the longest increasing sequence in polylogarithmic time, FOCS (2010), 458\u2013467."},{"key":"3035_CR11","volume-title":"SODA","author":"M. Saks","year":"2013","unstructured":"M. Saks and C. Seshadhri: Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance, SODA (2013)."},{"key":"3035_CR12","first-page":"336","volume-title":"SODA","author":"X. Sun","year":"2007","unstructured":"X. Sun and D. P. Woodruff: The communication and streaming complexity of computing the longest common and increasing subsequences, SODA (2007), 336\u2013345."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-3035-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-014-3035-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-3035-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T01:32:51Z","timestamp":1559093571000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-014-3035-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,10]]},"references-count":12,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["3035"],"URL":"https:\/\/doi.org\/10.1007\/s00493-014-3035-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,10]]}}}