Efficient Reuse of Metric Indexes for Multi-resolution Queries

Performing similarity queries using resolutions different from those used for the data employed during the index construction is a challenge for traditional Metric Access Methods (MAMs). Varying data resolution occurs, for example, in scenarios involving reduced data fidelity, such as when reducing data resolution for efficient network transmission. This work proposes a novel way to extend a MAM, using the Slim-tree as a case study, to efficiently and adaptively support queries over transformed data using indices built using only the original, full-resolution data. The proposed approach modifies the pruning heuristic to incorporate safe upper bounds on distances in the transformed domain, guaranteeing correct query results while preserving much of the pruning power of the original MAM. Experimental results on image datasets demonstrate substantial performance improvements over sequential search, even under conditions of high compression.