Conference Proceeding Article
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.
Queries, specificity, graphs, random walk, round trip, algorithms, ranking tasks
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
Proceedings of the IEEE International Conference on Data Engineering (ICDE)
IEEE Computer Society
City or Country
Fang, Yuan, Kevin C. C. Chang and Hady W. Lauw. 2013. "RoundTripRank: Graph-based Proximity with Importance and Specificity." In Proceedings of the IEEE International Conference on Data Engineering (ICDE).
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.