A Top-k Query Method by Estimating Score Distribution in Mobile Ad Hoc Networks
Yuya Sasaki, Ryo Hagihara, Takahiro Hara, Masako Shinohara, Shojiro Nishio · 2010
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.