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

协作研究：支持多维非有序离散数据空间的高效相似性搜索

• 批准号: 0414576
• 负责人: Sakti Pramanik
• 金额: --
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0414576&HistoricalAwards=false
• 关键词: Collaborative; Research; Supporting; Efficient; Similarity

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).

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