Skip to Main content Skip to Navigation
Reports

Algorithms and data structures for hyperedge queries

Jules Bertrand 1 Fanny Dufossé 2 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 that the proposed approach has shorter query response time than the other considered alternatives, while having the shortest or the second shortest construction time.
Complete list of metadata

https://hal.inria.fr/hal-03127673
Contributor : Bora Uçar <>
Submitted on : Tuesday, February 2, 2021 - 3:34:47 PM
Last modification on : Wednesday, February 3, 2021 - 3:33:30 AM

File

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

Identifiers

  • HAL Id : hal-03127673, version 2

Citation

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

Share

Metrics

Record views

83

Files downloads

120