Approximate Algorithms for Similarity Search using Hierarchical Spatial Indexes
When hierarchical similarity search indexes such as R-tree are employed, the answer to a nearest neighbor query comes at a great cost Particularly, the cost is very high when the answer is far away from the query. In many cases, the cost to confirm that an answer is optimal is much higher than the cost required for finding the answer. In other words, the real answer comes quickly but a long and expensive refinement process is required afterwards. To overcome these problems, we investigate approximate algorithms for spatial indexes which reduce the number of distance computations by early termination. Based on these observations, we propose a technique that terminates the process when no more refined answer can be expected by additional distance computations. This technique focuses on distance computations to guarantee that the candidate answer is optimal at the final stage. We experimentally show that our proposed approach can reduce the search cost to 25％ ~ 10％ while keeping the error rate low. Our technique is especially effective for far queries.
component query processing aproximation algorihtm r-tree
Yohei Iwasaki Takaaki Aoki Kei Tashima Arnold Jose Muller-Molina Takeshi Shinohara
Department of Artificial Intelligence Kyushu Institute of Technology Kawazu 680-4, lizuka. Fukuoka, Japan
国际会议
重庆
英文
195-199
2011-01-21（万方平台首次上网日期，不代表论文的发表时间）