skip to main content
article

Efficient indexing data structures for flash-based sensor devices

Published: 01 November 2006 Publication History

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]
Dai, H., Neufeld, M., and Han, R. 2004. Elf: An efficient log-structured flash file system for micro sensor nodes. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. 176--187.
[5]
Deligiannakis, A., Kotidis, Y., and Roussopoulos, N. 2004. Compressing historical information in sensor networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 527--538.
[6]
Desnoyers, P., Ganesan, D., and Shenoy, P. 2005. Tsar: A two tier sensor storage architecture using interval skip graphs. In Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems. 39--50.
[7]
Dipert, B. and Levy, M. 1994. Designing with Flash Memory. Annabooks.
[8]
Fagin, R., Nievergelt, J., Pippenger, N., and Strong, H. 1979. Extendible hashing---A fast access method for dynamic files. ACM Trans. Database Syst. 4, 3, 315--344.
[9]
Ganesan, D., Greenstein, B., Perelyubskiy, D., Estrin, D., and Heidemann, J. 2005. Multi-Resolution storage and search in sensor networks. ACM Trans. Storage 1, 3, 277--315.
[10]
Gay, D., Levis, P., Von, B., Welsh, M., Brewer, E., and Culler, D. 2003. The nesc language: A holistic approach to networked embedded systems. In ACM SIGPLAN Conference on Programming Language Design and Implementation.
[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]
Hill, J., Szewczyk, R., Woo, A., Hollar, S., Culler, D., and Pister, K. 2000. System architecture directions for networked sensors. SIGPLAN Not. 35, 11, 93--104.
[13]
Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the ACM IEEE Conference on Mobile Computing and Networking. 56--67 Tech. Rep. TR = 79.
[14]
Jensen, C., Lahrmann, H., Pakalnis, S., and Runge, J. 2005. The infati data. Time Center.
[15]
Levis, P., Lee, N., Welsh, M., and Culler, D. 2003. Tossim: Accurate and scalable simulation of entire tinyos applications. In Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems.
[16]
Li, X., Kim, Y., Govindan, R., and Hong, W. 2003. Multi-Dimensional range queries in sensor networks. In Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems.
[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]
Lymberopoulos, D. and Savvides, A. 2005. Xyz: A motion-enabled, power aware sensor node platform for distributed sensor network applications. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks.
[19]
Madden, S., Franklin, M., Hellerstein, J., and Hong, W. 2002. Tag: A tiny aggregation service for ad-hoc sensor networks. ACM SIGOPS Oper. Syst. Rev. 36, 131--146.
[20]
Madden, S., Franklin, M., Hellerstein, J., and Hong, W. 2003. The design of an acquisitional query processor for sensor networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 491--502.
[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]
Nievergelt, J., Hinterberger, H., and Sevcik, K. 1984. The grid file: An adaptable, symmetric multi-key file structure. ACM Trans. Database Sys. 9, 1, 38--71.
[23]
Orenstein, J. and Merrett, T. 1984. A class of data structures for associative searching. In Proceedings of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. 181--190.
[24]
Polastre, J. 2003. Design and implementation of wireless sensor networks for habitat monitoring. Master's Thesis. University of California, Berkeley.
[25]
Ramakrishnan, R. and Gehrke, J. 2002. Database management systems, 3rd ed. McGraw-Hill, New York.
[26]
Sadler, C., Zhang, P., Martonosi, M., and Lyon, S. 2004. Hardware design experiences in zebranet. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. 227--238.
[27]
Samet, H. 1984. The quadtree and related hierarchical data structures. ACM Comput. Surv. 16, 2, 187--260.
[28]
Sandisk 2006. Sandisk flash memory cards---Wear leveling. http://sandisk.com/pdf/oem/WPaperWearLevelv1.0.pdf.
[29]
Seeger, B. and Kriegel, H. 1990. The buddy-tree: An efficient and robust access method for spatial data base systems. In Proceedings of the 16th International Conference on Very Large Databases. 590--601.
[30]
Shenker, S., Ratnasamy, S., Karp, B., Govindan, R., and Estrin, D. 2003. Data-Centric storage in sensornets. ACM SIGCOMM Comput. Commun. Rev. 33, 1, 137--142.
[31]
Shnayder, V., Hempstead, M., Chen, B., Werner-Allen, G., and Welsh, M. 2004. Simulating the power consumption of large-scale sensor network applications. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. 188--200.
[32]
Szewczyk, R., Mainwaring, A., Polastre, J., Anderson, J., and Culler, D. 2004. An analysis of a large scale habitat monitoring application. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. 214--226.
[33]
Tang, C. and Raghavendra, C. 2004. Compression techniques for wireless sensor networks. In Wireless Sensor Networks. Kluwer Academic, Norwell, MA, 207--231.
[34]
Warneke, B., Last, M., Liebowitz, B., and Pister, K. 2001. Smart dust: Communicating with a cubic-millimeter computer. IEEE Computer. 34, 1, 44--51.
[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]
Wu, C., Chang, L., and Kuo, T. 2003b. An efficient r-tree implementation over flash-memory storage systems. In Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems. 17--24.
[40]
Xu, N., Rangwala, S., Chintalapudi, K., Ganesan, D., Broad, A., Govindan, R., and Estrin, D. 2004. A wireless sensor network for structural monitoring. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. 13--24.
[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]
Zeinalipour-Yazti, D., Vagena, Z., Gunopulos, D., Kalogeraki, V., Tsotras, V., Vlachos, M., Koudas, N., and Srivastava, D. 2005. The threshold join algorithm for top-k queries in distributed sensor networks. In Proceedings of the 2nd International Very Large Data Base Workshop on Data Management for Sensor Networks. 61--66.

