TY - GEN
T1 - RoundTripRank
T2 - 29th International Conference on Data Engineering, ICDE 2013
AU - Fang, Yuan
AU - Chang, Kevin Chen Chuan
AU - Lauw, Hady W.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84881324616&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84881324616&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2013.6544860
DO - 10.1109/ICDE.2013.6544860
M3 - Conference contribution
AN - SCOPUS:84881324616
SN - 9781467349086
T3 - Proceedings - International Conference on Data Engineering
SP - 613
EP - 624
BT - ICDE 2013 - 29th International Conference on Data Engineering
Y2 - 8 April 2013 through 11 April 2013
ER -