A feature-based indexing for spatial data objects

We propose a feature-based indexing method for spatial data objects. The aim is to efficiently retrieve the data objects as well as similar objects with a given query object in a spatial database environment. Our method extracts some features from each data object in order to build an index tree. A broad range of problems and issues such as indexing and modeling, similarity matching, transformations, features and spatial access methods must be dealt with in any feature-based indexing method. Our work consists of two parts. First, we propose a framework for feature-based indexing of image data and apply our method to the damage zone shapes of materials. A set of generic features which are invariant to rotation, translation and scaling for the sake of similarity matching are proposed. These features form a feature vector for each image. The feature vectors are extended with some domain specific features. The feature vectors are used to build the index structure. Any multi-dimensional point access method can then be used to build the index. However we use a variant of the K-D-B tree. Weighted Euclidean distance is used as similarity measure. Each feature in the feature vector is associated with a weight, based on the application, which is used in the search process for similarity matching. A formula is proposed to find the similarity of nodes in the index tree with a given query shape. This formula is used to prune the search tree in the query processing.; In the second part, we propose two inter-sequence matching methods for exact and similarity matching of image sequences. We assume that the image sequence matching problem is transformed into matching sequences of real numbers. The methods do not require sequences to have the same length. The first method tries to find the Longest Matching Subsequences (LMS) of two sequences to be matched and uses a modified version of the Longest Common Subsequence (LCS) method for actual matching. In the second method, a modified version of restricted edit distance is used for matching. We also propose a feature-based indexing mechanism to filter out those sequences which are matching candidates with a given query sequence from a large data set. Like all other feature-based indexing methods, our method maps each sequence into a point in K dimensional space, where K is the number of extracted features for the sequence. It operates in two phases, hypothesizing and verification. Lengths and moments (mean and variance) of sequences are used as features. Experimental results indicate that the features and proposed method for query processing perform well as a filter.