{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T11:30:33Z","timestamp":1655292633560},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,5]],"date-time":"2020-12-05T00:00:00Z","timestamp":1607126400000},"content-version":"vor","delay-in-days":309,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-15-1-2388"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"\n The distinct elements problem is one of the fundamental problems in streaming algorithms\u2014given a stream of integers in the range { 1,\u2026 ,\n n<\/jats:italic>\n }, we wish to provide a (1+\u03b5) approximation to the number of distinct elements in the input. After a long line of research an optimal solution for this problem with constant probability of success, using\n O<\/jats:italic>\n (1\/\u03b5\n 2<\/jats:sup>\n +lg\n n<\/jats:italic>\n ) bits of space, was given by Kane, Nelson, and Woodruff in 2010.\n <\/jats:p>\n \n The standard approach used to achieve low failure probability \u03b4 is to take the median of lg \u03b4\n \u22121<\/jats:sup>\n parallel repetitions of the original algorithm. We show that such a multiplicative space blow-up is unnecessary: We provide an optimal algorithm using\n O<\/jats:italic>\n (lg \u03b4\n \u22121<\/jats:sup>\n \/\u03b5\n 2<\/jats:sup>\n + lg\n n<\/jats:italic>\n ) bits of space\u2014matching known lower bounds for this problem. That is, the lg \u03b4\n \u22121<\/jats:sup>\n ; factor does not multiply the lg\n n<\/jats:italic>\n term. This settles completely the space complexity of the distinct elements problem with respect to all standard parameters.\n <\/jats:p>\n \n We consider also the\n strong tracking<\/jats:italic>\n (or\n continuous monitoring<\/jats:italic>\n ) variant of the distinct elements problem, where we want an algorithm that provides an approximation of the number of distinct elements seen so far, at all times of the stream. We show that this variant can be solved using\n O<\/jats:italic>\n (lg lg\n n<\/jats:italic>\n + lg \u03b4\n \u22121<\/jats:sup>\n \/\u03b5\n 2<\/jats:sup>\n + lg\n n<\/jats:italic>\n ) bits of space, which we show to be optimal.\n <\/jats:p>","DOI":"10.1145\/3309193","type":"journal-article","created":{"date-parts":[[2019,12,5]],"date-time":"2019-12-05T14:07:24Z","timestamp":1575554844000},"page":"1-28","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Streaming and Tracking Distinct Elements with High Probability"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-4372-9745","authenticated-orcid":false,"given":"Jaros\u0142aw","family":"B\u0142asiok","sequence":"first","affiliation":[{"name":"John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.31"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 36th SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS\u201917)","author":"Braverman Vladimir"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 35 ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201916)","author":"Braverman Vladimir"},{"key":"e_1_2_1_5_1","unstructured":"Jaros\u0142aw B\u0142asiok Jian Ding and Jelani Nelson. 2017. Continuous monitoring of ℓp norms in data streams in approximation randomization and combinatorial optimization. Algorithms and Techniques (APPROX\/RANDOM'17). DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.32 Jaros\u0142aw B\u0142asiok Jian Ding and Jelani Nelson. 2017. Continuous monitoring of ℓ p norms in data streams in approximation randomization and combinatorial optimization. Algorithms and Techniques (APPROX\/RANDOM'17). DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.32"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646978.711822"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365687"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","volume-title":"Loglog Counting of Large Cardinalities","author":"Durand Marianne","DOI":"10.1007\/978-3-540-39658-1_55"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2006.882836"},{"key":"e_1_2_1_10_1","volume-title":"Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In AofA: Analysis of Algorithms. Discrete Mathematics and Theoretical Computer Science, 137--156.","author":"Flajolet Philippe","year":"2007"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 24th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 76--82","author":"Flajolet Philippe","year":"1983"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","volume-title":"Inequalities: A Journey into Linear Analysis","author":"Garling D. J. H.","year":"2007","DOI":"10.1017\/CBO9780511755217"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672351"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201901)","author":"Phillip"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_2_1_18_1","volume-title":"Wai Ming Tai, and Ke Yi","author":"Huang Zengfeng","year":"2014"},{"key":"e_1_2_1_19_1","article-title":"Optimal bounds for johnson-lindenstrauss transforms and streaming problems with subconstant error","volume":"9","author":"Jayram T. S.","year":"2013","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS\u201910)","author":"Kane Daniel M.","year":"1807"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.73"},{"key":"e_1_2_1_22_1","volume-title":"A sharp tail bound for the expander random sampler. CoRR abs\/1703.10205","author":"Rao Shravas","year":"2017"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008772"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Woodruff David","year":"2004"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/280032.280035"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309193","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,5]],"date-time":"2022-01-05T02:43:28Z","timestamp":1641350608000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,31]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3309193"],"URL":"http:\/\/dx.doi.org\/10.1145\/3309193","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2020,1,31]]}}}