KOGNAC: Efficient Encoding of Large Knowledge Graphs

Jacopo Urbani, Sourav Dutta, Sairam Gurajada, Gerhard WeikumIJCAI 2016

Abstract

Knowledge Graphs (KGs) containing billions of facts require efficient storage and retrieval mechanisms. Dictionary encoding, which maps string identifiers to integer IDs, is a standard technique used by RDF engines. However, traditional encoding methods often ignore data locality and compression efficiency. This paper presents KOGNAC (KnOwledge Graph eNoding And Compression), a novel dictionary-encoding algorithm that utilizes a hybrid approach: Frequency-based Encoding (FBE) for high-frequency terms and Locality-based Encoding (LBE) for the long tail of infrequent terms. KOGNAC achieves significant query performance improvements—up to 10x—by optimizing bit-compression and minimizing random disk access during join operations.

Introduction

Large-scale Knowledge Graphs like DBpedia or the Google Knowledge Graph are foundational to modern semantic web applications. To manage the sheer volume of data, RDF engines typically replace long Internationalized Resource Identifiers (IRIs) and literals with short integer IDs. While this "dictionary encoding" reduces storage overhead, the assignment of these IDs is frequently arbitrary, based on appearance order or simple hashing.

This lack of strategy leads to two primary bottlenecks. First, poor compression occurs when frequent terms are assigned large IDs, preventing the use of efficient bit-packing techniques. Second, poor data locality results in "random walks" across memory or disk during join operations. If related entities are assigned disparate IDs, the engine must jump between non-contiguous index blocks, severely degrading performance.

Methodology: The KOGNAC Approach

KOGNAC addresses these issues through a dual-encoding strategy that distinguishes between "heavy hitters" and the "long tail" of terms.

Figure 1: The KOGNAC architecture combines frequency-based and locality-based encoding to generate an optimized dictionary.

Frequency-based Encoding (FBE)

For the most common terms in a dataset, KOGNAC prioritizes compression. It utilizes a hybrid algorithm called CM+MG, which combines Count-Min sketches for frequency estimation with Misra-Gries heaps to identify top-k items in a data stream. By assigning the smallest integer IDs to the most frequent terms, KOGNAC ensures that the majority of triples in the KG can be stored using minimal bits, maximizing downstream compression.

Locality-based Encoding (LBE)

For infrequent terms, KOGNAC focuses on data locality by leveraging the semantic structure of the graph. It constructs a taxonomy based on isA relations and ontological classes. Terms belonging to the same or related classes are assigned consecutive IDs. Since SPARQL queries often involve joins between entities of similar types (e.g., finding all "Scientists" born in "Berlin"), this clustering ensures that relevant data is physically adjacent in the database index, reducing I/O overhead.

Experimental Evaluation

The effectiveness of KOGNAC was evaluated using several large-scale benchmarks, including LUBM (synthetic), DBpedia (real-world), and LDBC (social network workloads).

Key Results

KOGNAC was integrated into four state-of-the-art RDF engines: RDF-3X, TripleBit, TriAD, and MonetDB. The results demonstrated a universal improvement in query performance, with some complex SPARQL queries executing up to 10 times faster than with baseline encodings.

Figure 6: (a) Encoding runtime comparison between KOGNAC and RDF-3X; (b) Scalability of KOGNAC encoding time relative to the number of CPU cores.

The system showed high resource efficiency, reducing both RAM usage and Disk I/O. While the initial encoding process is approximately 20% slower than the fastest baseline methods, this is a one-time cost that provides permanent performance gains. Furthermore, as shown in Figure 6(b), the encoding process is highly parallelizable and scales efficiently with additional hardware cores.

Conclusion and Future Work

KOGNAC demonstrates that intelligent dictionary encoding is a powerful lever for optimizing Knowledge Graph performance. By aligning ID assignment with both statistical frequency and semantic structure, it bridges the gap between raw data storage and efficient query execution.

Future research will focus on adapting KOGNAC for dynamic environments where Knowledge Graphs receive frequent updates. Additionally, the authors plan to explore graph-based connectivity clustering for datasets that lack formal ontologies, potentially extending the benefits of locality-based encoding to a wider range of graph structures.

Summary updated

BibTeX
@inproceedings{urbani2016kognac,
  author = {Jacopo Urbani and Sourav Dutta and Sairam Gurajada and Gerhard Weikum},
  title = {{KOGNAC: Efficient Encoding of Large Knowledge Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure