SimRank är ett likhetsmått för grafnoder som har många tillämpningar i praktiken. Skalbar SimRank beräkning har varit föremål för omfattande forskning i mer än ett decennium, och ändå, ingen av de befintliga lösningarna kan effektivt härleda SimRank poäng på stora grafer med påvisbara noggrannhetsgarantier. I synnerhet, den state-of-the-art lösning kräver upp till några sekunder för att beräkna en SimRank poäng i million-node grafer, och inte ger någon värsta fall försäkran när det gäller frågefelet. I detta dokument presenteras SLING, en effektiv indexstruktur för Sim-Rank beräkning. SLING garanterar att varje SimRank poäng returneras har som mest ε additivt fel, och det besvarar alla enkelpar och en källa SimRank frågor i O(1/ε) respektive O (n/ε) tid, respektive. Dessa tidskomplex är nästan optimala, och är betydligt bättre än de asymptotiska gränserna för den senaste metoden. Dessutom kräver SLING endast O (n/ε) utrymme (som också är nära optimal i en asymptotisk betydelse) och O (m/ε + n log n δ /ε 2 ) pre-beräkningstid, där δ är felsannolikheten för förbehandlingsalgoritmen. Vi utvärderar experimentellt SLING med en mängd olika verkliga grafer med upp till flera miljoner noder. Våra resultat visar att SLING är upp till 10000 gånger (sp. 110 gånger) snabbare än konkurrerande metoder för enkelpar (resp. en källa) SimRank frågor, till priset av högre utrymme overheads.
Tian och Xiao REF presenterar SLING, en indexstruktur som besvarar en enda källa SimRank fråga i O(m log 1 εa ) tid och kräver O (n/εa) utrymme.
SLING: A Near-Optimal Index Structure for SimRank
{'venue': "SIGMOD '16", 'journal': None, 'mag_field_of_study': ['Computer Science']}