Finding Good Permutants for Proximity Searching in Metric Spaces
The permutation index has shown to be very effective in medium and high dimensional metric spaces, even in difficult problems, for instance, when it is used to solve reverse k-nearest neighbor queries. Nevertheless, currently there is no study about which are the desirable features one can ask to a permutant set, or how to select good permutants. Similar to the case of pivots, oar experimental results show that, compared with a randomly chosen set, a good permutant set yields to fast query response or to reduce the amount of space used by the index. In this paper we start by characterizing permutants and studying their discrimination power. Next, we propose an effective heuristic to select a good permutant candidate set. Finally, we give another heuristic to refine that candidate set We also show empirical evidence that supports our technique.
component metric space indexing probabilistic algorithms indexing permutations
Karina Figueroa Mora Rodrigo Paredes
Facultad de Ciencias Fisico Matematicas Universidad Michoacana Morelia, Mexico Department of Computer Science University of Talca Talca, Chile
国际会议
成都
英文
320-323
2010-12-17(万方平台首次上网日期,不代表论文的发表时间)