Name
Abstract | ||
|---|---|---|
Recent advances in flash media have made it an attractive alternative for data storage in a wide spectrum of computing devices, such as embedded sensors, mobile phones, PDA's, laptops, and even servers. However, flash media has many unique characteristics that make existing data management/analytics algorithms designed for magnetic disks perform poorly with flash storage. For example, while random (page) reads are as fast as sequential reads, random (page) writes and in-place data updates are orders of magnitude slower than sequential writes. In this paper, we consider an important fundamental problem that would seem to be particularly challenging for flash storage: efficiently maintaining a very large (100 MBs or more) random sample of a data stream (e.g., of sensor readings). First, we show that previous algorithms such as reservoir sampling and geometric file are not readily adapted to flash. Second, we propose B-FILE, an energy-efficient abstraction for flash media to store self-expiring items, and show how a B-FILE can be used to efficiently maintain a large sample in flash. Our solution is simple, has a small (RAM) memory footprint, and is designed to cope with flash constraints in order to reduce latency and energy consumption. Third, we provide techniques to maintain biased samples with a B-FILE and to query the large sample stored in a B-FILE for a subsample of an arbitrary size. Finally, we present an evaluation with flash media that shows our techniques are several orders of magnitude faster and more energy-efficient than (flash-friendly versions of) reservoir sampling and geometric file. A key finding of our study, of potential use to many flash algorithms beyond sampling, is that "semi-random" writes (as defined in the paper) on flash cards are over two orders of magnitude faster and more energy-efficient than random writes. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00778-009-0164-z | The VLDB Journal — The International Journal on Very Large Data Bases |
Keywords | DocType | Volume |
Flash storage,Random sample,Sensor networks,Semi-random writes | Journal | 19 |
Issue | ISSN | Citations |
1 | 1066-8888 | 51 |
PageRank | References | Authors |
2.50 | 25 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Suman Nath | 1 | 2907 | 164.98 |
| Phillip B. Gibbons | 2 | 6863 | 624.14 |