RDF Cache K2 — Compact & Dynamic Caching System for RDF Graph Databases

A high-performance caching layer for RDF triple stores built on dynamic, compressed K2-trees. It stores RDF triples in a space-efficient way using one K2-tree per predicate, supports SPARQL Basic Graph Pattern (BGP) evaluation, and exposes a TCP server with protobuf-based messaging for client integration.

Developed as a Master's thesis at Universidad de Chile.

📄 Master thesis | Direct Download — PDF

Overview

RDFCacheK2 is a caching system designed for RDF graph databases. Its core idea is to represent RDF triples compactly using K2-trees — a compressed data structure for sparse binary matrices — where each RDF predicate gets its own K2-tree storing (subject, object) pairs.

Key features:

Compact storage: K2-trees compress sparse adjacency matrices, achieving significant space savings over raw triple storage.
Dynamic updates: Unlike static K2-tree implementations, this system supports insert and delete operations on the trees at runtime.
Cache eviction policies: Supports LRU, Frequency-based, and no-caching strategies with configurable memory budgets.
SPARQL BGP evaluation: Includes a query engine that evaluates Basic Graph Patterns with join operators (cross-product, intersection, hash join) directly over the K2-tree structures.
TCP server with protobuf protocol: Exposes the cache as a network service with support for triple pattern streaming, BGP queries, batch updates, and query cancellation.
Fully Indexed Cache (FIC): An optional second-level cache that materializes small predicates into direct subject→objects and object→subjects maps for fast lookup.

Architecture

┌─────────────────────────────────────────────────────────────────────┐
│                          Client (Protobuf/TCP)                      │
└────────────────────────────────┬────────────────────────────────────┘
                                 │
                    ┌────────────▼────────────┐
                    │      CacheServer        │
                    │  (TCP listener + workers)│
                    └────────────┬────────────┘
                                 │
                    ┌────────────▼────────────┐
                    │   TaskProcessor          │
                    │  (request routing)       │
                    └──┬─────────┬─────────┬──┘
                       │         │         │
            ┌──────────▼──┐ ┌───▼────┐ ┌──▼──────────┐
            │ Triple      │ │  BGP   │ │  Update     │
            │ Pattern     │ │ Query  │ │  Session    │
            │ Streaming   │ │ Engine │ │  (add/del)  │
            └──────┬──────┘ └───┬────┘ └──────┬──────┘
                   │            │              │
            ┌──────▼────────────▼──────────────▼──────┐
            │           CacheContainer                 │
            │  ┌──────────────────────────────────┐   │
            │  │  PredicatesCacheManager           │   │
            │  │  (per-predicate K2-tree loading)   │   │
            │  └──────────────┬───────────────────┘   │
            │  ┌──────────────▼───────────────────┐   │
            │  │  Replacement Policy               │   │
            │  │  (LRU / Frequency / None)         │   │
            │  └──────────────────────────────────┘   │
            │  ┌──────────────────────────────────┐   │
            │  │  Fully Indexed Cache (FIC)        │   │
            │  │  (optional, small predicates)      │   │
            │  └──────────────────────────────────┘   │
            │  ┌──────────────────────────────────┐   │
            │  │  NodeIds Manager                  │   │
            │  │  (RDF term ↔ numeric ID mapping)  │   │
            │  └──────────────────────────────────┘   │
            └─────────────────────────────────────────┘
                               │
                    ┌──────────▼──────────┐
                    │   K2-tree Index File │
                    │  (on-disk serialized │
                    │   per-predicate      │
                    │   K2-trees)          │
                    └─────────────────────┘

Prerequisites

C++17 compiler (GCC or Clang)
CMake ≥ 3.14
Protobuf (protoc + libraries)
OpenSSL
libcurl
Google Test (optional, for tests)
Make
Git (to fetch dependencies)

On Debian/Ubuntu:

sudo apt-get install build-essential cmake protobuf-compiler libprotobuf-dev \
  libssl-dev libcurl4-openssl-dev libgtest-dev git

On macOS (Homebrew):

brew install cmake protobuf openssl curl googletest

Building

1. Fetch dependencies

The project depends on three external libraries, fetched automatically:

