A General Framework for Efficient Continuous Multidimensional Top-k Query Processing in Sensor Networks
A General Framework for Efficient Continuous Multidimensional Top-k Query Processing in Sensor Networks
复制标题
DOI：
10.1109/tpds.2012.69
复制
发表时间：
2012-09
影响因子：
5.3
通讯作者：
Hongbo Jiang;Jie Cheng;Dan Wang;Chonggang Wang;Guang Tan
中科院分区：
文献类型：
--
作者：
Hongbo Jiang;Jie Cheng;Dan Wang;Chonggang Wang;Guang Tan
Top-k查询长期以来一直是计算机科学多个领域（例如数据处理和信息检索）中的关键问题。在新兴的网络物理系统中，可能有大量用户直接在物理世界中搜索信息，这给 top-k 查询处理带来了许多新的挑战。从客户的角度来看，用户可能会在不同的时间请求不同的信息集、不同的优先级。因此，top-k搜索不仅应该是多维的，而且应该是跨时域的。从系统的角度来看，数据收集通常是由小型传感设备进行的。与用于网络空间搜索的数据中心不同，这些设备通常资源极其有限，系统效率至关重要。在本文中，我们开发了一个可以有效满足这两方面需求的框架。传感器网络维护有效的主导图数据结构以进行数据读取。使用简单的top-k提取算法进行用户查询处理，并提出两种方案以进一步降低通信成本。我们的方法可用于任何线性凸查询函数的 top-k 查询。该框架具有足够的适应性，可以合并一些高级功能；例如，我们展示了如何应用近似查询和数据老化。据我们所知，这是传感器网络中连续多维 top-k 查询处理的第一项工作。仿真结果表明，与集中式方案或之前一维传感器数据上的 top-k 算法的直接扩展相比，我们的方案可以将总通信成本降低高达 90%。
Top-k query has long been a crucial problem in multiple fields of computer science, such as data processing and information retrieval. In emerging cyber-physical systems, where there can be a large number of users searching information directly into the physical world, many new challenges arise for top-k query processing. From the client's perspective, users may request different sets of information, with different priorities and at different times. Thus, top-k search should not only be multidimensional, but also be across time domain. From the system's perspective, data collection is usually carried out by small sensing devices. Unlike the data centers used for searching in the cyber-space, these devices are often extremely resource constrained and system efficiency is of paramount importance. In this paper, we develop a framework that can effectively satisfy demands from the two aspects. The sensor network maintains an efficient dominant graph data structure for data readings. A simple top-k extraction algorithm is used for user query processing and two schemes are proposed to further reduce communication cost. Our methods can be used for top-k query with any linear convex query function. The framework is adaptive enough to incorporate some advanced features; for example, we show how approximate queries and data aging can be applied. To the best of our knowledge, this is the first work for continuous multidimensional top-k query processing in sensor networks. Simulation results show that our schemes can reduce the total communication cost by up to 90 percent, compared with a centralized scheme or a straightforward extension from previous top-k algorithm on 1D sensor data.