SimRank är ett viktigt mått på vertex-par likhet enligt strukturen av grafer. Likhetssökningen baserad på SimRank är en viktig operation för att identifiera liknande hörn i en graf och har använts i många dataanalysapplikationer. Numera blir graferna i den verkliga världen mycket större och mer dynamiska. De befintliga lösningarna för likhetssökning är dyra när det gäller tids- och rymdkostnader. Ingen av dem kan effektivt stödja likhetssökning över stora dynamiska grafer. I detta dokument föreslår vi en ny ram för slumpmässig provtagning i två steg (TSF) för SimRank-baserad likhetssökning (t.ex. top-k-sökning). I förbehandlingen tar TSF prov på en uppsättning enkelriktade grafer för att indexera råa slumpmässiga promenader på ett nytt sätt inom O(N Rg) tid och rum, där N är antalet hörn och Rg är antalet enkelriktade grafer. Envägsgrafen kan uppdateras effektivt i enlighet med grafmodifieringen, vilket gör att TSF lämpar sig väl för dynamiska grafer. Under frågestadiet kan TSF söka liknande hörn snabbt genom att naturligt beskära okvalificerade hörn baserat på anslutning av enkelriktade grafer. Dessutom, med ytterligare Rq prover, TSF kan uppskatta SimRank poäng med probabil- (1‐c) 2 om felet i approximationen begränsas av 1 −  på. Slutligen, för att garantera skalbarheten av TSF, kan enkelriktade grafer också lagras kompakt på disken när minnet är begränsat. Omfattande experiment har visat att TSF kan hantera dynamiska miljarder-kant grafer med hög prestanda.
TSF REF är en tvåstegs slumpmässig provtagningsalgoritm för enkla och toppk SimRank-frågor på dynamiska grafer.
An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}