支持摘要搜索的数据库多维动态索引技术研究

As the development of the Internet and the diversification of sources of data collection, processing and analyzing such massive data becomes a central problem of the database community. Current database queries can be broadly classified into two categories: reporting queries and aggregation queries. The former returns the whole data which is accurate, but cannot handle massive data; while the later is efficient yet not expressive enough, as it only returns some simple statistics of the data...In this project, we aim at developing data structure techniques for the summary query problem. A summary query proposes some query constraints, and retrieves a summary for the data that matches the query constraint. To achieve this goal, we plan to focus on the research of merging non-orthogonal summaries, non-self-maintain summary update algorithms and dynamic error parameter supports. We plan to illustrate the efficiency and usefulness of our designs through extensive experiments and a system demonstration.

随着互联网技术的发展和数据收集渠道的多样化,如何处理和分析随之产生的海量数据成为当前数据结构研究中的核心关键问题之一。目前的数据库查询可以大致分为报告查询(reporting query)与聚合查询(aggregation query)。前者精确返回所有符合查询条件的数据，但无法处理海量数据；后者效率较高，但只能返回数据的单个统计量，无法刻画数据分布。.本项目针对以上数据库查询的缺陷，计划研一类支持摘要查询的数据库索引技术。摘要查询是一类新型数据库查询，其目标是在给定查询条件后，高效率地返回关于所有符合条件的数据的一个摘要，用于刻画元数据的分布。本项目针对传统数据库应对海量数据分析的挑战，以实现支持摘要搜索的多维动态数据库索引作为基本目标，通过对非正交范围摘要合并技术、非自维护摘要重建算法以及动态误差参数集成的研究，最终与实际数据库紧密集成并开发支持摘要搜索的数据库原型系统。

针对传统数据库查询的缺陷，项目计划研究一类支持摘要查询的数据库索引技术。摘要查询是一类新型数据库查询，其目标是在给定查询条件后，高效率地返回关于所有符合条件的数据的一个摘要，用于刻画元数据的分布。在课题执行过程中，针对对数据库中近似算法，我们研究了图数据库中各类相似度的近似算法，通过采样等摘要技术，大幅降低了相似度计算的复杂度，为实现百亿规模图上毫秒级相似度查询提供了理论基础。对多维度数据数据，本课题研究了高维度数据以矩阵形式存储时的近似算法，通过矩阵略图等技术，将高维数据转化为低维数据，实现了高精度低延时的转化算法。针对传统多维度索引树对摘要查询的研究，本课题研究了多维度索引树对于均匀独立采样查询与权重独立采样查询的支持。该类查询可进一步用于支持任意摘要查询，是摘要查询基础算法的进一步扩展。