Skip to Main content Skip to Navigation
Reports

Algorithms and data structures for hyperedge queries

Jules Bertrand 1 Fanny Dufossé 2 Somesh Singh 3 Bora Uçar 3 
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.
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⟩

Share

Metrics

Record views

329

Files downloads

322