Search Results

Documents authored by Łukasiewicz, Aleksander

Document
DOI: 10.4230/LIPIcs.ESA.2022.76
Cardinality Estimation Using Gumbel Distribution

Authors: Aleksander Łukasiewicz and Przemysław Uznański

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Cardinality estimation is the task of approximating the number of distinct elements in a large dataset with possibly repeating elements. LogLog and HyperLogLog (c.f. Durand and Flajolet [ESA 2003], Flajolet et al. [Discrete Math Theor. 2007]) are small space sketching schemes for cardinality estimation, which have both strong theoretical guarantees of performance and are highly effective in practice. This makes them a highly popular solution with many implementations in big-data systems (e.g. Algebird, Apache DataSketches, BigQuery, Presto and Redis). However, despite having simple and elegant formulation, both the analysis of LogLog and HyperLogLog are extremely involved - spanning over tens of pages of analytic combinatorics and complex function analysis. We propose a modification to both LogLog and HyperLogLog that replaces discrete geometric distribution with the continuous Gumbel distribution. This leads to a very short, simple and elementary analysis of estimation guarantees, and smoother behavior of the estimator.
Cite as

Aleksander Łukasiewicz and Przemysław Uznański. Cardinality Estimation Using Gumbel Distribution. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 76:1-76:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lukasiewicz_et_al:LIPIcs.ESA.2022.76,
  author =	{{\L}ukasiewicz, Aleksander and Uzna\'{n}ski, Przemys{\l}aw},
  title =	{{Cardinality Estimation Using Gumbel Distribution}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{76:1--76:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.76},
  URN =		{urn:nbn:de:0030-drops-170140},
  doi =		{10.4230/LIPIcs.ESA.2022.76},
  annote =	{Keywords: Streaming algorithms, Cardinality estimation, Sketching, Gumbel distribution}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.87
Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Authors: Alexandra Lassota, Aleksander Łukasiewicz, and Adam Polak

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. Our algorithm is actually designed to work for a more general Vector Bin Packing problem, in which items are multidimensional vectors. We improve over the previous fastest O^*(k! ⋅ 4^k) time algorithm. Our algorithm works by reducing the problem to finding an exact weight perfect matching in a (multi-)graph with O^*(2^k) edges, whose weights are integers of the order of O^*(2^k). To solve the matching problem in the desired time, we give a variant of the classic Mulmuley-Vazirani-Vazirani algorithm with only a linear dependence on the edge weights and the number of edges - which may be of independent interest. Moreover, we give a tight lower bound, under the Strong Exponential Time Hypothesis (SETH), showing that the constant 2 in the base of the exponent cannot be further improved for Vector Bin Packing. Our techniques also lead to improved algorithms for Vector Multiple Knapsack, Vector Bin Covering, and Perfect Matching with Hitting Constraints.
Cite as

Alexandra Lassota, Aleksander Łukasiewicz, and Adam Polak. Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 87:1-87:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lassota_et_al:LIPIcs.ICALP.2022.87,
  author =	{Lassota, Alexandra and {\L}ukasiewicz, Aleksander and Polak, Adam},
  title =	{{Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{87:1--87:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.87},
  URN =		{urn:nbn:de:0030-drops-164286},
  doi =		{10.4230/LIPIcs.ICALP.2022.87},
  annote =	{Keywords: Bin Packing, Vector Bin Packing, Parameterized Complexity, Matching}
}
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