Authors: D. Zeinalipour-Yazti, Song Lin, Vana Kalogeraki, Dimitrios Gunopulos and Valid Najjar

Title: MicroHash: An Efficient Index Structure for Flash-Based Sensor Devices

Conference: 4th USENIX Conference on File and Storage Technologies (FAST)

Year: 2005

Abstract: In this paper we propose the MicroHash index, which is an efficient external memory structure for Wireless Sensor Devices (WSDs). Themost prevalent storagemedium for WSDs is flash memory. Our index structure exploits the asymmetric read/write and wear characteristics of flash memory in order to offer high performance indexing and searching capabilities in the presence of a low energy budget which is typical for the devices under discussion. A key idea behindMicroHash is to eliminate expensive random access deletions. We have implemented MicroHash in nesC, the programming language of the TinyOS [7] operating system. Our trace-driven experimentation with several real datasets reveals that our index structure offers excellent search performance at a small cost of constructing and maintaining the index.

[Download]

Back