Algorithms and Data Structures for Hyperedge Queries
This work proposes an adaptation of a well-known perfect hashing approach for the problem at hand of querying the existence of hyperedges in hypergraphs and analyzes the space and runtime complexity and experimentally compares it with the state-of-the-art hashing-based solutions.
Abstract
We consider the problem of querying the existence of hyperedges in hypergraphs. More formally, given a hypergraph, we need to answer queries of the form: “Does the following set of vertices form a hyperedge in the given hypergraph?” Our aim is to set up data structures based on hashing to answer these queries as fast as possible. We propose an adaptation of a well-known perfect hashing approach for the problem at hand. We analyze the space and runtime complexity of the proposed approach and experimentally compare it with the state-of-the-art hashing-based solutions. Experiments demonstrate the efficiency of the proposed approach with respect to the state-of-the-art.