Library	Description
c-k2tree-dyn	Dynamic K2-tree C implementation (git submodule)
ntparser	N-Triples file parser
external-sort	External merge-sort for large triple files

2. Full build (recommended)

make all

This runs three stages:

proto-build — Generates C++ and Java protobuf code from .proto files
build-libs — Fetches dependencies and builds the NT parser
build — CMake configure + compile (Release mode)

3. Debug build

make all-debug

4. Clean rebuild

make re          # clean + release build
make re-debug    # clean + debug build

5. Parallel build

Set CACHE_CORES_BUILD to control parallelism (defaults to nproc):

CACHE_CORES_BUILD=8 make all

Indexing Pipeline

Before running the cache server, RDF data must be indexed into the K2-tree format. The pipeline converts N-Triples (.nt) files into a compact binary index.

Automated pipeline

Use build_index_all.py to run the full pipeline:

python3 build_index_all.py

Manual step-by-step

Convert triples to binary format:

./build/convert_triples_to_binary <input.nt> <output.bin>

External sort the binary triples (by predicate):

./build/external_sort <input.bin> <output_sorted.bin>

Build the K2-tree index:

./build/build_k2tree_index <sorted_triples.bin> <output_index_file>

Configuration

See template_config.ini for indexing parameters:

[Indexing]
K2Tree_TreeDepth=32          # Tree depth (32 or 64)
K2Tree_CutDepth=10           # Depth at which to cut internal nodes
K2Tree_MaxNodesCount=256     # Max nodes per leaf block
SortingWorkers=4             # Parallel sorting threads
SortingMemoryBudget=25%      # Memory budget for sorting

Utility tools

Tool	Description
`print_k2tree_index`	Inspect/dump the contents of a K2-tree index file
`print_nodeids`	Display the RDF term ↔ numeric ID mappings
`dataset_stats`	Print dataset statistics
`debug_read_k2trees_metadata`	Dump index metadata for debugging
`traverse_k2tree_band`	Traverse a K2-tree band (row/column slice)
`search_paths`	Search N-length paths through K2-trees
`random_dataset_gen`	Generate random binary triple datasets
`random_nt_dataset_generate`	Generate random N-Triples datasets
`generate_triples.py`	Generate a simple 10M-triple test dataset

Running the Cache Server

The cache server loads a K2-tree index into memory and serves queries over TCP using protobuf messages.

./build/cache_server \
  --index-file <path_to_index>         \   # K2-tree index file (required)
  --node-ids-file <path>               \   # Node IDs file (required)
  --mapped-node-ids-file <path>        \   # Mapped node IDs file (required)
  --node-ids-logs-file <path>          \   # Node IDs log file (required)
  --memory-budget <bytes>              \   # Memory budget in bytes (required)
  --port <port>                        \   # TCP port to listen on (required)
  --workers <count>                    \   # Number of worker threads (required)
  --replacement-strategy <strategy>    \   # lru | frequency | none (required)
  --update-log-filename <path>         \   # Update log file (required)
  --timeout-ms <ms>                    \   # Query timeout in milliseconds (required)
  --fic                                \   # Enable Fully Indexed Cache (optional)
  --sort-results                           # Sort query results (optional)

Example:

./build/cache_server \
  -I ./data/my_index.k2idx \
  -N ./data/node_ids.bin \
  -M ./data/mapped_node_ids.bin \
  -L ./data/node_ids_logs.bin \
  -m 1073741824 \
  -p 9090 \
  -w 4 \
  -R lru \
  -U ./data/update_log.bin \
  -T 30000 \
  -F -S

Replacement strategies

Strategy	Description
`lru`	Evicts least-recently-used predicates first
`frequency`	Evicts least-frequently-accessed predicates first
`none`	No eviction — loads all predicates eagerly

Project Structure

