Algorithms for Top-k join queries in wireless sensor networks

被引：0
作者：
Mo, Shang-Feng [1 ,2 ,3 ]
Chen, Ding-Jie [1 ,2 ]
Chen, Hong [1 ,2 ]
Li, Ying-Long [1 ,2 ,3 ]
Li, Cui-Ping [1 ,2 ]
机构：
[1] Key Laboratory of Data Engineering and Knowledge Engineering of MOE, Renmin University of China
[2] School of Information, Renmin University of China
[3] Hunan University of Science and Technology, Xiangtan
来源：
Jisuanji Xuebao/Chinese Journal of Computers | 2013年 / 36卷 / 03期
关键词：
Internet of Things; Join queries; Top-k queries; Wireless sensor networks;
D O I：
10.3724/SP.J.1016.2013.00557
中图分类号：
学科分类号：
摘要：
Wireless Sensor Networks (WSNs) is one of the core components of the Internet of Things (IoTs). Data query processing is a very important research area in Wireless Sensor Networks. Join queries can monitor similar network environments in different positions. Top-k join queries further obtain k similar network environments which have the maximum (or minimum) combination scores. The Top-k join query calculates the combination score of matching tuples according to scoring function and reports the top-k matching tuples which have the maximum (or minimum) combination score. In this paper, we propose a Basic Top-k Join Queries (BTJQ) algorithm. In BTJQ, the base station sorts the tuples based on the score attribute values in descending order. Then the base station gets the tuples from the sorted list in turn and produces the join result and calculates the combination score. If the join result meets the stop condition, the base station stops taking tuples and outputs the final top-k join result. Based on the BTJQ, we propose a Centralized Top-k Join Queries (CTJQ) algorithm and Optimize Centralized Top-k Join Queries (OCTJQ) algorithm. For a different scenario, we propose a Distributed Top-k Join Queries (DTJQ) algorithm. Experiments on real-world data set show that our algorithms outperform the typical algorithm SENS-Join.
引用
收藏
页码：557 / 570
页数：13
相关论文
共 19 条
  • [1] Ten emerging technologies that will change your world, IEEE Engineering Management Review, 32, 2, pp. 20-30, (2004)
  • [2] Zhang H., Wu Z.-B., Li D.-Y., Chen H., A sampling-based algorithm for approximating maximum average value region in wireless sensor network, Proceedings of the 39th International Conference on Parallel Processing Workshops (ICPPW'10), pp. 17-23, (2010)
  • [3] Cho Y.H., Son J., Chung Y.D., POT: An efficient top-k monitoring method for spatially correlated sensor readings, Proceedings of the 5th International Workshop on Data Management for Sensor Networks (DMSN'08), pp. 8-13, (2008)
  • [4] Wu M.-J., Xu J.-L., Tang X.-Y., Lee W.C., Top-k monitoring in wireless sensor networks, IEEE Transactions on Knowledge and Data Engineering, 19, 7, pp. 962-976, (2007)
  • [5] Yeo M.H., Seong D.O., Yoo J.S., PRIM: Priority-based top-k monitoring in wireless sensor networks, Proceedings of the International Symposium on Computer Science and its Applications (CSA'08), pp. 326-331, (2008)
  • [6] Yeo M., Seong D., Yoo J., Data-aware top-k monitoring in wireless sensor networks, Proceedings of the IEEE Radio and Wireless Symposium (RWS'09), pp. 103-106, (2009)
  • [7] Liu X.-J., Xu J.-L., Lee W.-C., A cross pruning framework for top-k data collection in wireless sensor networks, Proceedings of the 11th International Conference on Mobile Data Management (MDM'10), pp. 157-166, (2010)
  • [8] Mo S.-F., Chen H., Li Y.-L., Clustering-based routing for top-k querying in wireless sensor networks, EURASIP Journal on Wireless Communications and Networking, (2011)
  • [9] Abadi D.J., Madden S., Lindner W., REED: Robust, efficient filtering and event detection in sensor networks, Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05), pp. 769-780, (2005)
  • [10] Lai Y.-X., Chen Y.-L., Chen H., In-network execution of external join for sensor networks, Proceedings of the 9th International Conference on Web-Age Information Management (WAIM'08), pp. 78-85, (2008)
12