Effective protocols for kNN search on broadcast multi-dimensional index trees |
| |
Authors: | Chuan-Ming Liu Shu-Yu Fu |
| |
Affiliation: | Department of Computer Science and Information Engineering, National Taipei University of Technology, Taipei 106, Taiwan |
| |
Abstract: | In a wireless mobile environment, data broadcasting provides an efficient way to disseminate data. Via data broadcasting, a server can provide location-based services to a large client population in a wireless environment. Among different location-based services, the k nearest neighbors (kNN) search is important and is used to find the k closest objects to a given point. However, the kNN search in a broadcast environment is particularly challenging due to the sequential access to the data on a broadcast channel. We propose efficient protocols for the kNN search on a broadcast R-tree, which is a popular multi-dimensional index tree, in a wireless broadcast environment in terms of latency and tuning time as well as memory usage. We investigate how a server schedules the broadcast and provide the corresponding kNN search algorithms at the mobile clients. One of our kNN search protocols further allows a kNN search to start at an arbitrary time instance and it can skip the waiting time for the beginning of a broadcast cycle, thereby reducing the latency. The experimental results validate that our mechanisms achieve the objectives. |
| |
Keywords: | Data dissemination Multi-dimensional index trees Latency Tuning time kNN search Memory usage |
本文献已被 ScienceDirect 等数据库收录! |
|