近年来,随着共享视频、社交网络等新兴产品的崛起,网络中的数据规模也呈爆炸式增长。这些数据具有结构复杂、数量巨大等特点,因此从海量数据中提取关键数据难度变得越来越大,尤其是在海量数据中做相似性连接显得愈发困难。所谓相似性连接,是指从一个或两个数据源中查找所有的相似数据对,并返回结果。相似性搜索在概率数据相关的许多实际应用中扮演着十分重要的作用,如无线传感器网络、股票分析以及基于多个视频源的对象跟踪。EMD距离(Earth Mover’s Distance)在计算机视觉领域返回的相似性概率数据与人类对相似性的判断更一致。然而,EMD立方级的复杂度阻碍了其相关应用的普及,特别是在分析快速到达数据的数据流方面,同时源源不断到达的数据可能会造成系统缓存不足、系统过载导致性能急剧下降等问题。为此,本文尝试采用EMD的方法对滑动窗口语义的数据流进行相似性连接处理,主要开展了以下方面的研究工作:(1)针对EMD距离函数优化问题中存在的复杂度高、计算时间长,数据流数据的无限性等问题,提出一种基于B+森林索引框架的EMD相似性算法(称为EMD-DSJoin)。算法的设计思想是:利用线性规划的原始对偶理论把到达的直方图概率数据转换为EMD下界距离,然后基于EMD的下界距离构建一组B+森林索引,利用B+森林有效地对不需要进行EMD计算的直方图概率数据剪枝,从而加快基于EMD的相似性连接效率;最后利用滑动窗口解决有限缓存保存延迟数据问题。算法具体的实现方法为:(a)通过构建B+树森林和更新可行解,提高过滤效果,过滤掉完全相关或完全不相关的数据;通过构建子索引,利用丢弃成块的子索引完成数据的丢弃,减少丢弃数据的维护代价。(b)优化B+树森林存档周期,根据滑动窗口值和容量因子的变化,使存档周期P值达到自适应变化的效果,从而让B+树森林索引机制更高效运行。通过用真实环境的数据集进行的验证实验和对比分析结果表明,EMD-DSJoin算法的CPU时间、EMD求精次数都有一定程度的减少,处理速度比已有对比算法快了 35%左右,说明EMD-DSJoin算法使数据剪枝更为高效,为处理乱序数据提供更为有效的处理策略。(2)数据流的数据到达并不是匀速的,当数据在某时间段集中到达时,由于系统资源有限,数据流高爆发时容易造成系统过载,从而导致连接性能大幅度下降。为了解决这一问题,本文提出了基于EMD-DSJoin算法的降载策略。该策略充分考虑了数据流上数据具有的时间关联性,在系统过载时过滤掉数据中包含的冗余数据,有效减少了相似性连接的次数,同时尽可能保证相似性连接结果的完整性。实验结果表明,使用降载策略的EMD-DSJoin 算法可以根据丢弃阈值设定的不同,不同程度地减少EMD求精次数和CPU时间,验证了降载策略的可行性和有效性。本文首次采用基于滑动窗口语义的EMD处理数据流相似性连接技术,提出了一系列策略来提高EMD-DSJoin在数据流上处理乱序延迟直方图概率数据的能力,较好地解决了数据流高爆发时系统过载问题。论文的研究成果为数据流上的数据相似性连接提供了提供新的思路和技术手段。