NDLI: The Value of Multiple Read/Write Streams for Approximating Frequency Moments

Please wait, while we are loading the content...

The Value of Multiple Read/Write Streams for Approximating Frequency Moments

Content Provider	ACM Digital Library
Author	Beame, Paul Huynh, Trinh
Copyright Year	2012
Abstract	We consider the read/write streams model, an extension of the standard data stream model in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by such an algorithm. The other key parameters are the number of streams the algorithm uses and the number of passes it makes on these streams. We consider how the addition of multiple streams impacts the ability of algorithms to approximate the frequency moments of the input stream. We show that any randomized read/write stream algorithm with a fixed number of streams and a sublogarithmic number of passes that produces a constant factor approximation of the $\textit{k}-th$ frequency moment $F_{k}$ of an input sequence of length of at most $\textit{N}$ from {1,..., $\textit{N}}$ requires space $\textit{Ω}(\textit{N}$ $^{1™4/k™Δ})$ for any $\textit{Δ} > 0.$ For comparison, it is known that with a single read-only one-pass data stream there is a randomized constant-factor approximation for $F_{k}$ using $Õ(N^{1™2/k})$ space, and that by sorting, which can be done deterministically in $\textit{O}(log$ $\textit{N})$ passes using 3 read/write streams, $F_{k}$ can be computed exactly. Therefore, although the ability to manipulate multiple read/write streams can add substantial power to the data stream model, with a sublogarithmic number of passes this does not significantly improve the ability to approximate higher frequency moments efficiently. We obtain our results by showing a new connection between the read/write streams model and the multiparty number-in-hand communication model.
Starting Page	1
Ending Page	22
Page Count	22
File Format	PDF
ISSN	19423454
e-ISSN	19423462
DOI	10.1145/2077336.2077339
Volume Number	3
Issue Number	2
Journal	ACM Transactions on Computation Theory (TOCT)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-01-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Data streams Communication complexity External-memory algorithms Frequency moments Read/write streams
Content Type	Text
Resource Type	Article
Subject	Computational Theory and Mathematics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

On the value of multiple read/write streams for approximating frequency moments.

The Value of Multiple Read/Write Streams for Approximating Frequency Moments

On the value of multiple read/write streams for approximating frequency moments (2008).

The value of multiple read/write streams for approximating frequency moments

The value of multiple read/write streams for approximating frequency moments

On Approximating Frequency Moments of Data Streams with Skewed Projections

On the value of multiple read/write streams for approximating frequency moments

Hierarchical Sampling from Sketches: Estimating Functions over Data Streams

The Value of Multiple Read/Write Streams for Approximating Frequency Moments

Similar Documents

On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

On the value of multiple read/write streams for approximating frequency moments.

The Value of Multiple Read/Write Streams for Approximating Frequency Moments

On the value of multiple read/write streams for approximating frequency moments (2008).

The value of multiple read/write streams for approximating frequency moments

The value of multiple read/write streams for approximating frequency moments

On Approximating Frequency Moments of Data Streams with Skewed Projections

On the value of multiple read/write streams for approximating frequency moments

Hierarchical Sampling from Sketches: Estimating Functions over Data Streams

The Value of Multiple Read/Write Streams for Approximating Frequency Moments