KOGNAC: Efficient Encoding of Large Knowledge Graphs

1 Introduction

The advent of natural-language-based queries and entitycentric search has led to the enormous growth and applicability of Knowledge Graphs (KG) to model known relationships between entity-pairs. Large KGs have not only been built in academic projects like DBpedia [Bizer et al., 2009],but are also used by leading organizations like Google, Microsoft, etc., to support user-centric Internet services and missioncritical data analytics.

KGs are generally represented using the RDF data model [Klyne and Carroll, 2006], in which the KG corresponds to a finite set of subject-predicate-object (SPO) triples whose terms can be URIs, blank nodes, or literal values [Klyne and Carroll, 2006]. Since many Web applications rely on RDF-style KGs during their processing, efficient and scalable querying on huge KGs with billions of RDF triples have necessitated intelligent KG representation.

In concept, KGs can be managed using a variety of platforms, like RDF engines [Yuan et al., 2013; Gurajada et al., 2014; Neumann and Weikum, 2008], relational stores [Sidirourgos et al., 2008], or graph database systems [Robinson et al., 2015]. In this context, the storage of RDF terms in raw format is both space and process inefficient since these are typically long strings. As such, all existing approaches encode the RDF terms typically by mapping them to fix-length integer IDs, with the original strings retrieved only during execution.

Objectives. Modern KGs are typically queried using the W3C SPARQL language [Harris et al., 2013]. Currently, the impact of different ID mappings on advanced SPARQL operations (like query joins, index compression, etc.) is less well studied. Ideally, the encoding of RDF terms into numerical IDs should: i) Consider the skew in the term frequencies in the KG, and assign smaller IDs to frequent terms in order to facilitate efficient down-stream compression (by the storage engine). ii) For more advanced query access patterns, particularly for join operations, data locality should be increased as much as possible by the encoding. That is, terms that are often accessed together should have close ID assignment in order to further reduce memory and index access [Harbi et al., 2015]. iii) It is often crucial to quickly load billions of triples, for example, when a KG is required as background knowledge for new analytic applications, or for append-only bulk update operations. Thus, the encoding process should support parallelism as much as possible for better scale-up.

Problem Statement. Current RDF engines generally employ four types of encodings: order or hash-based, syntactic, or based on coordinates. Order-based approaches assign consecutive IDs for new incoming triples in the order of appearance. Hash-based procedures use term hashes as IDs. Syntactic encoding assigns IDs to terms based on their lexicographic order. Coordinate-based techniques stored the terms in special data structures and use memory coordinates as IDs.

Interestingly, we observe that none of the existing approaches performs well along all three dimensions of our desiderata. Assigning consecutive identifiers leads to good compression, but does not improve locality for joins. Hashbased encoding allows parallel loading, but has poor locality and is sub-optimal in exploiting skew. The last two disadvantages are also shared by methods which use memory coordinates as IDs. Syntactic encoding provides a compromise along the three objectives, but is not robust enough to handle the cases where term similarity cannot be extracted directly from the syntax. The problem addressed in this paper is to encode RDF terms in large KGs such that all three desiderata, namely better compression, query performance, and loading time, are well satisfied.

Contribution. We present KOGNAC (KnOwledge Graph eNoding And Compression), an efficient algorithm for KG encoding based on a judicious combination of statistical and semantic techniques. Our encoding procedure detects skewness in term frequency distribution with a approximation streaming technique, and subsequently encodes frequent terms differently in order to facilitate high down-stream compression. To improve data locality for join access patterns, KOGNAC computes semantic relatedness between terms by hierarchically grouping them into ontological classes, and mapping terms in the same group to consecutive IDs.

KOGNAC has the advantage that it is independent from RDF application details, since its output is a plain mapping from strings to IDs. To evaluate its efficiency, we integrated it with four RDF systems - RDF-3X [Neumann and Weikum, 2008], TripleBit [Yuan et al., 2013], MonetDB [Sidirourgos et al., 2008], and TriAD [Gurajada et al., 2014] - and observed significant improvements in query performance on metrics like runtime, RAM usage, and disk I/O.

A longer version of this paper, with more details and experiments, is available online at [Urbani et al., 2016].

2 Encoding KGs: State Of The Art

