Gauging Correct Relative Rankings For Similarity Search
File(s)Relative Ranking.pdf (408.18 KB)
Accepted version
Author(s)
Yu, W
McCann, JA
Type
Conference Paper
Abstract
One of the important tasks in link analysis is to quantify the similarity between two objects based on hyperlink structure. SimRank is an attractive similarity measure of this type. Existing work mainly focuses on absolute SimRank scores, and often harnesses an iterative paradigm to compute them. While these iterative scores converge to exact ones with the increasing number of iterations, it is still notoriously difficult to determine how well the relative orders of these iterative scores can be preserved for a given iteration. In this paper, we propose efficient ranking criteria that can secure correct relative orders of node-pairs with respect to SimRank scores when they are computed in an iterative fashion. Moreover, we show the superiority of our criteria in harvesting top-K SimRank scores and bucket orders from a full ranking list. Finally, viable empirical studies verify the usefulness of our techniques for SimRank top-K ranking and bucket ordering.
Date Issued
2015-10-17
Date Acceptance
2015-10-17
Citation
Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM '15), 2015, pp.1791-1794
ISBN
978-1-4503-3794-6
Publisher
Association for Computing Machinery
Start Page
1791
End Page
1794
Journal / Book Title
Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM '15)
Copyright Statement
© ACM 2015. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, http://dx.doi.org/10.1145/2806416.2806610.
Sponsor
NEC Corporation
Grant Number
N/A
Source
24th ACM International on Conference on Information and Knowledge Management (CIKM '15)
Publication Status
Published
Start Date
2015-10-19
Finish Date
2015-10-23
Coverage Spatial
Melbourne, Australia