POT: an efficient top-k monitoring method for spatially correlated sensor readings

ABSTRACT

In this paper, we discuss the top-k monitoring over sensor networks. Since sensor readings are usually correlated with location, top-k nodes are clustered at some areas. Motivated by such a characteristic, we propose a novel tree structure named partial ordered tree(POT) to efficiently maintain clusters of the highest readings. By using POTs, only candidate nodes which might be included in top-k result are evaluated for query processing. Through simulation experiments, we evaluate the performance of the POT method in comparison with conventional methods.

REFERENCES

• 1: Reza Akbarinia , Esther Pacitti , Patrick Valduriez, Reducing network traffic in unstructured P2P systems using Top-k queries, Distributed and Parallel Databases, v.19 n.2-3, p.67-86, May 2006 [doi>10.1007/s10619-006-8313-5]
• 2: Brian Babcock , Chris Olston, Distributed top-k monitoring, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872764]
• 3: W.-T. Balke, W. Nejdl, W. Siberski, and U. Thaden. Progressive distributed top-k retrieval in peer-to-peer networks. pages 174--185, 2005.
• 4: N. Bruno, L. Gravano, and A. Marian. Evaluating top-k queries over web-accessible databases. pages 369--380, 2002.
• 5: Pei Cao , Zhe Wang, Efficient top-K query calculation in distributed networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011798]
• 6: Surajit Chaudhuri , Luis Gravano , Amelie Marian, Optimizing Top-k Selection Queries over Multimedia Repositories, IEEE Transactions on Knowledge and Data Engineering, v.16 n.8, p.992-1009, August 2004 [doi>10.1109/TKDE.2004.30]
• 7: Chuck conner. modeling heat transfer in parallel. http://www.cas.usf.edu/~cconnor/parallel/2dheat/2dheat.html.
• 8: Earth remote sensing data analysis center. http://www.gds.aster.ersdac.or.jp/gds_www2002/index_e.html.
• 9: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 10: W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wireless Communications, 1(4):660--670, 2002.
• 11: Intel Lab Data. http://db.csail.mit.edu/labdata/labdata.html.
• 12: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 13: Sebastian Michel , Peter Triantafillou , Gerhard Weikum, KLEE: a framework for distributed top-k query algorithms, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 14: Kyriakos Mouratidis , Spiridon Bakiras , Dimitris Papadias, Continuous monitoring of top-k queries over sliding windows, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142544]
• 15: Query Processing Issues in Image(Multimedia) Databases, Proceedings of the 15th International Conference on Data Engineering, p.22, March 23-26, 1999
• 16: The Network Simulator NS-2. http://www.isi.edu/nsnam/ns.
• 17: Adam Silberstein Silberstein , Rebecca Braynard , Carla Ellis , Kamesh Munagala , Jun Yang, A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks, Proceedings of the 22nd International Conference on Data Engineering, p.68, April 03-07, 2006 [doi>10.1109/ICDE.2006.10]
• 18: R. Szewczyk, J. Polastre, A. M. Mainwaring, and D. E. Culler. Lessons from a sensor network expedition. In EWSN, pages 307--322, 2004.
• 19: Aster image database for volcanoes. http://www.gsj.jp/database/vsidb/image/proto_header.html.
• 20: Minji Wu , Jianliang Xu , Xueyan Tang , Wang-Chien Lee, Top-k Monitoring in Wireless Sensor Networks, IEEE Transactions on Knowledge and Data Engineering, v.19 n.7, p.962-976, July 2007 [doi>10.1109/TKDE.2007.1038]
• 21: Wenwei Xue , Qiong Luo , Lei Chen , Yunhao Liu, Contour map matching for event detection in sensor networks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142491]
• 22: D. Zeinalipour-Yazti, P. Andreou, P. K. Chrysanthis, and G. Samaras. Mint views: Materialized in-network top-k views in sensor networks. In MDM, pages 182--189, 2007.
• 23: 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:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation

Keywords:
sensor networks, top-k monitoring