regarding slow query execution

[pranav.puri]

Dear All

 The query execution time for sparql queries with regex filters is much 
more(10-12 minutes) as compared to queries with no filters applied.

The queries are being run on tables containing triples from dbpedia dataset.
Each table(ie Spo,osp,po) contains 110 million entries.I am currently 
using a three node accumulo cluster.

Please suggest some ways to improve the query execution time .

Regards
Pranav