FAST: Flash-aware external sorting for mobile database systems

Recently, flash memory has gained its popularity as storage on wide spectrum of computing devices such as cellular phones, digital cameras, digital audio players and PDAs. The integration of high-density flash memory has been accelerated twice every year for past few years. As flash memory’s capacity increases and its price drops, it is expected that flash memory will be more competitive with magnetic disk drives. Therefore, it is desirable to adapt disk-based algorithms to take advantage of the flash memory technology.In this paper, we propose a novel Flash-Aware external SorTing algorithm, FAST, that overcomes the limitation of larger writing cost for flash memory to improve both overall execution time and response time. In FAST, we reduce the write operations with additional read operations. We provide the analysis for both traditional and our flash-aware algorithms by comparing the detailed cost formulas. Experimental results with synthetic and real-life data sets show that FAST can result in faster execution time as well as smaller response time than traditional external sorting algorithms.