Title: An efficient algorithm for updating regular expression indexes in RDF databases

Authors: Jinsoo Lee; Romans Kasperovics; Wook-Shin Han; Jeong-Hoon Lee; Min Soo Kim; Hune Cho

Addresses: Department of Computer Engineering, Kyungpook National University, Daegu 702 701, Korea ' Department of Computer Engineering, Kyungpook National University, Daegu 702 701, Korea ' Department of Creative IT Engineering and Department of Computer Science and Engineering, POSTECH, Pohang 790 784, Korea ' Department of Creative IT Engineering, POSTECH, Pohang 790 784, Korea ' Department of Computer Science, Korea Advanced Institute of Science and Technology (KAIST), Daejeon 305 701, Korea ' Department of Medical Informatics, Kyungpook National University, Daegu 702 701, Korea

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.

Keywords: RDF databases; resource description framework; SPARQL query processing; regular expressions; multigram; updates; gene ontology; index updating; regular expression indexes; bioinformatics.

DOI: 10.1504/IJDMB.2015.066767

International Journal of Data Mining and Bioinformatics, 2015 Vol.11 No.2, pp.205 - 222

Received: 03 Jun 2012
Accepted: 23 Jul 2012
Published online: 05 Jan 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article