Cited By

View all
  • (2024)Polling Sanitization to Balance I/O Latency and Data Security of High-density SSDsACM Transactions on Storage10.1145/363982620:2(1-23)Online publication date: 19-Feb-2024
  • (2024)iFKVS: Lightweight Key-Value Store for Flash-Based Intermittently Computing DevicesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.344369843:11(3564-3575)Online publication date: 1-Nov-2024
  • (2023)Spatial Index Structures for Modern Storage Devices: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.324220735:9(9578-9597)Online publication date: 1-Sep-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Storage
ACM Transactions on Storage  Volume 2, Issue 4
November 2006
133 pages
ISSN:1553-3077
EISSN:1553-3093
DOI:10.1145/1210596
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2006
Published in TOS Volume 2, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Wireless sensor networks
  2. access methods
  3. flash memory

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)15
  • Downloads (Last 6 weeks)2
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Polling Sanitization to Balance I/O Latency and Data Security of High-density SSDsACM Transactions on Storage10.1145/363982620:2(1-23)Online publication date: 19-Feb-2024
  • (2024)iFKVS: Lightweight Key-Value Store for Flash-Based Intermittently Computing DevicesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.344369843:11(3564-3575)Online publication date: 1-Nov-2024
  • (2023)Spatial Index Structures for Modern Storage Devices: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.324220735:9(9578-9597)Online publication date: 1-Sep-2023
  • (2022)Porting disk-based spatial index structures to flash-based solid state drivesGeoinformatica10.1007/s10707-021-00455-w26:1(253-298)Online publication date: 1-Jan-2022
  • (2021)HyR-tree: a spatial index for hybrid flash/3D XPoint storageNeural Computing and Applications10.1007/s00521-021-05804-235:1(133-145)Online publication date: 25-Feb-2021
  • (2020)Linear Hashing Implementations for Flash MemoryEnterprise Information Systems10.1007/978-3-030-40783-4_18(386-405)Online publication date: 20-Feb-2020
  • (2019)A spatial index for hybrid storageProceedings of the 23rd International Database Applications & Engineering Symposium10.1145/3331076.3331091(1-8)Online publication date: 10-Jun-2019
  • (2019)A Study of R-tree Performance in Hybrid Flash/3DXPoint Storage2019 10th International Conference on Information, Intelligence, Systems and Applications (IISA)10.1109/IISA.2019.8900716(1-6)Online publication date: Jul-2019
  • (2019)LB-Grid: An SSD efficient Grid FileData & Knowledge Engineering10.1016/j.datak.2019.04.002Online publication date: Apr-2019
  • (2019)Parallel processing of spatial batch-queries using $${\text {xBR}}^+$$xBR+-trees in solid-state drivesCluster Computing10.1007/s10586-019-03013-0Online publication date: 9-Nov-2019
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media