Presented at: 7th International Semantic Web Conference (ISWC2008)
by Eyal Oren, Christophe Guéret, Stefan Schlobach
We present a technique for answering queries over RDF data through an evolutionary search algorithm, using fingerprinting and bloomfilters for rapid approximate evaluation of generated solutions. Our evolutionary approach has several advantages compared to traditional database-style query answering. First, the result quality increases monotonically and converges with each evolution, offering ``anytime'' behaviour with arbitrary trade-off between computation time and query results; in addition, the level of approximation can be tuned by varying the size of the bloomfilters. Secondly, through bloomfilter compression we can fit large graphs in main memory, reducing the need for disk I/O during query evaluation. Finally, since the individuals evolve independently, parallel execution is straightforward. We present an initial prototype that evaluates basic SPARQL queries over arbitrary RDF graphs and show initial results over large datasets.
Keywords: SPARQL, approximate reasoning, bloom filters, evolutionary algorithms, query answering, Semantic Web
Resource URI on the dog food server: http://data.semanticweb.org/conference/iswc/2008/paper/research/237
Explore this resource elsewhere: