University of British Columbia
An efficient external sorting algorithm for flash memory embedded devices
Abstract
dc:descriptionMany embedded systems applications involve storing and querying large datasets. Existing research in this area has focused on adapting and applying conventional database algorithms to embedded devices. Algorithms designed for processing queries on embedded devices must be able to execute given the small amount of available memory and energy constraints. Sorting is a fundamental algorithm used frequently in databases. Flash memory has unique performance characteristics. Page writes to flash memory are much more expensive than reads. In addition, random reads from flash memory can be performed at nearly the same speed as sequential reads. External sorting can be optimized for flash memory embedded devices by favoring page reads over writes. This thesis describes the Flash MinSort algorithm that, given little memory, takes advantage of fast random reads and generates an index at runtime to sort a dataset. The algorithm adapts its performance to the memory available and performs best for data that is temporally clustered. Experimental results show that Flash MinSort is two to ten times faster than previous approaches for small memory sizes where external merge sort is not executable.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Interdisciplinary Studies
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2012
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Cossentine, Tyler Andrew
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/40208