Boosting the Permutation Based Index for Proximity Searching
Boosting the Permutation Based Index for Proximity Searching
复制标题
增强邻近搜索的基于排列的索引
DOI：
10.1007/978-3-319-19264-2_11
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Rodrigo Paredes
中科院分区：
文献类型：
--
作者：
Karina Figueroa;Rodrigo Paredes
接近搜索包括从数据库中检索与给定查询相似的对象。在多媒体数据库蓬勃发展的今天，这是一项基本任务。基于排列索引的PBI及其变体是解决高维空间接近搜索问题的优秀方法，但在低维空间中难以克服。PBI的另一个缺点是排列之间的距离不允许在解决相似查询时安全地丢弃元素。
Proximity searching consists in retrieving objects out of a database similar to a given query. Nowadays, when multimedia databases are growing up, this is an elementary task. The permutation based index PBI and its variants are excellent techniques to solve proximity searching in high dimensional spaces, however they have been surmountable in low dimensional ones. Another PBI's drawback is that the distance between permutations cannot allow to discard elements safely when solving similarity queries.
In the following, we introduce an improvement on the PBI that allows to produce a better promissory order using less space than the basic permutation technique and also gives us information to discard some elements. To do so, besides the permutations, we quantize distance information by defining distance rings around each permutant, and we also keep this data. The experimental evaluation shows we can dramatically improve upon specialized techniques in low dimensional spaces. For instance, in the real world dataset of NASA images, our boosted PBI uses upi¾?to 90i¾?% less distances evaluations than AESA's, the state-of-the-art searching algorithm with the best performance in this particular space.