{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:46:29Z","timestamp":1759682789708,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2006,11,1]],"date-time":"2006-11-01T00:00:00Z","timestamp":1162339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2006,11]]},"abstract":"<jats:p>\n            Flash memory is the most prevalent storage medium found on modern\n            <jats:italic>wireless sensor devices (WSDs)<\/jats:italic>\n            . 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,\n            <jats:italic>MicroHash<\/jats:italic>\n            and\n            <jats:italic>MicroGF (micro grid files)<\/jats:italic>\n            , 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.\n          <\/jats:p>","DOI":"10.1145\/1210596.1210601","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"468-503","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Efficient indexing data structures for flash-based sensor devices"],"prefix":"10.1145","volume":"2","author":[{"given":"Song","family":"Lin","sequence":"first","affiliation":[{"name":"University of California, Riverside, CA"}]},{"given":"Demetrios","family":"Zeinalipour-Yazti","sequence":"additional","affiliation":[{"name":"University of Cyprus, Nicosia, Cyprus"}]},{"given":"Vana","family":"Kalogeraki","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}]},{"given":"Dimitrios","family":"Gunopulos","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}]},{"given":"Walid A.","family":"Najjar","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}]}],"member":"320","published-online":{"date-parts":[[2006,11]]},"reference":[{"volume-title":"Live from Earth and Mars project","key":"e_1_2_1_1_1","unstructured":"ATMO 2005. Live from Earth and Mars project . University of Washington , Seattle. http:\/\/www-k12.atmos.washington.edu\/k12\/grayskies\/. ATMO 2005. Live from Earth and Mars project. University of Washington, Seattle. http:\/\/www-k12.atmos.washington.edu\/k12\/grayskies\/."},{"volume-title":"Proceedings of the 2nd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks.","author":"Banerjee A.","key":"e_1_2_1_2_1","unstructured":"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. 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."},{"volume-title":"Crossbow Technology","author":"Crossbow","key":"e_1_2_1_3_1","unstructured":"Crossbow . 2005. Crossbow Technology , Inc . http:\/\/www.xbow.com\/. Crossbow. 2005. Crossbow Technology, Inc. http:\/\/www.xbow.com\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031516"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007628"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1098918.1098923"},{"key":"e_1_2_1_7_1","unstructured":"Dipert B. and Levy M. 1994. Designing with Flash Memory. Annabooks.   Dipert B. and Levy M. 1994. Designing with Flash Memory. Annabooks."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320092"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084779.1084780"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781133"},{"volume-title":"Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications.","author":"Greenstein B.","key":"e_1_2_1_11_1","unstructured":"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. 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."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/356989.356998"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/345910.345920"},{"key":"e_1_2_1_14_1","unstructured":"Jensen C. Lahrmann H. Pakalnis S. and Runge J. 2005. The infati data. Time Center.  Jensen C. Lahrmann H. Pakalnis S. and Runge J. 2005. The infati data. Time Center."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958506"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958500"},{"key":"e_1_2_1_17_1","volume-title":"6th International Conference on Very Large Data Bases. 212--223","author":"Litwin W.","year":"1980","unstructured":"Litwin , W. 1980 . Linear hashing: A new tool for file and table addressing . In 6th International Conference on Very Large Data Bases. 212--223 . Litwin, W. 1980. Linear hashing: A new tool for file and table addressing. In 6th International Conference on Very Large Data Bases. 212--223."},{"volume-title":"Proceedings of the 4th International Symposium on Information Processing in Sensor Networks.","author":"Lymberopoulos D.","key":"e_1_2_1_18_1","unstructured":"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. 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."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/844128.844142"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872817"},{"volume-title":"Proceedings of the Internatonal IEEE Conference on Information Processing in Sensor Networks (IPSN).","author":"Neema S.","key":"e_1_2_1_21_1","unstructured":"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). 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)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/348.318586"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/588011.588037"},{"volume-title":"Design and implementation of wireless sensor networks for habitat monitoring. Master's Thesis","author":"Polastre J.","key":"e_1_2_1_24_1","unstructured":"Polastre , J. 2003. Design and implementation of wireless sensor networks for habitat monitoring. Master's Thesis . University of California , Berkeley. Polastre, J. 2003. Design and implementation of wireless sensor networks for habitat monitoring. Master's Thesis. University of California, Berkeley."},{"key":"e_1_2_1_25_1","unstructured":"Ramakrishnan R. and Gehrke J. 2002. Database management systems 3rd ed. McGraw-Hill New York.   Ramakrishnan R. and Gehrke J. 2002. Database management systems 3rd ed. McGraw-Hill New York."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031522"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/356924.356930"},{"key":"e_1_2_1_28_1","unstructured":"Sandisk 2006. Sandisk flash memory cards---Wear leveling. http:\/\/sandisk.com\/pdf\/oem\/WPaperWearLevelv1.0.pdf.  Sandisk 2006. Sandisk flash memory cards---Wear leveling. http:\/\/sandisk.com\/pdf\/oem\/WPaperWearLevelv1.0.pdf."},{"volume-title":"Proceedings of the 16th International Conference on Very Large Databases. 590--601","author":"Seeger B.","key":"e_1_2_1_29_1","unstructured":"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 . 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."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/774763.774785"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031518"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031521"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Tang C. and Raghavendra C. 2004. Compression techniques for wireless sensor networks. In Wireless Sensor Networks. Kluwer Academic Norwell MA 207--231.   Tang C. and Raghavendra C. 2004. Compression techniques for wireless sensor networks. In Wireless Sensor Networks. Kluwer Academic Norwell MA 207--231.","DOI":"10.1007\/978-1-4020-7884-2_10"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.963443"},{"key":"e_1_2_1_35_1","unstructured":"Whang K. and Krishnamurthy R. 1985. Multilevel grid files. Res. Rep. RC11516 IBM Yorktown Heights New York.  Whang K. and Krishnamurthy R. 1985. Multilevel grid files. Res. Rep. RC11516 IBM Yorktown Heights New York."},{"key":"e_1_2_1_36_1","volume-title":"Jffs: The journalling flash file system","author":"Woodhouse D.","year":"2006","unstructured":"Woodhouse , D. 2006 . Jffs: The journalling flash file system . http:\/\/sources.redhat.com\/jffs2\/jffs2.pdf. Woodhouse, D. 2006. Jffs: The journalling flash file system. http:\/\/sources.redhat.com\/jffs2\/jffs2.pdf."},{"key":"e_1_2_1_37_1","volume-title":"Linux Conference of Tutorials","author":"Wookey","year":"2006","unstructured":"Wookey . 2006 . Yaffs - A filesystem designed for nand flash . In Linux Conference of Tutorials . Leeds, UK. Wookey. 2006. Yaffs - A filesystem designed for nand flash. In Linux Conference of Tutorials. Leeds, UK."},{"volume-title":"the 9th International Conference on Real-Time and Embedded Computing Systems and Applications.","author":"Wu C.","key":"e_1_2_1_38_1","unstructured":"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. 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."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/956676.956679"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031498"},{"volume-title":"Conference on Innovative Data Systems Research.","author":"Yao Y.","key":"e_1_2_1_41_1","unstructured":"Yao , Y. and Gehrke , J . 2003. Query processing in sensor networks . In Conference on Innovative Data Systems Research. Yao, Y. and Gehrke, J. 2003. Query processing in sensor networks. In Conference on Innovative Data Systems Research."},{"volume-title":"Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST). 31--44","author":"Zeinalipour-Yazti D.","key":"e_1_2_1_42_1","unstructured":"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 . 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."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.209"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080885.1080896"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1210596.1210601","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1210596.1210601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:22Z","timestamp":1750278142000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1210596.1210601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,11]]}},"alternative-id":["10.1145\/1210596.1210601"],"URL":"https:\/\/doi.org\/10.1145\/1210596.1210601","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2006,11]]},"assertion":[{"value":"2006-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}