摘 要

在数据挖掘等对大数据的应用中，对流数据的查询多以多重叠查询的形式存在，因此对于多重叠查询的优化能有效的提高查询效率。本文研究了针对多重叠查询的 固定策略、自适应策略和贪心自适应策略，并最终实现了贪心自适应策略。同时考虑到多重叠查询本身的条件共享特点，可以将查询的关系和点抽象成一个带权无向图，而当前对流数据的处理也多以分布式的形式处理，因此本文继续研究了基于图论的分割方法，并介绍了其最小割和Normalized Cut这两种基本的分割方法，最后实现了Normalized Cut方法。集成两种算法并用系统模拟实验，实验结果表明图分割后能减少处理的时间，使得查询的效率提高。

关键词：多重叠查询；图分割；共享查询；Normalized Cut

Abstract

In the application of data mining and other large data, the query of convective data mostly exists in the form of multi-overlapping query, so the optimization of multi-overlapping query can effectively improve the query efficiency. In this paper, we study the fixed strategy, adaptive strategy and greedy adaptive strategy for multi-overlapping query, and finally realize the greedy adaptive strategy. At the same time, taking into account the conditional sharing characteristics of the multi-overlapping query itself, the relationship and the point of the query can be abstracted into a weighted undirected graph, and the current convective data processing is also distributed in the form of distributed, so this paper continues to study the On the division of the method, and introduced the minimum cut and Normalized Cut these two basic segmentation method, and finally realized the Normalized Cut method. The two algorithms are integrated and simulated by the system. The experimental results show that the time of processing can be reduced after segmentation, and the efficiency of the query is improved.

Key Words：Multi-overlapping query;Segmentation;Shared query;Normalized Cut

目录

第一章 绪论 1

第二章 准备工作 2

2.1基本模型 2

2.2需求条件 2

2.3共享度 2

2.4基本算法模型 3

2.5基本成本模型 4

第三章 贪心自适应策略 6

3.1固定策略 6

3.2自适应策略 7

3.3基于贪心的自适应策略 9

3.4小结 10

第四章 图分割 12

4.1引入 12

4.2图分割及最小割 13

4.3 Normalized Cut 13

第五章 结果 15

第六章 总结 16

参考文献 17

致 谢 19

第一章 绪论

1.1研究背景及意义

目前随着网络化、智能化和自动化的发展趋势，流数据的处理尤为重要。所谓流数据是指由多个，通常是成百上千甚至更多，数据源持续不断地生成的一组大量、快速、连续到达的数据序列。流数据多应用于网络数据、传感器网络、气象监控、金融服务等领域，例如生活中各种软件生成的日志数据、视频监控、网购数据以及数据中心连接的各种设备或者仪器的遥测数据等。而对于流数据的多种分析而得到的各种信息可以让公司、研究中心等实时了解其业务或者研究内容的各个方面，进而可以做出更好的反应，因此针对流数据的处理就显得尤为重要。

流数据的一种处理就是针对流数据做连续查询，根据某些条件到即将到来的流数据中去查询进而获得我们需要的数据内容，而目前针对流数据的连续查询多以多重叠查询任务的形式存在，为了提高查询任务的执行效率，对查询任务的优化技术的要求显著，而条件共享概念正成为大规模多查询任务优化的基础。在大数据环境下，由于数据规模增大，以及流数据本身特性带来的数据分布不确定的影响，对实际处理中的资源共享问题带来了挑战，多数据流的环境也对分布式查询计算提出了需求。

研究及优化多重叠查询任务，能够使得针对流数据的连续查询得到优化，提高了查询效率，能够有效的降低查询成本，进而使得企业、研究中心等应用流数据得到的信息能够更快速地做出反应或者应对，提高企业生存力和竞争力。

1.2研究内容和目标

本文主要研究了在一般条件下，针对共享子条件的多重叠查询任务的特点，如何去确定处理子条件的顺序进而使得解决所有查询任务所花费的成本最少，从最基本的处理策略逐步优化到一个较好的策略，并实现一种处理策略。优化处理策略只是减少了花费的金钱等成本，而处理每个子条件的时间也许很小，但在流数据的背景下，处理所有的子条件的时间花费仍然会变得很大。同时由于查询任务和共享子条件的关系可以抽象成一张图，所以本文还研究了图分割的一些基本方法，通过图分割将查询任务和子条件划分，然后采用分布式去并行计算，进而使得时间减少，研究了基本的两种图分割算法实现一种图分割算法，最终模拟实验对比使用和不适用分割算法的时间开销。本文的预期研究目标是实现一种较好的共享执行策略和一种图分割算法，并结合两种算法，比较分割前后处理同样任务所需要的时间，进而证明将图分割算法应用于多重叠查询任务的优化是可以有效的提高查询效率的。

1.3本文的结构

本文的整体结构如下：

第一章是绪论，主要介绍了本文的研究背景、意义、内容以及预期目标等。

第二章是准备工作，主要是多重叠查询定义的引入，共享执行策略的引入，共享执行策略基本的算法模型和成本模型等。

第三章是共享执行策略，由基本的共享执行策略入手，并逐步优化，得到一个较好的共享执行策略，使其成本较小。