Chapter 6. 挖掘频繁模式、关联与相关

11数据仓库与数据挖掘

第6章挖掘频繁模式、关联和相关性李成安华南理工大学经济与贸易学院©201304February2023DataMining:ConceptsandTechniques23第6章:挖掘频繁模式、关联和相关性:基本概念和方法基本概念频繁模式挖掘方法

什么模式是有趣的?—模式评价方法小结4什么是频繁模式挖掘?频繁模式:频繁出现在数据集中的模式(如项集、子序列或子结构)首先由Agrawal,Imielinski,andSwami[AIS93]提出频繁模式和关联规则挖掘动机:发现数据中内在的规则什么产品经常被一起购买?—啤酒和尿布?!买PC后接下来会买什么?哪种DNA对这种新药敏感?我们可自动分类web文档吗?应用购物篮数据分析,交叉销售,顾客购买习惯分析,Web日志(clickstream)分析,和DNA序列分析等.5为什么频繁模式挖掘是重要的?频繁模式:数据集内在的和重要的特性是许多数据挖掘任务的基础关联,相关性,和因果性分析序列,结构(如子图)模式空间时间、多媒体、时间序列和流数据的模式分析分类:判别,频繁模式分析聚类分析:基于频繁模式的聚类数据仓库:立方体和立方体梯度(cube-gradient)语义数据压缩:分册广泛的应用6关联规则挖掘形式化定义给定：设I={i1,i2,…,im}是项(item)的集合。若干项的集合，称为项集（ItemSets）记D为交易(transaction)T(或事务)的集合，这里交易T是项的集合，并且T⊆I。对应每一个交易有唯一的标识，如交易号，记作TID。设X是一个I中项的集合，如果X⊆T，那么称交易T包含X。寻找：有趣的关联规则(强规则).7关联规则所有形如X⇒Y蕴涵式的称为关联规则，这里X⊂I,Y⊂I，并且X∩Y=Φ。关联规则是有趣的,如果它满足最小支持度阈值与最小置信度阈值,并称之为强规则8置信度与支持度项集X={i1,…,ik}找出所有具有最小置信度和支持度的关联规则X⇒Y买尿片的顾客两者都买的顾客买啤酒的顾客支持度,s,一个事务中包含XY的可能性

support(X⇒Y)=同时包含项目集X和Y的交易数/总交易数用于描述有用性.置信度

c,

一个事务中包含X也包含Y的条件概率.confidence(X⇒Y)=同时购买商品X和Y的交易数/购买商品X的交易数用于描述确定性,即”值得信赖的程度””可靠性”9关联规则的基本形式关联规则的基本形式：

前提条件⇒结论[支持度,置信度]buys(x,“diapers”)⇒buys(x,“beers”)[0.5%,60%]major(x,“CS”)takes(x,“DB”)⇒grade(x,“A”)[1%,75%]包含k个项目的集合，称为k-项集项集的出现频率是包含项集的事务个数，称为项集的频率、支持计数或者计数10基本概念:频繁模式项集:项的集合k-项集X={x1,…,xk}(绝对)支持度,or,支持计数

ofX:项集X出现的频数(相对)

支持度,s,X(如一个交易包含X的概率)出现的百分数项集X是频繁的，如果X的支持度不小于最小支持度

阈值。CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTidItemsbought10Beer,Nuts,Diaper20Beer,Coffee,Diaper30Beer,Diaper,Eggs40Nuts,Eggs,Milk50Nuts,Coffee,Diaper,Eggs,Milk11基本概念:关联规则发现所有规则XY

with最小支持度和置信度支持度,s，一个交易包含XY的概率置信度,c，一个包含X的交易也包含

