Estimating hybrid frequency moments of data streams
Sumit Ganguly (),
Mohit Bansal and
Shruti Dube
Additional contact information
Sumit Ganguly: Indian Institute of Technology, Kanpur
Mohit Bansal: Indian Institute of Technology, Kanpur
Shruti Dube: Indian Institute of Technology, Kanpur
Journal of Combinatorial Optimization, 2012, vol. 23, issue 3, No 5, 373-394
Abstract:
Abstract We consider the problem of estimating hybrid frequency moments of two dimensional data streams. In this model, data is viewed to be organized in a matrix form (A i,j )1≤i,j,≤n . The entries A i,j are updated coordinate-wise, in arbitrary order and possibly multiple times. The updates include both increments and decrements to the current value of A i,j . The hybrid frequency moment F p,q (A) is defined as $\sum_{j=1}^{n}(\sum_{i=1}^{n}{A_{i,j}}^{p})^{q}$ and is a generalization of the frequency moment of one-dimensional data streams. We present the first $\tilde{O}(1)$ space algorithm for the problem of estimating F p,q for p∈[0,2] and q∈[0,1] to within an approximation factor of 1±ε. The $\tilde{O}$ notation hides poly-logarithmic factors in the size of the stream m, the matrix size n and polynomial factors of ε −1. We also present the first $\tilde{O}(n^{1-1/q})$ space algorithm for estimating F p,q for p∈[0,2] and q∈(1,2].
Keywords: Algorithms; Randomized; Data streams; Frequency moments (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:
Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9339-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:23:y:2012:i:3:d:10.1007_s10878-010-9339-1
Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878
DOI: 10.1007/s10878-010-9339-1
Access Statistics for this article
Journal of Combinatorial Optimization is currently edited by Thai, My T.
More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().