Query Processing for Distance Metrics
Jason Tsong-Li Wang, Dennis E. Shasha · 1990
In applications such as vision and molecular biology, a common problem is to find the similar objects to a given target (according to some distance measure) in a large database. This paper presents a scheme for query pro-cessing in such situations. The basic strategy is to (par-tially) precompute inter-object distances, and by using the distance information and the triangle inequality, we eliminate the need to calculate certain object distances while evaluating queries. We propose several heuristics that may speed up query evaluation. A series of experi-ments are then performed to evaluate the effectiveness of our scheme and the relative performance of the heuristics for different queries. Finally we investigate the possibil-ity of parallelizing our scheme through simulation. Our results show that parallelism is best applied in the later stages in evaluating a query. 1