集合值索引关键技术研究

集合无处不在，集合查询分为集合包含查询和集合相似度查询两部分，在很多领域有广泛的应用，但同时面临集合数据量的不断增长、查询日益复杂的挑战。集合查询以高效的索引技术为基础，在基于统计分析、关联规则挖掘等方法深入分析集合数据统计特性的基础上，拟从全面、高效及并行化三个角度来研究集合索引结构和算法。首先，拟设计支持多种不同集合查询谓词的基于trie和反向索引的混合索引结构，以解决传统集合值索引结构只支持部分查询谓词或效率较低的问题；其次针对反向索引结构，通过物化部分频繁访问的反向列表交集结果，解决幂律分布下长列表交集效率低下的问题；最后，研究基于GPU的高效的索引结构和算法的高效实现，设计高效的并行集合查询架构，以进一步提高集合查询的效率。项目组拟开发集合数据综合查询平台，验证提出的索引结构和算法的有效性。本项目的研究成果，将对集合数据管理技术的完善和提高提供有益的补充。

Set is ubiquitous and set queries exist extensively in a large number of fields, such as database, data mining, information retrieval and biological information system. Set queries are facing challenges of ever-growing set sizes and ever-complexing queries. Efficient indexing is the way to efficient set queries. This project mainly aims at researching comprehensive, efficient and parallel set indexes and corresponding set querys based on the anlysis of the datasets in detail by statistics and association rule mining. Firstly, there are only partial predicates supported or all predicates but with low efficiency for traditional indexes. To solve this problem, this project aims to design efficient indexes based on trie and inverted index. Secondly, this project tries to solve the problem of power-law distribution in inverted index by materilizing the intersection of long lists which are frequently accessed. At last, this project researches parallel set indexing and queries on morden GPU platform. Comprehensive platform for set-valued data will be designed to evluate the efficiency of indexing and algorithms proposed. The main research achievements can be beneficial to the improvement and perfection of set data management.