Kakimura, Naonori; Nitta, Riku Randomized counter-based algorithms for frequency estimation over data streams in \(O(\log \log N)\) space. (English) Zbl 07782072 Theor. Comput. Sci. 984, Article ID 114317, 7 p. (2024). MSC: 68Qxx PDFBibTeX XMLCite \textit{N. Kakimura} and \textit{R. Nitta}, Theor. Comput. Sci. 984, Article ID 114317, 7 p. (2024; Zbl 07782072) Full Text: DOI
Nelson, Jelani Forty years of frequent items. (English) Zbl 07821715 Beliaev, Dmitry (ed.) et al., International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6–14, 2022. Volume 6. Sections 12–14. Berlin: European Mathematical Society (EMS). 4872-4896 (2023). MSC: 68Q99 68W20 PDFBibTeX XMLCite \textit{J. Nelson}, in: International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6--14, 2022. Volume 6. Sections 12--14. Berlin: European Mathematical Society (EMS). 4872--4896 (2023; Zbl 07821715) Full Text: DOI OA License
Ben-Eliezer, Omri; Jayaram, Rajesh; Woodruff, David P.; Yogev, Eylon A framework for adversarially robust streaming algorithms. (English) Zbl 07500723 J. ACM 69, No. 2, Article No. 17, 33 p. (2022). MSC: 68-XX PDFBibTeX XMLCite \textit{O. Ben-Eliezer} et al., J. ACM 69, No. 2, Article No. 17, 33 p. (2022; Zbl 07500723) Full Text: DOI
Ghazi, Badih; Golowich, Noah; Kumar, Ravi; Pagh, Rasmus; Velingker, Ameya On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy. (English) Zbl 1477.68101 Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2021. 40th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, October 17–21, 2021. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 12698, 463-488 (2021). MSC: 68P27 68Q10 94A60 PDFBibTeX XMLCite \textit{B. Ghazi} et al., Lect. Notes Comput. Sci. 12698, 463--488 (2021; Zbl 1477.68101) Full Text: DOI
Pulimeno, Marco; Epicoco, Italo; Cafaro, Massimo Distributed mining of time-faded heavy hitters. (English) Zbl 1475.68292 Inf. Sci. 545, 633-662 (2021). MSC: 68T05 68W15 PDFBibTeX XMLCite \textit{M. Pulimeno} et al., Inf. Sci. 545, 633--662 (2021; Zbl 1475.68292) Full Text: DOI arXiv
Huang, Zengfeng; Lin, Xuemin; Zhang, Wenjie; Zhang, Ying Communication-efficient distributed covariance sketch, with application to distributed PCA. (English) Zbl 07370597 J. Mach. Learn. Res. 22, Paper No. 80, 38 p. (2021). MSC: 68T05 PDFBibTeX XMLCite \textit{Z. Huang} et al., J. Mach. Learn. Res. 22, Paper No. 80, 38 p. (2021; Zbl 07370597) Full Text: Link
Belazzougui, Djamal; Gagie, Travis; Munro, J. Ian; Navarro, Gonzalo; Nekrich, Yakov Range majorities and minorities in arrays. (English) Zbl 1516.68125 Algorithmica 83, No. 6, 1707-1733 (2021). MSC: 68W32 68P05 68P30 68W40 PDFBibTeX XMLCite \textit{D. Belazzougui} et al., Algorithmica 83, No. 6, 1707--1733 (2021; Zbl 1516.68125) Full Text: DOI arXiv
Gagie, Travis; He, Meng; Navarro, Gonzalo; Ochoa, Carlos Tree path majority data structures. (English) Zbl 1453.68062 Theor. Comput. Sci. 833, 107-119 (2020). MSC: 68P05 05C05 05C38 PDFBibTeX XMLCite \textit{T. Gagie} et al., Theor. Comput. Sci. 833, 107--119 (2020; Zbl 1453.68062) Full Text: DOI Link
Gagie, Travis; He, Meng; Navarro, Gonzalo Compressed dynamic range majority and minority data structures. (English) Zbl 1498.68090 Algorithmica 82, No. 7, 2063-2086 (2020). MSC: 68P05 PDFBibTeX XMLCite \textit{T. Gagie} et al., Algorithmica 82, No. 7, 2063--2086 (2020; Zbl 1498.68090) Full Text: DOI arXiv
Ergün, Funda; Grigorescu, Elena; Sadeqi Azer, Erfan; Zhou, Samson Periodicity in data streams with wildcards. (English) Zbl 1434.68691 Theory Comput. Syst. 64, No. 1, 177-197 (2020). MSC: 68W27 68W20 68W32 PDFBibTeX XMLCite \textit{F. Ergün} et al., Theory Comput. Syst. 64, No. 1, 177--197 (2020; Zbl 1434.68691) Full Text: DOI arXiv
Jin, Ce Simulating random walks on graphs in the streaming model. (English) Zbl 07559089 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 46, 15 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{C. Jin}, LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 46, 15 p. (2019; Zbl 07559089) Full Text: DOI arXiv
Boyle, Elette; Lavigne, Rio; Vaikuntanathan, Vinod Adversarially robust property-preserving hash functions. (English) Zbl 07559059 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 16, 20 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{E. Boyle} et al., LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 16, 20 p. (2019; Zbl 07559059) Full Text: DOI
Song, Chunyao; Liu, Xuanming; Ge, Tingjian; Ge, Yao Top-\(k\) frequent items and item frequency tracking over sliding windows of any size. (English) Zbl 1442.68215 Inf. Sci. 475, 100-120 (2019). MSC: 68T09 68P05 PDFBibTeX XMLCite \textit{C. Song} et al., Inf. Sci. 475, 100--120 (2019; Zbl 1442.68215) Full Text: DOI
Sánchez, César; Schneider, Gerardo; Ahrendt, Wolfgang; Bartocci, Ezio; Bianculli, Domenico; Colombo, Christian; Falcone, Yliès; Francalanza, Adrian; Krstić, Srđan; Lourenço, João M.; Nickovic, Dejan; Pace, Gordon J.; Rufino, Jose; Signoles, Julien; Traytel, Dmitriy; Weiss, Alexander A survey of challenges for runtime verification from advanced application domains (beyond software). (English) Zbl 1425.68268 Form. Methods Syst. Des. 54, No. 3, 279-335 (2019). MSC: 68Q60 PDFBibTeX XMLCite \textit{C. Sánchez} et al., Form. Methods Syst. Des. 54, No. 3, 279--335 (2019; Zbl 1425.68268) Full Text: DOI arXiv
Huang, Zengfeng; Yi, Ke; Zhang, Qin Randomized algorithms for tracking distributed count, frequencies, and ranks. (English) Zbl 1421.68192 Algorithmica 81, No. 6, 2222-2243 (2019); correction ibid. 82, No. 11, 3413 (2020). MSC: 68W20 68W40 PDFBibTeX XMLCite \textit{Z. Huang} et al., Algorithmica 81, No. 6, 2222--2243 (2019; Zbl 1421.68192) Full Text: DOI arXiv
Luo, Luo; Chen, Cheng; Zhang, Zhihua; Li, Wu-Jun; Zhang, Tong Robust frequent directions with application in online learning. (English) Zbl 1484.68341 J. Mach. Learn. Res. 20, Paper No. 45, 41 p. (2019). MSC: 68W27 65F55 65K05 68T05 68T20 90C25 90C59 PDFBibTeX XMLCite \textit{L. Luo} et al., J. Mach. Learn. Res. 20, Paper No. 45, 41 p. (2019; Zbl 1484.68341) Full Text: arXiv Link
Gagie, Travis; He, Meng; Navarro, Gonzalo Tree path majority data structures. (English) Zbl 07561422 Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 68, 12 p. (2018). MSC: 68Wxx PDFBibTeX XMLCite \textit{T. Gagie} et al., LIPIcs -- Leibniz Int. Proc. Inform. 123, Article 68, 12 p. (2018; Zbl 07561422) Full Text: DOI arXiv
Epicoco, Italo; Cafaro, Massimo; Pulimeno, Marco Fast and accurate mining of correlated heavy hitters. (English) Zbl 1411.68098 Data Min. Knowl. Discov. 32, No. 1, 162-186 (2018). MSC: 68T05 62-07 68W27 PDFBibTeX XMLCite \textit{I. Epicoco} et al., Data Min. Knowl. Discov. 32, No. 1, 162--186 (2018; Zbl 1411.68098) Full Text: DOI arXiv
Jayapaul, Varukumar; Ian Munro, J.; Raman, Venkatesh; Satti, Srinivas Rao Finding modes with equality comparisons. (English) Zbl 1382.68057 Theor. Comput. Sci. 704, 28-41 (2017). MSC: 68P10 68R05 68W40 PDFBibTeX XMLCite \textit{V. Jayapaul} et al., Theor. Comput. Sci. 704, 28--41 (2017; Zbl 1382.68057) Full Text: DOI
Lahiri, Bibudh; Mukherjee, Arko Provo; Tirthapura, Srikanta Identifying correlated heavy-hitters in a two-dimensional data stream. (English) Zbl 1411.68112 Data Min. Knowl. Discov. 30, No. 4, 797-818 (2016). MSC: 68T05 62-07 PDFBibTeX XMLCite \textit{B. Lahiri} et al., Data Min. Knowl. Discov. 30, No. 4, 797--818 (2016; Zbl 1411.68112) Full Text: DOI arXiv
Cafaro, Massimo; Pulimeno, Marco; Tempesta, Piergiulio A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution. (English) Zbl 1390.68517 Inf. Sci. 329, 1-19 (2016). MSC: 68T05 68W10 PDFBibTeX XMLCite \textit{M. Cafaro} et al., Inf. Sci. 329, 1--19 (2016; Zbl 1390.68517) Full Text: DOI arXiv Link
Ghashami, Mina; Liberty, Edo; Phillips, Jeff M.; Woodruff, David P. Frequent directions: simple and deterministic matrix sketching. (English) Zbl 1348.65075 SIAM J. Comput. 45, No. 5, 1762-1792 (2016). MSC: 65F30 65F20 PDFBibTeX XMLCite \textit{M. Ghashami} et al., SIAM J. Comput. 45, No. 5, 1762--1792 (2016; Zbl 1348.65075) Full Text: DOI arXiv
Elmasry, Amr; He, Meng; Munro, J. Ian; Nicholson, Patrick K. Dynamic range majority data structures. (English) Zbl 1350.68068 Theor. Comput. Sci. 647, 59-73 (2016). MSC: 68P05 68U05 PDFBibTeX XMLCite \textit{A. Elmasry} et al., Theor. Comput. Sci. 647, 59--73 (2016; Zbl 1350.68068) Full Text: DOI
Jayapaul, Varunkumar; Raman, Venkatesh; Satti, Srinivasa Rao Finding mode using equality comparisons. (English) Zbl 1475.68216 Kaykobad, Mohammad (ed.) et al., WALCOM: algorithms and computation. 10th international workshop, WALCOM 2016, Kathmandu, Nepal, March 29–31, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9627, 351-360 (2016). MSC: 68R05 68W40 PDFBibTeX XMLCite \textit{V. Jayapaul} et al., Lect. Notes Comput. Sci. 9627, 351--360 (2016; Zbl 1475.68216) Full Text: DOI
McGregor, Andrew; Pavan, A.; Tirthapura, Srikanta; Woodruff, David P. Space-efficient estimation of statistics over sub-sampled streams. (English) Zbl 1351.62026 Algorithmica 74, No. 2, 787-811 (2016). MSC: 62D05 PDFBibTeX XMLCite \textit{A. McGregor} et al., Algorithmica 74, No. 2, 787--811 (2016; Zbl 1351.62026) Full Text: DOI Link
Phillips, Jeff M.; Verbin, Elad; Zhang, Qin Lower bounds for number-in-hand multiparty communication complexity, made easy. (English) Zbl 1336.68105 SIAM J. Comput. 45, No. 1, 174-196 (2016). MSC: 68Q17 68M12 68Q05 68Q10 PDFBibTeX XMLCite \textit{J. M. Phillips} et al., SIAM J. Comput. 45, No. 1, 174--196 (2016; Zbl 1336.68105) Full Text: DOI arXiv
Giannakopoulos, Yiannis; Koutsoupias, Elias Competitive analysis of maintaining frequent items of a stream. (English) Zbl 1303.68159 Theor. Comput. Sci. 562, 23-32 (2015). MSC: 68W27 PDFBibTeX XMLCite \textit{Y. Giannakopoulos} and \textit{E. Koutsoupias}, Theor. Comput. Sci. 562, 23--32 (2015; Zbl 1303.68159) Full Text: DOI
Lahiri, Bibudh; Tirthapura, Srikanta; Chandrashekar, Jaideep Space-efficient tracking of persistent items in a massive data stream. (English) Zbl 07260383 Stat. Anal. Data Min. 7, No. 1, 70-92 (2014). MSC: 62-XX 68-XX PDFBibTeX XMLCite \textit{B. Lahiri} et al., Stat. Anal. Data Min. 7, No. 1, 70--92 (2014; Zbl 07260383) Full Text: DOI
Chen, Ling; Mei, Qingling Mining frequent items in data stream using time fading model. (English) Zbl 1320.68133 Inf. Sci. 257, 54-69 (2014). MSC: 68T05 68T10 PDFBibTeX XMLCite \textit{L. Chen} and \textit{Q. Mei}, Inf. Sci. 257, 54--69 (2014; Zbl 1320.68133) Full Text: DOI
Yi, Ke; Wang, Lu; Wei, Zhewei Indexing for summary queries, theory and practice. (English) Zbl 1321.68259 ACM Trans. Database Syst. 39, No. 1, Article No. 2, 39 p. (2014). MSC: 68P20 68P15 PDFBibTeX XMLCite \textit{K. Yi} et al., ACM Trans. Database Syst. 39, No. 1, Article No. 2, 39 p. (2014; Zbl 1321.68259) Full Text: DOI
Cormode, Graham Summary data structures for massive data. (English) Zbl 1387.68082 Bonizzoni, Paola (ed.) et al., The nature of computation. Logic, algorithms, applications. 9th conference on computability in Europe, CiE 2013, Milan, Italy, July 1–5, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-39052-4/pbk). Lecture Notes in Computer Science 7921, 78-86 (2013). MSC: 68P05 PDFBibTeX XMLCite \textit{G. Cormode}, Lect. Notes Comput. Sci. 7921, 78--86 (2013; Zbl 1387.68082) Full Text: DOI
Phillips, Jeff M.; Verbin, Elad; Zhang, Qin Lower bounds for number-in-hand multiparty communication complexity, made easy. (English) Zbl 1422.68090 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 486-501 (2012). MSC: 68Q17 68M12 68Q05 68Q10 PDFBibTeX XMLCite \textit{J. M. Phillips} et al., in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 486--501 (2012; Zbl 1422.68090) Full Text: Link
Çapuni, Ilir; Gács, Peter A Turing machine resisting isolated bursts of faults. (English) Zbl 1298.68089 Bieliková, Mária (ed.) et al., SOFSEM 2012: Theory and practice of computer science. 38th conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 21–27, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-27659-0/pbk). Lecture Notes in Computer Science 7147, 165-176 (2012). MSC: 68Q05 PDFBibTeX XMLCite \textit{I. Çapuni} and \textit{P. Gács}, Lect. Notes Comput. Sci. 7147, 165--176 (2012; Zbl 1298.68089) Full Text: DOI arXiv
Ting, Hing-Fung; Lee, Lap-Kei; Chan, Ho-Leung; Lam, Tak-Wah Approximating frequent items in asynchronous data stream over a sliding window. (English) Zbl 1461.68260 Algorithms (Basel) 4, No. 3, 200-222 (2011). MSC: 68W25 68P05 68W27 PDFBibTeX XMLCite \textit{H.-F. Ting} et al., Algorithms (Basel) 4, No. 3, 200--222 (2011; Zbl 1461.68260) Full Text: DOI
Durocher, Stephane; He, Meng; Munro, J. Ian; Nicholson, Patrick K.; Skala, Matthew Range majority in constant time and linear space. (English) Zbl 1332.68032 Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 244-255 (2011). MSC: 68P05 PDFBibTeX XMLCite \textit{S. Durocher} et al., Lect. Notes Comput. Sci. 6755, 244--255 (2011; Zbl 1332.68032) Full Text: DOI
Lahiri, Bibudh; Tirthapura, Srikanta Identifying frequent items in a network using gossip. (English) Zbl 1233.68065 J. Parallel Distrib. Comput. 70, No. 12, 1241-1253 (2010). MSC: 68M14 68P05 PDFBibTeX XMLCite \textit{B. Lahiri} and \textit{S. Tirthapura}, J. Parallel Distrib. Comput. 70, No. 12, 1241--1253 (2010; Zbl 1233.68065) Full Text: DOI
Hung, Regant Y. S.; Lee, Lap-Kei; Ting, H. F. Finding frequent items over sliding windows with constant update time. (English) Zbl 1209.68661 Inf. Process. Lett. 110, No. 7, 257-260 (2010). MSC: 68W27 68W25 PDFBibTeX XMLCite \textit{R. Y. S. Hung} et al., Inf. Process. Lett. 110, No. 7, 257--260 (2010; Zbl 1209.68661) Full Text: DOI
Feigenblat, Guy; Itzhaki, Ofra; Porat, Ely The frequent items problem, under polynomial decay, in the streaming model. (English) Zbl 1196.68348 Theor. Comput. Sci. 411, No. 34-36, 3048-3054 (2010). MSC: 68W32 PDFBibTeX XMLCite \textit{G. Feigenblat} et al., Theor. Comput. Sci. 411, No. 34--36, 3048--3054 (2010; Zbl 1196.68348) Full Text: DOI
Nie, Guoliang; Lu, Zhengding Dynamically computing approximate frequency counts in sliding window over data stream. (English) Zbl 1097.68150 Wuhan Univ. J. Nat. Sci. 11, No. 1, 283-288 (2006). MSC: 68W25 PDFBibTeX XMLCite \textit{G. Nie} and \textit{Z. Lu}, Wuhan Univ. J. Nat. Sci. 11, No. 1, 283--288 (2006; Zbl 1097.68150) Full Text: DOI
Guibas, Leonidas J.; Overmars, Mark H.; Robert, Jean-Marc The exact fitting problem in higher dimensions. (English) Zbl 0851.68112 Comput. Geom. 6, No. 4, 215-230 (1996). MSC: 68U05 PDFBibTeX XMLCite \textit{L. J. Guibas} et al., Comput. Geom. 6, No. 4, 215--230 (1996; Zbl 0851.68112) Full Text: DOI Link
Fribourg, Laurent; Peixoto, Marcos Veloso Bottom-up evaluation of Datalog programs with arithmetic constraints. (English) Zbl 1433.68083 Bundy, Alan (ed.), Automated deduction – CADE-12. 12th international conference, Nancy, France, June 26 – July 1, 1994. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 814, 311-325 (1994). MSC: 68N17 68P15 PDFBibTeX XMLCite \textit{L. Fribourg} and \textit{M. V. Peixoto}, Lect. Notes Comput. Sci. 814, 311--325 (1994; Zbl 1433.68083) Full Text: DOI
Arge, Lars; Knudsen, Mikael; Larsen, Kirsten A general lower bound on the I/O-complexity of comparison-based algorithms. (English) Zbl 1504.68076 Dehne, Frank (ed.) et al., Algorithms and data structures. 3rd workshop, WADS ’93. Montréal, Canada 11–13, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 709, 83-94 (1993). MSC: 68Q17 68W05 PDFBibTeX XMLCite \textit{L. Arge} et al., Lect. Notes Comput. Sci. 709, 83--94 (1993; Zbl 1504.68076) Full Text: DOI
Alonso, Laurent; Reingold, Edward M.; Schott, René Determining the majority. (English) Zbl 0780.68051 Inf. Process. Lett. 47, No. 5, 253-255 (1993). MSC: 68Q25 68R05 PDFBibTeX XMLCite \textit{L. Alonso} et al., Inf. Process. Lett. 47, No. 5, 253--255 (1993; Zbl 0780.68051) Full Text: DOI
Saks, Michael E.; Werman, Michael On computing majority by comparisons. (English) Zbl 0739.05006 Combinatorica 11, No. 4, 383-387 (1991). Reviewer: H.Werner MSC: 05A18 68Q25 68R05 PDFBibTeX XMLCite \textit{M. E. Saks} and \textit{M. Werman}, Combinatorica 11, No. 4, 383--387 (1991; Zbl 0739.05006) Full Text: DOI
Backhouse, Roland; Chisholm, Paul; Malcolm, Grant; Saaman, Erik Do-it-yourself type theory. (English) Zbl 0697.68020 Formal Aspects Comput. 1, No. 1, 19-84 (1989). MSC: 68Q60 68P05 03F35 PDFBibTeX XMLCite \textit{R. Backhouse} et al., Formal Asp. Comput. 1, No. 1, 19--84 (1989; Zbl 0697.68020) Full Text: DOI