大数据确定性近似查询算法关键技术研究

Faced with big data with explosive growth rate, current query algorithms cannot return the exact query result in an acceptable response time, which affects the query interaction and users’ productivity severely. Thus, approximate query processing has become an important research issue in big data analytics. It is analyzed that most of the existing approximate query algorithms are focused on basic queries, some of them are based on the regularity assumption and some have the problem of poor scalability. Therefore they cannot process approximate query on big data in general cases efficiently. This proposal proposes a new type of approximate query, i.e. deterministic approximate query, which returns the approximate results satisfying users’ requirement with the deterministic approximation. This proposal will research on the key techniques of deterministic approximate query algorithm on big data, striving for the optimal trade-off between the approximation degree and execution cost. The proposal aims to study the mathematical abstraction and storage structure of deterministic approximate query on big data, deterministic approximate basic query algorithms on big data, and deterministic approximate complex query algorithms on big data. This proposal will propose a series of theories, techniques and methods about deterministic approximate query on big data. Finally, the prototype system of deterministic approximate query on big data will be developed to evaluate the validity and efficiency of the algorithms proposed in this proposal.

数据的爆炸性增长使得现有查询算法无法快速返回大数据上的准确查询结果，严重影响查询交互性和用户工作效率，因此近似查询已成为目前大数据查询处理的一个重要研究问题。通过分析发现，现有的大多数近似查询算法在实际应用中集中于基本查询，并且或者依赖于底层数据的正则性分布，或者存在扩展性较差的问题，无法有效处理大数据在一般情况下的近似查询问题。本项目提出一类新的近似查询类型，即确定性近似查询，该查询以确定性近似度返回满足用户要求的近似结果。本项目拟以查询结果的确定性近似度和执行代价的优化折衷为目标，研究大数据确定性近似查询算法的关键技术，包括大数据确定性近似查询的数学抽象及存储结构、大数据确定性近似基本查询算法、大数据确定性近似复杂查询算法，拟提出一系列有关大数据确定性近似查询算法的理论、技术和方法，并实现大数据确定性近似查询原型系统，验证本项目所提出方法的正确性和有效性。

大数据的出现使得数据驱动的决策方法成为目前商业、科学甚至政府执行决策的主要方法，现有查询算法无法快速返回大数据上的准确查询结果，严重影响查询交互性和用户工作效率，近似查询处理技术正成为目前大数据计算的热点研究问题。为解决现有近似查询算法不能有效解决大数据近似查询的问题，本项目主要研究大数据确定性近似查询算法的关键技术，针对具体的近似查询应用设计有效的大数据确定性近似查询算法，提出互补抽样、裁剪策略、早结束策略、综合索引结构、计算重用方法、多层数据概要、条件生成模型、代表性结果选择、近似压缩等关键方法来解决大数据确定性近似查询算法的性能问题。在本项目支持下，项目组聚集在大数据确定性近似查询算法研究，分别在轨迹大数据近似最大范围和查询、不完整大数据近似skyline查询、大规模SIOT网络数据近似社交空间关键词搜索、大数据近似G-Skyline查询、大数据top/bottom k分数查询估计方法、大数据高效近似查询处理框架等方面取得较大研究进展，已发表高水平论文14篇，授权专利4项。本项目的研究成果表明，课题组提出的近似查询算法比现有方法，无论在执行时间、内存消耗和磁盘费用方面，都表现出较大的性能优势，在大数据上可以高效返回用户需要的查询结果。