Incremental C-Rank: An Effective and Efficient Ranking Algorithm for Dynamic Web Environment

Abstract

Web page ranking is one of the core components in search engines. Given a user query, it aims at providing a ranked list of Web pages that the user is likely to prefer the most. C-Rank, which is a contribution-based ranking algorithm that combines content and link information effectively by using the concept of contribution, is known to provide high performance in terms of both accurate and prompt responses to user queries. However, C-Rank suffers from the very high cost to reflect the changes in World Wide Web, which are highly dynamic as well as very frequent these days because it re-computes all the C-Rank scores used for ranking from the scratch so as to reflect the changes. This could make C-Rank considered inappropriate in providing users with accurate and up-to-date search results. This paper aims to remedy this limitation of CRank. We propose Incremental C-Rank, which is designed to update the C-Rank scores of only a part of the Web pages carefully chosen rather than those of all the Web pages, without any accuracy loss. Our experimental results on real-world datasets confirm both the effectiveness and efficiency of our proposed method.