  The Resource Description Framework (RDF) is a W3C standard for representing
graph-structured data, and SPARQL is the standard query language for RDF.
Recent advances in Information Extraction, Linked Data Management and the
Semantic Web have led to a rapid increase in both the volume and the variety of
RDF data that are publicly available. As businesses start to capitalize on RDF
data, RDF data management systems are being exposed to workloads that are far
more diverse and dynamic than what they were designed to handle. Consequently,
there is a growing need for developing workload-adaptive and self-tuning RDF
data management systems. To realize this vision, we introduce a fast and
efficient method for dynamically clustering records in an RDF data management
system. Specifically, we assume nothing about the workload upfront, but as
SPARQL queries are executed, we keep track of records that are co-accessed by
the queries in the workload and physically cluster them. To decide dynamically
(hence, in constant-time) where a record needs to be placed in the storage
system, we develop a new locality-sensitive hashing (LSH) scheme, Tunable-LSH.
Using Tunable-LSH, records that are co-accessed across similar sets of queries
can be hashed to the same or nearby physical pages in the storage system. What
sets Tunable-LSH apart from existing LSH schemes is that it can auto-tune to
achieve the aforementioned clustering objective with high accuracy even when
the workloads change. Experimental evaluation of Tunable-LSH in our prototype
RDF data management system, chameleon-db, as well as in a standalone hashtable
shows significant end-to-end improvements over existing solutions.