RDFCacheK2/
├── core/                          # Core data structures and logic
│   ├── k2tree/                    #   K2TreeMixed — dynamic compressed K2-tree
│   │   ├── K2TreeMixed.hpp/cpp    #     Insert, remove, has, scan, serialize/deserialize
│   │   ├── K2TreeBulkOp.*         #     Bulk operation wrapper with reusable state
│   │   ├── FullScanner.*          #     Iterate all (subject, object) points
│   │   ├── BandScanner.*          #     Iterate a row or column slice
│   │   └── EmptyScanner.*         #     No-op scanner
│   ├── builder/                   #   Index construction pipeline
│   │   ├── PredicatesIndexFileBuilder.*   # Build index file from sorted triples
│   │   ├── K2TreesFeedFromSortedTriplesFeed.*  # Group triples → K2-trees
│   │   └── TriplesFeedSBPFromIstream.*    # Stream reader for sorted triples
│   ├── fic/                       #   Fully Indexed Cache (optional 2nd-level cache)
│   │   ├── FullyIndexedCacheImpl.*       # LRU cache of materialized predicates
│   │   ├── FullyIndexedPredicate.*       # Materialized subject↔object maps
│   │   ├── CacheDataManager.*            # Load/unload predicates from index
│   │   └── NoFIC.*                       # No-op implementation
│   ├── manager/                   #   Predicate cache management
│   │   ├── PredicatesIndexCacheMD.*      # Index metadata + K2-tree loading
│   │   └── PredicatesCacheManagerImpl.*  # High-level predicate management
│   ├── replacement/               #   Cache eviction policies
│   │   ├── CacheReplacement.*            # Generic eviction engine
│   │   ├── LRUReplacementStrategy.*      # Recency-based eviction
│   │   ├── FrequencyReplacementStrategy.*# Frequency-based eviction
│   │   └── NoCachingReplacement.*        # No eviction (load everything)
│   ├── updating/                  #   Update logging and merge
│   ├── nodeids/                   #   RDF term ↔ numeric ID mapping
│   └── algorithms/                #   Path search algorithms
│
├── cache/                         # Cache container (bootstrap & facade)
│   ├── CacheContainer.*           #   Runtime facade (manager + policy + FIC)
│   └── CacheContainerFactory.*    #   Factory with strategy-based construction
│
├── query_engine/                  # SPARQL BGP query evaluation
│   ├── BGPMessage.*               #   BGP query AST (variables + triple patterns)
│   ├── query_processing/
│   │   ├── BGPProcessor.*         #   Query planner: resolves IDs, builds iterators
│   │   ├── BGPOpsFactory.*        #   Selects join operator by variable layout
│   │   ├── VarIndexManager.*      #   Variable name ↔ index mapping
│   │   └── iterators/             #   Query result iterators
│   │       ├── BGPIterator.*      #     Runs operator chain, yields result rows
│   │       ├── QueryIterator.*    #     Abstract result iterator
│   │       └── bgpops/            #     BGP join operators
│   │           ├── OneVarCPBGPOp         # Single-variable cross-product
│   │           ├── OneVarIntersectBGPOp  # Single-variable intersection
│   │           ├── TwoVarCProductBGPOp   # Two-variable cross-product
│   │           ├── TwoVarJoinOneBGPOp    # Two-variable hash join
│   │           ├── TwoVarIntersectionBGPOp # Two-variable intersection
│   │           └── TripleExistenceBGPOP  # Existence check (no variables)
│   └── TimeControl.*              #   Query timeout / cancellation control
│
├── network/                       # TCP server and streaming layer
│   ├── server/
│   │   ├── CacheServer.*          #   TCP listener + worker pool
│   │   ├── conn/TCPServerConnection.*   # Socket bind/listen/accept
│   │   ├── tasks/
│   │   │   ├── TaskProcessor.*          # Request routing interface
│   │   │   ├── CacheServerTaskProcessor.*  # Full implementation
│   │   │   └── ServerTask.*             # Per-connection state machine
│   │   ├── session/UpdaterSession.*     # Batch update session (add/delete)
│   │   └── replacement/                 # Deferred replacement tasks
│   ├── streaming/                 #   Triple pattern + BGP result streaming
│   │   ├── TripleMatchesPartStreamer.*   # Chooses streamer strategy
│   │   ├── StreamerFromCachedSource.*   # Stream from FIC
│   │   ├── TriplePatternMatchingStreamer.*  # Stream from K2-tree scanner
│   │   ├── TPMSortedStreamer.*          # Sorted streaming with pagination
│   │   └── BGPStreamer.*               # BGP join result streaming
│   ├── scanner/                   #   Cached-source scanners
│   └── messages/                  #   Protobuf message parsing utilities
│
├── memory/                        # Memory management
│   ├── MemoryManager.*            #   Singleton manager with segment tracking
│   ├── MemorySegment.*            #   Linear byte-region allocator
│   └── MemoryPool.hpp             #   Thread-safe pooled allocator
│
├── utils/                         # Utility libraries
│   ├── I_IOStream.hpp             #   Abstract I/O stream interfaces
│   ├── FileRWHandler.*            #   File-backed I/O implementations
│   ├── serialization_util.*       #   Endian-safe binary serialization
│   ├── hashing.*                  #   MD5/SHA hash helpers
│   └── sort/                      #   External sort for node-ID generation
│
├── algorithms/                    # Parallel algorithms
│   ├── ParallelWorker.hpp         #   Thread pool implementation
│   └── triple_external_sort.hpp   #   External merge-sort for triples
│
├── proto/                         # Protobuf message definitions
│   ├── message_type.proto         #   Request/response message types enum
│   ├── request_msg.proto          #   Client request messages
│   ├── response_msg.proto         #   Server response messages
│   └── sparql_tree.proto          #   SPARQL algebra AST
│
├── scripts/                       # CLI tool entry points
├── benchmarks/                    # Performance benchmarks
├── experiments/                   # Validation & correctness experiments
├── test/                          # Google Test unit/integration tests
├── docker/                        # Docker build configuration
├── lib/                           # External dependencies (submodules)
│   ├── c-k2tree-dyn/              #   Dynamic K2-tree C library
│   ├── ntparser/                  #   N-Triples parser
│   └── external-sort/             #   External merge-sort library
├── cmake/                         # CMake modules
├── bash/                          # Shell scripts (Docker builds, etc.)
├── build_index_all.py             # Full indexing pipeline orchestrator
├── generate_triples.py            # Test dataset generator
├── template_config.ini            # Indexing configuration template
├── Makefile                       # Top-level build orchestration
└── CMakeLists.txt                 # CMake build configuration

