External Sorting for Index Construction of Large Semantic Web Databases

摘要

Today's Semantic Web datasets become increasingly larger containing up to several hundred million triples. The performance of index construction is a crucial factor for the success of large Semantic Web databases. In this paper, we propose two new approaches for RDF index construction: External chunks merge sort and Distribution Sort for RDF. The former stores and retrieves chunks from a special chunks heap to speed up replacement selection. The latter leverages the RDF-specific properties to construct RDF indices and significantly improves the performance. Our experimental results show that our approaches significantly speed up RDF index construction, and are important techniques for large Semantic Web databases.