Paper Info
Title
PBFilter: A flash-based indexing scheme for embedded systems
Abstract
NAND Flash has become the most widely used electronic stable storage technology for embedded systems. As on-board storage capacity increases, the need for efficient indexing techniques arises. Such techniques are very challenging to design due to a combination of NAND Flash constraints (e.g., block-erase-before-page-rewrite constraint and limited number of erase cycles) and embedded system constraints (e.g., tiny RAM and resource consumption predictability). Previous work adapted traditional indexing methods to cope with Flash constraints by deferring index updates using a log and batching them to decrease the number of rewrite operations in Flash memory. However, these methods were not designed with embedded system constraints in mind and do not address them properly. In this paper, we propose a different alternative for indexing Flash-resident data that specifically addresses the embedded context. This approach, called PBFilter, organizes the index structure in a purely sequential way. Key lookups are sped up thanks to two principles called Summarization and Partitioning. We instantiate these principles with data structures and algorithms based on Bloom Filters and show the effectiveness of this approach through a comprehensive analytical performance study. Extensions of PBFilter on range queries and multi-criteria queries are also discussed. The proposed technique is integrated into a full-fledged embedded DBMS engine. We describe the complete design of the DBMS engine to illustrate the feasibility of adopting PBFilter technique in a real system. Finally, we show some performance measurements of the prototype on top of a real hardware platform, in order to validate the new technique in a practical manner.
Year
DOI
Venue
2012
10.1016/j.is.2012.02.002
Inf. Syst.
Keywords
Field
DocType
flash memory,flash constraint,full-fledged embedded dbms engine,nand flash constraint,embedded context,flash-based indexing scheme,efficient indexing technique,pbfilter technique,nand flash,embedded system constraint,embedded system,bloom filter,indexing,embedded systems
Data mining,Automatic summarization,Data structure,Bloom filter,Flash memory,Computer science,Flash memory emulator,Range query (data structures),Search engine indexing,Database,Stable storage,Embedded system
Journal
Volume
Issue
ISSN
37
7
0306-4379
Citations 
PageRank 
References 
4
0.44
25
Authors
2
Name
Order
Citations
PageRank
Shaoyi Yin1898.93
Philippe Pucheral251471.89