Typically, applications query KGs using SPARQL [Harris et al., 2013] - a W3C declarative language. The core execution of SPARQL queries corresponds to finding all graph isomorphisms between the KG and the graphs defined in the queries. RDF Encoding. SPARQL engines, e.g., TripleBit [Yuan et al., 2013], TriAD [Gurajada et al., 2014], Virtuoso [Erling and Mikhailov, 2009], etc., use dictionary encoding to assign numeric IDs to terms based on their appearance ordering, i.e., simply using consecutive or pseudo-random numbers for incoming triples. The 4Store engine [Harris et al., 2009] uses a string-hashing based ID assignment that disregards any possible co-relation among terms. Both approaches do not consider term frequencies leading to sub-optimal encoding with frequent terms possibly assigned to larger IDs. Further, sophisticated partitioning methods in TriAD renders such encoding prohibitively compute expensive [Harbi et al., 2015].

RDF-3X [Neumann and Weikum, 2008], one of the fastest single-machine RDF storage engines, pre-sorts the SPO triples lexicographically and then assigns consecutive integer IDs. A similar approach is also followed by [Urbani et al., 2013], while [Cheng et al., 2014] proposes a combination of appearance order with hashing to improve partitioning. In contrast to our work, these approaches strongly leverage the string similarity heuristics to cluster the elements. These heuristics break when the semantic similarity does not follow the lexicographic ordering. Such dissimilarity occurs frequently via subdomain usage in URIs, or may even be imposed explicitly by political decisions (e.g., Wikidata [Vrandeˇci´c and Kr¨otzsch, 2014] uses meaningless strings to avoid an English bias).

Some relational engines (e.g., MonetDB [Sidirourgos et al., 2008]) can optionally use dedicated data structures for the storage of strings (mainly using variants of Tries). In this context, a particular variant of Trie with term prefix overlap was proposed in [Gallego et al., 2013] to capture syntactic similarity. In these cases, the coordinates to the data structure (e.g., memory addresses) are used as numerical IDs. These IDs are typically long, and the induced locality reflects the physical storage of the strings rather than the semantics in the KG. Older versions of MonetDB followed this approach, but it was later abandoned.

Semantic Relateness. There is a rich literature on semantic relatedness based on the lexicographic features [Zhang et al., 2013], or on domain-dependant data like Wikipedia [Gabrilovich and Markovitch, 2007], Wordnet [Budanitsky and Hirst, 2006], biomedical data [Pedersen et al., 2007], and spatial [Hecht et al., 2012]. In our case, we cannot make assumptions about the domain of the input and the strings may be completely random, so lexicographic features are not applicable.

In general, semantic relatedness functions cannot be directly applied to our problem of graph encoding. For instance, [Leal, 2013] defines semantic relatedness among two nodes as a function of combining the path length and the number of different paths between two nodes. In our context, it would be too expensive to compute relatedness for many (or even any possible) pairs of nodes. Furthermore, the high sparsity in the graph results in very low relatedness coefficients in almost all cases. [Cur´e et al., 2015] describes how ontological taxonomies can be exploited to speed up reasoning via intelligent ID encoding. In spirit, this approach is similar to our approach for encoding infrequent terms. However, [Cur´e et al., 2015] focuses on improving reasoning efficiency rather than the semantic relatedness. Furthermore, [Cur´e et al., 2015] does not consider data skewness, as we do.

Finally, clustering methods based on the graph structure (e.g., METIS [Karypis and Kumar, 1998], or graph-coloring approach of [Bornea et al., 2013]) are infeasible at our scale [Gurajada et al., 2014], and often require a conversion to an undirected single-label graph disregarding entirely the semantics in the KG. In contrast, the goal of KOGNAC is to leverage precisely this semantics to improve the encoding.

3 The KOGNAC Algorithm

Algorithmic Overview. KOGNAC performs a crucial distinction between (few) frequent terms from the (many) remaining infrequent ones. For the frequent terms, it applies a frequency-based encoding, which is highly effective in terms of compression due to the skewed distribution of modern KGs [Kotoulas et al., 2010]. For the infrequent ones, it exploits the semantics contained in the KG to encode similar terms together to improve data locality.

Fig. 1 describes at a high level the functioning of KOGNAC.

