Dtrie-allpair:高效的集合T-覆盖连接算法

传统的T-覆盖连接算法会因生成的候选集庞大而导致系统性能降低,为此,文中提出了一种基于trie的动态索引结构——DTI结构,并构建了基于该结构的相似度连接算法——Dtrie-allpair算法.通过该算法可以直接得到allpair连接的结果,不产生任何候选集,有效解决了高候选集产生的问题,克服了传统算法因生成并验证候选集而带来的开销.文中还研究了数据库中记录的顺序及记录中元素顺序对Dtrie-allpair算法性能的影响,并在msweb、msnbc两个数据集下对Dtrie-allpair算法与All-pair、PPJoin算法进行对比.结果表明:Dtrie-allpair算法具有明显的优势,覆盖阈值较小时优势更明显;对msweb数据集,阈值为2时,Dtrie-allpair算法的效率相对于All-pair、PPJoin算法提高近两个数量级;通过对数据集进行频率降序和长度升序组合预处理可大幅降低Dtrie-allpair算法访问的trie结点数量,从而显著提升性能.

3-(v,K_4^((3))-e,λ)最小覆盖问题

考虑一种特殊类型的超图分解.证明了对任意的正整数v≥4和λ,存在具有[λv(v-1)(v-2)/18]个区组的MCλ(3,K(43)-e,v),其边超越中至多含有两条边.

等密拟阵在图论中的一个应用

研究等密拟阵在图论中的一个应用。由τc(G)的表示式,讨论了F∈β〔M′〔n-c〕〕的等价条件。证明了η〔M′〔n-c〕〕=τc(G)。结合等密拟阵的定义推得(ⅰ)τc(G)≥k的充要条件;(ⅱ)τc(G)=s等价条件;(ⅲ)当c=1时τc(G)的图论意义。

完全3-一致超图的一类填充问题和覆盖问题

设Γ是一些单t-一致超图的集合.填充设计Pλ(t,Γ,v)(或覆盖设计Cλ(t,Γ,v))是一个二元有序组(X,B),其中X是完全t-一致超图λKv(t)的顶点集,B是λKv(t)的一些子超图的集合,要求每个子超图都同构于Γ中的某一个超图,每个子超图称为是一个区组,并且满足λKv(t)中的每一条边至多(或至少)含在B的λ个区组中.给定参数t,v,λ,Γ,填充设计Pλ(t,Γ,v)的最大可能的区组数称为填充数,记为dλ(t,Γ,v);覆盖设计Cλ(t,Γ,v)的最小可能的区组数称为覆盖数,记为cλ(t,Γ,v).本文将确定Γ中仅含超图K4(3)+e时的dλ(t,Γ,v)和cλ(t,Γ,v)的精确值.