FSort: external sorting on flash-based sensor devices

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.

REFERENCES

• 1: Aly M., Chrysanthis P. K., Pruhs K., "Decomposing Data-Centric Storage Query Hot-spots in Sensor Networks", In MOBIQUITOUS, 2006.
• 2: Aly M., Pruhs K., Chrysanthis P. K., "KDDCS: a load-balanced in-network data-centric storage scheme for sensor networks", In CIKM pp. 317--326, 2006.
• 3: Andreou P., Zeinalipour-Yazti D., Vassiliadou M., Chrysanthis P. K., Samaras G., "KSpot: Effectively Monitoring the K Most Important Events in a Wireless Sensor Network", In ICDE, 2009.
• 4: Atmel AT45DB041B, http://www.atmel.com/
• 5: Bouganim L., Jonsson B. T., Bonnet P., "uFLIP: Understanding Flash IO Patterns", In CIDR, 2009.
• 6: Crossbow Technology Inc., http://www.xbow.com/
• 7: Intel Lab Data http://db.csail.mit.edu/labdata/labdata.html
• 8: Knuth D. E., "The Art of Computer Programming: Sorting and Searching" Addison Wesley, Vol. 3, April 1997, ISBN:0-201-89685-0.
• 9: Larson P., Graefe G., "Memory management during run generation in external sorting", In ACM SIGMOD, pp. 472--483, 1998.
• 10: Lee K. Y., Kim H., Woo K., Chung Y. D., Kim M. H., "Design and implementation of MLC NAND flash-based DBMS for mobile devices", In Journal of Systems and Software, 2009.
• 11: Lee S., Moon B., "Design of Flash-Based DBMS: An In-Page Logging Approach", In ACM SIGMOD, pp. 1--10, 2007.
• 12: Lee S., Park D., Chung T., Lee D., Park S., Song, H., "A log buffer-based flash translation layer using fully-associative sector translation", In ACM (TECS), Vol. 6, No. 3, pp. 18, 2007.
• 13: Madden S. R., Franklin M. J., Hellerstein J. M., Hong W., "TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks", In USENIX OSDI, Vol. 36, pp. 131--146, 2002.
• 14: Masuoka F., Iizuka H., "Semiconductor memory device and method for manufacturing the same", US patent:4531203, July, 1985.
• 15: Elmasri R., Navathe S. B., "Fundamentals of Database Systems (5^th Edition): Chapter:15.3.2" Addison Wesley, 2007, ISBN:0-321-41506-X.
• 16: Ning X., Sumit R., Krishna K. C., Deepak G., Alan B., Ramesh G., Deborah E., "A wireless sensor network For structural monitoring", In ACM SenSys, pp. 13--24, 2004.
• 17: Nyberg C., Barclay T., Cvetanovic Z., Gray J., Lomet D., "AlphaSort: a cache-sensitive parallel external sort", In VLDB, Vol. 4, No. 4, pp. 603--628, 1995.
• 18: Pang H., Carey M. J., Livny M., "Memory-Adaptive External Sorting", In VLDB, pp. 618--629, 1993.
• 19: Rosenblum M., Ousterhout J. K., "The design and implementation of a log-structured file system", In ACM TOCS, Vol. 10, No. 1, pp. 26--52, 1992.
• 20: Sadler C., Zhang P., Martonosi M., Lyon S., "Hardware Design Experiences in ZebraNet", In ACM SenSys, pp. 227--238, 2004.
• 21: Selavo L., Wood A., Cao Q., Sookoor T., Liu H., Srinivasan A., Wu Y., Kang W., Stankovic J., Yound D., Porter J., "LUSTER: wireless sensor network for environmental research", In ACM SenSys, pp. 103--116, 2007.
• 22: Sharaf M. A., Beaver J., Labrinidis A. and Chrysanthis P. K., "TiNA: a scheme for temporal coherency-aware in-network aggregation", In MobiDe, pp. 69--76, 2003.
• 23: Szewczyk R., Mainwaring A., Polastre J., Anderson J., Culler D., "An Analysis of a Large Scale Habitat Monitoring Application", In ACM SenSys, pp. 214--226, 2004.
• 24: Yao Y., Gehrke J. E., "The cougar approach to in-network query processing in sensor networks", In SIGMOD Record, Vol. 32, No. 3, pp. 9--18, 2002.
• 25: Zeinalipour-Yazti D., Andreou P., Chrysanthis P. and Samaras G., "MINT Views: Materialized In-Network Top-k Views in Sensor Networks", In IEEE MDM, 2007.
• 26: Zeinalipour-Yazti D., Lin S., Kalogeraki V., Gunopulos D., Najjar W., "MicroHash: An Efficient Index Structure for Flash-Based Sensor Devices", In Usenix FAST, pp. 31--44, 2005.

INDEX TERMS

Primary Classification:
  E. Data
  E.5 FILES
      Subjects: Sorting/searching

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Selection process

General Terms:
Algorithms, Design, Management