### Abstract

Original language | English |
---|---|

Title of host publication | SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval |

Place of Publication | New York, NY (US) |

Publisher | ACM |

Pages | 859-862 |

Number of pages | 4 |

Publication status | Published - 3 Jul 2014 |

Event | 37th international ACM SIGIR conference on Research & Development in Information Retrieval - Gold Coast, Queensland, Australia Duration: 6 Jul 2014 → 11 Jul 2014 |

### Conference

Conference | 37th international ACM SIGIR conference on Research & Development in Information Retrieval |
---|---|

Abbreviated title | SIGIR 2014 |

Country | Australia |

City | Gold Coast, Queensland |

Period | 6/07/14 → 11/07/14 |

### Cite this

*SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval*(pp. 859-862). New York, NY (US): ACM.

}

*SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval.*ACM, New York, NY (US), pp. 859-862, 37th international ACM SIGIR conference on Research & Development in Information Retrieval, Gold Coast, Queensland, Australia, 6/07/14.

**Sig-SR: SimRank search over singular graphs.** / Yu, Weiren; McCann, Julie A.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Sig-SR: SimRank search over singular graphs

AU - Yu, Weiren

AU - McCann, Julie A.

PY - 2014/7/3

Y1 - 2014/7/3

N2 - SimRank is an attractive structural-context measure of similarity between two objects in a graph. It recursively follows the intuition that "two objects are similar if they are referenced by similar objects". The best known matrix-based method [1] for calculating SimRank, however, implies an assumption that the graph is non-singular, its adjacency matrix is invertible. In reality, non-singular graphs are very rare; such an assumption in [1] is too restrictive in practice. In this paper, we provide a treatment of [1], by supporting similarity assessment on non-invertible adjacency matrices. Assume that a singular graph G has n nodes, with r(2+Kr2)) time for K iterations. In contrast, the only known matrix-based algorithm that supports singular graphs [1] needs O(r4n2) time. The experimental results on real and synthetic datasets demonstrate the superiority of InvSR on singular graphs against its baselines.

AB - SimRank is an attractive structural-context measure of similarity between two objects in a graph. It recursively follows the intuition that "two objects are similar if they are referenced by similar objects". The best known matrix-based method [1] for calculating SimRank, however, implies an assumption that the graph is non-singular, its adjacency matrix is invertible. In reality, non-singular graphs are very rare; such an assumption in [1] is too restrictive in practice. In this paper, we provide a treatment of [1], by supporting similarity assessment on non-invertible adjacency matrices. Assume that a singular graph G has n nodes, with r(2+Kr2)) time for K iterations. In contrast, the only known matrix-based algorithm that supports singular graphs [1] needs O(r4n2) time. The experimental results on real and synthetic datasets demonstrate the superiority of InvSR on singular graphs against its baselines.

M3 - Conference contribution

SP - 859

EP - 862

BT - SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval

PB - ACM

CY - New York, NY (US)

ER -