BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Sumit Ganguly

Sumit Ganguly appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational ComplexityMachine Learning

Catalog footprint

What is connected

5works
3topics
1close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

5 published item(s)

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)$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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}$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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}))$.

0 citations0 reviewsNo code linkedOpen access