RoundTripRank: Graph-based proximity with importance and specificity?

Yuan Fang, Kevin Chen Chuan Chang, Hady W. Lauw

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

Abstract

Graph-based proximity has many applications with different ranking needs. However, most previous works only stress the sense of importance by finding "popular" results for a query. Often times important results are overly general without being well-tailored to the query, lacking a sense of specificity - which only emerges recently. Even then, the two senses are treated independently, and only combined empirically. In this paper, we generalize the well-studied importance-based random walk into a round trip and develop RoundTripRank, seamlessly integrating specificity and importance in one coherent process. We also recognize the need for a flexible trade-off between the two senses, and further develop RoundTripRank+ based on a scheme of hybrid random surfers. For efficient computation, we start with a basic model that decomposes RoundTripRank into smaller units. For each unit, we apply a novel two-stage bounds updating framework, enabling an online top-K algorithm 2SBound. Finally, our experiments show that RoundTripRank and RoundTripRank+ are robust over various ranking tasks, and 2SBound enables scalable online processing.

Original languageEnglish (US)
Title of host publicationICDE 2013 - 29th International Conference on Data Engineering
Pages613-624
Number of pages12
DOIs
StatePublished - 2013
Event29th International Conference on Data Engineering, ICDE 2013 - Brisbane, QLD, Australia
Duration: Apr 8 2013Apr 11 2013

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Other

Other29th International Conference on Data Engineering, ICDE 2013
Country/TerritoryAustralia
CityBrisbane, QLD
Period4/8/134/11/13

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'RoundTripRank: Graph-based proximity with importance and specificity?'. Together they form a unique fingerprint.

Cite this