A Top-k Query Method by Estimating Score Distribution in Mobile Ad Hoc Networks

In mobile ad hoc networks (MANETs), to acquire only necessary data items, it is effective that each mobile node retrieves data items using a top-k query, in which data items are ordered by the score of a particular attribute and the query-issuing mobile node acquires data items with k highest scores. In this paper, we propose a query processing method for top-k query for reducing traffic and also keeping high accuracy of the query result. In this method, each mobile node constructs a histogram from the scores of its holding data items and estimates the distribution of scores of all data items and k-th score in the entire network. This histogram is attached with query messages and replies so that other mobile nodes can estimate the score distribution and k-th score more accurately. When transmitting a reply, each mobile node sends back only data items whose scores that are larger than the estimated k-th score to reduce traffic as much as possible. We also present simulation results to evaluate the performance of our proposed method.