Search K-Nearest Neighbors On Air
Conference Proceeding Article
While the K-Nearest-Neighbor (KNN) problem is well studied in the traditional wired, disk-based client-server environment, it has not been tackled in a wireless broadcast environment. In this paper, the problem of organizing location dependent data and answering KNN queries on air are investigated. The linear property of wireless broadcast media and power conserving requirement of mobile devices make this problem particularly interesting and challenging. An efficient data organization, called sorted list, and the corresponding search algorithm are proposed and compared with the well-known spatial index,R-Tree. In addition, we develop an approximate search scope to guide the search at the very beginning of the search process and a learning algorithm to adapt the search scope during the search to improve energy and access efficiency. Simulation based performance evaluation is conducted to compare sorted list and R-Tree. The results show that the utilization of search scope and learning algorithm improves search efficiency of both index mechanisms significantly. While R-Tree is more power efficient when a large number of nearest neighbors is requested, the sorted list has better access efficiency and less power consumption when the number of nearest neighbors is small.
KNN, location-dependent search, wireless broadcast, index structure, mobile computing
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
Mobile Data Management: 4th International Conference, MDM 2003 Melbourne, Australia, January 21-24, 2003: Proceedings
City or Country
ZHENG, Baihua; LEE, Wang-Chien; and LEE, Dik Lun.
Search K-Nearest Neighbors On Air. (2003). Mobile Data Management: 4th International Conference, MDM 2003 Melbourne, Australia, January 21-24, 2003: Proceedings. 2574, 181-195. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1064