Please use this identifier to cite or link to this item: http://hdl.handle.net/20.500.11889/4193
Title: The Graph Signature: A Scalable Query Optimization Index for RDF Graph Databases Using Bisimulation and Trace Equivalence Summarization
Authors: Jarrar, Mustafa
Deik, Anton
Keywords: Big data
Coinduction (Mathematics)
Bisimulation
Database design
Database management
Issue Date: 2015
Abstract: Querying large data graphs has brought the attention of the research community. Many solutions were proposed, such as Oracle Semantic Technologies, Virtuoso, RDF3X, and C-Store, among others. Although such approaches have shown good performance in queries with medium complexity, they perform poorly when the complexity of the queriesincreases. In this paper, the authors propose the Graph Signature Index, a novel and scalable approach to index and query large data graphs. The idea is that they summarize a graph and instead of executing the query on the original graph, they execute it on the summaries. The authors’ experiments with Yago (16M triples) have shown that e.g., a query with 4 levels costs 62 sec using Oracle but it only costs about 0.6 sec with their index. Their index can be implemented on top of any Graph database, but they chose to implement it as an extension to Oracle on top of the SEM_MATCH table function. The paper also introduces disk-based versions of the Trace Equivalence and Bisimilarity algorithms to summarize data graphs, and discusses their complexity and usability for RDF graphs
URI: http://hdl.handle.net/20.500.11889/4193
Appears in Collections:Fulltext Publications

Files in This Item:
File Description SizeFormat 
JD15.pdf5.01 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.