Search Results

Documents authored by Groz, Benoit

Found 2 Possible Name Variants:

Groz, Benoit

Document
DOI: 10.4230/LIPIcs.ICDT.2022.14
Inference of Shape Graphs for Graph Databases

Authors: Benoît Groz, Aurélien Lemay, Sławek Staworko, and Piotr Wieczorek

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
We investigate the problem of constructing a shape graph that describes the structure of a given graph database. We employ the framework of grammatical inference, where the objective is to find an inference algorithm that is both sound, i.e., always producing a schema that validates the input graph, and complete, i.e., able to produce any schema, within a given class of schemas, provided that a sufficiently informative input graph is presented. We identify a number of fundamental limitations that preclude feasible inference. We present inference algorithms based on natural approaches that allow to infer schemas that we argue to be of practical importance.
Cite as

Benoît Groz, Aurélien Lemay, Sławek Staworko, and Piotr Wieczorek. Inference of Shape Graphs for Graph Databases. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{groz_et_al:LIPIcs.ICDT.2022.14,
  author =	{Groz, Beno\^{i}t and Lemay, Aur\'{e}lien and Staworko, S{\l}awek and Wieczorek, Piotr},
  title =	{{Inference of Shape Graphs for Graph Databases}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.14},
  URN =		{urn:nbn:de:0030-drops-158889},
  doi =		{10.4230/LIPIcs.ICDT.2022.14},
  annote =	{Keywords: RDF, Schema, Inference, Learning, Fitting, Minimality, Containment}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2016.12
Filtering With the Crowd: CrowdScreen Revisited

Authors: Benoit Groz, Ezra Levin, Isaac Meilijson, and Tova Milo

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract
Filtering a set of items, based on a set of properties that can be verified by humans, is a common application of CrowdSourcing. When the workers are error-prone, each item is presented to multiple users, to limit the probability of misclassification. Since the Crowd is a relatively expensive resource, minimizing the number of questions per item may naturally result in big savings. Several algorithms to address this minimization problem have been presented in the CrowdScreen framework by Parameswaran et al. However, those algorithms do not scale well and therefore cannot be used in scenarios where high accuracy is required in spite of high user error rates. The goal of this paper is thus to devise algorithms that can cope with such situations. To achieve this, we provide new theoretical insights to the problem, then use them to develop a new efficient algorithm. We also propose novel optimizations for the algorithms of CrowdScreen that improve their scalability. We complement our theoretical study by an experimental evaluation of the algorithms on a large set of synthetic parameters as well as real-life crowdsourcing scenarios, demonstrating the advantages of our solution.
Cite as

Benoit Groz, Ezra Levin, Isaac Meilijson, and Tova Milo. Filtering With the Crowd: CrowdScreen Revisited. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{groz_et_al:LIPIcs.ICDT.2016.12,
  author =	{Groz, Benoit and Levin, Ezra and Meilijson, Isaac and Milo, Tova},
  title =	{{Filtering With the Crowd: CrowdScreen Revisited}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.12},
  URN =		{urn:nbn:de:0030-drops-57817},
  doi =		{10.4230/LIPIcs.ICDT.2016.12},
  annote =	{Keywords: CrowdSourcing, filtering, algorithms, sprt, hypothesis testing}
}

Groz, Benoît

Document
DOI: 10.4230/LIPIcs.ICDT.2022.14
Inference of Shape Graphs for Graph Databases

Authors: Benoît Groz, Aurélien Lemay, Sławek Staworko, and Piotr Wieczorek

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
We investigate the problem of constructing a shape graph that describes the structure of a given graph database. We employ the framework of grammatical inference, where the objective is to find an inference algorithm that is both sound, i.e., always producing a schema that validates the input graph, and complete, i.e., able to produce any schema, within a given class of schemas, provided that a sufficiently informative input graph is presented. We identify a number of fundamental limitations that preclude feasible inference. We present inference algorithms based on natural approaches that allow to infer schemas that we argue to be of practical importance.
Cite as

Benoît Groz, Aurélien Lemay, Sławek Staworko, and Piotr Wieczorek. Inference of Shape Graphs for Graph Databases. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{groz_et_al:LIPIcs.ICDT.2022.14,
  author =	{Groz, Beno\^{i}t and Lemay, Aur\'{e}lien and Staworko, S{\l}awek and Wieczorek, Piotr},
  title =	{{Inference of Shape Graphs for Graph Databases}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.14},
  URN =		{urn:nbn:de:0030-drops-158889},
  doi =		{10.4230/LIPIcs.ICDT.2022.14},
  annote =	{Keywords: RDF, Schema, Inference, Learning, Fitting, Minimality, Containment}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2016.12
Filtering With the Crowd: CrowdScreen Revisited

Authors: Benoit Groz, Ezra Levin, Isaac Meilijson, and Tova Milo

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract
Filtering a set of items, based on a set of properties that can be verified by humans, is a common application of CrowdSourcing. When the workers are error-prone, each item is presented to multiple users, to limit the probability of misclassification. Since the Crowd is a relatively expensive resource, minimizing the number of questions per item may naturally result in big savings. Several algorithms to address this minimization problem have been presented in the CrowdScreen framework by Parameswaran et al. However, those algorithms do not scale well and therefore cannot be used in scenarios where high accuracy is required in spite of high user error rates. The goal of this paper is thus to devise algorithms that can cope with such situations. To achieve this, we provide new theoretical insights to the problem, then use them to develop a new efficient algorithm. We also propose novel optimizations for the algorithms of CrowdScreen that improve their scalability. We complement our theoretical study by an experimental evaluation of the algorithms on a large set of synthetic parameters as well as real-life crowdsourcing scenarios, demonstrating the advantages of our solution.
Cite as

Benoit Groz, Ezra Levin, Isaac Meilijson, and Tova Milo. Filtering With the Crowd: CrowdScreen Revisited. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{groz_et_al:LIPIcs.ICDT.2016.12,
  author =	{Groz, Benoit and Levin, Ezra and Meilijson, Isaac and Milo, Tova},
  title =	{{Filtering With the Crowd: CrowdScreen Revisited}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.12},
  URN =		{urn:nbn:de:0030-drops-57817},
  doi =		{10.4230/LIPIcs.ICDT.2016.12},
  annote =	{Keywords: CrowdSourcing, filtering, algorithms, sprt, hypothesis testing}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact