Gauging correct relative ranking on similarity search

Weiren Yu, Julie McCann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationCIKM '15 : Proceedings of the 24th ACM International on Conference on Information and Knowledge Management
Place of PublicationNew York, NY (US)
PublisherACM
Pages1791-1794
Number of pages4
ISBN (Print)978-1-4503-3794-6
DOIs
Publication statusPublished - 17 Oct 2015
Event24th ACM International on Conference on Information and Knowledge Management - Melbourne, Australia
Duration: 18 Oct 201523 Oct 2015

Conference

Conference24th ACM International on Conference on Information and Knowledge Management
Abbreviated titleCIKM 2015
CountryAustralia
CityMelbourne
Period18/10/1523/10/15

Fingerprint

Gaging

Cite this

Yu, W., & McCann, J. (2015). Gauging correct relative ranking on similarity search. In CIKM '15 : Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (pp. 1791-1794). New York, NY (US): ACM. https://doi.org/10.1145/2806416.2806610
Yu, Weiren ; McCann, Julie. / Gauging correct relative ranking on similarity search. CIKM '15 : Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. New York, NY (US) : ACM, 2015. pp. 1791-1794
@inproceedings{bcf9038a17334b3ba815372de0e3b57e,
title = "Gauging correct relative ranking on similarity search",
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.",
author = "Weiren Yu and Julie McCann",
year = "2015",
month = "10",
day = "17",
doi = "10.1145/2806416.2806610",
language = "English",
isbn = "978-1-4503-3794-6",
pages = "1791--1794",
booktitle = "CIKM '15 : Proceedings of the 24th ACM International on Conference on Information and Knowledge Management",
publisher = "ACM",
address = "United States",

}

Yu, W & McCann, J 2015, Gauging correct relative ranking on similarity search. in CIKM '15 : Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, New York, NY (US), pp. 1791-1794, 24th ACM International on Conference on Information and Knowledge Management, Melbourne, Australia, 18/10/15. https://doi.org/10.1145/2806416.2806610

Gauging correct relative ranking on similarity search. / Yu, Weiren; McCann, Julie.

CIKM '15 : Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. New York, NY (US) : ACM, 2015. p. 1791-1794.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Gauging correct relative ranking on similarity search

AU - Yu, Weiren

AU - McCann, Julie

PY - 2015/10/17

Y1 - 2015/10/17

N2 - 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.

AB - 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.

UR - http://dl.acm.org/citation.cfm?id=2806610

U2 - 10.1145/2806416.2806610

DO - 10.1145/2806416.2806610

M3 - Conference contribution

SN - 978-1-4503-3794-6

SP - 1791

EP - 1794

BT - CIKM '15 : Proceedings of the 24th ACM International on Conference on Information and Knowledge Management

PB - ACM

CY - New York, NY (US)

ER -

Yu W, McCann J. Gauging correct relative ranking on similarity search. In CIKM '15 : Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. New York, NY (US): ACM. 2015. p. 1791-1794 https://doi.org/10.1145/2806416.2806610