Graph Data Management: Techniques and Applications

Graph Data Management: Techniques and Applications

Sherif Sakr (University of New South Wales, Australia) and Eric Pardede (LaTrobe University, Australia)
Release Date: August, 2011|Copyright: © 2012 |Pages: 502
ISBN13: 9781613500538|ISBN10: 161350053X|EISBN13: 9781613500545|DOI: 10.4018/978-1-61350-053-8


Graphs are a powerful tool for representing and understanding objects and their relationships in various application domains. The growing popularity of graph databases has generated data management problems that include finding efficient techniques for compressing large graph databases and suitable techniques for visualizing, browsing, and navigating large graph databases.

Graph Data Management: Techniques and Applications is a central reference source for different data management techniques for graph data structures and their application. This book discusses graphs for modeling complex structured and schemaless data from the Semantic Web, social networks, protein networks, chemical compounds, and multimedia databases and offers essential research for academics working in the interdisciplinary domains of databases, data mining, and multimedia technology.

Topics Covered

  • Business Process Graphs
  • Clustering Vertices in Weighted Graphs
  • Graph Applications in Chemoinformatics
  • Graph Indexing Querying Techniques
  • Kernel-Based Similarity Searches
  • Large Scale Graph Mining
  • Querying RDF
  • Real and Synthetic Graphs
  • Relational Approaches for Graph Pattern Matching
  • Semantic Process Model Discovery

Reviews and Testimonials

This book is the first that approaches the challenges associated with graphs from a data management point of view; it connects the dots. As I am currently involved in building a native graph database engine, I encounter problems that arise from every possible aspect: data representation, indexing, transaction support, parallel query processing, and may others. All of them sound familiar to a database researcher, but the inherent change is fundamental as they originate from a new foundation. I found that this book contains a lot of timely information, aiding my efforts. To be clear, it does not offer the blueprint for building a graph database system, but it contains a bag of diamonds, enlightening the readers as they start exploring a field that may fundamentally change data management in the future.

– Haixun Wang, Microsoft Research Asia

Table of Contents and List of Contributors

Search this Book:
Editorial Advisory Board
Table of Contents
Haixun Wang
Sherif Sakr, Eric Pardede
Sherif Sakr, Eric Pardede
Chapter 1
Graph Representation  (pages 1-28)
D. Dominguez-Sal, V. Muntés-Mulero, N. Martínez-Bazán, J. Larriba-Pey
In this chapter, we review different graph implementation alternatives that have been proposed in the literature. Our objective is to provide the... Sample PDF
Graph Representation
Chapter 2
Marko A. Rodriguez, Peter Neubauer
A graph is a structure composed of a set of vertices (i.e. nodes, dots) connected to one another by a set of edges (i.e. links, lines). The concept... Sample PDF
The Graph Traversal Pattern
Chapter 3
Srinath Srinivasa
Management of graph structured data has important applications in several areas. Queries on such data sets are based on structural properties of the... Sample PDF
Data, Storage and Index Models for Graph Databases
Chapter 4
Sherif Sakr, Ghazi Al-Naymat
Recently, there has been a lot of interest in the application of graphs in different domains. Graphs have been widely used for data modeling in... Sample PDF
An Overview of Graph Indexing and Querying Techniques
Chapter 5
Alfredo Ferro, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha
From biochemical applications to social networks, graphs represent data. Comparing graphs or searching for motifs on such data often reveals... Sample PDF
Efficient Techniques for Graph Searching and Biological Network Mining
Chapter 6
Jiefeng Cheng, Jeffrey Xu Yu
Due to rapid growth of the Internet and new scientific/technological advances, there exist many new applications that model data as graphs, because... Sample PDF
A Survey of Relational Approaches for Graph Pattern Matching over Large Graphs
Chapter 7
Hongzhi Wang, Jianzhong Li, Hong Gao
When data are modeled as graphs, many research issues arise. In particular, there are many new challenges in query processing on graph data. This... Sample PDF
Labelling-Scheme-Based Subgraph Query Processing on Graph Data
Chapter 8
Xiaohong Wang, Jun Huan, Aaron Smalter, Gerald H. Lushington
Our objective in this chapter is to enable fast similarity search in large graph databases with graph kernel functions. In particular, we propose... Sample PDF
G-Hash: Towards Fast Kernel-Based Similarity Search in Large Graph Databases
Chapter 9
Fang Wei
Our experimental results show that TEDI offers orders-of-magnitude performance improvement over existing approaches on the index construction time... Sample PDF
TEDI: Efficient Shortest Path Query Answering on Graphs
Chapter 10
Ana Paula Appel, Christos Faloutsos, Caetano Traina Junior
Graphs appear in several settings, like social networks, recommendation systems, computer communication networks, gene/protein biological networks... Sample PDF
Graph Mining Techniques: Focusing on Discriminating between Real and Synthetic Graphs
Chapter 11
Hiroto Saigo, Koji Tsuda
Graph is a mathematical framework that allows us to represent and manage many real-world data such as relational data, multimedia data and... Sample PDF
Matrix Decomposition-Based Dimensionality Reduction on Graph Data
Chapter 12
Derry Tanti Wijaya, Stephane Bressan
Clustering is the unsupervised process of discovering natural clusters so that objects within the same cluster are similar and objects from... Sample PDF
Clustering Vertices in Weighted Graphs
Chapter 13
Charalampos E. Tsourakakis
In this Chapter, we present state of the art work on large scale graph mining using MapReduce. We survey research work on an important graph mining... Sample PDF
Large Scale Graph Mining with MapReduce: Counting Triangles in Large Real Networks
Chapter 14
Xiaoxun Sun, Min Li
We study the challenges of protecting privacy of individuals in the large public survey rating data in this chapter. Recent study shows that... Sample PDF
Graph Representation and Anonymization in Large Survey Rating Data
Chapter 15
Querying RDF Data  (pages 335-353)
Faisal Alkhateeb, Jérôme Euzenat
This chapter provides an introduction to the RDF language as well as surveys the languages that can be used for querying RDF graphs. Then it reviews... Sample PDF
Querying RDF Data
Chapter 16
Maria-Esther Vidal, Amadís Martínez, Edna Ruckhaus, Tomas Lampo, Javier Sierra
In the context of the Semantic Web, different approaches have been defined to represent RDF documents, and the selected representation affects... Sample PDF
On the Efficiency of Querying and Storing RDF Documents
Chapter 17
Eleanor Joyce Gardiner
The focus of this chapter will be the uses of graph theory in chemoinformatics and in structural bioinformatics. There is a long history of chemical... Sample PDF
Graph Applications in Chemoinformatics and Structural Bioinformatics
Chapter 18
Remco Dijkman, Marlon Dumas, Luciano García-Bañuelos
Organizations create collections of hundreds or even thousands of business process models to describe their operations. This chapter explains how... Sample PDF
Business Process Graphs: Similarity Search and Matching
Chapter 19
Ahmed Gater, Daniela Grigori, Mokrane Bouzeghoub
One of the key tasks in the service oriented architecture that Semantic Web services aim to automate is the discovery of services that can fulfill... Sample PDF
A Graph-Based Approach for Semantic Process Model Discovery
Chapter 20
Radwa Elshawi, Joachim Gudmundsson
In this chapter we consider two versions of the problem; the shortest path in a transportation network and the shortest path in a weighted... Sample PDF
Shortest Path in Transportation Network and Weighted Subdivisions
About the Contributors


