Collaborative Research: Supporting Efficient Similarity Searches for Multidimensional Non-ordered Discrete Data Spaces

这个合作研究项目由密歇根州立大学和密歇根大学在迪尔伯恩联合进行调查的问题和技术，支持有效的相似性搜索多维无序离散数据空间（NDDS）。在基于多维离散向量的应用中，如基因组序列数据库、生物识别和电子商务等，NDDS中的相似性搜索变得越来越重要。有效的相似性搜索需要强大的索引技术，以提供快速访问数据。当前现有的索引方法要么不适合NDDS（例如，R* 树）或过于通用而不能为NDDS提供良好的性能（例如，公制树）。这个项目的主要目标是研究NDDS的基本属性，并开发利用这些属性的索引方法，以支持NDDS中的高效相似性搜索。基于传统的（有序）连续数据空间的扩展方法，引入了一组基本的几何概念的NDDS。一些有前途的基于数据分区和基于空间分区的索引技术（包括索引树结构，建设策略，搜索算法和性能模型）使用这些概念的NDDS的探索和比较。其他相关的问题，包括支持各种类型的查询，采用不同的距离措施，混合有序和无序维的混合数据空间的索引，开发高效的批量加载技术和利用有效的压缩方案进行了研究。这项研究将提供新的数据库索引技术，以解决科学，医学和商业领域的相关问题，需要快速访问大量的NDDS数据。研究结果，包括软件工具或程序和实验数据，将通过项目的网站（http：//www.cse.msu/nepramanik/nsf05/nsf05msu.html和http：//www.engin.umd.umich.edu/nepqzhu/nsf05/nsf05umd.html）传播。

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 (http://www.cse.msu/~pramanik/nsf05/nsf05msu.html and http://www.engin.umd.umich.edu/~qzhu/nsf05/nsf05umd.html).