An efficient algorithm for updating regular expression indexes in RDF databases. (6th January 2015)

• Record Type: Journal Article
• Authors: Lee, Jinsoo; Kasperovics, Romans; Han, Wook–Shin; Lee, Jeong–Hoon; Kim, Min Soo; Cho, Hune
• Is Part Of: International journal of data mining and bioinformatics. Volume 11:Number 2(2015)
• Page Start: 205
• Page End: 222
• Publication Date: 2015-01-06
• Subjects: RDF databases -- resource description framework -- SPARQL query processing -- regular expressions -- multigram -- updates -- gene ontology -- index updating -- regular expression indexes -- bioinformatics; Data mining -- Periodicals; Bioinformatics -- Periodicals; 006.312
• Languages: English
• ISSNs: 1748-5673

Abstract

The Resource Description Framework (RDF) is widely used for sharing biomedical data, such as gene ontology or the online protein database UniProt. SPARQL is a native query language for RDF, featuring regular expressions in queries for which exact values are either irrelevant or unknown. The use of regular expression indexes in SPARQL query processing improves the performance of queries containing regular expressions by up to two orders of magnitude. In this study, we address the update operation for regular expression indexes in RDF databases. We identify major performance problems of straightforward index update algorithms and propose a new algorithm that utilises unique properties of regular expression indexes to increase performance. Our contributions can be summarised as follows: (1) we propose an efficient update algorithm for regular expression indexes in RDF databases, (2) we build a prototype system for the proposed algorithm in C++ and (3) we conduct extensive experiments demonstrating the improvement of our algorithm over the straightforward approaches by an order of magnitude.