Y的条件概率设minsup=50%,minconf=50%频繁模式:Beer:3,Nuts:3,Diaper:4,Eggs:3,{Beer,Diaper}:3CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerNuts,Eggs,Milk40Nuts,Coffee,Diaper,Eggs,Milk50Beer,Diaper,Eggs30Beer,Coffee,Diaper20Beer,Nuts,Diaper10ItemsboughtTid关联规则:(manymore!)BeerDiaper(60%,100%)DiaperBeer(60%,75%)12闭合模式和最大模式长模式包含组合数量的子模式，即，{a1,…,a100}包含(1001)+(1002)+…+(110000)=2100–1=1.27*1030子模式!解决方法:挖掘闭合模式和最大模式项集X

是闭合的如果X是频繁的，且不存在超模式

YכX,有

X同样的支持度(proposedbyPasquier,etal.@ICDT’99)项集X是最大模式，如果X是频繁的，且不存在超频繁模式YכX(proposedbyBayardo@SIGMOD’98)闭合模式是频繁模式的无损压缩减少模式和规则的数量13闭合模式和最大模式例子.DB={<a1,…,a100>,<a1,…,a50>}Min_sup=1.闭合模式集是什么?<a1,…,a100>:1<a1,…,a50>:2最大模式集是什么?<a1,…,a100>:1所有模式集是什么?!!14频繁模式挖掘的计算复杂度在极端情况可能生成多少频繁项集?频繁项集的数量与最小支持度阈值有关当minsup很小时,频繁项集的数量指数性增长最糟糕的情形:MNwhereM:#distinctitems,andN:maxlengthoftransactions极端情形的复杂度与期望概率例.假设Walmart有104

种产品选购一种产品的机会为10-4选购特定10种产品的机会:~10-40一个特定10种产品在109交易中出现103次的机会是多少？

15第6章:挖掘频繁模式、关联和相关性:基本概念和方法基本概念频繁模式挖掘方法

什么模式是有趣的?—模式评价方法小结16Apriori方法频繁项集的定义如果项集满足最小支持度，则称之为频繁项集（高频项集）频繁项集的基本特征任何频繁项集的非空子集均为频繁项集。例如：ABC是频繁项集，则AB、AC、BC均为频繁项集。反之：如AB不是频繁项集，则ABC不可能是频繁项集17Apriori方法是一种称作逐层搜索的迭代方法。用k-项集探求（k+1）-项集。具体地：首先找出频繁1-项集，该集合记为L1;用L1找出频繁2-项集的集合L2；如此继续下去，直到找到最大频繁项集该方法，主要有连接和剪枝两步构成。18Apriori算法－例子DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}219Apriori算法伪代码:Ck:大小为k的候选集Lk:大小为k的频繁项集L1={频繁项集};for

(k=1;Lk!=;k++)dobegin

Ck+1=从Lk生成的候选集

for数据库中每个交易

tdo

增加Ck+1

中包含在t的候选项集的计数

Lk+1=Ck+1

的候选集withmin_support

endreturn

k

Lk;20Apriori的重要细节如何生成候选集?Step1:self-joiningLkStep2:pruning如何计算候选集的支持度?候选集生成例子L3={abc,abd,acd,ace,bcd}连接步:L3*L3abcdfromabcandabdacdefromacdandace修剪:acdeisremovedbecauseadeisnotinL3C4={abcd}21如何生成候选集?假定Lk-1

的项集被按序排列Step1:连接Lk-1

insertinto

Ckselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1Step2:修剪forallitemsetscinCk

doforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk22如何计算候选集的支持度?为什么计数支持度是一个问题?候选集的数量非常大一条交易可能包含很多候选项集方法:Candidateitemsetsarestoredinahash-treeLeafnodeofhash-treecontainsalistofitemsetsandcountsInteriornodecontainsahashtable23

Apriori算法足够的快吗?

—瓶颈问题的产生2023/2/4数据挖掘：概念和技术24提高Apriori效率的方法1.基于Hash的项集计数:若

k-项集在hash-tree的路径上的一个计数值低于阈值，那他本身也不可能是频繁的。(157页图5-6)2.减少交易记录:不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集，下一步计算时删除这些记录。3.划分:

