Multi-dimensional Top-κ Dominating Query Processing In Sensor Networks

Advances in sensor technology have given rise to new information retrieval applica-tions. For many sensor applications, such as abnormal event detection and animal behaviorchange, top-κ dominating query is a crucial problem which aims at returning k data pointswhich dominate the highest number of points in a data set. This query is an important toolwhich combines the advantages of top-κ and skyline queries such as controllable output sizeas well as no need for user preference functions, while without sharing their disadvantages.The system may want to extract snapshot top-κ dominating results from the networks foranalysis later.As the energy is limited which determines the life of the wireless sensor networks, it iscrucial for the algorithm to minimize the communication cost; meanwhile, even if the com-munication cost is kept in a low level, as there may be some sensor nodes bearing much morecommunication than others, the algorithm must try to distribute plainly the communicationcost among all sensors. It makes difficult the design of the algorithm that sensor readingsoften include multi-dimensional data and that any centralized algorithm is not allowed.To the best of our knowledge, this is the first work focusing on top-κ dominating querywith multi-dimensional sensor data. In the paper, we propose two algorithms and theirenhanced version. Firstly, we propose a naive algorithm which utilizes our observationthat the top-κ dominating query result is a subset of the top-κ query result. Then, with thehelp of Binary Space Partitioning(BSP) method, we propose our basic algorithm for furtherreducing the communication cost. Lastly, we enhance our naive and basic algorithmsbased on the fact that sensor data have temporal and spatial coherencies. We implementsimulations on both Intel Berkeley Lab data and synthetized data of three patterns. Weconsider the EXACT algorithm as the compared algorithm, which calls for every sensorto upload all concerned data to the sink; our simulation results show that our proposedalgorithms can dramatically reduce the communication cost compared with the EXACTalgorithm.