Let V be the set of terms in a generic RDF graph G. KOGNAC receives G and a threshold value k (used for the top-k frequent elements) as input, and returns a dictionary table D ⇢ V ⇥N that maps every element in V to a unique ID in N.

The dictionary table D is constructed using two different encoding algorithms: Frequency-based encoding (FBE), which encodes only the frequent terms, and Locality-based encoding (LBE), which encodes the infrequent ones. The core computation of FBE corresponds to the execution of an approximated procedure for accurate frequency detection. LBE instead constructs a class taxonomy, groups the terms into these classes, and assigns the IDs accordingly. Both methods support parallelism. FBE is executed before LBE. If D1 is the output of FBE, and D2 of LBE, then D = D1 [ D2 and D1 \ D2 = ;.

4 Frequency-based Encoding (FBE)

The goal of this procedure is to detect the top-k frequent terms and assign them incremental IDs starting from the most to the least frequent term. For our purpose, an exact calculation of the frequencies is not required, and even though it can be easily computed for small KGs, it would be unnecessarily expensive for very large KGs. Sampling provides the reference technique for a fast approximation [Urbani et al., 2013]. Unfortunately, an excessive sampling might lead to false positives and negatives, and increasing the sample size for tolerable error rates might still be too expensive.

To obtain a better approximation, we investigated the applicability of hash-based sketch algorithms [Karp et al., 2003; Charikar et al., 2002]. Sketch algorithms have successfully been deployed in other domains to identify distinct items in streams [Karp et al., 2003], but never to our problem domain. Sketch Algorithms. We experimented with three stateof-the-art sketch algorithms: Count-Sketch [Charikar et al., 2002], Misra-Gries [Misra and Gries, 1982], and CountMin [Cormode and Muthukrishnan, 2005]. Count-Sketch, a single-scan algorithm, requires a heap with quadratic space in error tolerability. After many experiments, we concluded that updating such large heap was too expensive for our inputs.

Misra-Gries is similar to Count-Sketch, with the difference that it uses a smaller heap and reports the terms that are at least k-frequent, i.e., having a frequency > nk , where n denotes the total number of term occurrences. This method approximates the relative frequencies (i.e., frequency after a term is inserted in the heap). We found that the relative frequencies were not accurate enough to allow a precise ordering of terms, as the count depends on the appearance ordering.

Count-Min uses n > 1 hash counter arrays and n hash functions to count the frequencies. In contrast to the previous two methods, it always requires two input scans: First to count the frequencies, and then to extract the actual frequent terms. Count-Min does not use heaps and this makes it in principle faster than the other two. However, for large inputs the cost of second input scan offsets this gain.

Our proposal: CM+MG. Count-Min provides a good estimate of term frequencies, but cannot identify the top-k elements within a single pass. Misra-Gries detects the top-k elements but does not report good frequencies. The disadvantages of the two are complementary. We thus propose a hybrid approach, which we call CountMin+MisraGries (CM+MG), that intelligently combines elements of the two.

An overview of its functioning is reported in Fig. 2. As input it receives the input KG, k, a hash family H with n hash functions, m parallel threads, and a threshold k of popular elements. In our implementation, we selected as default values three hash functions for H, while m is the number of physical cores, and the value k is requested from the user.

CM+MG is executed in two steps: In the first step, CM+MG creates m ⇤ n counter arrays and m Misra-Gries heaps of size k. The KG is split into m subsets, and fed to the m threads. Each thread calculates n hash codes for each term occurrence in its partition. The n hash-codes are modulo-ed the array size and the corresponding indices in the arrays are incremented by 1. The terms are also inserted into the heaps.

In the second step, the m heaps are merged in a single heap. Also the arrays are summed into n final arrays. As threshold value for the frequent terms, we select the top-k value in the first array. The algorithm now scans all elements in the merged heap. Instead of using the relative frequency as estimate, CM+MG queries the arrays using the term's hashcodes, and uses the minimum of the returned values. If this value is greater than the threshold, the term is marked as frequent.

Effectiveness of FBE. Our approach works well because KGs are skewed. In order to better characterize the gain we can obtain with our approach, we present a short theoretical analysis on the space efficiency of FBE.

Assume T = ¶t1↪ t2↪ ▷ ▷ ▷ ↪ tn♦ to be n distinct RDF terms, with term ti having a frequency of fi in the input KG. In the worst case, an assignment criterion which is independent from the term frequencies (e.g., an order-based one) will produce an assignment which is close to a fixed-length encoding; that is where all terms will be assigned to IDs of length dlog2 ne bits. In this case, the total space required to store an encoded KG in the database would be

In KOGNAC, the terms are divided into blocks depending on their frequencies. Here, block i 2 ¶1 ▷ ▷ ▷ b♦ contains the top 2i elements which are not in any previous group. Hence, there exists b = dlog2 ne non-empty blocks for n distinct items in T. An item in block i is encoded using i bits. Since the assignment is not prefix-free, in order to properly decode the IDs we need to append to each term some extra data to discriminate it from the different values. This extra data must take at least dlog2 be bits as this is the minimum space necessary to identify each of the b blocks. Hence, the total space required for decoding an item in block i takes (i + dlog2 be) bits. Assuming, f i j to denote the frequency of the j th item in block i, the total encoding space required for KG is,

Since modern KGs have a skewed term distribution [Kotoulas et al., 2010], we now assume that the item frequencies is drawn from a Zipfian distribution 1 with parameter s ≥ 2, such that the frequency of the kth frequent term fk ⇡ F sk . If we apply this distribution in Eq. (2), we obtain

By algebraic manipulations, we have

If we compare Eq. 3 with Eq. 2, then we see that with KOGNAC we can achieve nearly an exponential theoretical decrease (i.e., log log n vs. log n) in the total encoding space required to store the KG. This is the scale of potential improvement that our encoding can offer to the current frequency-independent encoding algorithms.

5 Locality-based Encoding (LBE)

In the long tail of the frequency distribution, a frequencybased encoding no longer pays off. Each infrequent term appears only a few times and this reduces the negative impact of assigning large IDs to them. Moreover, the increased ID space provides a much larger number of disposable IDs: for instance, after the most frequent 224 th ID, all the following 232 - 224 IDs will take the same number of bytes.

Data Locality. With LBE, we propose an encoding that is designed to improve data locality during the execution of

1 This distribution is used for heavy-tailed characteristics observed in natural language sources used for KG construction.

S := ¶♦; Dinfreq := ¶♦; cID := max ID in Dfreq; MAX := constant with number higher than any class ID in T ; for every triple <s,p,o> in the KG do Add to S three pairs: hs↪MAXi,hp↪MAXi,ho↪MAXi; If p = 'type', then add hs↪ id(o↪ T)i to S; If p has domain c, then add hs↪ id(c↪ T)i to S; If p has range c, then add ho↪ id(c↪ T)i to S; end Remove from S all pairs ht↪ ci where t is in Dfreq; for all pairs ht1↪ c1i and ht2↪ c2i in S do if t1 = t2 then Remove ht1↪ c1i from S if c1 > c2 or remove ht2↪ c2i otherwise; end end while S is not empty do Take out from S one pair ht1↪ c1i s.t. @ht2↪ c2i 2 S : c2 < c1 _ c1 = c2 ^ t2 < t1; Increment cID by 1; Add to dictionary Dinfreq the assignment ht1↪ cIDi; end

SPARQL queries. Data locality plays a significant role to reduce the cost of index access for advanced operations like relational joins. Consider, as example, Fig. 3, which shows a join between two generic relations A and B. It is common that these relations are indexed (i.e., sorted) to enable merge joins [Neumann and Weikum, 2008]. If the index locations of the join terms are spread around the entire relations, as shown in Fig. 3a, then the join algorithm must process large parts of the indexes. On the contrary, if the join succeeds using only sub-portions of the index, then the join algorithm can save significant computation by ignoring large chunks of the indexes (Fig. 3b).

Encoding and Data-Locality. Since SPARQL engines work (mostly) directly on the encoded data, the elements on which the join operates are precisely the IDs which we should assign during encoding. Therefore, an assignment of close IDs will significantly improve data locality.

Unfortunately, it is not possible to encode the terms so that they are always next to each other. We can make one assignment only, and SPARQL queries could request joins on any subset of the relations. Still, we can leverage a heuristics that is surprisingly effective: SPARQL joins tend to materialize between terms which are semantically related.

Following this heuristic, we propose to cluster the terms into the ontological classes they are connected to via the isA relation, and assign consecutive IDs to the members of each cluster. Our approach has several advantages: (i) isA is a common relation in KGs and is domain-independent; (ii) new isA edges can be inferred using other ontological information, e.g., definitions of the domain/range of properties; (iii) classes can be organized in a taxonomy using the rdfs:subClassOf relation of the RDF Schema [Brickley and Guha, 2014]. The taxonomy can help us to further sepa-

(a)

rate instances of subclasses from instances of siblings of the parents (e.g., Students should be closer to Professors than to Robots because the first two are both subclasses of Persons). Algorithm Overview. Our locality-based encoding works as follows: First, we must create the taxonomy of classes. To this end, we extract all triples that define the subclass relation between classes, or mention classes (these share rdfs:subClassOf as predicate, and are the objects of triples with the predicates isA, rdfs:domain, and rdfs:range). We create a graph where the classes are vertices and the edges are defined by the subclassOf triples. We add the standard class rdfs:Class (the class of all classes [Brickley and Guha, 2014]), and add one edge from each vertex to it, to ensure that there are no disconnected components. We remove possible loops in the graph by extracting the tree with the maximum number of edges rooted in rdfs:Class using the well-known Tarjan's algorithm [Tarjan, 1977].

We now assign in post-order an incremental class ID to each class in the tree. We indicate with id(c↪ T) the class ID assigned to the class c contained in the taxonomy T .

After the taxonomy is built, we are ready to encode the terms. This procedure is outlined in Alg. 1. First, we annotate each term with a class ID it is an instance of. The annotation might come from an explicit relation (isA) or an implicit one (domain and range). If a term cannot be associated to any class, we give it a dummy ID (MAX). Then, for each term we maintain only the annotation with the class which has the smallest ID. Finally, we order all annotations first by class ID, and then (lexicographically) by term. We use the same counter used in FBE and assign incremental IDs to the terms with the order defined in the sorted list. In this way, the assignment first considers the semantic type of the term, and then its syntax. Notice that terms which are not mapped to any class (mainly labels), will be encoded only syntactically.

A large part of the computation of LBE can be parallelized. The task of assigning the terms to the smallest class IDs does not require thread synchronization because at this point the taxonomy is a read-only data structure. Therefore, the task can be trivially parallelized using standard input range partitioning and parallel merge sorts. The final assignment is performed sequentially due to the usage of a single counter.

6 Evaluation

We implemented KOGNAC in a C++ prototype. We tested it in combination with four SPARQL engines: RDF-3X, TripleBit, TriAD, and MonetDB. We chose them because they represent the state-of-the-art of different type of SPARQL engines: native/centralized (RDF-3X, TripleBit), native/distributed (TriAD), and RDBMS/centralized (MonetDB). These engines also perform different encodings: RDF-3X performs syntactic encoding, TripleBit and TriAD performs an orderbased encoding, MonetDB can be loaded with arbitrary encodings (we used a syntactic encoding).

We used two types of machines: M1, a dual 8-core 2.4 GHz Intel CPU, 64 GB RAM, and two disks of 4 TB in RAID-0; and M2, a 16 quad-core Intel Xeon CPUs of 2.4GHz with 48GB of RAM. As input, we used three RDF graphs in NT format: LUBM [Guo et al., 2005] - a popular benchmark tool, LDBC [Angles et al., 2014], another, more recent benchmark designed for advanced SPARQL 1.1 workloads, and DBPedia [Bizer et al., 2009], one of the most popular KGs. We created two LUBM datasets: LUBM1K (133M triples, 33M terms), and LUBM8K (1B triples, 263M terms). We created a LDBC dataset with 168M triples and 177M terms. The DBPedia dataset contains about 1B triples and 232M terms.

Due to space reasons, for LUBM, we used only five adaptations of benchmark queries which were selected as representative in [Yuan et al., 2013]. For DBPedia, we slightly changed five example queries that are reported in the project's website. For LDBC, we use the official queries in the SPB usecase [Angles et al., 2014]. These queries require SPARQL 1.1 operators which were unsupported by any of our engines. We implemented some of the missing operators in RDF-3X so that we could launch 7 of the 12 SPB queries. Fig. 5 reports the LUBM and DBPedia queries in compressed form. The LDBC queries are freely available at benchmark website www.ldbcouncil.org. Here we use abbreviations to refer to them (e.g. query Q3 is the third query of the official benchmark). The KOGNAC code is available at https://github.com/jrbn/kognac.

Encoding runtime. As baseline, we selected the syntactic encoding algorithm performed by RDF-3X. We found that syntactic encoding performs better than the others, and RDF3X implements a highly optimized loading procedure.

First, we measured the (sequential) encoding runtimes of all four datasets and report them in Fig. 4(a). We notice that our approach is slightly slower than the one of RDF3X. We expected such difference, since we perform a much more complex operation than a simple syntactic encoding. In the worst case, KOGNAC is about 20% slower. Considering that loading is a one-time operation whose cost gets amortized over time, we deem it as an acceptable cost, especially in view of the benefit we get at query time. In Fig. 4(b), we measured the KOGNAC runtime doubling each time the number of threads from 1 to 64. We see that the runtime steadily decreases until it stabilizes after 8 threads. The runtime left after this point is the one necessary to sequentially assign the IDs to the list of terms and write the dictionary to disk.

In a series of experiments (not shown in this paper), we compared the performance of CM+MG against sampling at 5% (the most popular technique) and Count-Min (the fastest one). We varied the k threshold, and measured the runtime and accuracy of the approximation. We found that k = 50

was a good threshold value because KGs typically contain only few very frequent terms. Therefore, all experiments in this section should be intended with k = 50. In general, CM+MG was the fastest algorithm with k up to 500. In the best case, it was twice as fast as Count-Min (the second best). In the worst case, it was 10% slower. With higher ks, CM+MG became slower because of the heap and Count-Min returns the best runtimes. In terms of accuracy, all three managed to identify the very first top k. However, as we increased k, all methods started to fail: Sampling quickly lost accuracy, Count-Min produced large overestimates (due to hash collisions in the arrays), while CM+MG produced underestimates (due to the limited heap).

SPARQL Query performance. Tab. 1 reports on the execution of SPARQL queries with the mappings produced by KOGNAC and by RDF-3X's syntactic encoding. The table reports cold query runtimes, the maximum amount of RAM used by the system, and the disk I/O. From the table, we see that KOGNAC leads to a significant improvement over all three metrics. All query runtimes are faster, with improvements of up to ten times. The system always uses less main memory and in all but four cases it reads less data from disk.

We tested KOGNAC also with the other three systems, which use a traditional order-based encoding. For conciseness, we report in Tab. 2 only the runtimes of the LUBM queries as they are representatives of the general behaviour. We observe that also here KOGNAC produced better runtimes. For TriAD, there was an improvement in all but two cases, where the runtime was unchanged. For TripleBit, one query failed due to bugs in the system, while another produced a slightly worse runtime. In the remaining cases KOGNAC encodings were beneficial. Finally, with MonetDB we observed an improvement in all cases. In essence, our results show that an intelligent assignment, like the one produced by KOGNAC, has a significant impact on the processing of the KG. Given the encoding runtime, this improvement comes at little cost.

7 Conclusions

We proposed KOGNAC, an algorithm for efficient encoding of RDF terms in large Knowledge Graphs. KOGNAC adopts a combination of estimated frequency-based encoding (for frequent terms) and semantic clustering (for infrequent terms) to encode the graph efficiently and improve data locality in a scalable way. We evaluated the performance of KOGNAC by integrating it into multiple state-of-the-art RDF engines and relational stores. We observed significant improvements regarding query runtimes, a reduction in memory usage, and disk I/O. These results were achieved without altering the architecture or functioning of the RDF engine, but only by rearranging the encodings in an intelligent way.

We identified several directions for future work. More combinations of encoding, or other clustering criteria for terms that cannot be mapped to the taxonomy might further improve the performance. Moreover, it is interesting to study how well our FBE and LBE encodings can deal with updates, or whether they can improve other tasks than SPARQL. For instance, methods for knowledge completion with embeddings might also benefit from our encodings.

To the best of our knowledge, our work is the first that seeks an improvement of KG processing via intelligent dictionary encoding. KOGNAC represents a first step in this direction to further improve the processing of emerging KGs. Acknowledgments. This work was partially funded by the

NWO VENI project 639.021.335.