Algorithms and data structures for hyperedge queries - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2021

Algorithms and data structures for hyperedge queries

Jules Bertrand
  • Fonction : Auteur
  • PersonId : 1089964
Fanny Dufossé

Résumé

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 the shortest query response time than the other considered alternatives, while having a larger construction time than some of the alternatives.
Nous considérons le problème de requêtes d'existences d'hyperarêtes dans des hypergraphes. Plus formellement, pour un hypergraphe donné, nous devons répondre à des requêtes de la forme "est-ce que l'ensemble de sommets suivant forme une hyperarête de l'hypergraphe?". Notre objectif est de mettre en place une structure de donnée basée sur du hachage pour répondre à ces requêtes le plus rapidement possible. Nous proposons une adaptation d'une approche bien connue de hachage parfait pour notre problème. Nous analysons la complexité en temps et en espace de cette approche, et nous la comparons expérimentalement à des solutions de l'état de l'art basées sur le hachage. Les expériences démontrent que cette approche a un temps de réponse aux requêtes plus court que les alternatives considérées, pour un temps de construction plus long que certaines des alternatives.
Fichier principal
Vignette du fichier
RR-9390.pdf (1.87 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03127673 , version 1 (01-02-2021)
hal-03127673 , version 2 (02-02-2021)
hal-03127673 , version 3 (01-06-2021)
hal-03127673 , version 4 (28-04-2022)

Identifiants

  • HAL Id : hal-03127673 , version 3

Citer

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.25. ⟨hal-03127673v3⟩
474 Consultations
465 Téléchargements

Partager

Gmail Facebook X LinkedIn More