DOGMA: A disk-oriented graph matching algorithm for RDF databases

Matthias Bröcheler*, Andrea Pugliese, V. S. Subrahmanian

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations

Abstract

RDF is an increasingly important paradigm for the representation of information on the Web. As RDF databases increase in size to approach tens of millions of triples, and as sophisticated graph matching queries expressible in languages like SPARQL become increasingly important, scalability becomes an issue. To date, there is no graph-based indexing method for RDF data where the index was designed in a way that makes it disk-resident. There is therefore a growing need for indexes that can operate efficiently when the index itself resides on disk. In this paper, we first propose the DOGMA index for fast subgraph matching on disk and then develop a basic algorithm to answer queries over this index. This algorithm is then significantly sped up via an optimized algorithm that uses efficient (but correct) pruning strategies when combined with two different extensions of the index. We have implemented a preliminary system and tested it against four existing RDF database systems developed by others. Our experiments show that our algorithm performs very well compared to these systems, with orders of magnitude improvements for complex graph queries.

Original languageEnglish (US)
Title of host publicationThe Semantic Web, ISWC 2009 - 8th International Semantic Web Conference, ISWC 2009, Proceedings
PublisherSpringer Verlag
Pages97-113
Number of pages17
ISBN (Print)364204929X, 9783642049293
DOIs
StatePublished - 2009
Externally publishedYes
Event8th International Semantic Web Conference, ISWC 2009 - Chantilly, United States
Duration: Oct 25 2009Oct 29 2009

Publication series

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

Conference

Conference8th International Semantic Web Conference, ISWC 2009
Country/TerritoryUnited States
CityChantilly
Period10/25/0910/29/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'DOGMA: A disk-oriented graph matching algorithm for RDF databases'. Together they form a unique fingerprint.

Cite this