Source author record

Sumit Ganguly

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Machine Learning

Catalog footprint

Research overview

5works

3topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Taylor Polynomial Estimator for Estimating Frequency Moments

We present a randomized algorithm for estimating the $p$ th moment $F_p$ of the frequency vector of a data stream in the general update (turnstile) model to within a multiplicative factor of $1 \pm ε$ , for $p > 2$ , with high constant confidence. For $0 < ε\le 1$ , the algorithm uses space $O( n^{1-2/p} ε^{-2} + n^{1-2/p} ε^{-4/p} \log (n))$ words. This improves over the current bound of $O(n^{1-2/p} ε^{-2-4/p} \log (n))$ words by Andoni et. al. in \cite{ako:arxiv10}. Our space upper bound matches the lower bound of Li and Woodruff \cite{liwood:random13} for $ε= (\log (n))^{-Ω(1)}$ and the lower bound of Andoni et. al. \cite{anpw:icalp13} for $ε= Ω(1)$ .

preprint2011arXiv

A Lower Bound for Estimating High Moments of a Data Stream

We show an improved lower bound for the Fp estimation problem in a data stream setting for p>2. A data stream is a sequence of items from the domain [n] with possible repetitions. The frequency vector x is an n-dimensional non-negative integer vector x such that x(i) is the number of occurrences of i in the sequence. Given an accuracy parameter Omega(n^{-1/p}) < ε< 1, the problem of estimating Fp is to estimate \norm{x}_p^p = \sum_{i \in [n]} \abs{x(i)}^p correctly to within a relative accuracy of 1\pm εwith high constant probability in an online fashion and using as little space as possible. The current space lower bound for this problem is Omega(n^{1-2/p} ε^{-2/p}+ n^{1-2/p}ε^{-4/p}/ \log^{O(1)}(n)+ (ε^{-2} + \log (n))). The first term in the lower bound expression was proved in \cite{B-YJKS:stoc02,cks:ccc03}, the second in \cite{wz:arxiv11} and the third in \cite{wood:soda04}. In this note, we show an Omega(p^2 n^{1-2/p} ε^{-2}/\log (n)) bits space bound, for Omega(pn^{-1/p}) \le ε\le 1/10.

preprint2011arXiv

Polynomial Estimators for High Frequency Moments

We present an algorithm for computing $F_p$ , the $p$ th moment of an $n$ -dimensional frequency vector of a data stream, for $2 < p < \log (n)$ , to within $1\pm ε$ factors, $ε\in [n^{-1/p},1]$ with high constant probability. Let $m$ be the number of stream records and $M$ be the largest magnitude of a stream update. The algorithm uses space in bits $O(p^2ε^{-2}n^{1-2/p}E(p,n) \log (n) \log (nmM)/\min(\log (n),ε^{4/p-2}))$ where, $E(p,n) = (1-2/p)^{-1}(1-n^{-4(1-2/p})$ . Here $E(p,n)$ is $O(1)$ for $p = 2+Ω(1)$ and $O(\log n)$ for $p = 2 + O(1/\log (n)$ . This improves upon the space required by current algorithms \cite{iw:stoc05,bgks:soda06,ako:arxiv10,bo:arxiv10} by a factor of at least $Ω(ε^{-4/p} \min(\log (n), ε^{4/p-2}))$ . The update time is $O(\log (n))$ . We use a new technique for designing estimators for functions of the form $ψ(\expect{X})$, where, $X$ is a random variable and $ψ$ is a smooth function, based on a low-degree Taylor polynomial expansion of $ψ(\expect{X})$ around an estimate of $\expect{X}$.

preprint2010arXiv

Estimating small moments of data stream in nearly optimal space-time

For each $p \in (0,2]$ , we present a randomized algorithm that returns an $ε$ -approximation of the $p$ th frequency moment of a data stream $F_p = \sum_{i = 1}^n \abs{f_i}^p$. The algorithm requires space $O(ε^{-2} \log (mM)(\log n))$ and processes each stream update using time $O((\log n) (\log ε^{-1}))$ . It is nearly optimal in terms of space (lower bound $O(ε^{-2} \log (mM))$ as well as time and is the first algorithm with these properties. The technique separates heavy hitters from the remaining items in the stream using an appropriate threshold and estimates the contribution of the heavy hitters and the light elements to $F_p$ separately. A key component is the design of an unbiased estimator for $\abs{f_i}^p$ whose data structure has low update time and low variance.

preprint2010arXiv

On Estimating the First Frequency Moment of Data Streams

Estimating the first moment of a data stream defined as $F_1 = \sum_{i \in \{1, 2, \ldots, n\}} \abs{f_i}$ to within $1 \pm ε$ -relative error with high probability is a basic and influential problem in data stream processing. A tight space bound of $O(ε^{-2} \log (mM))$ is known from the work of [Kane-Nelson-Woodruff-SODA10]. However, all known algorithms for this problem require per-update stream processing time of $Ω(ε^{-2})$ , with the only exception being the algorithm of [Ganguly-Cormode-RANDOM07] that requires per-update processing time of $O(\log^2(mM)(\log n))$ albeit with sub-optimal space $O(ε^{-3}\log^2(mM))$ . In this paper, we present an algorithm for estimating $F_1$ that achieves near-optimality in both space and update processing time. The space requirement is $O(ε^{-2}(\log n + (\log ε^{-1})\log(mM)))$ and the per-update processing time is $O( (\log n)\log (ε^{-1}))$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.