remainingeq2

Thisdocumentistheonline-onlyappendixto:Efficientk-closestpairqueriesingeneralmetricspacesYunjunGao·LuChen·XinhanLi·BinYao·GangChenReceived:21May2014/Revised:10February2015/Accepted:13March2015A.
EXAMPLEOFRMAEXAMPLE1.
WeillustrateRMAusingtherunningexampledepictedinFig.
7,andsupposek=2.
Firstofall,RMAupdatesmaxCPD2to5.
5usingLemma2,andprunestherootentrypairEP3,EQ1byRule1duetomindist(EP3,EQ1)>maxCPD2.
IttheninvokesRMA-PEPfortherootentrypairEP2,EQ1withthesmallestmindist.
SinceEP2andEQ1aretheintermediateentriespointingtonon-leafnodes,RMA-PEPcallsPRUNEtoevaluatethesubentriesofEP2,i.
e.
,EP6andEP7,whichcannotbediscardedbyRules1-2.
Similarly,thesubentriesEQ3andEQ4ofEQ1canalsonotbepruned.
Next,itevaluatestheremainingsubentriesnotpruned.
Forexample,sincebothemindist(EP6,EQ3)andmindist(EP6,EQ3)aresmallerthanmaxCPD2,EP6,EQ3isinsertedintoH,andmaxCPD2isupdatedto5viaLemma1;whileasmindist(EP6,EQ4)andmindist(EP6,EQ4)arelargerthanmaxCPD2,EP6,EQ4andEP7,EQ4arediscarded.
Atthistime,thealgorithmgetsH={EP6,EQ3,EP7,EQ3},andthen,recursivelyinvokesRMA-PEPforeveryentrypairinHuntilmindist(EP7,EQ3)>maxCPD2,afterwhichSR={p7,q3,p6,q3}.
Thereafter,similarasEP2,EQ1,RMAbacktrackstovisitthenextrootentrypairEP1,EQ2.
Thealgorithmproceedsinthesamemanneruntilmindist(EP1,EQ1)>maxCPD2,andreturnsthefinalqueryresultsetSR={p5,q9,p4,q9}.
Fig.
22illustratesthemainoperationsofRMAforM2CPsearch,inwhichtheprunedentrypairsareshownwithstrikethroughfonts.
B.
EXAMPLEOFIMAEXAMPLE2.
ConsidertherunningexampleillustratedinFig.
7again.
Tobeginwith,IMAupdatesmaxCPD2to5.
5usingLemma2,andinsertstherootentrypairsnotpruned(byRule1)intoH,whereH={EP2,EQ1,EP1,EQ2,EP1,EQ1,EP2,EQ2,EP3,EQ2}.
Then,itvisitsthetopentrypairEP2,EQ1ofH,addsallqualifiedsubentrypairsofEP2,EQ1notprunedbyRules1-2toH,andupdatesmaxCPD2to5viaLemma1.
Thereafter,similarasEP2,EQ1,IMAvisitstheheadentryEP1,EQ2ofH.
Next,itvisitsthetopentryEP5,EQ6ofH.
SinceEP5andEQ6pointstoleafnodes,IMAupdatesSRto{p5,q9,p4,q9},andmaxCPD2tod(p4,q9)(=1.
2).
Finally,IMAterminatesandreturnsthefinalresultsetSR,duetomindist(EP1,EQ1)>maxCPD2.
ThemainoperationsofIMAforM2CPretrievalaredepictedinFig.
23,wheretheprunedentrypairsareshownwithstrikethroughfonts.
C.
EXAMPLEOFEHMEXAMPLE3.
ConsidertherunningexampleshowninFig.
7again,andsupposeeCPD2=3(k=2).
Firstofall,EHMoperationsandcontentsoflocalheapsProcessrootentrypairsandgetH1={,,,,,},,,SRmaxCPDk5.
551.
233VisitofH1andgetH2={,,,}VisitofH2andupdateSRTerminatevisitingH2duetomindist(EP7,EQ3)>maxCPDkBacktracktovisitofH1andgetH3={,,,}VisitofH3andupdateSR,TerminatevisitingH3duetomindist(EP5,EQ5)>maxCPDk31.
2,TerminatevisitingH1duetomindist(EP1,EQ1)>maxCPDk,1.
2Fig.
22IllustrationofRMAoperationsProcessrootentrypairsVisitVisitVisitH(global),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,SRmaxCPDk5.
5531.
2Fig.
23IllustrationofIMAupdatesmaxCPD2to5.
5,prunestherootentrypairEP3,EQ1asmindist(EP3,EQ1)>maxCPD2,andinsertsEP2,EQ1intoS(duetomindist(EP2,EQ1)=0),EP3,EQ2intoCH(asmindist(EP3,EQ2)>eCPD2),andEP1,EQ2,EP1,EQ1,EP2,EQ2intoH(sincetheirmindistarelargerthan0butsmallerthaneCPD2).
Then,thealgorithmvisitsthetopentrypairEP2,EQ1ofS,andaddsallitssubentrypairstoEHbecausetheiremindistislargerthaneCPD2.
Next,itvisitsentrypairsinHiterativelyuntilmindist(EP1,EQ1)>maxCPD2.
Finally,EHMterminates,andreturnsthefinalresultsetSR.
Notethat,inthiscase,compensationdoesnotneedsince,foreveryentrypairEP,EQpreservedinEHandCH,theiremindistormindistarelargerthanmaxCPD2.
Also,theI/OcostofEHMisthesameasthatofIMA,i.
e.
,threeintermediateentrypairsareaccessed.
Nevertheless,EHMavoidscomputingthemindistforentrypairsstoredinEH,incurringsmallercomputationalcost.
Fig.
24illustratestheoperationsofEHMforM2CPretrieval.
D.
EXAMPLEOFEHSEXAMPLE4.
WeillustrateEHSusingtheSM2CP(k=2)queryontheobjectsetOshowninFig.
2a,andsupposeeCPD2=r4.
Firstofall,EHSupdatesmaxCPD2withr5usingLemma7,andinsertse5,e5,e5,e6,ande6,e6intoSastheirmindistsequalsto0.
Itthenvisitsthetopentrye5,e5ofS,andcallsEHS-PEPtoexpande5,e5.
Sincee5=e5ande5pointstothenon-leafnode,EHS-PEPinsertsthequalifiedsubentrypairse1,e1,e1,e2,ande2,e2intoS,andupdatesmaxCPD2tor2usingLemma7.
Next,EHSvisitsthetopentrypaire1,e1ofS,andinvokesEHS-PEPtoexpande1,e1.
Sincee1=e1ande1pointstotheleafnode,EHS-PEPupdatesSRto{o1,o2}.
Similarly,thealgorithmproceedstoevaluateentrypairsofSuntilSisempty.
Finally,thealgorithmterminatesandreturnsSR={o3,o4,o1,o2}.
Fig.
25showstheoperationsofEHSforSM2CPretrieval.
E.
EXAMPLEOFMSAEXAMPLE5.
ConsidertheSM2CP(k=2)queryontheobjectsetOshowninFig.
2a,withCOMdnn-treeillustratedinFig.
10.
First,maxCPD2isinitializedtoinfinity.
MSAinsertsrootentriese5ande6intoH.
Then,itpopsthetopentrye5fromH.
Sincee5pointstothenon-leafnode,thealgorithminsertsthequalifiedsub-entriese1ande2intoH,sincee1.
dnn(=r1)ande2.
dnn(=d(o3,o4))aresmallerthanmaxCPD2.
Next,thealgorithmpopstheheadentrye1fromH.
Ase1pointstotheleafnode,thequalifiedsubentries(objects)o1ando2areinsertedintoCH.
Then,e2isprocessedsimilarly,afterwhichCH={o3,o4,o1,o2}andmaxCPD2=r1.
Thereafter,e6ispopped,andthewhile-loopstopsduetoe6.
dnn>maxCPD2.
Inthesequel,MSAevaluateseachobjectoiinCHinorder,andcomparesoiwithalreadyvisitedobjectsojtoupdateSRandmaxCPD2ifd(oi,oj)≤maxCPD2.
Forexample,whenvisitingo4,asd(o4,o3)≤maxCPD2,SRisupdatedto{o3,o4}.
Finally,thealgorithmreturnsSR={o3,o4,o1,o2}.
Fig.
26depictstheoperationsofMSAforSM2CPretrieval.
operationsProcessrootentrypairsVisitofSVisitofHVisitofHS,,,,,,,,,,,,,,HCHEH,,,,,,,,,SRmaxCPDk5.
5531.
2Fig.
24IllustrationofEHMoperationsProcessrootentrypairsVisitofSVisitofSVisitofSSSR,,HCHEH,,,,,,,VisitofS,,,,VisitofS,,VisitofS,,VisitofSVisitofSVisitofS,,,,maxCPDkr5r2r2r2r1r1r1r1r1r1Fig.
25IllustrationofEHSoperationsProcessrootentriesVisite5ofHVisite1ofHHSRe5,e6CHmaxCPDke1,e2,e6e2,e6Visito3ofCHe6Visito4ofCHVisito1ofCH,Visite2ofHo1,o2o3,o4,o1,o2o3,o4,o1,o2o3,o4,o1,o2Visito2ofCHo3,o4,o1,o2o3,o4,o1,o2r1r1r1r1r1∞∞∞Fig.
26IllustrationofMSA