Testing

Tests use Google Test and are built automatically when GTest is found.

# Run all tests
cd build && ctest -j$(nproc) .

# Run a specific test
./build/k2tree_tests
./build/bgp_processor_test
./build/cache_replacement_test

Test categories

Category	Tests
K2-tree core	`k2tree_tests`, `k2tree_mixed_test`, `k2tree_serialization_test`
Serialization	`serialization_test`, `predicates_metadata_serialization_test`
Cache/eviction	`cache_replacement_test`, `fully_indexed_cache_test`
Updates	`update_log_test`
Node IDs	`node_ids_dyn_mapper_test`, `nodeids_manager_impl_test`, `nodeids_build_flow_test`, `nodes_map_test`
Query/BGP	`bgp_ops_test`, `bgp_processor_test`, `bgp_streamer_test`
Network	`server_task_test`
Path search	`search_paths_test`
Sorting	`sort_results_test`, `test_external_sort`
Memory	`memory_segment_test`
c-k2tree-dyn	`block_test`, `block_leak_test`, `morton_code_test`, `bitvector_test`, `k2node_test`, `lazy_scan_test`, `block_delete_test`, `k2node_delete_test`

Benchmarks & Experiments

Benchmarks

./build/insertion_speed              # Time 1M inserts/removes across configs
./build/k2tree_mixed_benchmark       # Random bulk insert + serialization size
./build/k2tree_size_benchmark        # Space usage analysis
./build/lazy_scan_benchmark          # Scan performance
./build/cluster_insertion_speed      # Clustered insertion performance
./build/compare_64_32_depths_performance  # 32 vs 64-depth tree comparison
./build/points_size_relationship     # Points count vs size relationship

Experiments

./build/build_from_raw_points        # Build tree, validate scans, test serialization round-trips
./build/validate_k2tree_correctness  # Randomized correctness validation
./build/deserialize_k2tree           # Deserialize and dump tree contents

Docker

A Docker-based build and deployment setup is included.

Build the Docker image

# First, create a code bundle
make bundle-code

# Build the image
cd docker
docker build -t rdfcachek2 .

Build arguments

