摘要：Similarity search is a difficult problem and variousindexing schemas have been defined to process similarityqueries efficiently in many applications, includingmultimedia databases and other repositories handlingcomplex objects. Metric indices support efficientsimilarity searches, but most of them are designedfor main memory. Thus, they can handle onlysmall datasets, suffering serious performance degradationswhen the objects reside on disk. Most reallifedatabase applications require indices able to workon secondary memory.Among a plethora of indices, the List of ClusteredPermutations (LCP) has shown to be competitivein main memory.We introduce a secondary-memoryvariant of the LCP, which maintains the low numberof distance evaluations when comparing the permutationsthemselves, and also needs a low number of I/Ooperations at construction and searching.
关键词：metric spaces; permutation-based algorithm;list of clusters; secondary memory
