EconPapers    
Economics at your fingertips  
 

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

 
Page updated 2025-03-20
Handle: RePEc:spr:jcomop:v:23:y:2012:i:3:d:10.1007_s10878-010-9339-1