Distance-based indexing and its applications in bioinformatics
Daniel P. Miranker, Rui Mao · 2007
Distance-based indexing is a general solution to the problem of searching based on similarity of complex data types. Distances between pairs of data objects are specified by a metric function, which is positive definite, symmetric and satisfies the triangle inequality. Distance-based indexing is exploited in many data intensive applications, such as multimedia and biological databases. This dissertation concerns distance-based indexing in the context of the MoBIoS (Molecular Biology Information System) project, a next generation DBMS aimed at bioinformatics applications. The three primary contributions of this dissertation include evaluation and improvement of existing distance-based index structures, a pivot space model for the pivot selection problem of distance-based indexing and the MoBIoS Index software package. For the first part, we designed a bi-directional construction algorithm for Metric Tree (M-tree). It increased the construction speed and improved the query performance. Then, we conducted a comparative analysis of the performance of M-tree, General Hyper-plane Tree (GHT) and Vantage Point Tree (VPT) on biological work loads, and VPT turned out to be the optimal choice. Further, we designed better heuristics for pivot selection and partition of VPT. Superior to multi-dimensional indexing in its generality, distance-based indexing is difficult by virtue that no coordinate structure is available and thus many mathematical tools in Rn cannot be applied. A common method used is to map the metric space into Rn and then apply geometric methods. Summarizing this method, we propose the pivot space model, which demonstrates the validity of tackling distance-based problems in Rn. Further, we study distance-based indexing from the perspective of dimension reduction. We prove that the only form of dimension reduction leading to performance gain for distance-based indexing is pivot selection, which does not create new dimensions. To adapt general dimension reduction techniques to distance-based problems, we propose a heuristic that approximates the dimensions created by dimension reduction. As a demonstration, a dimension reduction algorithm and a method to estimate the intrinsic dimension of data are proposed based on Principal Component Analysis (PCA). These ideas are evaluated on a test suite consisting of synthetic and real workloads. The MoBIoS Index was released in 2006. It supports similarity queries for user defined data types and distance functions. It has been used to build several biological application.