{"entities":{"Q1677498":{"pageid":1688239,"ns":120,"title":"Item:Q1677498","lastrevid":71887362,"modified":"2026-04-14T01:11:55Z","type":"item","id":"Q1677498","labels":{"en":{"language":"en","value":"On the monotonicity of a data stream"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6806059"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$7E212FFB-7DD8-44B7-940B-B146C4CF691A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2e20b7e180fb77098813d197a18784a96a9dcb2b","datavalue":{"value":{"text":"On the monotonicity of a data stream","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1677498$8316C625-6B35-496D-995F-7DADEA9A54C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f1b9c82c6133f431be419ab76e6d2d85ea8893c7","datavalue":{"value":"1389.68037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1677498$A4DDE7F9-E35A-484B-BB0E-BB2FD6AF4085","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a46ac62899778ffdb3c8ffb010f6e23879c0810e","datavalue":{"value":{"entity-type":"item","numeric-id":740972,"id":"Q740972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$8A98B946-F009-4468-B078-8D6E5DA98E1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"925b48d75982ab523639072c41a35e408132dd32","datavalue":{"value":{"entity-type":"item","numeric-id":1625144,"id":"Q1625144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$DCA1D7E4-D28E-4919-BED7-EB6EBAE99089","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$D986D769-79BE-42AA-98AB-DD3812E2C705","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c851dddc18687fa1af98fb94fafafdff8d946b43","datavalue":{"value":{"time":"+2017-11-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1677498$048D341D-9141-41CC-8511-FECDA88BDF75","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b165654e93f0707669aca3f56df9d02547bb0463","datavalue":{"value":"In this paper the authors consider problems related to the sortedness of a data stream. In the first part of this work the problem of estimating the distance to monotonicity is investigated. Then the problem of approximating the length of the longest increasing subsequence of the input stream is discussed. Through the analysis of a multi-party communication game, bounds are given using the deterministic streaming algorithms that approximate the length of the longest increasing subsequence.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1677498$B1EDC805-C61E-4E89-B3EA-EA120E416C46","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1677498$AE4FFCC3-256F-4BC2-B76D-486103C46FD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1677498$377B9411-26FB-4097-80A7-465CA64CE2D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1677498$1D229538-0479-4893-ADAB-45B772987294","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"92340e5eb483e8513cccad30f4f84039346a1e2c","datavalue":{"value":"6806059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1677498$E208C5A0-D752-43CE-9CB8-63E8A78F272A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afe493c1ace3fa52144c0315aaea9019dde435a3","datavalue":{"value":"monotonicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1677498$49CBA4F3-1C12-4041-91AC-8AFA48748ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e11fe2ee22b7b1505c47034e5f511b4050327e1","datavalue":{"value":"streaming algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1677498$6D9D6CCF-759E-41D5-9842-5D0400F7914C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6b12ff661f7a2aa084e4bb43ea3d85ff58492b6","datavalue":{"value":"inversions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1677498$2915D29F-252A-4C79-A534-D210228D9AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e940ac37279303889e6f8c6cd8870094f89fb3aa","datavalue":{"value":"probabilistic method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1677498$5CDEEF45-271C-4E31-AFFB-E3413AA134A1","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$23E3EEE7-697E-4CA8-991E-905415179B6A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8e8e74e20037dc3f89745d541c140b26e7aabb78","datavalue":{"value":"https://doi.org/10.1007/s00493-014-3035-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1677498$E25B5D16-DA11-4E98-B04B-94163E0D2389","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"de9113e4319701c68a568609cfca6530e921a703","datavalue":{"value":"W2090968858","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1677498$D9D25BE8-FE35-4B88-9EA7-1CF542F849F1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0e3b672d7742cf14899d7e0164d781c95536ede","datavalue":{"value":{"entity-type":"item","numeric-id":5433267,"id":"Q5433267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$36E65634-BAA3-4BCA-9537-E25C5054B5DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf15bfb2c53c34cc2fb2b04de41cb80fb5e138be","datavalue":{"value":{"entity-type":"item","numeric-id":4269106,"id":"Q4269106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$D363AFEF-0390-47E1-88B5-41E22813A188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dce46465877ee0e0a98093e8931eae6bfef5662a","datavalue":{"value":{"entity-type":"item","numeric-id":413292,"id":"Q413292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$0750FF95-9F7B-47B6-BF1C-1E202E8C5C14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40d6c22ddd3a867574d073125b9c000c5906a0ff","datavalue":{"value":{"entity-type":"item","numeric-id":5390602,"id":"Q5390602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$D4878B27-EF5D-49A2-AC44-9631536F195F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ace15000d6865e936332a89a179e584087acefee","datavalue":{"value":{"entity-type":"item","numeric-id":2934610,"id":"Q2934610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$33A77E45-38F7-4A7E-B7DF-F3E834D156E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5fc44e909036e1677192b5b39f98a2730907c50","datavalue":{"value":{"entity-type":"item","numeric-id":3521964,"id":"Q3521964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$152454F3-47C4-4845-8E53-6BAB98B5F5DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ec4896edc35f1e12505542682c8c6b6145a21f0","datavalue":{"value":{"entity-type":"item","numeric-id":4875692,"id":"Q4875692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$8E112A93-EF19-442A-9A55-BD28DF22C2A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15dd5c47e772dd28b406e5705ea74767362b6052","datavalue":{"value":{"entity-type":"item","numeric-id":5716944,"id":"Q5716944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$4856BD24-F8A6-4A2F-83A5-1A59BC2113A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70cecb70142fe9dad0d6a1b6ab5299e93ddefb59","datavalue":{"value":{"entity-type":"item","numeric-id":5737810,"id":"Q5737810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$7C7E6F91-3916-4370-B250-CF013ED80BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e00170786f259948cba48a48878984a582fe63a2","datavalue":{"value":{"entity-type":"item","numeric-id":5741831,"id":"Q5741831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$2452E695-A28E-448C-B74A-3FE2E2DEB140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"288225d4f15ccc201c9b9d31994d32f43562c0f3","datavalue":{"value":{"entity-type":"item","numeric-id":2934612,"id":"Q2934612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1677498$333E9A4C-7D05-4D69-BF20-865CAECF069A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a3739d4de6a367ad57c16b6374451d496cfd627","datavalue":{"value":"10.1007/S00493-014-3035-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1677498$B6D4BA30-9BB9-4A43-974D-AFB32BBD59FF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ea41e3b4bf84d2afd0750c29848b817fb0a7de6","datavalue":{"value":{"entity-type":"item","numeric-id":2934610,"id":"Q2934610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c32f9fd5ed9e9dfb21694a99980270e1915ec54a","datavalue":{"value":{"amount":"+0.9136775732040404","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1677498$F78508BA-FF4D-4C69-8B33-7B6941F7F2F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ec59fd117eaa81e7834892c1e9a3397f5b7c28a","datavalue":{"value":{"entity-type":"item","numeric-id":5363105,"id":"Q5363105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"276d62b577243da8f292e011f1f4fc5cc41088e7","datavalue":{"value":{"amount":"+0.8334412574768066","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1677498$888CF1FD-71B3-4B0A-8710-83530DFAB71B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e5e1b6bed724f8eaa295e3d9c556ffd35379715","datavalue":{"value":{"entity-type":"item","numeric-id":5741831,"id":"Q5741831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"849b075aab0278c62b3881d67244ca20425b1aa9","datavalue":{"value":{"amount":"+0.8074790239334106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1677498$8AA9C80B-AF4A-481E-8C1C-8B2E521378C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"123f7ada27eaf18d28a3d7564c7d3b61eeccdda8","datavalue":{"value":{"entity-type":"item","numeric-id":5390602,"id":"Q5390602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"342feac1e96545b07937b47aff6eb5496f96a35c","datavalue":{"value":{"amount":"+0.7928426861763","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1677498$01DE7A57-E288-4490-9654-121950C56EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68cd9e9a3edea67395a980bc28d8fe77139587da","datavalue":{"value":{"entity-type":"item","numeric-id":5716944,"id":"Q5716944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef6713e59bc821b3ea0bb7f9a5bc457648e85cbc","datavalue":{"value":{"amount":"+0.7920912504196167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1677498$43BE4E69-1E24-4A1F-A894-53C4C83A8D4B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the monotonicity of a data stream","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_monotonicity_of_a_data_stream"}}}}}