| Monitoring nearest neighbor queries with cache strategies |
| |
| 作者姓名： | PAN Peng LU Yan-sheng |
| |
| 作者单位： | College of Computer Science and Technology，Huazhong University of Science and Technology，Wuhan 430074，China |
| |
| 基金项目： | Project (No.ABA048) supported by the Natural Science Foundationof Hubei Province,China |
| |
| 摘 要： | The problem of continuously monitoring multiple K-nearest neighbor (K-NN) queries with dynamic object and query dataset is valuable for many location-based applications. A practical method is to partition the data space into grid cells, with both object and query table being indexed by this grid structure, while solving the problem by periodically joining cells of objects with queries having their influence regions intersecting the cells. In the worst case, all cells of objects will be accessed once. Object and query cache strategies are proposed to further reduce the I/O cost. With object cache strategy, queries remaining static in current processing cycle seldom need I/O cost, they can be returned quickly. The main I/O cost comes from moving queries, the query cache strategy is used to restrict their search-regions, which uses current results of queries in the main memory buffer. The queries can share not only the accessing of object pages, but also their influence regions. Theoretical analysis of the expected I/O cost is presented, with the I/O cost being about 40% that of the SEA-CNN method in the experiment results.
|
| 关 键 词： | K-最近邻查询 高速缓存策略 连续查询 监测 |
| 收稿时间： | 2006-10-13 |
| 修稿时间： | 2006-12-29 |
Monitoring nearest neighbor queries with cache strategies |
| |
| PAN Peng LU Yan-sheng.Monitoring nearest neighbor queries with cache strategies[J].Journal of Zhejiang University Science,2007,8(4):529-537. |
| |
| Authors: | Pan Peng Lu Yan-sheng |
| |
| Institution: | (1) College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, 430074, China |
| |
| Abstract: | The problem of continuously monitoring multiple K-nearest neighbor (K-NN) queries with dynamic object and query dataset is valuable for many location-based applications. A practical method is to partition the data space into grid cells, with both object and query table being indexed by this grid structure, while solving the problem by periodically joining cells of objects with queries having their influence regions intersecting the cells. In the worst case, all cells of objects will be accessed once. Object and query cache strategies are proposed to further reduce the I/O cost. With object cache strategy, queries remaining static in current processing cycle seldom need I/O cost, they can be returned quickly. The main I/O cost comes from moving queries, the query cache strategy is used to restrict their search-regions, which uses current results of queries in the main memory buffer. The queries can share not only the accessing of object pages, but also their influence regions. Theoretical analysis of the expected I/O cost is presented, with the I/O cost being about 40% that of the SEA-CNN method in the experiment results. |
| |
| Keywords: | K-nearest neighbors (K-NNs) Continuous query Object cache Query cache |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
|
