Frequency Estimation with One-Sided Error

Piotr Indyk, Shyam Narayanan, David P. Woodruff

Type: Preprint

Publication Date: 2021-11-06

Citations: 0

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Frequency Estimation with One-Sided Error	2021	Piotr Indyk Shyam Narayanan David P. Woodruff
+ PDF Chat	Frequency Estimation with One-Sided Error	2022	Piotr Indyk Shyam Narayanan David P. Woodruff
+	Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributions	2018	Daniel Ting
+	(Learned) Frequency Estimation Algorithms under Zipfian Distribution	2019	Anders Aamand Piotr Indyk Ali Vakilian
+	Optimal Lower Bound for Itemset Frequency Indicator Sketches	2014	Eric Price
+	Streaming Algorithms from Precision Sampling	2010	Alexandr Andoni Robert Krauthgamer Krzysztof Onak
+	Streaming Algorithms from Precision Sampling	2010	Alexandr Andoni Robert Krauthgamer Krzysztof Onak
+	Simple and Efficient Cardinality Estimation in Data Streams.	2020	Seth Pettie Dingyu Wang Longhui Yin
+ PDF Chat	Learning-based Sketches for Frequency Estimation in Data Streams without Ground Truth	2024	Xinyu Yuan Qiao Yan Li Meng Zhenchun Wei Cuiying Feng
+	Count-min sketch with variable number of hash functions: an experimental study	2023	Éric Fusy Grégory Kucherov
+	Simple and Deterministic Matrix Sketching	2012	Edo Liberty
+ PDF Chat	Count-Min Sketch with Conservative Updates: Worst-Case Analysis	2024	Younes Ben Mazziane Othmane Marfoq
+	Maximum Coverage in Sublinear Space, Faster	2023	Stephen Jaud Anthony Wirth Farhana M. Choudhury
+	Approximating Large Frequency Moments with Pick-and-Drop Sampling	2012	Vladimir Braverman Rafail Ostrovsky
+ PDF Chat	Sampling Space-Saving Set Sketches	2024	Homin K. Lee Charles Masson
+	Composable Sketches for Functions of Frequencies: Beyond the Worst Case	2020	Edith Cohen Ofir Geri Rasmus Pagh
+	Composable Sketches for Functions of Frequencies: Beyond the Worst Case	2020	Edith Cohen Ofir Geri Rasmus Pagh
+ PDF Chat	Sharp Frequency Bounds for Sample-Based Queries	2019	Eric Bax John Donald
+	Succinct Sampling on Streams	2007	Vladimir Braverman Rafail Ostrovsky Carlo Zaniolo
+	Streaming Algorithms with Large Approximation Factors	2022	Yi Li Honghao Lin David P. Woodruff Yuheng Zhang

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (7)

Action	Title	Year	Authors
+	A Recurring Theorem on Determinants	1949	Olga Taussky
+	Randomness is Linear in Space	1996	Noam Nisan David Zuckerman
+	Quantum vs. classical communication and computation	1998	Harry Buhrman Richard Cleve Avi Wigderson
+	On deterministic sketching and streaming for sparse recovery and norm estimation	2013	Jelani Nelson Huy L. Nguyễn David P. Woodruff
+ PDF Chat	Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information	2006	Emmanuel J. Candès Justin Romberg Terence Tao
+	Lower bounds for the rank and location of the Eigenvalues of a matrix	1953	Ky Fan Alan J. Hoffman
+	Towards Optimal Moment Estimation in Streaming and Distributed Models	2019	Rajesh Jayaram David P. Woodruff