Skip to Main content Skip to Navigation

PBFilter: Indexing Flash-Resident Data through Partitioned Summaries

Shaoyi Yin 1 Philippe Pucheral 1 Xiaofeng Meng 1 
1 SMIS - Secured and Mobile Information Systems
PRISM - Parallélisme, Réseaux, Systèmes, Modélisation, UVSQ - Université de Versailles Saint-Quentin-en-Yvelines, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8144
Abstract : NAND Flash has become the most popular persistent data storage medium for mobile and embedded devices and is even being considered as a credible competitor for traditional disks. The hardware characteristics of NAND Flash (e.g. page granularity for read/write with a block-erase-before-rewrite constraint, limited number of erase cycles) preclude in-place updates. Previous works adapted traditional indexing methods to cope with these constraints mainly by deferring index updates thanks to a log and batching them to decrease the number of rewrite operations in Flash. These methods introduce a complex trade-off between read and write performance and neglect negative side-effects on the RAM consumption, Flash consumption and garbage collection cost. In this paper, we propose a new alternative for indexing Flash-resident data, designed from the outset to exploit the peculiarities of NAND Flash. This ap-proach, called PBFilter, organizes the index structure in a pure sequential way to avoid the side-effects mentioned above. Key lookups are sped up thanks to two principles called Summariza-tion and Partitioning. We instantiate these principles by data structures and algorithms based on Bloom Filters and show the effectiveness of this approach through a comprehensive perform-ance analysis. PBFilter can be instantiated with different Summarization and Partitioning algo-rithms opening up a new way to think about indexing Flash-resident data.
Document type :
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Shaoyi Yin Connect in order to contact the contributor
Submitted on : Wednesday, June 4, 2008 - 4:59:16 PM
Last modification on : Friday, January 21, 2022 - 3:18:04 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 4:41:53 PM


Files produced by the author(s)


  • HAL Id : inria-00284359, version 2



Shaoyi Yin, Philippe Pucheral, Xiaofeng Meng. PBFilter: Indexing Flash-Resident Data through Partitioned Summaries. [Research Report] RR-6548, INRIA. 2008. ⟨inria-00284359v2⟩



Record views


Files downloads