Efficient indexing data structures for flash-based sensor devices

ABSTRACT

Flash memory is the most prevalent storage medium found on modern wireless sensor devices (WSDs). In this article we present two external memory index structures for the efficient retrieval of records stored on the local flash memory of a WSD. Our index structures, MicroHash and MicroGF (micro grid files), exploit the asymmetric read/write and wear characteristics of flash memory in order to offer high-performance indexing and searching capabilities in the presence of a low-energy budget, which is typical for the devices under discussion. Both structures organize data and index pages on the flash media using a sorted by timestamp file organization. A key idea behind these index structures is that expensive random access deletions are completely eliminated. MicroHash enables equality searches by value in constant time and equality searches by timestamp in logarithmic time at a small cost of storing index pages on the flash media. Similarly, MicroGF enables spatial equality and proximity searches in constant time. We have implemented these index structures in nesC, the programming language of the TinyOS operating system. Our trace-driven experimentation with several real datasets reveals that our index structures offer excellent search performance at a small cost of constructing and maintaining the index.

REFERENCES

• 1: ATMO 2005. Live from Earth and Mars project. University of Washington, Seattle. http://www-k12.atmos.washington.edu/k12/grayskies/.
• 2: Banerjee, A., Mitra, A., Najjar, W., Zeinalipour-Yazti, D., Kalogeraki, V., and Gunopulos, D. 2005. Rise co-s : High performance sensor storage and co-processing architecture. In Proceedings of the 2nd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks.
• 3: Crossbow. 2005. Crossbow Technology, Inc. http://www.xbow.com/.
• 4: Hui Dai , Michael Neufeld , Richard Han, ELF: an efficient log-structured flash file system for micro sensor nodes, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031516]
• 5: Antonios Deligiannakis , Yannis Kotidis , Nick Roussopoulos, Compressing historical information in sensor networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007628]
• 6: Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, TSAR: a two tier sensor storage architecture using interval skip graphs, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098923]
• 7: Brian Dipert , Markus Levy, Designing with Flash Memory, Annabooks, 1993
• 8: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 9: Deepak Ganesan , Ben Greenstein , Deborah Estrin , John Heidemann , Ramesh Govindan, Multiresolution storage and search in sensor networks, ACM Transactions on Storage (TOS), v.1 n.3, p.277-315, August 2005 [doi>10.1145/1084779.1084780]
• 10: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 11: Greenstein, B., Estrin, D., Govindan, R., Ratnasamy, S., and Shenker, S. 2003. Difs: A distributed index for features in sensor networks. In Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications.
• 12: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, ACM SIGPLAN Notices, v.35 n.11, p.93-104, Nov. 2000 [doi>10.1145/356989.356998]
• 13: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 14: Jensen, C., Lahrmann, H., Pakalnis, S., and Runge, J. 2005. The infati data. Time Center.
• 15: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire tinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 16: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958500]
• 17: Litwin, W. 1980. Linear hashing: A new tool for file and table addressing. In 6th International Conference on Very Large Data Bases. 212--223.
• 18: Dimitrios Lymberopoulos , Andreas Savvides, XYZ: a motion-enabled, power aware sensor node platform for distributed sensor network applications, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 19: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844142]
• 20: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 21: Neema, S., Mitra, A., Banerjee, A., Najjar, W., Zeinalipour-Yazti, D., Gunopulos, D., and Kalogeraki, V. 2005. Nodes: A novel system design for embedded sensor networks. In Proceedings of the Internatonal IEEE Conference on Information Processing in Sensor Networks (IPSN).
• 22: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 23: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 24: Polastre, J. 2003. Design and implementation of wireless sensor networks for habitat monitoring. Master's Thesis. University of California, Berkeley.
• 25: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Science/Engineering/Math, 2002
• 26: Pei Zhang , Christopher M. Sadler , Stephen A. Lyon , Margaret Martonosi, Hardware design experiences in ZebraNet, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031522]
• 27: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 28: Sandisk 2006. Sandisk flash memory cards---Wear leveling. http://sandisk.com/pdf/oem/WPaperWearLevelv1.0.pdf.
• 29: Bernhard Seeger , Hans-Peter Kriegel, The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems, Proceedings of the 16th International Conference on Very Large Data Bases, p.590-601, August 13-16, 1990
• 30: Scott Shenker , Sylvia Ratnasamy , Brad Karp , Ramesh Govindan , Deborah Estrin, Data-centric storage in sensornets, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.137-142, January 2003 [doi>10.1145/774763.774785]
• 31: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]
• 32: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 33: Caimu Tang , Cauligi S. Raghavendra, Compression techniques for wireless sensor networks, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
• 34: Brett Warneke , Matt Last , Brian Liebowitz , Kristofer S. J. Pister, Smart Dust: Communicating with a Cubic-Millimeter Computer, Computer, v.34 n.1, p.44-51, January 2001 [doi>10.1109/2.963443 ]
• 35: Whang, K. and Krishnamurthy, R. 1985. Multilevel grid files. Res. Rep. RC11516, IBM, Yorktown Heights, New York.
• 36: Woodhouse, D. 2006. Jffs: The journalling flash file system. http://sources.redhat.com/jffs2/jffs2.pdf.
• 37: Wookey. 2006. Yaffs - A filesystem designed for nand flash. In Linux Conference of Tutorials. Leeds, UK.
• 38: Wu, C., Chang, L., and Kuo, T. 2003a. An efficient b-tree layer for flash memory storage systems. In the 9th International Conference on Real-Time and Embedded Computing Systems and Applications.
• 39: Chin-Hsien Wu , Li-Pin Chang , Tei-Wei Kuo, An efficient R-tree implementation over flash-memory storage systems, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.17-24, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956679]
• 40: Ning Xu , Sumit Rangwala , Krishna Kant Chintalapudi , Deepak Ganesan , Alan Broad , Ramesh Govindan , Deborah Estrin, A wireless sensor network For structural monitoring, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031498]
• 41: Yao, Y. and Gehrke, J. 2003. Query processing in sensor networks. In Conference on Innovative Data Systems Research.
• 42: Zeinalipour-Yazti, D., Lin, S., Kalogeraki, V., Gunopulos, D., and Najjar, W. 2005. Microhash: An efficient index structure for flash-based sensor devices. In Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST). 31--44.
• 43: Zeinalipour-Yazti, D., Neema, S., Gunopulos, D., Kalogeraki, V., and Najjar, W. 2005. Data acquision in sensor networks with large memories. In 1st IEEE International Workshop on Networking Meets Databases (NetDB).
• 44: D. Zeinalipour-Yazti , Z. Vagena , D. Gunopulos , V. Kalogeraki , V. Tsotras , M. Vlachos , N. Koudas , D. Srivastava, The threshold join algorithm for top-k queries in distributed sensor networks, Proceedings of the 2nd international workshop on Data management for sensor networks, August 30-30, 2005, Trondheim, Norway [doi>10.1145/1080885.1080896]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Design, Experimentation

Keywords:
Wireless sensor networks, access methods, flash memory