Item

Abstract

Web archives like the {I}nternet {A}rchive preserve the evolutionary history of large portions of the {W}eb. Access to them, however, is still via rather limited interfaces – a search functionality is often missing or ignores the time axis. Time-travel search alleviates this shortcoming by enriching keyword queries with a time-context of interest. In order to be effective, time-travel queries require historical {P}age{R}ank scores. In this paper, we address this requirement and propose rank synopses as a novel structure to compactly represent and reconstruct historical {P}age{R}ank scores. Rank synopses can reconstruct the {P}age{R}ank score of a web page as of any point during its lifetime, even in the absence of a snapshot of the {W}eb as of that time. We further devise a normalization scheme for {P}age{R}ank scores to make them comparable across different graphs. Through a comprehensive evaluation over different datasets, we demonstrate the accuracy and space-economy of the proposed methods.