Distributed query processing on compressed graphs using K2-trees

Sandra Álvarez-García, Nieves R. Brisaboa, Carlos Gómez-Pantoja, Mauricio Marin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)


Compact representation of Web and social graphs can be made efficiently with the K2-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 2-tree also enables fast processing of relevant queries such as direct and reverse neighbours in the compressed graph. These two properties make the K2-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 K2-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.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319024318
Publication statusPublished - 1 Jan 2013
Event20th International Symposium on String Processing and Information Retrieval, SPIRE 2013 - Jerusalem, Israel
Duration: 7 Oct 20139 Oct 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8214 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Symposium on String Processing and Information Retrieval, SPIRE 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Distributed query processing on compressed graphs using K2-trees'. Together they form a unique fingerprint.

Cite this