In the past decade, the volume of RDF (Resource Description Framework, which is a standard model for data interchange on the Web) data has grown enormously, and many RDF datasets (e.g., Wikipedia) have reached up to billions of triples. As a result, efficient management of this huge RDF data has become a tremedous challenge. In this paper, we present HTStore, a hash tree based system for fast storing and accessing large scale RDF data. The design of HTStore has three salient features. First, the compact design can effectively reduce the size of the indexes. Second, HTStore utilizes the hash function to significantly reduce the query time. Third, the proposed hash tree structure can easily adapt to the changes in data volume (e.g., data expansion). The experimental results demonstrate that the proposed system can improve the query efficiency up to 21.3% compared with the representative RDF data management systems.
The RDF (Resource Description Framework) data model and its query language SPARQL
have been widely used for managing schema-free structured information. Large amounts
of semantic data are available in RDF format in many fields, such as Yago[
Several systems, such as Gstore[
In this paper, we propose HTStore to fast store and access large scale RDF data. In HTStore, we organize RDF data in the form of an RDF graph and establish indexes according to the RDF graph. The index structure includes two layers: the hash layer containing a hash table and the tree layer containing hash trees. More specifically, we construct a hash table for fast lookup. When a hash collision happens in a hash table, new hash trees will be established in the second layer. With such a structure, only limited hash operations are required to perform a data query. As a result, the query time is significantly reduced. We conduct experiments over LUBM datasets to confirm the effectiveness and efficiency of our proposed approach. The experimental results prove the proposed system can improve the query efficiency by 21.3% compared with the representative RDF data management systems. 2
In HTStore, we organize RDF data in the form of an RDF graph and establish index according to the vertexes in the graph. Fig. 1 shows an overview of the proposed structure used to manage RDF graph. The left part of the figure is an RDF graph, and the right part is the index built according to the vertexes in the graph. Before building an index in a RDF dataset, each vertex in the RDF graph is assigned a unique identifier. The index structure includes two parts: the hash layer containing a hash table and the tree layer containing hash trees. In the first layer, a m-length hash table is constructed. In the second layer, we build hash trees dynamically based on a prime sequence P = fp1; p2; p3 g during inserting RDF graph vertexes.
001 1969-09-10 bornOnDate bornIn Jack Ma 006
chairmanOf spouse 008 Cathy ZhangYing 009
002 namedFor ZheJiang Total area
density 007 Alibaba Group website Alibabagroup.com services010
Online shopping
003 Qiantang River
004 39,300 sq mi 1,400/sq mi 005 select ?x where {?x bornIn ZheJiang}
string hash value:002 001
003 004 002 007 009 005 006 008 010 hash layer tree layer
Suppose that we intend to insert a new vertex into an RDF datasets, Fig. 2 shows different solutions for different insertion situations. The simplest case is when no collision happens in hash table. The vertex will be added to the blank bucket directly(as shown in Fig. 2(a)). In Fig. 2(b), collision happens in the hash table and there exists no hash tree of the collided vertex. Therefore, a new hash tree should be established in the second layer. If hash tree of the collided vertex has been constructed(as shown in Fig. 2(c)) and collision still occurs between the new node and the root node of hash tree, according to hash tree’s construction regulation, we will leverage first prime number p1 to obtain a hash value t of the new node. It means that we will consider the t-th child node of root node – cnode. If collision still occurs in the cnode, the second prime number p2 will be used to determine which child node of cnode will be considered. Similar operations by different prime number will be conducted until there is no collision occurs. All the experiments were conducted on a Dell optiptex 7040 PC with a 3.20 GHz CPU, 16 GBytes of RAM. The operating system is a 64-bit Linux with 4.8.0 kernel. We use LUBM as our datasets. LUBM (Lehigh University Benchmark) is developed to facilitate the evaluation of Semantic Web repositories in a standard and systematic way. It consists of a university domain ontology, customizable and repeatable synthetic data, and several performance metrics. Different LUBM datasets have different sizes and different triple numbers. We also compare our experiments with RDF-3x and Gstore.
Table 1 lists the SPARQL query used in our experiment. We execute these six queries over different LUBM datasets. Table 2 compares the query performance of our method, Gstore and RDF-3x. In our query samples, Gstore always perform better than
In this paper, we propose HTStore to manage large scale RDF data. HTStore utilizes the hash tree structure to significantly reduce the query time. In addition, the proposed management scheme can also easily adapt to the changes in data volume. Experimental results demonstrate that HTStore can effectively improve performance of SPARQL query.
This work is supported by the programs of the National Natural Science Foundation of China (61373165 and 61702357).