【摘要】 k个集合S1,S2 ,… ,Sk的链域交是由所有满足以下条件的k元组 (s1,s2 ,… ,sk)组成的集合 :e( 1)i si-si+1 e( 2 )i ,其中sk ∈Sk,si ∈Si,0 e( 1)i e( 2 )i 是常数( 1 i k - 1 ) .已知的求链域交的算法采用k元组表示k集合的链域交 ,其最坏情况时间复杂度为Ω(k∏ki=1ni) ,其中ni=｜Si｜ ,1 i k .本文采用森林表示k集合的链域交 ,并基于这种表示方法提出了一个求链域交的串行算法 .该算法的最坏情况时间复杂度为Ω( ∑k-1i=1nini+1) ,极大地改进了已知的结果 .更多还原

【Abstract】 The chain range join of k sets S 1,S 2,…,S k, is the set containing all tuples (s 1,s 2,…,s k) that satisfy e i (1) |s i-s i+1 |e i (2) ,where s k∈S k, s i∈S i,0e i (1) e i (2)  are fixed constants, 1ik-1. In this paper k set chain range join is represented with a forest, by means of which the tight lower bound of time complexity for computing k set chain range join in the worst case when all elements in S t match every element in S t+1  for  1tk-1  becomes Ω(∑k-1i=1n in i+1 ), whereas it is Ω(k∏ki=1n i) with the k tuple representation, where n i=|S i|,1ik. A sequenti alalgorithm is also presented for computing k set chain range join with the forest representation which reaches the lower bound of time complexity in the worst case.更多还原