class KVTrie {
public:
std::vector<vtype> keys; // u candidates (key
layer)
std::vector<uint32_t> offsets; // Offset to v
candidates for each u
std::vector<uint32_t> counts; // Number of v
candidates for each u
std::vector<vtype> values; // v candidates (value
layer)
uint32_t num_keys; // Number of unique
keys
uint32_t total_pairs; // Total number of key-value
pairs
// Hash table support (EGSM-style)
std::vector<uint32_t> hash_keys; // Hash table
keys for fast lookup
std::vector<uint32_t> hash_buckets; // Bucket
organization
uint32_t num_buckets; // Number of hash
buckets
uint32_t hash_constants[4]; // C0, C1, C2, C3 hash
constants for 2 hash functions
bool hash_built; // Whether hash table is built
// GPU pointers - CSR
vtype *d_keys;
uint32_t *d_offsets;
uint32_t *d_counts;
vtype *d_values;
// GPU pointers - Hash table
uint32_t *d_hash_keys;
uint32_t *d_hash_buckets;
};
class EdgeCandidateTrie {
public:
// <et, id> relation is the same as which in
Lattice.
ettype et; // Edge type identifier
int id; // Unique identifier
vtype query_u; // First query vertex
vtype query_v; // Second query vertex
// Directional validity flags
bool forward_valid; // u → v candidates valid
bool reverse_valid; // v → u candidates valid
// Forward direction: u → v
KVTrie forward_trie, reverse_trie;
// Hash constants management (shared across edges
with same vertex)
static std::unordered_map<vtype,
std::array<uint32_t, 4>>
shared_hash_constants;
// Index structures for efficient lookup
std::unordered_map<vtype, uint32_t>
forward_key_index; // key → index in [Link]
std::unordered_map<vtype, uint32_t>
reverse_key_index; // key → index in [Link]
// Memory management
bool device_allocated;
size_t memory_usage;
};
class EdgeCandidateManager {
public:
// data used to construct edge candidates
vtype *d_u_candidates_v_;
numtype *d_num_u_candidates_;
numtype *h_num_u_candidates_;
std::vector<EdgeCandidateTrie *> candidate_tries;
// store edge candidate tries
std::unordered_map<ettype, EdgeCandidateTrie *>
et_to_trie_map;
std::unordered_map<std::pair<vtype, vtype>,
EdgeCandidateTrie *, PairHash> edge_to_trie_map;
MemoryManager *memory_manager;
size_t total_memory_usage;
int num_tries;
};
class TrieLayer
{
public:
// layer properties
vtype query_u; // the query vertex this
layer corresponds to
int trie_layer_id; // unique id of each layer,
may be concluded in different interTries.
uint32_t num_rows; // size of values, parents.
uint32_t mask_length; // =ceil(size/32), size of
bool_vec.
// host data
std::vector<vtype> values; // Values at this
level
std::vector<uint32_t> parents; // Parent indices
in previous layer (or previous trie)
std::vector<uint32_t> bool_vec; // compressed
boolean vector representation
// device data
void *d_mem_space;
vtype *d_values;
uint32_t *d_parents;
uint32_t *d_bool_vec;
bool device_data_allocated;
size_t memory_usage;
};
class LayeredTrie
{
public:
ettype et;
int inter_id;
int num_levels; // Total number of levels
across all layers, #expand + #mask = #edge
int num_cols; // #cols = #expand_level
vtype *query_us_; // in the order of layers, not
u_ids
int refer_to; // Trie_inter_id
// Chain of trie layers
int parent_trie_id;
std::vector<int> layer_ids;
std::vector<int> child_trie_ids;
// Current layer (the one added in latest
expansion)
int current_layer_id; // should be the same as
trie_inter_id;
// Memory management
size_t total_memory_usage;
bool device_data_allocated;
};
class LayeredTrieManager
{
public:
int num_layers;
int num_trie_intermediates;
std::vector<LayeredTrie *> all_tries;
std::vector<TrieLayer *> all_layers;
std::unordered_set<ettype> computed_tries;
std::unordered_set<ettype> to_be_computed_et;
// Expansion tracking
std::unordered_map<ettype, LayeredTrie *>
et_to_trie_map;
std::vector<LayeredTrie *> root_tries; // Tries
that are not expansions of others
// Memory management
MemoryManager *mem_mgr;
size_t total_memory_saved;
double average_compression_ratio;
};
class Lattice {
public:
int num_edges;
ettype max_bit;
int num_lattice_nodes;
ettype src;
std::vector<std::vector<int>> linked_list; //
store one's children nodes. (subset)
std::vector<std::vector<int>>
reversed_linked_list; // store one's parents
(superset)
std::unordered_map<ettype, int> et2id;
std::unordered_map<int, ettype> id2et;
std::unordered_set<uint32_t> rq_set;
std::vector<std::unordered_set<int>>
reachable_nodes; // what nodes can I contribut to?
std::vector<std::unordered_set<int>>
uncomputed_reachable_nodes;
std::vector<std::unordered_set<int>>
computed_reachable_nodes;
std::vector<int> num_reachable_nodes; // how many
nodes can I contribute to?
std::vector<std::unordered_set<int>>
reachable_rq;
std::vector<std::unordered_set<int>>
computed_reachable_rq;
std::vector<std::unordered_set<int>>
uncomputed_reachable_rq;
std::vector<int> num_reachable_rq; // how many
relaxed queries can I contribute to?
std::unordered_map<int, double>
contribution_value_cache;
};
class HashTable
{
public:
// hash table data
uint32_t *d_keys_[NUM_TABLES];
uint32_t *d_values_[NUM_TABLES];
uint32_t hash_constants_[MAX_EQ * NUM_TABLES * 4];
uint32_t *d_hash_constants_; // the same size as hash_constants_
uint32_t *d_buffer_;
uint32_t *d_hash_table_offs_;
uint32_t *d_num_buckets_;
// for the 0-th layer
offtype *d_offsets_; // device memory: flat
array of all edge offsets
std::vector<size_t> edge_offset_starts_; // host: starting
position of each edge's offsets
// host copy
uint32_t *h_buffer;
uint32_t *h_num_candidates_;
uint32_t *h_num_buckets_;
uint32_t *h_hash_table_offs_;
};
class DataBlock
{
public:
void *d_space; // device pointer
size_t size_in_byte; // size of the block
uint32_t *d_data; // column data or mask.
uint32_t *d_parents; // parent indices
size_t num_rows; // real number(for both)
size_t num_compressed_blocks; // only for mask
// see if this block is a mask by checking num_compressed_blocks >
0
};
class UnifiedTrie
{
public:
// my info
uint32_t id; // inter_id
ettype et; // edge tag
uint32_t num_levels;
uint32_t num_cols;
vtype *query_us_;
uint32_t num_results;
// chain relations
uint32_t mask_parent_id;
uint32_t expansion_parent_id;
std::vector<uint32_t> layer_ids;
// data
DataBlock *data; // one column of data.
DataBlock *r_data; // reversed data, only for edge.
};
class UnifiedTrieManager
{
public:
std::vector<UnifiedTrie *> tries; // one trie - one lattice node
uint32_t num_tries;
std::unordered_set<uint32_t> complete_rq_ids; // for look up
std::unordered_set<uint32_t> computed_rq_ids;
std::unordered_set<uint32_t> uncomputed_rq_ids;
std::unordered_set<uint32_t> computed_subgraphs_ids;
// relation info
std::vector<std::vector<vtype *>> parent_addr_list;
};