5 Search Results for "Mailler, Cécile"

Volume

LIPIcs, Volume 302

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

AofA 2024, June 17-21, 2024, University of Bath, UK

Editors: Cécile Mailler and Sebastian Wild

Document
Complete Volume
DOI: 10.4230/LIPIcs.AofA.2024
LIPIcs, Volume 302, AofA 2024, Complete Volume

Authors: Cécile Mailler and Sebastian Wild

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
LIPIcs, Volume 302, AofA 2024, Complete Volume
Cite as

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 1-458, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{mailler_et_al:LIPIcs.AofA.2024,
  title =	{{LIPIcs, Volume 302, AofA 2024, Complete Volume}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{1--458},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024},
  URN =		{urn:nbn:de:0030-drops-204341},
  doi =		{10.4230/LIPIcs.AofA.2024},
  annote =	{Keywords: LIPIcs, Volume 302, AofA 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.AofA.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Cécile Mailler and Sebastian Wild

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mailler_et_al:LIPIcs.AofA.2024.0,
  author =	{Mailler, C\'{e}cile and Wild, Sebastian},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.0},
  URN =		{urn:nbn:de:0030-drops-204353},
  doi =		{10.4230/LIPIcs.AofA.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.5
Bit-Array-Based Alternatives to HyperLogLog

Authors: Svante Janson, Jérémie Lumbroso, and Robert Sedgewick

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We present a family of algorithms for the problem of estimating the number of distinct items in an input stream that are simple to implement and are appropriate for practical applications. Our algorithms are a logical extension of the series of algorithms developed by Flajolet and his coauthors starting in 1983 that culminated in the widely used HyperLogLog algorithm. These algorithms divide the input stream into M substreams and lead to a time-accuracy tradeoff where a constant number of bits per substream are saved to achieve a relative accuracy proportional to 1/√M. Our algorithms use just one or two bits per substream. Their effectiveness is demonstrated by a proof of approximate normality, with explicit expressions for standard errors that inform parameter settings and allow proper quantitative comparisons with other methods. Hypotheses about performance are validated through experiments using a realistic input stream, with the conclusion that our algorithms are more accurate than HyperLogLog when using the same amount of memory, and they use two-thirds as much memory as HyperLogLog to achieve a given accuracy.
Cite as

Svante Janson, Jérémie Lumbroso, and Robert Sedgewick. Bit-Array-Based Alternatives to HyperLogLog. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{janson_et_al:LIPIcs.AofA.2024.5,
  author =	{Janson, Svante and Lumbroso, J\'{e}r\'{e}mie and Sedgewick, Robert},
  title =	{{Bit-Array-Based Alternatives to HyperLogLog}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.5},
  URN =		{urn:nbn:de:0030-drops-204402},
  doi =		{10.4230/LIPIcs.AofA.2024.5},
  annote =	{Keywords: Cardinality estimation, sketching, Hyperloglog}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.21
The Disordered Chinese Restaurant and Other Competing Growth Processes

Authors: Cécile Mailler, Peter Mörters, and Anna Senkevich

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
The disordered Chinese restaurant process is a partition-valued stochastic process where the elements of the partitioned set are seen as customers sitting at different tables (the sets of the partition) in a restaurant. Each table is assigned a positive number called its attractiveness. At every step a customer enters the restaurant and either joins a table with a probability proportional to the product of its attractiveness and the number of customers sitting at the table, or occupies a previously unoccupied table, which is then assigned an attractiveness drawn from a bounded distribution independently of everything else. When all attractivenesses are equal to the upper bound this process is the classical Chinese restaurant process; we show that the introduction of disorder can drastically change the behaviour of the system. Our main results are distributional limit theorems for the scaled number of customers at the busiest table, and for the ratio of occupants at the busiest and second busiest table. The limiting distributions are universal, i.e. they do not depend on the distribution of the attractiveness. They follow from two general Poisson limit theorems for a broad class of processes consisting of families growing with different rates from different birth times, which have further applications, for example to preferential attachment networks.
Cite as

Cécile Mailler, Peter Mörters, and Anna Senkevich. The Disordered Chinese Restaurant and Other Competing Growth Processes. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mailler_et_al:LIPIcs.AofA.2020.21,
  author =	{Mailler, C\'{e}cile and M\"{o}rters, Peter and Senkevich, Anna},
  title =	{{The Disordered Chinese Restaurant and Other Competing Growth Processes}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.21},
  URN =		{urn:nbn:de:0030-drops-120511},
  doi =		{10.4230/LIPIcs.AofA.2020.21},
  annote =	{Keywords: Chinese restaurant process, competing growth processes, reinforced branching processes, preferential attachment tree with fitness, Poisson processes}
}
  • Refine by Author
  • 3 Mailler, Cécile
  • 2 Wild, Sebastian
  • 1 Janson, Svante
  • 1 Lumbroso, Jérémie
  • 1 Mörters, Peter
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing
  • 2 Mathematics of computing → Discrete mathematics
  • 2 Mathematics of computing → Information theory
  • 2 Mathematics of computing → Mathematical analysis
  • 2 Mathematics of computing → Probability and statistics
  • Show More...

  • Refine by Keyword
  • 1 Cardinality estimation
  • 1 Chinese restaurant process
  • 1 Conference Organization
  • 1 Front Matter
  • 1 Hyperloglog
  • Show More...

  • Refine by Type
  • 4 document
  • 1 volume

  • Refine by Publication Year
  • 4 2024
  • 1 2020

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact