On Metric-Space Indexing and Real Workloads
Rui Mao, Ving I. Lei, Smriti R. Ramakrishnan, Weijia Xu, Daniel P. Miranker · 2005
Contemporary technology is fostering new demands to manage large collections of complex data, including the contents of multimedia and biological databases. In many cases the similarity of the data is defined using a metric distance function. There are many competing algorithmic approaches which, off-line, create data structures materializing a hierarchical clustering of the data and leverage the triangle inequality to speed the search for similar data. In order to determine a solution of general applicability it is important to assess the variety of methods on various types of real world data. We evaluate the performance of an algorithm from each of the three major classes of metric-space indexing methods: generalized hyper-plane, vantage point, and radius-based methods. The workloads comprise an image database, a yeast protein sequence database and a database of mass spectrometer protein signatures. For range queries of practical interest the multi-vantage point algorithm (MVP-trees) is shown to be superior. We further consider the optimization of MVP-trees. We consider a common heuristic, choosing corners as vantage points, and show that on real workloads choosing centers perform better. 1.