Måttet på likhet mellan objekt är ett mycket användbart verktyg inom många områden inom datavetenskapen, inklusive informationssökning. SimRank är ett enkelt och intuitivt mått av detta slag, baserat på graf-teoretisk modell. SimRank är typiskt beräknas iterativt, i anda av PageRank. Det befintliga arbetet med SimRank saknar dock noggrannhetsbedömning av iterativ beräkning och har avskräckt från tids komplexitet. I detta papper presenterar vi en teknik för att uppskatta noggrannheten av dator SimRank iterativt. Denna teknik ger ett sätt att ta reda på det antal iterationer som krävs för att uppnå önskad noggrannhet när du datorar SimRank. Vi presenterar också optimeringstekniker som förbättrar den beräkningsmässiga komplexiteten hos den iterativa algoritmen från O(n 4 ) till O(n 3 ) i värsta fall. Vi inför också ett tröskelvärde för heuristisk heurism och dess noggrannhetsbedömning som ytterligare förbättrar metodens effektivitet. Som en praktisk illustration av våra tekniker beräknade vi SimRank poäng på en delmängd av engelska Wikipedia corpus, bestående av den kompletta uppsättningen artiklar och kategori länkar.
Lizorkin m.fl. REF presenterar en teknik för att uppskatta noggrannheten i beräkning SimRank iterativt och vissa optimeringstekniker som förbättrar prestandan hos den iterativa algoritmen.
Accuracy estimate and optimization techniques for SimRank computation
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}