The graph is a powerful tool for representing and understanding objects and their relationships in various application domains. Recently, graphs have been widely used to model many complex structured and schemaless data such as semantic web, social networks, biological networks, protein networks, chemical compounds and business process models. The growing popularity of graph databases has generated interesting data management problems. Therefore, the domain of graph databases have attracted a lot of attention from the research community and different challenges have been discussed such as: subgraph search queries, supergraph search queries, approximate subgraph matching, short path queries and graph mining techniques.

This book is designed for studying various fundamental challenges of storing and querying graph databases. In addition, it discusses the applications of graph databases in various domains. In particular, the book is divided into three main sections.

The first section discusses the basic definitions of graph data models, graph representations and graph traversal patterns. It also provides an overview of different graph indexing techniques and evaluation mechanisms for the main types of graph queries. The second section further discusses advanced querying aspects of graph databases and different mining techniques of graph databases. It should be noted that many graph querying algorithms are sensitive to the application scenario in which they are designed and cannot be generalized for all domains. Therefore, the third section focuses on presenting the usage of graph database techniques in different practical domains such as: semantic web, chemoinformatics, bioinformatics, business process model and transportation networks. 

In a nutshell, the book provides a comprehensive summary from both of the algorithmic and the applied perspectives. It will provide the reader with a better understanding of how graph databases can be effectively utilized in different scenarios.

Author(s)/Editor(s) Biography

Sherif Sakr, Ph.D., is a Research Scientist in the Managing Complexity Group at National ICT Australia (NICTA), ATP lab, Sydney, Australia. He is also a Conjoint Lecturer in The School of Computer Science and Engineering (CSE) at University of New South Wales (UNSW) and an Adjunct Lecturer with the Department of Computing in the Division of Information and Communication Sciences at Macquarie University . He received his PhD degree in Computer Science from Konstanz University, Germany in 2007. He received his BSc and MSc degree in Computer Science from the Information Systems department at the Faculty of Computers and Information in Cairo University, Egypt, in 2000 and 2003 respectively. His research interest is data and information management in general, particularly in areas of indexing techniques, query processing and optimization techniques, graph data management, social networks, data management in cloud computing.
Eric Pardede, Ph.D., is a lecturer in the Department of Computer Science and Computer Engineering at La Trobe University, Melbourne, Australia. From the same university, he received his Doctor of Philosophy and Master of Information Technology in 2006 and 2002 respectively. He has research interests in data modelling, data quality, data security and data privacy in XML and Web Databases as well as data repository for social networks.


Editorial Board

  • Sourav S. Bhowmick, Nanyang Technological University, Singapore
  • Michael Böhlen, University of Zurich, Switzerland
  • Marlon Dumas, University of Tartu, Estonia
  • Claudio Gutierrez, Universidad de Chile, Chile
  • Jun Huan, University of Kansas, USA
  • Irwin King, The Chinese University of Hong Kong, China
  • Raymond Wong, University of New South Wales, Australia
  • Mohammed  Zaki, Rensselaer Polytechnic Institute, USA
  • Xiaofang Zhou, University of Queensland, Australia