论文研究-基于压缩全文索引的演变图查询.pdf

所需积分/C币:5 2019-09-08 05:08:15 733KB .PDF
收藏 收藏
举报

演变图中含有大量的时间和空间信息,其中某些空间信息随着时间的推移表现出相似的演变规律。给出了一种演变图查询模型,可以挖掘出在相同时间范围内具有相同变化规律的演变子图。但是演变图的规模往往是巨大的,当需要对其进行多次查询时,每次遍历整个演变图将带来非常高的查询代价,而现有的基于枚举的哈希索引算法又使得预处理过程拥有相当大的时间和空间开销,为了减少对大规模演变图的预处理代价,将压缩的全文索引技术应用于演变图,它基于涡轮转换和后缀数组。在构建后缀数组时,给出了两种不同的线性算法,确保了预处理过程的稳定性。通过在Facebook、Enron邮件系统以及模拟数据集上的实验,评估了该算法的可行性、效率以及
肖洋,朱青,吴粤皖:基干压缩全文索引的演变图查询 2015,51(2)119 的WS在特定时间范围內的变化趋势。S可以由WS推在演变图上构建的基于后缀数组的索引。 出,具体做法类似于曼彻斯特编码:将从0变为1的记为3.1演变图遍历査询 +”,从1变为0的记为“-”,将其余的模式其忽略。从时间和空间两个维度对演变图进行杳询,即在演 图3给出了W和相应的TS的实例。 变图上进行一次选择运算时,本文査询模型的输入是 001100110011110110 个演变图还有一个 输出是演变子图集合。查询 图示 模型可以形式化地表示为个选择算子: G(EG, 0)=(SGCEG: SG-WS, P(SG)=truc) 图3权重变化序列WS和趋势序列TS 给出查询模型之前,先介绍断言函数 Predicate()。 在演变图中边是随着时间而变化的,从而每条边上此函数的输入是演变图,输出是布尔类型值e或 便形成了一个权重变化序列WS。如果想要获取边的 false A' redicate()可以用米对演变图的吋空特性进行 个子变化序列WS,或者一个子变化序列WS在原始序断言。下面给出对演变图EG=(,E,s,te,6)进行断言 列S中的起始位置,就需要对s的每个子序列建立的例了,其中演变图的边数为n。 索引,下面定义几个构建索引时需要的基本概念。 时间断言:Pn(EG)=(s>6and(te-+)>5) 定义3(后缀)给定一个字符串S=[S。S2…SJ把 规模断言:P(EG)=(n≥100 以S开头,长度为n-i+1的子串[S,S1…S(0≤i≤n), 在演变图上进行查询时的条 Query是一个二元 称为字符串S的一个后缀,记为sm。例如字符串组ws,P},其中HS是权重变化序列,P是一个断言。 “01110001的所有后缀经过字典排序后如图4所示。 值得注意的是P可以是几个断言函数的复合函数,例如 在牛成一个权重变化序列的所有后级之后,需要保P=( PI and p2)orP)。在输入一个 Query之后,将输入 存这些后缀在原始序列中的起始位置。这里引入两个二元组中的权重变化序列和演变图中的所有权重变化 数组:后缀数组和Rank数组 序列的子序列进行比较,如果它们相应的趋势变化序列 定义4(后级数组)后缀数组S410≤m是一个相同的话,则将相应的边取出,最后把其中满足输入断 一维数组,它记录的是经过字典排序后的字符串S的所言的边构成演变了图输出。 有后缀,在S中的起始位置。即如果svfx()在所有后 在查询模型中,一种最简单的方法就是,把查询输 缀中排名为j,那么S41=i。概括的,字符串S的后入中的权重变化序列WS和演变图中每条边h的所有 缀数组指的是在所有后缀中,排第几的是谁。例如图4 权重变化子序列进行遍历匹配,如果匹配成功且能满足 中的S的后缀数组SA[]=[45607321 P,则将此边取出,否则舍去 定义5(Rank数组)Rank[(0≤in同样也是一个 算法1的主要思想是在每个时间点t∈[s,el独立 维数组中,它保存的是字符串S的每个后缀在宇典序地进行演变子图查找,即在每个时问点t上进行算法迭 中的排名,即如果sa在所有后缀中排第j,那么代,找出【,t+ls-1时间范围内的演变字体SG,SG Rank]=j。它的计算和后缀数组是可逆的。图4中s中的边集是EG中[,t+lms-1时问范围内所有与WS 的Rank数组Ramk[]=[37650124]。 相关的边的集合。在得到SG后,把它划分为若干个连 通的演变子图,且每个演变子图都是与WS相关的。最 01234567 后,将不满足断言P的演变子图筛选掉。 01 Sux(4)0001 在使用算法1进行查询时,每输入一个WS和P都 Sunx(5)001 要对整个演变图进行一次遍历无论是在社会网络或 ux(6)01 是邮件系统中,演变图的规模通常是巨大的,当需要进 Sux(0)01110001 行多次查询时,遍历的代价会非常高。 Kan在之前的工作中提出了利用hash表对演变图 Sux(3)10001 Six(2)11000 中的时空信息建立索引,在这里称之为 Query-Hash,主 Suffix(1)1110001 要思想是针对每条边e,通过遍历得到它从任意t∈[s,te 图4字符串S=01110001经过字典排序后的后缀 时间点开始,在[,te-t+1的时间范围内的所有WS 并将它们组合成一个三元组{t,l,ws}作为hash表中的 3某础查询与FM索引的构建 key值, value值是对应的边集。在进行査询吋,根据输 在本章中,首先闸述了本文的演变图查询模型,然入的WS以及t,得到一个三元组,在hash表中进行查找 后给出了遍历查询的基础算法 Query- Baseline,并对其使可得到相应的边集。 进行说明和分析;最后在3.2和3.3节中详细介绍了两种 算法 I Query- Baseline 120 015,51(2) Computer Engineering and Applications计算机工程与应用 -+-$+一#+-+ evolving graph EG=(V,E, t, t s #+-+#-+-$+ waveform ws $+一#+-+-+ +-+#-+-$+ predicate P #-+-$+-#+ set of matching evolving subgraphs R=O(EG, WS, P) #11# #1-1#1-S I:R=0 2: foreach t in t,tI 图5对字符串S进行涡轮转换后生成的BWT矩阵 gct subgraph containing all cdgs 边和WS相关。其中的位置信息便存储在SA数组中 //correlated to Ws during period [t, t+Iws -I] 下面介绍的SA数组构造算法是基丁长度倍增思想,称 SG,Subgraph With CorrEdges(EG,t, wS) 6: //Pt is a set of connected subgraphs 之为S P← Partition(SG1) 算法2SA-Mult up f all n if (P(SG) aph add sg to r Output: Rank[: //Rank array of s endfor SA[]〃 Suffix array of s endfor Rank[=0; Sa[=2i 然而Iash索引是基于枚举的,当演变图具有一定 2: N-GetLength(S) 规模时,通过遍历建立索引这个预处理过程的时间开销 3: //Radix for each cha 和空问开销都非常巨大。在3.2节中,将给出到一种更 4: for (int i-0: i<N: i++) 合理的索引算法,在对演变图构建索引时,节省时间和 5: Ranki]-S[] 空间开销,同吋能保证杏询速度 6:Rank门]← Rank sor(Rank[ 7: //Radix sorting for Rank while length of string 32堪于长度倍增的FM索引 在演变图上构建的FM索引,共包括三个部分:(1)涡 2(2>n) 轮转换(BWT是用来生成全部权重变化序列WS的所 9 for (int k-1: k<n: k*-2) 有后缀;(2)SA4数组用米存储每个后缀在原始MS中的 起始位置信息、;(3)Maαc○)的功能是精确匹配与査询 Rank[i=Rank[i]*nIRank[ilk Query ws',P}中WS'相关的后缀。 Rank[+Rank Sort(Rank[1); 321涡轮转换 13: SALe-lnvert( Rank[) /obtain S[ by inverting Rank[ 由于FM索引实现的是精确匹酡,先将演变图上的 算法的主要思想是:用倍增的方法对从每个字符开 uS全转换成7S,这样做的目的是能找出所有与查洵输始的长度为2的子字符串进行基数推序,求出排名,即 入WS相关的WS。比如输入WS=“0110,应的Rank数组。k从0开始,每次加1当2大于n以后,每 7S=“+-+",在查询时只要满足“+-+”的Ws的后级都个字符开始的长度为2的子字符申便相当于所有的后 会被保留,其体做法如下 缀。并且这些子字符牛都一定已经比较出大小,即rank 首先,将邻接矩阵中的01串全部转换为由十和-组值中没有相同的值,那么此时的rank值就是最后的结 成的TS,如果全0或全1,则记为空。 果。每一次排序都利用上次长度为2的字符串的 其次,定义两个字符“#”和“$”,规定字典序“ rank值,那么长度为2的字符串就可以用两个长度为 “+”<“#”<“$”。 的字符串的排名作为关键字表示,然后进行基数排 接下来,将邻接矩阵中的所有TS连接成一个长串,序,便得出了长度为2的字符串的rank值。仍然以宇 记为S。其中在连接矩阵中每个TS(不为空的话)时,符串“+-#+-+#-+-$”为例,整个过程如图6所示。 用#分隔,在连接完最后一个不为空的TS时,以$结尾。其中x、y是表示长度为2的字符串的两个关键字 最后,利用BWT,对S循环左栘,生成所有后缀,并3.2.3精确匹配查询 使用字典序对它们进行排序。图5给出了对演变图转 这一部分将介绍在M索引上是如何进行精确查 换后的字符串S=“+-#+-+#-+-S生成后缀的例子。询的,山上面两部分已经得到字符串S的所有后缀以及 322基丁长度倍增的后数组构造 这些后缀在S中的位置信息,为了要找出与输入中的 在输入的WS和字符串S的某个后缀匹配成功后,WS相关的边,此时只需用WS与字符串S中的所有后 需要荻取这个后缀在S中的位置信息,才能知道是哪条缀进行精确匹配即可。 肖洋,朱青,吴粤皖:基干压缩全文索引的演变图查询 2015,51(2)121 FM-DC3。与 FM-mult相比,区别仅在于构造后缀数组 第1次排序 Rank数组 ]方法的不同 322133223131223322000 算法4SA-DC3 第2次排序 Rank数组 Input: String S; /cOnnection of all non-empty Ts in x y 72472576516517537030100 evolving Graph 第3次排序 Rnk数组9 10 0 Output: Rank[: //Rank array of S 次静户937210658173110160801301001 r I SA /Suffix array of S Rank数组942105 16830 1: Rank=O; Sa= 2: N=GetLength(S) 图6基于长度倍增的Rank数组构遣过程 3: iconnect suffix(1) and suffix(2) of S 在此之前,先引入两个概念:C[c],Occ]。c代表 4:S=S[1,2,…,n-l+S[2,3,…,n 个宇符,C[c]是在宇符串S的所有宇符中,字典序小 5: //Radix sorting for every 3 character in s 于c的所有字符的个数;Occ,代表在BWr(S)中,即 6:Rank]← Rank sori(s”); 经过字典排序后S的所有后缀中,第r行之前出现字符 7: /recurse SA-DC3() and return Rank[ c的个数。比如在图5的BWT中,不考虑最后终止符S 8:Rank门]←SA-DC3(S C[+]=6,Oc+,10]-3。如此一米通过C[c]+Occ,r+1 便可确定在S的后缀中,以某个字符开头的后缀的位置 10: /compute Rank which is the Rank array 信息。 11: //of suffix(i) whe Rank [i ppn 算法3 Match() Input: BWT, string Ws 14: Ranki=Rank[il 1*2n t Rank[i121 Output: sp, ep /sp is the first position of suffix in 15: //compare and merge Rank0 and Ranku BWT which begins with Ws;ep is the last position 16: Rank[]+Merge(Rank[, Rank) c←Ws[p] 17: SA[e-Invcrt( RankI) so by 2:sp←C[c]+1 FMDC3屮构造后缀数组的过程分为三步,首先对 3:ep←C[e+1l-1 所有后缀sfix(0≤κ≤n)中,模3不等于0的后缀进 5: while sp<ep and i>=l do 行排序;接下来对剩下的后缀进行排序,即i对3取模等 ←WS[il 于0的后缀;最后将两次排序的结果进行合并,即可得 sp←LFC(c,sp) 出后缀数组 ep←LFC(c, 对第一部分进行排序时,首先需要将safx和 9 1←1 s/fax[2]进行合并,并且保证它们的长度均是3的倍数, 10. cndwhilc 如果不满足,则在末尾补0。合并以后每3个字符作为 return sp, ep 组,进行基数排序,将每组字符“合并”成一个新的字 在算法Mat()中,定位的具体做法是先从WS的符,然后用递归的方法求这个新的字符串的后缀数组。 最后一个字符WS开始匹配,找出所有第个和最后在得到新字符的S4后,便可计算出原字符串中所有 个以HS[开头的后缀的位置信息:sp和ep,如此·起始位置模3不等于0的后缀的SA。 来在[ep-p这个范围内均是以p开头的后缀;接下来 对于原始字符串中剩下的后缀,即那些起始位置模 开始匹配倒数第二位WSp-1因为BWT中的后级是3等于0的后级,可以用字符串中的字符加上一步求 由原始字符串左移得来,故利用刚才得到的s和ep可出的SA来表示。在合并时,需要依次比较两个后缀的 以得到以“WS[pJS[p-1”开头的后缀范围;将WS不大小,生成新的SA,此时的SA便是原始字符串的SA。 断向前查找,最后得到的便是以WS开头的后缀的范闱 在得到所有以WS为开头的后缀以后,也就得到了 实验和评佔 这些后缀所对应的SA数组,即这些后缀在原始字符串 为了对FM索引算法的可行性、效率以及可扩展性 S中的位置信总,通过矩阵位置计算,得到的便是演变图进行评估和分析,本章将通过具体的实验来加以验证 屮的边信息,从而完成了对 Query- Baseline屮功能函数和说明。实验环境为 Inter@ CoreTM i3CPU2.53GHz, SubgraphWithCorrEdges()的优化。 4GB内存, Windows7操作系统所涉及代码用 Visual 33基于位置划分的FM索引 C+-(60)实现。 本节介绍了另一种基于后缀数组的的FM索引 首先,为了衡量本文算法的效率和可扩展性,并与 122 015,51(2) Computer Engineering and Applications计算机工程与应用 Hash岽引作对比,模拟生成了一系列规模较小的演变 在表2中可以看到,随着L的增加,FM索引的预处 图,这是因为在有限的硬件资源下,只能在小规模演变理时间开销是线性增长的,当L取到100时,整个预处 图上构建Iash索引。其次,在对大规模演变图上构建理过程仅需要0.051s;而Hash索引则是指数增长的,当 FM索引的可行性进行评估时,选取了两个真实数据集L取到60的时候,预处理过程已经花费了23971 进行实验并分析:non邮件系统和 Facebook:其中第L=70时Hash索引创建的Hash表已经不能放入内存 个数据集是由Kint和Yang(2004)提供,第二个是由中,导致预处理崩溃。 Maⅹ Plank在线社会网络研究中心提供。 在上述数据集中,分别建立Hash索引和 FM-Mult 41模拟数据集上的评估 索引后,对其进行了随机生成的1000次奁询(不一定是 模拟数据集生成的演变图中,顶点数N=100,快照有效查询),并统计了查询时间。图7给出了预处理时 数的选取为[10,1001。仅仅如此还不能保证Hash索引间和查询时间组成的总时间消耗对比。 构建成功,此外还设置了两个参数a和b来控制演变图 的稀疏程度以及每条边的TS的长短。在生成演变图的 过程中,规定a=0.9,即每个演变图上只有10%的边发 200 FM查询 生过变化;b=0.98,这意味着每条边的WS上的每一位 FM预处弹 Hash登询 有98%的概率是“0”。这两个参数的选取,是在多次实 罐Hash顶处理 验中反复筛选确定,即俫证了演变图不会稀疏,同时支 102030405060708090100 持Hash索引的构建。表2给出了在这一系列的演变图 快照数量 上构建Iash索引和FM索引的时间开销对比。 图7模拟数据集上构建索引并査询的总时间消耗 表2Iash索引与FM索引预处理开销对比 从图7可看出,FM-Mult算法预处理时间非常小,查 Hash索引 FM-Mult M-(3 时间跨度 询时间占总时间消耗的绝大部分。而Hash索引随着快 内存KB时间s内存kB时间6内存kB时间照数的增加,预处理时间成指数级的増长,在50张快照 10 13200.011 27 l89 483 }02313570.011 时,总时间消耗已经超过FM-Mut索引算法。值得注意 30 143775020.02514210011的是,当快照数增加到70以后,由于硬件限制,Hash索 36.53515002814590.012引已经不能处理,但是总时间消耗远远大于FM索引 952 30.76 0.032153」0.010 针对不同稀疏程度的演变图,FM索引算法拥有稳 1794239.715470.03315500.011 定的出色性能。当b=0.5,调整系数a的取值,在图 2000 0.03316040.012 0.03916700.013 中给出了相应的预处理时间消耗。可以看出,当a=0.5 601004517010.013即演变图非常稠密的时侯,随着快照数的增加,FM索引 616005117440.014的预处理过程仍然是线性增长的。 二40 FM-DC 3 H FM-DC3 102030405060708090100 1020 405060708090100 快照数量 快照数量 (a)a=0.9 (b)a=0.8 300 200 t FM-Mult 150 FM-Mult HLFM-DC3 *100 HE FM-DC3 0学平平 102030405060708090100 102030405060708090100 快照数量 快照数量 (c)a=0.6 图8FM索引在不同稀疏程度演变图上的预处理开销 肖洋,朱青,吴粤皖:基干压缩全文索引的演变图查询 2015,51(2) 123 4.2 Enron邮件系统上的评估 为0,在[t,L全为1图10为随着L的增加构建两种压 数据集 eRON Email Corpus是 ENRON公司在缩全文索引的空间开销数据 200至2004年邮件的集合,每一封邮件都包含了发件 人地址、收件人的地址以及发送时问戳。在生成演变图5相关研究 时,员T代表图的顶点,将总的时间跨度划分为若十个 现有的动态图或演变图研究主要分为两类,一类是 相等时间段,每个时间段对应演变图中的一张快照。如关于拓扑结构的研究,络拓扑结构加上时间序列数 果两个员工在某个时间段内发送过郎件,那么在相应的据共同给出了动态变化系统的全局。网络中随着时问 快照中,两个顶点之间的边的权重被置为1,否则置为0,改变的权重隐含了大量的信息,单纯地研究网络拓扑结 borgwardt等人之前在此数据集上建立的演变图仅包含构的变化会使这些信息得不到很好的利用 ∫15张快照四,Kan在之前的论文中构造的演变图也仅 另一类则集中在频繁子图挖掘或趋势主题挖掘上, 包含了52张快照,每张快照中的顶点数仅为140个。这例如,Chan等人在文献[6]中定义了演变图中相关时空 远远不能满足对规模较大的演变图进行分析时的需求,变化的区域,并设计了一个算法找岀所有的区域;Ji研 因此从数据集中选取了更多的顶点、更广的时间跨度以究了顶点标签随时间变化的演变图,并给出了一个挖掘 及更小的时间问隔。 趋势主题的方法; Borgman在文献[2]中的T作则是挖 随着演变图时间跨度的增加,每条边上的WS变长,掘动态子图,这些子图都是连通的、具有相同的时问行 相应的,TS也会增加。为了评估FM索引算法的可行为,并且至少发生了一定的次数,其中发生的次数即时 性以及稳定性,选取了1000个顶点,时间跨度范围为间是预定义好的;Lahm和 Berger-wolf在文献|8]中研究 [100,1000,长单位是100。图9给出了随着快照数增了动态子图的周期行为 多时,预处理开销的增长趋势。 然而,这些工作都是在一种特定的情况下枚举出所 图9中,利用FMDC3对包含100°个顶点,100张有的模式,相较而言,基于查询的方法能使用户灵活的 快照的演变图进行预处理的时间开销是3.75s:即使在演定义结果的大小,找出它们所感兴趣的内容。对比枚举 变图包含1000张快照时,预处理过程才花费了28.035。所有模式的方法,基于查询的挖掘的另一个优势就是速 这说明,本文算法不仙适用J大规模真实演变图,同时度快。Chan在文献[]中曾提出了在由0和1组成的 规模的增加,表现出相当好的稳定性 值演变图中进行挖掘子图的方法,但是索引方式是基于 值得注意的是,此处只给出了FM索引在大规模演枚举的,当演变图规模较大时,构建索引的预处理过程 变图上的开销数据。这是因为,在这个数量级的演变图将带来巨大的时间和空间开销。 上构建Iash索引会导致内存崩溃。 基于压缩的全文索引技术结合了涡轮转换和后缀 4.3 Facebook数据集上的评估 数组,它是一种无损压缩,即在压缩后不会丢失原始数 在验证本文算法在大规模真实演变图上的可行性据信息。涡轮转换之前曾被应用于生物信息领域中。 和稳定性时还选取了社交网络 Facebook在美国新奥尔在DNA序列检测中,一个基因序列的长度可以达到 良州的一组数据集。此数据集中包含了10万多条记数千兆,当需要对一个短基因序列在原始基因序列中进 录,每一条记录均包含了两个匿名用户ID以及一个他行匹配时,只需要存储原始基因序列的涡轮转换BWT 们初次成为好友时的UNIX时问戳。 和生成的后缀数组,即可快速地进行检测。然而近年来 在从数据集中抽取数据建模成演变图时,随机选取由于核苷酸序列数据库的大小成指数级的增长,这引起 其中5000个用户ID作为顶点,它们之间存在的关系作了很多学者的注意,并开始把数据库的压缩作为唯一H 为边,构成演变图以后大约有6000条边,选取的时间跨的来进行研究。 Tembe"和 Deorowicz等人"均对 度的范围是[100,10001值得注意的是,如果用户建 FASTQ格式的文件提出了压缩方法,但这些方法都 立关系的时间为,对应的边的权重变化序列在[,1全是标准文本压缩方法的组合: Huffman和 Lempel-7ⅳ,很 80 15 FM-DC3 FM-DC 0 三浇3§§ 快照数量 快照数量 图9在上nron数据集上构造FM索引的时间开销图10在 Facebook数据集上构造FM索引的时间开销 124 015,51(2) Computer Engineering and Applications计算机工程与应用 难从本质上对只有2值的序列进行压缩效果的提升。 Group formation in large social netw orks: membership 在硬件领域,比如内存屮的信号检测也用到了基 growth, and evolution[c]/KDD, 2006: 44-54 于压缩的全文索引,原理上同样也是基于后缀数组和涡[5] Palla g, Barabasi a l, Vicsek T Quantifying social group 轮转换,最终将问题转换为字符串匹配。然而针对演变 cvolution[]. Naturc, 2007, 446: 664-667 图领域,基于压缩的全文索引技术还没有得到应用,特 [6 Chan J, Bailey J, Leckie C. Discovering correlated spatio 刎是针对不同规模、不同稀疏程度以及不同的硬件环 temporal changes in evolving graphs[J]. Knowledge and 境,目前还没有更合理的索引技术 nformation Systems, 2008, 16(1): 53-96 [7 Jin R, Mc Callen S, Almaas E Trend motif: a graph mining approach for analysis of dynamic complex netw orks[C] 6总结及展望 Procccdings of the 7th Ieee International Confcrcncc 本文在演变图上给出了一种查询模型,可以荻得那 on Data Mining. Washington, DC, USA: IEEE Computer 些时间和空间特性均满足用户输入的演变子图;并在其 Society,2007:541-546. 上构建了压缩全文索引,在有限硬件环境下,实现了对8] Lahiri m, Berger-Wolf TMining periodic behavior in dynamic 大规模演变图构建索引的预处理过程,减少了时间和空 social networks[C]/ Proceedings of the &th IEEE Interna 间开销;在构建索引时,给出了两种线性的构造后缀数 tional Conference on Data Mining. Washington, DC, USA 组的算法:一种是基于位置倍增的基数排序,另一种为 IEEE Computer Society 2008: 373-382 基于位置划分的基数排序,均使整个预处理过程具有很[9c0XAJ, Bauer M I, akohi t; et al.Large-scale compres 好的可扩展性 sion of genomic sequence databases with the burrows 在构造后缀数组时,把每个后缀的位置信息都存储 Wheeler transform[J]. Bioinformatics, 2012, 28(11): 1415-1419 下来,这也占据了一定的空间,下一步会考虑利用继续 [10] Simpson J T, Durbin R Efficient construction of an assem bly string graph using the FM-index[J]. Bioinformatics 压缩存储空间,来处理更大规模的演变图;另外,现在的 2010,26(12):367-373 研究还局限于由“0”和“1”构成的二值演变图,以后的工 [ll Chen X, Li M, Ma B, et al. DNACompress: fast and effec- 作中会考虑在多值权重的演变图上构建压缩全文索引。 tive DNA sequence compression[J. Bioinformatics, 2002 18(12):1696-1698 参考文献: 12]Giancarlo R, Scaturro D, Utro FTextual data compres [1 Kan A, Chan J, Bailey ct al.A query bascd approach sion in computational biology [J]. Bioinformatics, 2009 for mining evolving graphs[C]/Proceedings of the &th 25(13):1575-1586 Australasian Data Mining Conference-Volume 101[S1.: [13 Tembe W, Lowey J, Suh E.G-SQZ: compact encoding Australian Computer Society, Inc, 2009: 139-150 of genomic sequence and quality data J Bioinformatics [2 Borgwardt K, Kriegel H, Wackersreuther P, et al. Pattern 2010,26(17):2192-2194 mininginfrequentdynamicsubgraphs[c)/proceedings[14]DeorowiczS,GrabowskiS.comPressionofDnasequence of the 6th International Conference on Data Mining reads in FASTQ format[J]. Bioinformatics, 2011, 27(6) 2006:818-822 860-862 [3] Leskovec J, Kleinberg J M, Faloutsos C Graphs over [15] Fernandez. E, Najjar w, Harris F, et al. String matching time: densification laws, shrinking diameters and possi in hardware using the FM-index c 2011 IEEE 19th ble explanations[C]//KDD, 2005: 177-187. Annual International Symposium on able [4 Backstrom L. Huttenlocher D P, Kleinberg J M, ct al Custom Computing Machines( FCCM), 2011: 218-225 (上接107页) l1中国国家安仝漏洞共亨平台[EBOL][2012-11-03]tp: 16 US-CERT vulnerability notes field descriptions eB/OLI www.cnvd.org.cn. 201210-llht:/ww. kb, cert. org/vuls/html fieldhelp#metric.[12]王秋艳,张玉清.一种通用漏洞评级方法[计算机工程, [7 SANS critical vulnerability analysis[EB/OLJ-2012-10-11 2008,34(19):133-140 http://www.sans.org/newsletters/cva/ [1]3]楼文高,姜丽,孟祥辉计算机网络安全综合评估的神经 [8 about secunia advisorics eb/ol].[2012-10-11].htTp: //sccu 趔终模型[J计算机工程与应用,2007,43(32):128-131. nia. com about secunia advisories [14]黄丽,BP神经网络算法改进及应用研究[D]重庆:重庆师 9 Verissimo P E, Neves N F, Correia M P Intrusion toler 范大学,2008 ant architecture; concepts and designEB/OL(2003-07-18).[15]卓先德网络安全评估的仿真与应用研究门计算机仿真 .difc ul. pt/tech 03-5,pdf 10]中国国冢安全漏洞数据厍[EBOL]:2012-11-03hp:[16]于群,冯玲基于BP神经网络的网络安全评价方法研究[J] www.cnnvd.orgcn/ 计算机工稈与设计,2008,29(8):1963-1966

...展开详情
试读 8P 论文研究-基于压缩全文索引的演变图查询.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744207 你的留言是对我莫大的支持
2019-09-08
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
最新推荐
论文研究-基于压缩全文索引的演变图查询.pdf 5积分/C币 立即下载
1/8
论文研究-基于压缩全文索引的演变图查询.pdf第1页
论文研究-基于压缩全文索引的演变图查询.pdf第2页

试读结束, 可继续读1页

5积分/C币 立即下载 >