| We are witnessing the emergence of large-scale graphs such as social networks and the deployment of applications that are designed to fully utilize these graphs. Since the invention of PageRank, the mainstream approach has been to use similarity degrees that are calculated based on the link structures of the graphs. Personalized Page Rank (PPR) is the most popular degree, which is obtained from random walks that originate at a querying node. PPR has the advantage of being able to incorporate a userfs preference into the importance of graph nodes for each query. In reality, graphs may dynamically change with the passage of time. If a user were able to query a given graph in an ad-hoc manner, it would be good news. The issue lies in the calculation cost; as the scale of graphs gets higher, such ad-hoc calculation needs a much longer time. Several researchers have tried to reduce the calculation cost, but the solutions proposed so far are shackled by technical limitations; one needs preparatory calculations and another sacrifices calculation accuracy. In contrast to the past work, Castanet, the querying method proposed in this paper, has the unique feature of recursively calculating upper and lower limits of PPR scores and pruning unnecessary nodes in a process to answer a Top-k graph query for an arbitrary graph. Thus, it can be expected that the given Top-k query will be answered quickly and accurately. The paper proposes a querying algorithm in Castanet, presents a theoretical cost analysis that demonstrates its superiority, and describes experiments that the authors performed using different graph applications to verify its technical effectiveness in comparison with conventional methods. As remarked above, the paper introduces a highly promising algorithm that will enable fast and accurate querying for large-scale graphs. Consequently, the paper undoubtedly deserves IEICEfs Best Paper Award.
|