Argument	Default	Description
`debug`	`FALSE`	Set to `TRUE` for a debug build (includes gdb, vim)
`CACHE_CORES_BUILD`	`1`	Number of parallel build cores
`DISABLE_TEST`	`FALSE`	Set to `TRUE` to skip running tests during build

docker build --build-arg CACHE_CORES_BUILD=4 --build-arg debug=TRUE -t rdfcachek2:debug .

Protocol (Protobuf Messages)

The client-server communication uses length-prefixed protobuf messages over TCP. The protocol supports:

Message Type	Description
`RUN_QUERY`	Execute a SPARQL query
`STREAM_REQUEST_TRIPLE_PATTERN`	Start streaming triples matching a pattern
`STREAM_CONTINUE_TRIPLE_PATTERN`	Continue a paginated triple stream
`REQUEST_BGP_JOIN`	Execute a BGP join query
`REQUEST_MORE_BGP_JOIN`	Continue paginated BGP results
`CACHE_REQUEST_START_UPDATE_TRIPLES`	Begin an update batch session
`TRIPLES_UPDATE_BATCH`	Send a batch of add/delete operations
`CACHE_DONE_UPDATE_TRIPLES`	Commit the update batch
`SYNC_LOGS_WITH_INDEXES_REQUEST`	Sync update logs with index files
`CANCEL_QUERY`	Cancel a running query
`CONNECTION_END`	Close the connection

The full SPARQL algebra AST is defined in proto/sparql_tree.proto, supporting Project, Join, BGP, Filter, Optional, Minus, Union, Distinct, Order, Slice, GroupBy, and more.

Citation

If you use this software, please cite:

@mastersthesis{miranda2024rdfcachek2,
  title   = {A compact and dynamic caching system for RDF graph databases},
  author  = {Miranda, Cristóbal},
  school  = {Universidad de Chile},
  year    = {2024},
  url     = {https://repositorio.uchile.cl/handle/2250/203843}
}

License

See the repository for license information.

Navigation Menu

Repository files navigation

RDF Cache K2 — Compact & Dynamic Caching System for RDF Graph Databases

Table of Contents

Overview

Architecture

Prerequisites

Building

1. Fetch dependencies

2. Full build (recommended)

3. Debug build

4. Clean rebuild

5. Parallel build

Indexing Pipeline

Automated pipeline

Manual step-by-step

Configuration

Utility tools

Running the Cache Server

Replacement strategies

Project Structure

Testing

Test categories

Benchmarks & Experiments

Benchmarks

Experiments

Docker

Build the Docker image

Build arguments

Protocol (Protobuf Messages)

Citation

License

About

Releases

Packages

Contributors

Languages

Name		Name	Last commit message	Last commit date
algorithms		algorithms
bash		bash
benchmarks		benchmarks
cache		cache
cmake/Modules		cmake/Modules
core		core
docker		docker
experiments		experiments
lib		lib
memory		memory
network		network
proto		proto
query_engine		query_engine
scripts		scripts
test		test
utils		utils
.gitignore		.gitignore
.gitmodules		.gitmodules
CITATION.cff		CITATION.cff
CMakeLists.txt		CMakeLists.txt
CTestCustom.cmake		CTestCustom.cmake
Makefile		Makefile
README.md		README.md
build_index_all.py		build_index_all.py
clang-format.txt		clang-format.txt
fetch_deps.sh		fetch_deps.sh
format.sh		format.sh
gcc-clang-checker.sh		gcc-clang-checker.sh
generate_triples.py		generate_triples.py
template_config.ini		template_config.ini

Latest commit

History

Folders and files

Repository files navigation

RDF Cache K2 — Compact & Dynamic Caching System for RDF Graph Databases

Table of Contents

Overview

Architecture

Prerequisites

Building

1. Fetch dependencies

2. Full build (recommended)

3. Debug build

4. Clean rebuild

5. Parallel build

Indexing Pipeline

Automated pipeline

Manual step-by-step

Configuration

Utility tools

Running the Cache Server

Replacement strategies

Project Structure

Testing

Test categories

Benchmarks & Experiments

Benchmarks

Experiments

Docker

Build the Docker image

Build arguments

Protocol (Protobuf Messages)

Citation

License

About

Topics

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages