Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

4-2013

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.

Keywords

Queries, specificity, graphs, random walk, round trip, algorithms, ranking tasks

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

2013 IEEE International Conference on Data Engineering ICDE: 8-12 April, Brisbane, Australia: Proceedings

First Page

613

Last Page

624

ISBN

9781467349093

Identifier

10.1109/ICDE.2013.6544860

Publisher

IEEE Computer Society

City or Country

Los Alamitos, CA

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/ICDE.2013.6544860

Download

Share

COinS