Extraktorer och taggar förvandlar ostrukturerad text till enhetsrelationsdiagram där noder är enheter (e-post, papper, person, konferens, företag) och kanter är relationer (skrivs, citeras, verk-för). Skriven närhetssökning av formen type=person NÄRA företag"IBM", paper till"XML" är en allt mer användbar sökparadigm i ER grafer. Närhet sökning implementationer antingen utföra en Pagerank-liknande beräkning vid frågestunden, som är långsam, eller förkompilera, lagra och kombinera per-word Pageranks, som kan vara mycket dyrt när det gäller förbehandling tid och utrymme. Vi presenterar HubRank, ett nytt system för snabba, dynamiska, rymdeffektiva närhetssökningar i ER-grafer. Under förbehandling, HubRank beräknar och indexerar vissa "sketchy" slumpmässiga gå fingeravtryck för en liten del av noder, noga valt med hjälp av statistik frågelogg. Vid frågestunden identifieras en liten "aktiv" subgraf, som gränsar till noder med indexerade fingeravtryck. Dessa fingeravtryck är adaptivt laddade till olika upplösningar för att bilda ungefärliga personliga Pagerank vektorer (PPV). PPVs vid återstående aktiva noder beräknas nu iterativt. Vi rapporterar om experiment med CiteSeer's ER graf och miljontals riktiga CiteSeer frågor. Några representativa siffror följer. På vår testbädd förbehandlar och indexerar HubRank 52 gånger snabbare än en helvokabulär PPV-beräkning. Ett textindex upptar 56 MB. Helvokabulära PPV:er skulle förbruka 102 GB. Om PPVs trunkeras till 56 MB, precision jämfört med sant Pagerank sjunker till 0,55, i kontrast, HubRank har precision 0,91 vid 63 MB. HubRanks genomsnittliga frågetid är 200-300 millisekunder; frågetid Pagerank beräkning tar 11 sekunder i genomsnitt.
Mer nyligen, Chakrabarti REF utvecklat HubRank algoritm, som precompute offline den Personaliserade Pagerank Vectors (PPVs) för en liten bråkdel av noder, noga valt med hjälp av statistik frågelogg.
Dynamic personalized pagerank in entity-relation graphs
{'venue': "WWW '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}