Campus Units
Electrical and Computer Engineering
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
6-1-2016
Journal or Book Title
IEEE Transactions on Knowledge and Data Engineering
Volume
28
Issue
6
First Page
1356
Last Page
1368
DOI
10.1109/TKDE.2016.2518679
Abstract
We present a simple, message-optimal algorithm for maintaining a random sample from a large data stream whose input elements are distributed across multiple sites that communicate via a central coordinator. At any point in time, the set of elements held by the coordinator represent a uniform random sample from the set of all the elements observed so far. When compared with prior work, our algorithms asymptotically improve the total number of messages sent in the system. We present a matching lower bound, showing that our protocol sends the optimal number of messages up to a constant factor with large probability. We also consider the important case when the distribution of elements across different sites is non-uniform, and show that for such inputs, our algorithm significantly outperforms prior solutions.
Rights
© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Copyright Owner
IEEE
Copyright Date
2016
Language
en
File Format
application/pdf
Recommended Citation
Chung, Yung-Yu; Tirthapura, Srikanta; and IBM Almaden Research Center, "A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream" (2016). Electrical and Computer Engineering Publications. 149.
https://lib.dr.iastate.edu/ece_pubs/149
Comments
This is a manuscript of an article published as Chung, Yung-Yu, Srikanta Tirthapura, and David P. Woodruff. "A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream." IEEE Transactions on Knowledge and Data Engineering 28, no. 6 (2016): 1356-1368. 10.1109/TKDE.2016.2518679. Posted with permission.