Distributed query processing on compressed graphs using K2-trees

Compact representation of Web and social graphs can be made efficiently with the K²-tree as it achieves compression ratios about 5 bits per link for web graphs and about 20 bits per link for social graphs. The K ²-tree also enables fast processing of relevant queries such as direct and reverse neighbours in the compressed graph. These two properties make the K²-tree suitable for inclusion in Web search engines where it is necessary to maintain very large graphs and to process on-line queries on them. Typically these search engines are deployed on dedicated clusters of distributed memory processors wherein the data set is partitioned and replicated to enable low query response time and high query throughput. In this context a practical strategy is simply to distribute the data on the processors and build local data structures for efficient retrieval in each processor. However, the way the data set is distributed on the processors can have a significant impact in performance. In this paper, we evaluate a number of data distribution strategies which are suitable for the K²-tree and identify the alternative with the best general performance. In our study we consider different data sets and focus on metrics such as overall compression ratio and parallel response time for retrieving direct and reverse neighbours.