DOGMA
Disk-Oriented Graph Management
As social networks such as Facebook, Twitter, Myspace, LinkedIn, LiveJournal and others get increasingly larger, efficient indexes need to be developed in order to support very basic social network operations such as graph matching. We assume a social network consists of edge-labeled nodes and that a query can be expressed as a graph pattern (with some variables denoting nodes with unknown labels). Subgraph matching deals with the problem of finding all instances of the query graph in the social network. Subgraph matching is well known to be NP-hard, but unfortunately, this does not make the problem of subgraph matching go away. We need to perform this operation efficiently in practice in a wide variety of applications that try to find groups of people in social networks who are related to others in the group in certain ways.
The DOGMA system is the first disk-based index specialized for subgraph matching (with complex query subgraphs) against a database with millions of edges. DOGMA leverages past work on graph partitioning to build a disk-resident index. The DOGMA index has high performance. In an experimental study it was shown that DOGMA outperforms other state of the art graph databases by orders of magnitude on a large range of complex subgraph matching queries, yielding answers to such queries over a graph with 15 million edges in milliseconds where other systems took seconds or even minutes to respond.
In addition to social networks, DOGMA can also be used to execute graph matching queries expressed in the Semantic Web language SPARQL against a database in the W3C “Resource Description Framework” (RDF) database paradigm.
We hope to release an open-source version of the DOGMA database framework for non-commercial use in July 2010.
For additional information, please contact Matthias Broecheler or V.S. Subrahmanian.
Last updated: June 2010 by John Dickerson
Research and implementation of this project performed jointly by members of the University of Maryland and the Universita della Calabria.
This page will be updated as our work enters print. For information about receiving draft publications, technical reports, and conference presentations, please do not hesitate to contact team members.
This project has been recently started and no presentations are available yet.
This page will be updated as our work progresses. For information about receiving draft publications, technical reports, and conference presentations, please do not hesitate to contact team members.
No software is available currently.