Welcome to the ADMT Publication Server

FSort: External Sorting on Flash-based Sensor Devices

DocUID: 2009-018 Full Text: PDF

Author: Panayiotis Andreou, Orestis Spanos, Demetrios Zeinalipour-Yazti, George Samaras, Panos K. Chrysanthis

Abstract: In long-term deployments of Wireless Sensor Networks, it is often more efficient to store sensor readings locally at each device and transmit those readings to the user only when requested (i.e., in response to a user query). Many of the techniques that collect information from a sensor network require that the data is sorted on some attribute (e.g., range queries, top-k queries, join queries, etc.) Yet, the underlying storage medium of these devices (i.e., Flash media) presents some unique characteristics which renders traditional disk-based sorting algorithms inefficient in this context. In this paper we devise the $FSort$ algorithm, an efficient external sorting algorithm for flash-based sensor devices with a small memory footprint. $FSort$ minimizes the expensive write/delete operations of flash memory minimizing in that way the consumption of energy. In particular, $FSort$ uses a top-down replacement selection algorithm in order to produce sorted runs on flash media in a log-based manner. Sorted runs are then recursively merged in order to yield the sorted result. Our experimentation with real traces from Intel Research Berkeley show that $FSort$ greatly outperforms the traditional External Mergesort Algorithm both in regards to time and energy consumption. We found similar advantages in regards to the wearability constraints of flash media.

Keywords: Sensor Networks, Sorting, Flash

Published In: Proc. of 6th International Workshop on Data Management for Sensor Networks

Place Published: Lyon, France

Year Published: 2009

Note: held in conjunction with the VLDB 2009 Conference

Project: STREAMS Subject Area: Sensor Databases

Publication Type: Workshop Paper

Sponsor: NSF IIS-0534531

Citation:Text Latex BibTex XML Panayiotis Andreou, Orestis Spanos, Demetrios Zeinalipour-Yazti, George Samaras, and Panos K. Chrysanthis. FSort: External Sorting on Flash-based Sensor Devices, Proc. of 6th International Workshop on Data Management for Sensor Networks (DMSN'09), Lyon, France, August 2009.(held in conjunction with the VLDB 2009 Conference)