Efficient Top-k Result Diversification for Mobile Sensor Data

Due to recent developments in sensor technologies, mobile sensor device use has become widespread, and many researchers have been attempting to leverage data collected by these devices. We call such data 'mobile sensor data'. Mobile sensor data are geo-referenced data with environmental attribute values, and they enable us to determine the geographical distribution of hot spots by retrieving data (such as higher air-pollution index values) with comparatively extreme environmental attribute values. Top-k search result diversification in geographical space is valid for applications of this sort. However, the preference scores for data items are different from each user's interest, and must be calculated for each query from scratch. In this case, the computational cost of a naive method is excessively high when the amount of mobile sensor data is very large. Thus, in this paper, we propose an efficient top-k search result diversification method for mobile sensor data. In a naive method, it is necessary to scan all data existing in a given query range when seeking the best data. Our proposed method, however, can reduce the amount of scanned data by exploiting cluster information, and the query result can thereby be returned much more rapidly. Moreover, a number of optimization problems can be solved using only one cluster file set. Experimental results show that our proposed method involves short computation time and reduces the disk IO cost in comparison with a naive method.