DOE OSTI · 1056553
Massive-scale RDF Processing Using Compressed Bitmap Indexes
Abstract
The Resource Description Framework (RDF) is a popular data model for representing linked data sets arising from the web, as well as large scienti c data repositories such as UniProt. RDF data intrinsically represents a labeled and directed multi-graph. SPARQL is a query language for RDF that expresses subgraph pattern- nding queries on this implicit multigraph in a SQL- like syntax. SPARQL queries generate complex intermediate join queries; to compute these joins e ciently, we propose a new strategy based on bitmap indexes. We store the RDF data in column-oriented structures as compressed bitmaps along with two dictionaries. This paper makes three new contributions. (i) We present an e cient parallel strategy for parsing the raw RDF data, building dictionaries of unique entities, and creating compressed bitmap indexes of the data. (ii) We utilize the constructed bitmap indexes to e ciently answer SPARQL queries, simplifying the join evaluations. (iii) To quantify the performance impact of using bitmap indexes, we compare our approach to the state-of-the-art triple-store RDF-3X. We nd that our bitmap index-based approach to answering queries is up to an order of magnitude faster for a variety of SPARQL queries, on gigascale RDF data sets.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Madduri, Kamesh, Wu, Kesheng. 2011-05-26. Massive-scale RDF Processing Using Compressed Bitmap Indexes. https://engineeringpapers.com/record/osti%3A1056553/massive-scale-rdf-processing-using-compressed-bitmap-indexes
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Engineering Papers by Indiciae: BibTeX · RIS.