基于抽样的大数据聚合查询系统的研究与实现

摘要

关于大数据的研究，近几年已经迅速成为了学术界和工业界广泛关注的焦点。用户希望通过对大数据的分析处理挖掘出隐藏在数据间的关联关系，获得更多深入的、智能的、有参考价值的信息。由于其数据量大且稀疏的特性，使得传统的精确查询系统难以满足用户在效率上的要求。与此同时，用户在针对大数据进行分析挖掘时所提出的查询可以理解为目的性不够明确的探索性查询，其特点为:用户对其结果的准确性要求并非十分严格。 为了支持面向稀疏型大数据的分析及挖掘，有必要开发一个探索性查询处理系统，实现敏锐的发现及快速的探索。依次通过理论研究、算法设计、系统实现以及实验验证等阶段，最终初步完成了该查询系统。该系统可根据用户的历史查询行为，提供个性化样本更新;希望在总体误差的约束内获得近似的查询结果，以权衡查询结果的准确性和误差率。 论文将重点阐述该查询系统中的关键技术:基于抽样技术的稀疏型大数据的聚合查询优化算法。为此，以真实可靠的数据集为应用背景，在以下几个方面进行了相关研究。 首先，从数据角度对原始数据处理进行理论分析，从查询角度对用户聚合查询模式进行理论分析，从而完成对该系统的理论性定位。创建分层样本前需要对查询的模式进行分类，以确定历史查询与未来查询相似性的假设关系，避免过度拟合的情况发生。通过对数据以及查询的理论分析，该系统最终选择可预测查询列集(Predictable Query Column Sets)模型指导数据样本的创建，实现对查询结果在效率上的提升。 其次，确定系统的整体结构设计，分为离线计算以及在线计算这2部分。其中，离线部分完成样本池的创建，样本池将通过该系统的样本创建模块完成。抽样方案设计为简单随机抽样（Simple Random Sample，SRS）与分层抽样(Stratified Sample)相结合的形式，通过解决合理选择分层样本的分层查询列集(Query Column Sets，QCSs)以及确定分层样本中各组的元组个数等问题，完成样本池的创建。系统的在线部分完成用户实时到来的查询。该查询将通过系统的样本选择模块完成。用户查询请求给定的误差率及置信度确定了样本池中样本的选择及被选择样本的二次分割量，基于最终样本完成查询计算。 然后，用户查询中涉及的属性组合将被统计与分析，直接影响样本池更新时查询列集的分布，从而影响样本的创建。系统希望为用户在各方面提供个性化的优化服务。 最终，将系统部署于MySQL Cluster上，完成对数据的分布式处理。该系统将电影评分数据作为原始数据，通过样本创建及样本选择，实现了对用户查询请求的高效反馈，且查询结果符合用户的误差约束条件。并且，通过模拟的查询请求测试集对系统“个性化”服务的适应性进行了测试。结果表明，随着用户关注属性的变化，呈现了与之相适应的样本集合。整体看来，该系统较传统的精确查询系统更加适合于稀疏型大数据的分析与信息挖掘。

目录

声明

摘要

第1章绪论

1．1研究背景

1．1．1大数据的查询处理研究

1．1．2稀疏性数据研究

1．1．3抽样技术及典型应用

1．1．4个性化需求

1．2研究内容

1．3主要贡献

1．4论文组织结构

第2章相关工作

2．1数据仓库中的数据分析技术

2．2模式分析

2．2．1查询模式分析

2．2．2离线计算与在线计算模式分析

2．3抽样策略

2．4 MYSQL Cluster

2．5本章总结

第3章原型系统概述及问题定义

3．1原型系统概述

3．2问题定义

3．2．1样本创建模块问题定义

3．2．2样本选择模块问题定义

3．3形式化定义

第4章样本创建模块

4．1样本创建算法

4．1．1创建简单随机样本

4．1．2创建单个分层样本

4．1．3分层样本存储结构

4．2创建分层样本集合

4．2．1 QCS的选择因素

4．2．2 QCS的选择算法

4．2．3个性化分层样本更新

4．3本章小结

第5章样本选择模块

5．1样本选择策略

5．1．1随机样本的在线选择

5．1．2分层样本的在线选择

5．2查询请求的处理

5．2．1分层子样本大小的确定

5．2．2查询日志统计模块

5．3本章小结

第6章系统实现与实验评价

6．1实现环境详述

6．1．1实验环境和数据集

6．1．2环境架构实现

6．1．3数据预处理

6．2样本创建的实现与分析

6．2．1 K值的选择

6．2．2实现初始样本建立

6．2．3实现动态样本建立

6．3查询性能分析

6．3．1个性化交互式查询

6．3．2该系统与精确查询的比较

6．4个性化服务性能分析

6．5单节点与集群性能的比较

6．6本章小结

第7章总结与展望

7．1内容总结

7．2未来展望

参考文献

致谢

攻硕期间参加的项目及发表的论文