Cached GBWT

General

The cached GBWT is a caching layer over the compressed index. It is defined in cached_gbwt.h.

Caching is useful for workloads that repeatedly access the same subset of nodes. Accessed records are stored in an array and a hash table maps node identifiers to cache offsets. Future accesses are faster, because the header has already been decompressed and there is a pointer to the compressed body of the record.

Warning: The cache is not thread-safe. Use a separate cache for each query thread.

Interface

class CachedGBWT
{
  const GBWT* index;
  mutable std::vector<edge_type>        cache_index;
  mutable std::vector<CompressedRecord> cached_records;
};

• The cached GBWT index is index.
• Hash table cache_index maps node identifiers to cache offsets.
• Array cached_records contains the cached records.

CachedGBWT supports the same query interface and search interface as GBWT and DynamicGBWT.

Construction

explicit CachedGBWT(const GBWT& gbwt_index, bool single_record = false);

The constructor creates a cache for GBWT index gbwt_index. When single_record is set, the cache only allocates enough space for caching a single record. Otherwise the initial allocation will provide space for INITIAL_CAPACITY records.

Cache interface

The following functions operate on the cache itself:

• size_type cacheSize() const: Number of records in the cache.
• size_type cacheCapacity() const: Hash table size. When the load factor reaches MAX_LOAD_FACTOR, it will initiate rehashing.
• void clearCache(): Clear the cache.

Inserting new records to the cache may invalidate references to the cached records. Hence the records are accessed through cache offsets instead. The following functions operate on cache offsets:

• size_type findRecord(node_type node) const: Return the cache offset of node node. Cache the record, if it is not already in the cache.
• size_type outdegree(size_type cache_offset) const: Return the outdegree of the node with cache offset cache_offset.
• node_type successor(size_type cache_offset, size_type i) const: Return the identifier of the ith successor of the node with cache offset cache_offset. The successors are 0-based.

The following search operations also have cached variants:

SearchState cachedExtend(SearchState state, size_type cache_offset, size_type i) const
BidirectionalState cachedExtendForward(BidirectionalState state, size_type cache_offset, size_type i) const
BidirectionalState cachedExtendBackward(BidirectionalState state, size_type cache_offset, size_type i) const

They correspond to extend(state, node), bdExtendForward(state, node), and bdExtendBackward(state, node), respectively. They extend the search to the ith successor of the node with cache offset cache_offset. This node is assumed to be state.node, state.forward.node, and state.backward.node, respectively.