Hierarchical Characteristic Set Merging for Optimizing SPARQL Queries in\n Heterogeneous RDF

Characteristic sets (CS) organize RDF triples based on the set of properties\ncharacterizing their subject nodes. This concept is recently used in indexing\ntechniques, as it can capture the implicit schema of RDF data. While most\nCS-based approaches yield significant improvements in space and query\nperformance, they fail to perform well in the presence of schema heterogeneity,\ni.e., when the number of CSs becomes very large, resulting in a highly\npartitioned data organization. In this paper, we address this problem by\nintroducing a novel technique, for merging CSs based on their hierarchical\nstructure. Our technique employs a lattice to capture the hierarchical\nrelationships between CSs, identifies dense CSs and merges dense CSs with their\nancestors, thus reducing the size of the CSs as well as the links between them.\nWe implemented our algorithm on top of a relational backbone, where each merged\nCS is stored in a relational table, and we performed an extensive experimental\nstudy to evaluate the performance and impact of merging to the storage and\nquerying of RDF datasets, indicating significant improvements.\n