Show simple item record

dc.contributor.authorLin, S.en
dc.contributor.authorZeinalipour-Yazdi, Constantinos D.en
dc.contributor.authorKalogeraki, Vanaen
dc.contributor.authorGunopulos, Dimitriosen
dc.contributor.authorNajjar, W. A.en
dc.creatorLin, S.en
dc.creatorZeinalipour-Yazdi, Constantinos D.en
dc.creatorKalogeraki, Vanaen
dc.creatorGunopulos, Dimitriosen
dc.creatorNajjar, W. A.en
dc.description.abstractFlash memory is the most prevalent storage medium found on modern wireless sensor devices (WSDs). In this article we present two external memory index structures for the efficient retrieval of records stored on the local flash memory of a WSD. Our index structures, MicroHash and MicroGF (micro grid files), exploit 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. Both structures organize data and index pages on the flash media using a sorted by timestamp file organization. A key idea behind these index structures is that expensive random access deletions are completely eliminated. MicroHash enables equality searches by value in constant time and equality searches by timestamp in logarithmic time at a small cost of storing index pages on the flash media. Similarly, MicroGF enables spatial equality and proximity searches in constant time. We have implemented these index structures in nesC, the programming language of the TinyOS operating system. Our trace-driven experimentation with several real datasets reveals that our index structures offer excellent search performance at a small cost of constructing and maintaining the index. © 2006 ACM.en
dc.sourceACM Transactions on Storageen
dc.subjectWireless sensor networksen
dc.subjectComputer programming languagesen
dc.subjectData structuresen
dc.subjectFlash memoryen
dc.subjectIndexing (of information)en
dc.subjectComputer operating systemsen
dc.subjectOnline searchingen
dc.subjectAccess methodsen
dc.subjectComputer operating system - TinyOSen
dc.subjectComputer programming language - nesCen
dc.subjectContent based retrievalen
dc.subjectFile organizationen
dc.subjectWireless sensor devices (WSD)en
dc.titleEfficient indexing data structures for flash-based sensor devicesen
dc.description.endingpage503 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :23</p>en
dc.source.abbreviationACM Trans.Storageen
dc.contributor.orcidZeinalipour-Yazdi, Constantinos D. [0000-0002-8388-1549]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record