非对称数据率网络下的无阻塞连接算法

Non-blocking joining algorithm based on asymmetric data ratio network

基于稳定网的数据流连接算法已有很多研究成果,但在实际应用中,还需要处理不同速率网络下的查询连接,这使得目前流行的基于稳定数据流且内存分配固定环境下的连接算法难以适用。介绍了一种在非对称数据率网络下的无阻塞排序归并连接算法SMA。SMA算法的连接运算分为两阶段:join during run creation和join during merge,第一阶段可用于网络无阻塞情况下通过内存刷新策略来生成头批连接结果,第二阶段用于数据源受阻时借助外存驻留数据继续生成查询连接结果,从而保证了连接结果产生的无阻塞性。试验证明,SMA对等值和空间连接效率很高。

Data stream joining algorithms, based on stable network, have attracted considerable researches. However, the inquiry link in different network speeds is also required in practice, so that the joining algorithm based on stable network speed and fixed memory distribution is not adapted. Therefore, SMA, an algorithm of non-blocking sort-merge join based on asymmetric data ratio network, is introduced. Joining operation of the algorithm consists of two phases： join during run creation and join during merge. The former can produce early results through memory refresh strategy when there are no obstacles in network, while the latter produces the results through the out-disk data when network suffocates. The experiences show that SMA has high efficiency in the equal value join and spatial join.