一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的。两次扫描数据。(157页图5-6)4.抽样:使用小的支持度+完整性验证方法。在小的抽样集上找到局部频繁项集，然后在全部数据集找频繁项集。5.动态项集计数:在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。25挖掘频繁模式项集的模式增长方法Apriori方法的瓶颈宽度(i.e.,level-wise)优先搜索候选集生产与测试经常产生巨大数量的候选集频繁模式增长方法(J.Han,J.Pei,andY.Yin,SIGMOD’00)深度优先搜索避免显式的候选集生成主要思想:仅仅用局部频繁项从短项中生成长项“abc”是频繁模式得到所有包含“abc”的交易,如,projectDBonabc:DB|abc“d”是局部频繁项inDB|abcabcd是频繁项26从交易数据库构建FP树{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf 4c 4a 3b 3m 3p 3min_support=3TID Itemsbought (ordered)frequentitems100 {f,a,c,d,g,i,m,p}

{f,c,a,m,p}200 {a,b,c,f,l,m,o}

{f,c,a,b,m}300

{b,f,h,j,o,w}

{f,b}400

{b,c,k,s,p}

{c,b,p}500

{a,f,c,e,l,p,m,n}

{f,c,a,m,p}第一次扫描数据库,发现频繁1-项集按降序排列频繁项f-list第二次扫描数据库，构建FP-树F-list=f-c-a-b-m-p27划分模式与数据库频繁模式被划分成子集，根据f-listF-list=f-c-a-b-m-p包含p的模式包含m但不包含p的模式…包含c但不包含a,b,m,p的模式模式f完整但不冗余28从P-条件数据库中发现包含P的模式从FP数据的频繁项头表开始跟踪每个频繁项P的连接，遍历FP树TraversetheFP-treebyfollowingthelinkofeachfrequentitemp累积项P的变换前缀路径，组成p’-条件模式库条件模式库item cond.patternbasec f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf 4c 4a 3b 3m 3p 329从条件模式库到条件FP树

对每个条件模式库累计每个项的计数构建FP-treeforthefrequentitemsofthepatternbasem-conditionalpatternbase:fca:2,fcab:1{}f:3c:3a:3m-conditionalFP-treeAllfrequentpatternsrelatetomm,fm,cm,am,fcm,fam,cam,fcam{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf 4c 4a 3b 3m 3p 330递归:挖掘所有条件FP树{}f:3c:3a:3m-conditionalFP-treeCond.patternbaseof“am”:(fc:3){}f:3c:3am-conditionalFP-treeCond.patternbaseof“cm”:(f:3){}f:3cm-conditionalFP-treeCond.patternbaseof“cam”:(f:3){}f:3cam-conditionalFP-tree31特例:FP树的单路径假定(条件)FP-treeT有一个共享的前缀路径P挖掘分成两部分单个前缀路径约简为一个节点连接两个部分的挖掘结果a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=32FP树结构的优势完整

保留了频繁模式挖掘的完整信息不破坏任何交易的长模式简洁压缩不相关的非频繁项降序的项不比原始数据库更长33频繁模式增长树挖掘方法思想:频繁模式增长通过模式和数据库划分递归的增长频繁模式方法

对每个频繁项,建立条件模式库和条件FP树对每一个新建立的条件FP树重复该过程直到导出的FP树为空，或者仅包含单路径。单路径将生成其子路径的所有组合，其中每一个都是频繁模式34通过数据库投影伸缩FP增长如果FP树不能置于内存，怎么办?数据库投影首先将数据库划分成一个投影数据库的集合然后，在每个投影数据库上建立和挖掘FP树并行投影vs.划分投影技术并行投影ProjecttheDBinparallelforeachfrequentitemParallelprojectionisspacecostlyAllthepartitionscanbeprocessedinparallel划分投影PartitiontheDBbasedontheorderedfrequentitemsPassingtheunprocessedpartstothesubsequentpartitions35划分投影ParallelprojectionneedsalotofdiskspacePartitionprojectionsavesitTran.DBfcampfcabmfbcbpfcampp-projDBfcamcbfcamm-projDBfcabfcafcab-projDBfcb…a-projDBfc…c-projDBf…f-projDB…am-projDBfcfcfccm-projDBfff…36FP-Growthvs.Apriori:基于支持度阈值的伸缩性DatasetT25I20D10KDataMining:ConceptsandTechniques37FP-Growthvs.Tree-Projection:基于支持度阈值的伸缩性DatasetT25I20D100K38模式增长方法的优势分而治之:DecomposeboththeminingtaskandDBaccordingtothefrequentpatternsobtainedsofarLeadtofocusedsearchofsmallerdatabases其他因素Nocandidategeneration,nocandidatetestCompresseddatabase:FP-treestructureNorepeatedscanofentiredatabaseBasicops:countinglocalfreqitemsandbuildingsubFP-tree,nopatternsearchandmatchingAgoodopen-sourceimplementationandrefinementofFPGrowthFPGrowth+(GrahneandJ.Zhu,FIMI'03)39挖掘方法的进一步改进AFOPT(Liu,etal.@KDD’03)A“push-right”methodforminingcondensedfrequentpattern(CFP)treeCarpenter(Pan,etal.@KDD’03)MinedatasetswithsmallrowsbutnumerouscolumnsConstructarow-enumerationtreeforefficientminingFPgrowth+(GrahneandZhu,FIMI’03)EfficientlyUsingPrefix-TreesinMiningFrequentItemsets,Proc.ICDM'03Int.WorkshoponFrequentItemsetMiningImplementations(FIMI'03),Melbourne,FL,Nov.2003TD-Close(Liu,etal,SDM’06)40频繁模式挖掘方法的扩展挖掘闭合模式和最大模式CLOSET(DMKD’00),FPclose,andFPMax(Grahne&Zhu,Fimi’03)挖掘序列模式PrefixSpan(ICDE’01),CloSpan(SDM’03),BIDE(ICDE’04)挖掘图模式gSpan(ICDM’02),CloseGraph(KDD’03)基于约束的频繁模式挖掘Convertibleconstraints(ICDE’01),gPrune(PAKDD’03)基于模式增长的分类Miningfrequentanddiscriminativepatterns(Cheng,etal,ICDE’07)41伸缩性频繁项集挖掘方法Apriori:ACandidateGeneration-and-TestApproachImprovingtheEfficiencyofAprioriFPGrowth:AFrequentPattern-GrowthApproachECLAT:FrequentPatternMiningwithVerticalDataFormatMiningCloseFrequentPatternsandMaxpatterns42ECLAT:使用垂直数据格式挖掘频繁项集垂直模式:t(AB)={T11,T25,…}tid-list:listoftrans.-idscontaininganitemset基于垂直格式推导频繁模式t(X)=t(Y):XandYalwayshappentogethert(X)t(Y):transactionhavingXalwayshasY用diffset

来加速挖掘Onlykeeptrackofdifferencesoftidst(X)={T1,T2,T3},t(XY)={T1,T3}Diffset(XY,X)={T2}Eclat(Zakietal.@KDD’97)MiningClosedpatternsusingverticalformat:CHARM(Zaki&Hsiao@SDM’02)挖掘频繁闭合模式:CLOSETFlist:按支持度升序建立频繁项集表Flist:d-a-f-e-c分解搜索空间PatternshavingdPatternshavingdbutnoa,etc.递归的挖掘频繁闭合模式每一个有d的交易也有cfa

cfad

是一个频繁闭合模式J.Pei,J.Han&R.Mao.“CLOSET:AnEfficientAlgorithmforMiningFrequentClosedItemsets",DMKD'00.TIDItems10a,c,d,e,f20a,b,e30c,e,f40a,c,d,f50c,e,fMin_sup=2MaxMiner:挖掘最大模式1stscan:findfrequentitemsA,B,C,D,E2ndscan:findsupportforAB,AC,AD,AE,ABCDEBC,BD,BE,BCDECD,CE,CDE,DESinceBCDEisamax-pattern,noneedtocheckBCD,BDE,CDEinlaterscanR.Bayardo.Efficientlymininglongpatternsfromdatabases.SIGMOD’98TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,FPotentialmax-patterns45VisualizationofAssociationRules:PlaneGraph46VisualizationofAssociationRules:RuleGraph47VisualizationofAssociationRules

(SGI/MineSet3.0)48第6章:挖掘频繁模式、关联和相关性:基本概念和方法基本概念频繁模式挖掘方法

什么模式是有趣的?—模式评价方法小结49兴趣度的度量客观度量两个最为流行的度量:

支持度和置信度（supportandconfidence）主观度量(Silberschatz&Tuzhilin,KDD95)一个规则（模式）是感兴趣的，如果没有想到的(用户感到惊讶的);可操作的(用户在得到结果后，可以在此之上做些什么)50

支持度-置信度方法的不足Example1:(Aggarwal&Yu,PODS98)5000个学生中3000喜欢打篮球3750喜欢吃米饭2000同时喜欢打篮球和吃米饭关联规则：playbasketball⇒eatcereal[40%,66.7%]该规则具有欺骗性，因为从整个学生情况来看，有75%的学生喜欢吃米饭，大大高于66.7%。关联规则：playbasketball⇒noteatcereal[20%,33.3%]该规则虽然拥有较低的支持度和置信度，但是比较精确。BasketballNotbasketballSum(row)Cereal200017503750Notcereal10002501250Sum(col.)30002000500051

提升：一种兴趣度的度量设A,B是两个项集，P(A∪B)=P(B)*P(A),A和B是独立事件A,B的相关性度量取值小于1，AandB负相关取值大于1，AandB正相关如：上例corr=0.89P(B|A)/P(B)称为规则A=>B的“提升”挖掘相关性关联规则，X^2检验是否有统计意义52Areliftand2GoodMeasuresofCorrelation?“Buywalnutsbuymilk[1%,80%]”ismisleadingif85%ofcustomersbuymilkSupportandconfidencearenotgoodtoindicatecorrelationsOver20interestingnessmeasureshavebeenproposed(seeTan,Kumar,Sritastava@KDD’02)Whicharegoodones?53Null-InvariantMeasures04February2023DataMining:ConceptsandTechniques54兴趣度指标的比较MilkNoMilkSum(row)Coffeem,c~m,ccNoCoffeem,~c~m,~c~cSum(col.)m~m零不变性(transaction)对相关分析是关键的Liftand2

arenotnull-invariant5null-invariantmeasuresNull-transactionsw.r.t.mandcNull-invariantSubtle:TheydisagreeKulczynskimeasure(1927)55AnalysisofDBLPCoauthorRelationshipsAdvisor-adviseerelation:Kulc:high,coherence:low,cosine:middleRecentDBconferences,removingbalancedassociations,lowsup,etc.TianyiWu,YuguoChenandJiaweiHan,“AssociationMininginLargeDatabases:ARe-ExaminationofItsMeasures”,Proc.2007Int.Conf.PrinciplesandPracticeofKnowledgeDiscoveryinDatabases(PKDD'07),Sept.2007哪一个零不变性指标更好?IR(不平衡比):评估规则蕴含式中两个项集A和B的不平衡程度KulczynskiandImbalanceRatio(IR)togetherpresentaclearpictureforallthethreedatasetsD4throughD6D4isbalanced&neutralD5isimbalanced&neutralD6isveryimbalanced&neutral57第6章:挖掘频繁模式、关联和相关性:基本概念和方法基本概念频繁模式挖掘方法

什么模式是有趣的?—模式评价方法小结58小结基本概念:关联,支持度-置信度框架,闭合与最大模式可伸缩频繁模式挖掘方法Apriori(Candidategeneration&test)基于投影的方法(FPgrowth,CLOSET+,...)垂直数据格式(ECLAT,CHARM,...)什么模式是有趣的?模式评估方法59Ref:BasicConceptsofFrequentPatternMining(关联规则)R.Agrawal,T.Imielinski,andA.Swami.Miningassociationrulesbetweensetsofitemsinlargedatabases.SIGMOD'93.(最大模式)R.J.Bayardo.Efficientlymininglongpatternsfromdatabases.SIGMOD'98.(闭合模式)N.Pasquier,Y.Bastide,R.Taouil,andL.Lakhal.Discoveringfrequentcloseditemsetsforassociationrules.ICDT'99.(序列模式)R.AgrawalandR.Srikant.Miningsequentialpatterns.ICDE'9560Ref:AprioriandItsImprovementsR.AgrawalandR.Srikant.Fastalgorithmsforminingassociationrules.VLDB'94.H.Mannila,H.Toivonen,andA.I.Verkamo.Efficientalgorithmsfordiscoveringassociationrules.KDD'94.A.Savasere,E.Omiecinski,andS.Navathe.Anefficientalgorithmforminingassociationrulesinlargedatabases.VLDB'95.J.S.Park,M.S.Chen,andP.S.Yu.Aneffectivehash-basedalgorithmforminingassociationrules.SIGMOD'95.H.Toivonen.Samplinglargedatabasesforassociationrules.VLDB'96.S.Brin,R.Motwani,J.D.Ullman,andS.Tsur.Dynamicitemsetcountingandimplicationrulesformarketbasketanalysis.SIGMOD'97.S.Sarawagi,S.Thomas,andR.Agrawal.Integratingassociationruleminingwithrelationaldatabasesystems:Alternativesandimplications.SIGMOD'98.61Ref:Depth-First,Projection-BasedFPMiningR.Agarwal,C.Aggarwal,andV.V.V.Prasad.Atreeprojectionalgorithmforgenerationoffrequentitemsets.J.ParallelandDistributedComputing:02.J.Han,J.Pei,andY.Yin.Miningfrequentpatternswithoutcandidategeneration.SIGMOD’00.J.Liu,Y.Pan,K.Wang,andJ.Han.MiningFrequentItemSetsbyOpportunisticProjection.KDD'02.J.Han,J.Wang,Y.Lu,andP.Tzvetkov.MiningTop-KFrequentClosedPatternswithoutMinimumSupport.ICDM'02.J.Wang,J.Han,andJ.Pei.CLOSET+:SearchingfortheBestStrategiesforMiningFrequentClosedItemsets.KDD'03.G.Liu,H.Lu,W.Lou,J.X.Yu.OnComputing,StoringandQueryingFrequentPatterns.KDD'03.G.GrahneandJ.Zhu,EfficientlyUsingPrefix-TreesinMiningFrequentItemsets,Proc.ICDM'03Int.WorkshoponFrequentItemsetMiningImplementations(FIMI'03),Melbourne,FL,Nov.200362Ref:VerticalFormatandRowEnumerationMethodsM.J.Zaki,S.Parthasarathy,M.Ogihara,andW.Li.Parallelalgorithmfordiscoveryofassociationrules.DAMI:97.ZakiandHsiao.CHARM:AnEfficientAlgorithmforClosedItemsetMining,SDM'02.C.Bucila,J.Gehrke,D.Kifer,andW.White.DualMiner:ADual-PruningAlgorithmforItemsetswithConstraints.KDD’02.F.Pan,G.Cong,A.K.H.Tung,J.Yang,andM.Zaki,CARPENTER:FindingClosedPatternsinLongBiologicalDatasets.KDD'03.H.Liu,J.Han,D.Xin,andZ.Shao,MiningInterestingPatternsfromVeryHighDimensionalData:ATop-DownRowEnumerationApproach,SDM'06.63Ref:MiningCorrelationsandInterestingRulesM.Klemettinen,H.Mannila,P.Ronkainen,H.Toivonen,andA.I.Verkamo.Findinginterestingrulesfromlargesetsofdiscoveredassociationrules.CIKM'94.S.Brin,R.Motwani,andC.Silverstein.Bey