An Experimental Study of the Treewidth of Real-World Graph Data
| العنوان: | An Experimental Study of the Treewidth of Real-World Graph Data |
|---|---|
| المؤلفون: | Maniu, Silviu, Senellart, Pierre, Jog, Suraj |
| المساهمون: | Données et Connaissances Massives et Hétérogènes (LRI) (LaHDAK - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Data, Intelligence and Graphs (DIG), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Department of Electrical and Computer Engineering [Urbana] (University of Illinois), University of Illinois at Urbana-Champaign [Urbana], University of Illinois System-University of Illinois System, Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris) |
| المصدر: | ICDT 2019 – 22nd International Conference on Database Theory ICDT 2019 – 22nd International Conference on Database Theory, Mar 2019, Lisbon, Portugal. pp.18, ⟨10.4230/LIPIcs.ICDT.2019.12⟩ |
| بيانات النشر: | HAL CCSD, 2019. |
| سنة النشر: | 2019 |
| مصطلحات موضوعية: | 000 Computer science, knowledge, general works, Query processing, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Treewidth, 02 engineering and technology, Computer Science::Computational Complexity, Computer Science::Discrete Mathematics, 020204 information systems, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Computer Science, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Computer Science::Data Structures and Algorithms, Experiments, Computer Science::Databases, Graph decompositions, MathematicsofComputing_DISCRETEMATHEMATICS |
| الوصف: | International audience; Treewidth is a parameter that measures how tree-like a relational instance is, and whether it can reasonably be decomposed into a tree. Many computation tasks are known to be tractable on databases of small treewidth, but computing the treewidth of a given instance is intractable. This article is the first large-scale experimental study of treewidth and tree decompositions of real-world database instances (25 datasets from 8 different domains, with sizes ranging from a few thousand to a few million vertices). The goal is to determine which data, if any, can benefit of the wealth of algorithms for databases of small treewidth. For each dataset, we obtain upper and lower bound estimations of their treewidth, and study the properties of their tree decompositions. We show in particular that, even when treewidth is high, using partial tree decompositions can result in data structures that can assist algorithms. |
| اللغة: | English |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c23f908d4d108e2ed897c7fde385961c https://inria.hal.science/hal-02087763 |
| رقم الأكسشن: | edsair.doi.dedup.....c23f908d4d108e2ed897c7fde385961c |
| قاعدة البيانات: | OpenAIRE |
| الوصف غير متاح. |