This collaborative research project conducted jointly by the Michigan State University and the University of Michigan at Dearborn investigates the issues and techniques for supporting efficient similarity searches in multidimensional Non-ordered Discrete Data Spaces (NDDS). Similarity searches in NDDSs are becoming increasingly important for applications based on multidimensional discrete vectors, such as genome sequence databases, biometrics and E-commerce. Efficient similarity searches require robust indexing techniques in order to provide fast access to data. The currently existing indexing methods are either not suitable for an NDDS (e.g., the R*-tree) or too generic to provide good performance for an NDDS (e.g., metric trees). The main goal of this project is to study the fundamental properties of NDDSs and develop indexing methods exploiting these properties to support efficient similarity searches in NDDSs. A set of essential geometric concepts for an NDDS is introduced based on extended methods for traditional (ordered) continuous data spaces. A number of promising data-partitioning-based and space-partitioning-based indexing techniques (including index tree structures, building strategies, search algorithms and performance models) using these concepts for NDDSs are explored and compared. Other related issues including supporting various types of queries, adopting different distance measures, indexing hybrid data spaces with mixed ordered and non-ordered dimensions, developing efficient bulk loading techniques and utilizing effective compression schemes are studied. This research will provide new database indexing techniques to solve relevant issues in scientific, medical and commerce fields that require fast access to large volumes of NDDS data. Research results, including software tools or programs and experimental data will be disseminated via the projects' Web sites (www.cse.msu/~pramanik/nsf05/nsf05msu.html and www.engin.umd.umich.edu/~qzhu/nsf05/nsf05umd.html).
