论文部分内容阅读
2004年,Ishai,Kushilevitz,Ostrovsky和Sahai首次提出了批处理码的概念,它的提出是为了表示一种数据分配方式以用来解决信息搜索问题,这个问题是:如何把n项数据分配到m个服务器里,使得当我们需要n项数据中的任意k项时,都可以通过从每个服务器里选择至多t项来找到这k项,同时让这些服务器总存储量N尽可能小.数据分配完毕之后,如果把每个存有数据的服务器看做是n项数据的一个子集,此时的批处理码称为组合批处理码,一般只考虑t=1时的情形,具有参数n,k,m的组合批处理码记作(n,N,k,m)-CBC.如果对所有的(n,N,k,m)-CBC,存在一个(n,N,k,m)-CBC,使得N≤N,则称此(n,N,k,m)-CBC是最优的,并用N(n,k,m)来表示这个最优值. 当n<(mk-2)时,对于给定参数n,k,m的一般情形下的CBC的最优值还没有完全确定.对于n<(mk-2)的情形,本文通过可分解横截设计RTD(q-2,q)构造了一类(q2+q-2,q3-q2-2q,q2-2q-16,q2-2q)-CBC,给出了一种把q2+q-2项数据分配到q2-2q个服务器里较为合理的分配方式.对于给定的相同参数n=q2+q-2,k=q2-2q-16,m=q2-2q,已有构造(m+p,m+p+ε(k,p),k,m)-CBC不能确定此参数情形下的N值;已有构造(k+s+d,2k+2s+(d-1)p-b,k,k+s)-CBC确定的N值为3q3-7q2-46q+32;我们的构造确定的N值为q3-q2-2q.通过对比,我们的构造优于已有构造(k+s+d,2k+2s+(d-1)p-b,k,k+s)-CBC.