Soft lists: A native index structure for NOR-flash-based embedded devices

Li-Pin Chang*, Chen Hui Hsu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

Abstract- Efficient data indexing is significant to embedded devices, because both CPU cycles and energy are very precious resources. Soft lists, a new index structure for embedded devices with NOR flash, are proposed. The challenge of data indexing over NOR flash is that data update and pointer update may recursively trigger each other. Our approach is to allow a bounded number of probes when a pointer is de-referenced. By this way update and garbage collection is largely simplified, because data can be moved around physical locations without invalidating any pointers. Even better, search with soft lists is very fast, because the probes provide opportunities of forward random skips. Soft lists are evaluated and compared against tree-based index, and soft lists are shown simple but efficient.

Original languageEnglish
Title of host publicationProceedings of the ASP-DAC 2009
Subtitle of host publicationAsia and South Pacific Design Automation Conference 2009
Pages799-804
Number of pages6
DOIs
StatePublished - 20 Apr 2009
EventAsia and South Pacific Design Automation Conference 2009, ASP-DAC 2009 - Yokohama, Japan
Duration: 19 Jan 200922 Jan 2009

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Conference

ConferenceAsia and South Pacific Design Automation Conference 2009, ASP-DAC 2009
CountryJapan
CityYokohama
Period19/01/0922/01/09

Fingerprint Dive into the research topics of 'Soft lists: A native index structure for NOR-flash-based embedded devices'. Together they form a unique fingerprint.

Cite this