| Presentation | 2013-03-18 Reservoir sampling in stream using O(loglogn) space Naoto SONODA, Yukiko YAMAUCHI, Shuji KIJIMA, Masafumi YAMASHITA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This paper presents a simple algorithm for uniform sampling of elements in a stream; that is for reservoir sampling uses memory of O(loglogn)bits for an input stream with length n, without knowing an approximate value of n in advance. The idea of our algorithm is based on the Bernoulli sampling algorithm by Ogata et al (2011). Ogata's algorithm samples uniformly using memory of O(loglogn)bits, but the number of samples is not fixed. 0n the other hand, our algorithm outputs exactly c elements for samples of the stream. Using this algorithm, we present a randomized approximation algorithm for the difference of the frequency of elements between streams. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | reservoir sampling / space complexity / streaming algorithm / difference of frequency / randomize approximation algorithm |
| Paper # | COMP2012-53 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2013/3/11(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Reservoir sampling in stream using O(loglogn) space |
| Sub Title (in English) | |
| Keyword(1) | reservoir sampling |
| Keyword(2) | space complexity |
| Keyword(3) | streaming algorithm |
| Keyword(4) | difference of frequency |
| Keyword(5) | randomize approximation algorithm |
| 1st Author's Name | Naoto SONODA |
| 1st Author's Affiliation | Kyushu University() |
| 2nd Author's Name | Yukiko YAMAUCHI |
| 2nd Author's Affiliation | Kyushu University |
| 3rd Author's Name | Shuji KIJIMA |
| 3rd Author's Affiliation | Kyushu University |
| 4th Author's Name | Masafumi YAMASHITA |
| 4th Author's Affiliation | Kyushu University |
| Date | 2013-03-18 |
| Paper # | COMP2012-53 |
| Volume (vol) | vol.112 |
| Number (no) | 498 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |