1. 研究目的与意义（文献综述）

目前基于流数据的应用往往涉及到多数据流的处理，例如传感器网络，而针对流数据的连续查询也以多重叠查询任务的形式存在，为了提高查询任务执行效率，对查询任务的优化技术的要求日益显著，而条件共享概念正成为大规模多查询任务优化的基础。在大数据环境下，由于数据规模增大，以及流数据本身特性带来的数据分布不确定的影响，对实际处理中的资源共享问题带来了挑战，多数据流的环境也对分布式查询计算提出了需求。

在多重叠查询中，每个查询都是一个或多个过滤器的交集集合，而每个过滤器都是可以存在在多个查询中，即对于我们的过滤器(查询子条件)的集合{F₁，F₂，…F_m}(其中m趋近无限大)和查询的集合{Q₁，Q₂，…Q_n}(其中n趋近无限大)，每一个查询Q_x(x∈{1,2, …n})，均有Q_x=F_y1∩F_y2…∩F_yk(其中y1，y2，…yk∈{1,2, …m})，而针对每个过滤器其查询均有一定的花费，包括时间，金钱等成本，记为C，同时该过滤器计算得到结果为TRUE的概率也是可以计算的，记为S，另外，每个过滤器与多少个查询相关联也是我们要考虑的，记为P，即最终每个过滤器的实际花销是由成本C，TRUE的概率S和关联查询P结算得出一个值记为SCORE，很显然，最终每个SCORE相加最小是理论上我们最好的查询处理过程。

考虑在实际过程中，单个去计算每个的值也是一笔很大的开销，而在实际过程中会存在一些情况，例如某个过滤器F_k为TRUE的概率几乎为0%或者就100%为FALSE，那么和这个过滤器相关的查询是否可以忽略或者延后处理，所以这里我们需要考虑一种分割方法，将理论上无限大的有过滤器的集合和查询的集合组成的GRAPH进行分割，进而减少我们在实际查询过程中的花销。

2. 研究的基本内容与方案

一、基本内容

1. 了解多重叠查询任务的原理和方法；

2. 了解图分割和矩阵分割的方法；

3. 研究计划与安排

第1~3周 查阅文献；分析题目研究现状，学习基本理论；

第4周 阅读文献、撰写开题报告，英文文献翻译；

第5周 学习了解贪心算法及其改进，确定实施方案；

4. 参考文献（12篇以上）

[1] b. babcock, s. babu, m. datar, r. motwani, and j.widom, "models and issues in data stream systems", in pods 2002,p.1-16.

[2] s. babu and j. widom, "continuous queries overdata streams", acm sigmod record, 2001, 30: 109-120.

[3] d. yang, e. a. rundensteiner, and m. o. ward,"a shared execution strategy for multiple pattern mining requests overstreaming data", vldb endowment, 2009, 2(1): 874-885