互联网、传感器以及物联网等技术的发展,使数据产生的速度越来越快。无处不在的数据中隐藏着各种有价值的信息,这些信息给人们的日常生活提供了便利。在很多应用中,信息以数据流的形式提供给用户,这些信息带有很强的时效性,要求用户以"on-the-fly"的形式进行处理。另外,由于设备以及应用特点的限制,单条数据流往往只能提供部分数据,用户需要将多条数据流结合起来才能获取完整信息。连接(Join)作为获取综合信息的有效手段之一,在数据流处理中占有重要地位。大数据时代的到来使单节点的计算模式已经不能满足数据流连接的需求,由多个‘’shared-nothing"廉价节点构成的集群成为解决该问题的有效手段之一。本文在深入研究和总结相关工作的基础上,围绕分布式环境下多路数据流的连接问题展开研究,内容主要集中在以下几个方面：首先,在数据流模型下提出了基于增量计算的Compressed直方图构建和维护算法。在允许的误差范围内,Compressed直方图可以反映当前滑动窗口中数据的大致分布情况,为接下来多路数据流的连接优化问题提供支持,该部分为后面研究的基础。其次,针对二路数据流的特点提出了基于流水线的二路数据流连接算法。该算法将计算节点以线性形式组织,将两条数据流以相向的方式注入流水线,可以处理二路数据流等值及不等值连接,在不需要数据备份的条件下能够保证结果的完整性。另外,在流水线模型下提出了基于上游备份的容错机制、类似按压橡皮泥的负载均衡机制以及可扩展性机制等。再次,针对多路数据流等值连接的特点提出了基于一致性hash的多路数据流等值连接分配算法,该算法在保证相关联元组能够分配到相同节点的前提下,可以维持各个计算节点间的负载均衡。另外,根据直方图提供的信息,在数据流连接过程中采用基于贪心的算法实时维持连接树,保证数据流以相对较优的顺序执行,减少网络传输及连接过程的执行时间。最后,对通用性更强的多路数据流非等值连接进行了研究,提出了基于范围hash和共享时间片的分配策略。这两个策略在兼顾结果完整性和负载均衡的同时,也尽量减少备份数据的传递量,降低网络负载。另外,针对很多应用滑动窗口中连接属性属于多重集的情况,提出了基于(key,valueList)的"Group Join"连接算法,降低网络传输量,在某些情况下减少执行时间。本文从分布式多路数据流连接出发,提出了适合二路数据流连接的流水线算法、适合等值连接的一致性hash算法以及适合非等值连接的范围hash和共享时间片算法,并在这些算法的基础上提出了一系列的负载均衡、容错、扩容以及连接优化算法,为后续研究研究工作提供了参考。