{"entities":{"Q1736485":{"pageid":1747226,"ns":120,"title":"Item:Q1736485","lastrevid":56681760,"modified":"2026-03-18T18:47:15Z","type":"item","id":"Q1736485","labels":{"en":{"language":"en","value":"Approximating frequent items in asynchronous data stream over a sliding window"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042105"}},"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":"Q1736485$E1D6F2B4-7941-4CD0-8194-81959658DF12","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8a3f4741c2d6046c86561621cf92365eed43493b","datavalue":{"value":{"text":"Approximating frequent items in asynchronous data stream over a sliding window","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736485$47FB88C8-C726-439E-B004-D7CF4C871380","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8130a5d63907d17a4a57708030c394f0972ed57","datavalue":{"value":"1461.68260","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736485$74A6737E-243E-4041-A244-7FDF32483BA4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a42b76bf88be18fe61b5431863cec7c6b4c7c556","datavalue":{"value":{"entity-type":"item","numeric-id":328689,"id":"Q328689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$202E8DB7-FB41-4584-93E6-B17AC1CEB8AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0b81387644395860ccc90c101662f568f2b3241","datavalue":{"value":{"entity-type":"item","numeric-id":644793,"id":"Q644793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$8439FDBD-E568-4FA7-8890-DC4D183FA69B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c95eafb9df755b7c09c16036fc15b99dbab0b9b4","datavalue":{"value":{"entity-type":"item","numeric-id":243586,"id":"Q243586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$D9CF3334-840E-4EE6-80E0-FC7524F54EFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3074e2d17a24363b7134fcaedb1b82aa3a9c64b9","datavalue":{"value":{"entity-type":"item","numeric-id":235652,"id":"Q235652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$F087E486-864F-4FDD-B680-A1918E2FC955","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$FF76B6B7-AE06-4D42-8AB0-FA2A6DD1BF20","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736485$545FB573-3359-4A33-91C2-E48A7063B29B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e31da918b4e61156fcc41c2215da995bc0c6e501","datavalue":{"value":"Summary: In an asynchronous data stream, the data items may be out of order with respect to their original timestamps. This paper studies the space complexity required by a data structure to maintain such a data stream so that it can approximate the set of frequent items over a sliding time window with sufficient accuracy. Prior to our work, the best solution is given by \\textit{G. Cormode} [``Time-decaying aggregates in out-of-order streams'', in: Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, PODS'08. New York, NY. 89--98 (2008; \\url{doi:10.1145/1376916.1376930})], who gave an \\(O\\left(\\frac{1}{\\epsilon} \\log W \\log\\left(\\frac{\\epsilon B}{\\log W}\\right) \\min \\left\\{\\log W, \\frac{1}{\\epsilon} \\right\\} \\log | U|\\right)\\)-space data structure that can approximate the frequent items within an \\(\\epsilon\\) error bound, where \\(W\\) and \\(B\\) are parameters of the sliding window, and \\(U\\) is the set of all possible item names. We gave a more space-efficient data structure that only requires \\(O\\left(\\frac{1}{\\epsilon} \\log W \\log\\left(\\frac{\\epsilon B}{\\log W}\\right) \\log \\log W\\right)\\) space.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736485$9986D1B4-52FB-46A3-A22B-449B442FC03F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736485$8DA0ACBB-5499-4964-9075-A059BEAA63C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736485$ECC3233B-0592-418C-B58C-B114CD5239AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d5a866d412ef8af951814448fda0a03016cd3a5","datavalue":{"value":"68W27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736485$D81B3359-FC2A-4E83-BF93-2DE9BE5F0DA1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"021ee3eceaeebc4f79acef9fd401b7cdfbee6fa7","datavalue":{"value":"7042105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736485$16C19DCC-51EF-42CF-83DB-C5FA9A32C2F4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02b701abb7a094faca95ee2d6ceb72e83cafd795","datavalue":{"value":"asynchronous data streams","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736485$2A2597F9-26EF-428D-BC1D-AD0942CCAC06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9cd68a62c1b50cd12c386d54edd72fa51e41510","datavalue":{"value":"frequent items","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736485$677BDCAA-F28E-4A0C-9A8F-1E9AEB10A5F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f28a9c5fafaaade9fbae5a7e5269fe2b55fb7c25","datavalue":{"value":"sliding window","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736485$7A88A1ED-E89C-4A62-A7DD-2FBA8D3F7FA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fc59007b2b1960a263350309435ca1e06e896b5","datavalue":{"value":"space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736485$C50656FC-BDFE-4BEF-B213-40C133529988","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":"Q1736485$939447FB-7EC7-45E1-8303-A4F6FEAA2090","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2bd02984f3fbbb9157da3ea1421002edcdd041e8","datavalue":{"value":"https://doi.org/10.3390/a4030200","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736485$4D96AA82-DE53-4DD3-8A99-7704818D6FFD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"da28ab9b247671e0366c6e9b136acdaf8abadc95","datavalue":{"value":"W2027826195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736485$43DEC673-75A1-4F53-A443-292A19201FC6","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a2062f96fb197991e113fe7266156dbd424cc894","datavalue":{"value":"Q58062912","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736485$C86D8137-9214-48B5-825A-6F8B0D508F13","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb8a77962796fc1b4e047c5afed7964472f25ef7","datavalue":{"value":{"entity-type":"item","numeric-id":4411371,"id":"Q4411371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$A7E6BAA4-358C-42BD-B845-E0B9183EC9F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab55912bde4ac461b67aa1060ea23f38f2f798d7","datavalue":{"value":{"entity-type":"item","numeric-id":3425115,"id":"Q3425115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$806B7CA1-9C33-4231-B66C-6F779BB87EF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b2c7d50b98a127ab30c4ac542d9a5c463ad95d6","datavalue":{"value":{"entity-type":"item","numeric-id":3581550,"id":"Q3581550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$C707BFA8-8DC7-431B-986E-4C444CD86C88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aee5f91ff84f1d349f0ab186217649c96386f95","datavalue":{"value":{"entity-type":"item","numeric-id":4785622,"id":"Q4785622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$B5E06327-B300-4D45-9A81-1F5217966754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16003289b68322788cbc4b90d7cbc84fe7645ccb","datavalue":{"value":{"entity-type":"item","numeric-id":5177269,"id":"Q5177269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$8DDBDA8F-709D-4C41-B967-F53ECD606501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3ba0d7593dc8cf4ed0a9f07e480895a6ea3ca19","datavalue":{"value":{"entity-type":"item","numeric-id":3590955,"id":"Q3590955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$35F0B42F-2A83-417B-9E04-7D419BD0936B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84b97023f3ef85fc5d21ffa1d8c82b66bc626702","datavalue":{"value":{"entity-type":"item","numeric-id":3586182,"id":"Q3586182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$7267A1C2-A63D-4514-8764-DDA954A8DE4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"437b64f03d976224f4d81e6eff8cf6fb540c061c","datavalue":{"value":{"entity-type":"item","numeric-id":3558912,"id":"Q3558912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$791A2747-2A99-4C77-9DB7-959083A075CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92ef01f1ccd0d92179594af5b16646d7118dcda2","datavalue":{"value":{"entity-type":"item","numeric-id":1170891,"id":"Q1170891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$95FC72A8-2FD9-40AD-9C90-866FAC4301E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36cd12b030ccaee80449caca3704d0495eefd5b4","datavalue":{"value":{"entity-type":"item","numeric-id":3638028,"id":"Q3638028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$DF10B79F-6425-4305-A42F-8A2DB5535A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40b856b21fe15bd8c877027830154c5030a6cf0c","datavalue":{"value":{"entity-type":"item","numeric-id":991773,"id":"Q991773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$16439755-99CB-4421-A8AD-C92D9BC864AB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d141a0c093e8e904ac7ff3a77c088f711735a73a","datavalue":{"value":"10.3390/A4030200","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736485$6B1B8660-8627-4763-8069-D3E7C2CA2015","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e75d8bcfd98e735821d109e9ddd3a2913b85474","datavalue":{"value":{"entity-type":"item","numeric-id":3558912,"id":"Q3558912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d72854cf1857e4d0420db0a70120a86594ed71f3","datavalue":{"value":{"amount":"+0.9748085141181946","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":"Q1736485$397A97F2-FEC3-4B44-A86C-32BCA37F4D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de4129961006076a9ece4712d6139f1546f90dd2","datavalue":{"value":{"entity-type":"item","numeric-id":991773,"id":"Q991773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d06d4fdb3af2075f170fe07673bfa0be471e20e","datavalue":{"value":{"amount":"+0.7905281782150269","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":"Q1736485$39F83231-6CFE-458B-916E-9C095AF32B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"283e97ba1d0869acc6021065feedcdd577121ad4","datavalue":{"value":{"entity-type":"item","numeric-id":3610976,"id":"Q3610976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc61221c1fe4e61af943a51a9efa81a1b3d5e7ce","datavalue":{"value":{"amount":"+0.7902823090553284","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":"Q1736485$FB781847-04CD-4531-8D8F-5D85F0066562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bec2e7049818e1d2b7dc3d3d4df3050f004813e","datavalue":{"value":{"entity-type":"item","numeric-id":3590955,"id":"Q3590955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d91768541e978adb682de475ecce36faad230fa","datavalue":{"value":{"amount":"+0.7838795781135559","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":"Q1736485$C3E000E9-0998-48A2-9B00-2647C37CF3F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce372bf178fcd594e70c0b79ea5e300ff6735a73","datavalue":{"value":{"entity-type":"item","numeric-id":1954256,"id":"Q1954256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ba8a84eefb84b897d81229fb2f754e7a88a6d5a","datavalue":{"value":{"amount":"+0.774691104888916","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":"Q1736485$CD5BF1B3-1198-4301-87DC-1DB8E8104CED","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736485$DD114E65-11FE-4C20-A1C0-05C23B7C88B3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736485","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736485"}}}}}