| Rav-tree:一种有效支持反向近似近邻查询的索引结构 |
| |
| 引用本文： | 李博涵,郝忠孝.Rav-tree:一种有效支持反向近似近邻查询的索引结构[J].计算机科学,2010,37(1):158-162. |
| |
| 作者姓名： | 李博涵 郝忠孝 |
| |
| 作者单位： | 1. 哈尔滨理工大学计算机科学与技术学院,哈尔滨,150080
2. 哈尔滨理工大学计算机科学与技术学院,哈尔滨,150080;哈尔滨工业大学计算机科学与技术学院,哈尔滨,150001 |
| |
| 基金项目： | 国家自然科学基金项目(60673136);;黑龙江省自然科学基金项目(F200601)资助 |
| |
| 摘 要： | 空间数据库的索引结构是实现有效数据查询的前提和基础。空间数据反向近似近邻查询是空间查询的一个新方向,它避免了精确查询中过多的距离计算,从而能够在效率与准确性上取得平衡。提出的Rav-tree不同于基于启发式规则的索引结构,首先利用局部近似,然后根据Voronoi cell区域和估计圆的方法实现近似近邻查询,并利用过滤结果和分域查询得到初步的候选集,最终通过反向近似近邻查询(RANNQuery)算法得到RANN集,并完整地给出基于Rav-tree的ANN查询算法和RANN查询算法。实验结果表明,Rav-tree对RANN等查询具有较好的查询效率和查全率。
|
| 关 键 词： | 索引结构 反向近似近邻 分域查询 区域估计 |
| 收稿时间： | 2009/2/20 0:00:00 |
| 修稿时间： | 5/2/2009 12:00:00 AM |
Rav-tree:An Efficient Index Structure for Reverse Approximate Nearest Neighbor Query |
| |
| LI Bo-han,HAO Zhong-xiao.Rav-tree:An Efficient Index Structure for Reverse Approximate Nearest Neighbor Query[J].Computer Science,2010,37(1):158-162. |
| |
| Authors: | LI Bo-han HAO Zhong-xiao |
| |
| Affiliation: | College of Computer Science and Technology/a>;Harbin University of Science and Technology/a>;Harbin 150080/a>;China;College of Computer Science and Technology/a>;Harbin Institute of Technology/a>;Harbin 150001/a>;China |
| |
| Abstract: | Index structure is the precondition and foundation in the efficient data query.The reverse approximate nearest neighbor query is a new issue in the area of spatial query.This approach can avoid much metric distance computation in exact query,and acquire a better tradeoff between the efficiency and precision.The Rav-tree is different from the index structures based on the heuristic rules.It applies partial Voronoi cell approximation with estimated circles to filter the results of approximate nearest neighbor... |
| |
| Keywords: | Index structure Reverse approximate nearest neighbor Division query Region estimation |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
