Distributed query processing on compressed graphs using K2-trees

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

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva

2 Citas (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.

Idioma originalInglés
Título de la publicación alojadaString Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings
EditorialSpringer Verlag
Número de páginas13
ISBN (versión impresa)9783319024318
EstadoPublicada - 1 ene. 2013
Evento20th International Symposium on String Processing and Information Retrieval, SPIRE 2013 - Jerusalem, Israel
Duración: 7 oct. 20139 oct. 2013

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen8214 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349


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

Áreas temáticas de ASJC Scopus

  • Ciencia computacional teórica
  • Informática (todo)


Profundice en los temas de investigación de 'Distributed query processing on compressed graphs using K2-trees'. En conjunto forman una huella única.

Citar esto