# Algorithms and data structures for hyperedge queries

2 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We consider the problem of querying the existence of hyperedges in hypergraphs. More formally, we are given a hypergraph, and 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 run time 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.
Keywords :
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/hal-03127673
Contributor : Bora Uçar Connect in order to contact the contributor
Submitted on : Thursday, April 28, 2022 - 4:39:21 PM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM

### File

RR-9390.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-03127673, version 4

### Citation

Jules Bertrand, Fanny Dufossé, Somesh Singh, Bora Uçar. Algorithms and data structures for hyperedge queries. [Research Report] RR-9390, Inria Grenoble Rhône-Alpes. 2022, pp.28. ⟨hal-03127673v4⟩

Record views