Search Results

Documents authored by Sedgewick, Robert

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/DagRep.9.1.104
Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051)

Authors: Gerth Stølting Brodal, Ulrich Carsten Meyer, Bernhard E. Nebel, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 9, Issue 1 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16101 "Data Structures for the Cloud and External Memory Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
Cite as

Gerth Stølting Brodal, Ulrich Carsten Meyer, Bernhard E. Nebel, and Robert Sedgewick. Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051). In Dagstuhl Reports, Volume 9, Issue 1, pp. 104-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.9.1.104,
  author =	{Brodal, Gerth St{\o}lting and Meyer, Ulrich Carsten and Nebel, Bernhard E. and Sedgewick, Robert},
  title =	{{Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051)}},
  pages =	{104--124},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{1},
  editor =	{Brodal, Gerth St{\o}lting and Meyer, Ulrich Carsten and Nebel, Bernhard E. and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.1.104},
  URN =		{urn:nbn:de:0030-drops-105722},
  doi =		{10.4230/DagRep.9.1.104},
  annote =	{Keywords: algorithms, big data, cloud computing, data structures, external memory methods, large data sets, web-scale}
}
Document
DOI: 10.4230/DagRep.6.3.1
Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101)

Authors: Alejandro Lopez-Ortiz, Ulrich Carsten Meyer, Markus E. Nebel, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 6, Issue 3 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16101 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
Cite as

Alejandro Lopez-Ortiz, Ulrich Carsten Meyer, Markus E. Nebel, and Robert Sedgewick. Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101). In Dagstuhl Reports, Volume 6, Issue 3, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{lopezortiz_et_al:DagRep.6.3.1,
  author =	{Lopez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Nebel, Markus E. and Sedgewick, Robert},
  title =	{{Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{3},
  editor =	{Lopez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Nebel, Markus E. and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.3.1},
  URN =		{urn:nbn:de:0030-drops-61457},
  doi =		{10.4230/DagRep.6.3.1},
  annote =	{Keywords: algorithms, big data, cloud services, data structures, external memory methods, information theory, large data sets, streaming, web-scale}
}
Document
DOI: 10.4230/DagRep.4.2.129
Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 14091)

Authors: Alejandro López-Ortiz, Ulrich Carsten Meyer, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 4, Issue 2 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14091 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
Cite as

Alejandro López-Ortiz, Ulrich Carsten Meyer, and Robert Sedgewick. Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 14091). In Dagstuhl Reports, Volume 4, Issue 2, pp. 129-149, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{lopezortiz_et_al:DagRep.4.2.129,
  author =	{L\'{o}pez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Sedgewick, Robert},
  title =	{{Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 14091)}},
  pages =	{129--149},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{2},
  editor =	{L\'{o}pez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.2.129},
  URN =		{urn:nbn:de:0030-drops-45489},
  doi =		{10.4230/DagRep.4.2.129},
  annote =	{Keywords: data structures, big data, models of computation, I/O Model, sorting, quicksort, graph algorithms, hashing, compression, succinct data structures, trajectories, text search, GPU algorithms, MapReduce}
}
Document
DOI: 10.4230/DagSemProc.08081.1
08081 Abstracts Collection – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Raimund Seidel

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)

Abstract
From February 17th to 22nd 2008, the Dagstuhl Seminar 08081 ``Data Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. It brought together 49 researchers from four continents to discuss recent developments concerning data structures in terms of research but also in terms of new technologies that impact how data can be stored, updated, and retrieved. During the seminar a fair number of participants presented their current research. There was discussion of ongoing work, and in addition an open problem session was held. This paper first describes the seminar topics and goals in general, then gives the minutes of the open problem session, and concludes with abstracts of the presentations given during the seminar. Where appropriate and available, links to extended abstracts or full papers are provided.
Cite as

Lars Arge, Robert Sedgewick, and Raimund Seidel. 08081 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.08081.1,
  author =	{Arge, Lars and Sedgewick, Robert and Seidel, Raimund},
  title =	{{08081 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.1},
  URN =		{urn:nbn:de:0030-drops-15325},
  doi =		{10.4230/DagSemProc.08081.1},
  annote =	{Keywords: Data structures, information retrieval, complexity, algorithms, flash memory}
}
Document
DOI: 10.4230/DagSemProc.06091.1
06091 Abstracts Collection – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

Abstract
From 26.02.06 to 03.03.06, the Dagstuhl Seminar 06091 ``Data Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Lars Arge, Robert Sedgewick, and Dorothea Wagner. 06091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.06091.1,
  author =	{Arge, Lars and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{06091 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.1},
  URN =		{urn:nbn:de:0030-drops-8428},
  doi =		{10.4230/DagSemProc.06091.1},
  annote =	{Keywords: Algorithms, data structures}
}
Document
DOI: 10.4230/DagSemProc.06091.2
06091 Executive Summary – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

Abstract
The Dagstuhl Seminar on Data Structures in 2006 reported on ongoing research on data structures, including randomized, cache-oblivious and succinct data structures. There was some shift of interest away from purely theoretical issues towards scientific studies that are directly relevant to practical applications. The participants were asked to think about the direction that research on data structure should take. Several presentations were provocative responses to this question. Interest in the topic remains high: another attendance record was set.
Cite as

Lars Arge, Robert Sedgewick, and Dorothea Wagner. 06091 Executive Summary – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.06091.2,
  author =	{Arge, Lars and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{06091 Executive Summary – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.2},
  URN =		{urn:nbn:de:0030-drops-8411},
  doi =		{10.4230/DagSemProc.06091.2},
  annote =	{Keywords: algorithms, data structures}
}
Document
DOI: 10.4230/DagSemProc.04091.1
04091 Abstracts Collection – Data Structures

Authors: Susanne Albers, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 4091, Data Structures (2005)

Abstract
From 22.02. to 27.02.2004, Dagstuhl Seminar "Data Structures" was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar are put together in this paper. The first section describes the seminar topics and goals in general.
Cite as

Susanne Albers, Robert Sedgewick, and Dorothea Wagner. 04091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 4091, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.04091.1,
  author =	{Albers, Susanne and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{04091 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4091},
  editor =	{Susanne Albers and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04091.1},
  URN =		{urn:nbn:de:0030-drops-1758},
  doi =		{10.4230/DagSemProc.04091.1},
  annote =	{Keywords: Cache oblivious algorithms , cell probe model , computational geometry , data compression , dictionaries , finger search , hashing , heaps I/O efficiency , lower bounds}
}
Document
DOI: 10.4230/DagSemRep.335
Data Structures (Dagstuhl Seminar 02091)

Authors: Susanne Albers, Robert Sedgewick, and Peter Widmayer

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Susanne Albers, Robert Sedgewick, and Peter Widmayer. Data Structures (Dagstuhl Seminar 02091). Dagstuhl Seminar Report 335, pp. 1-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{albers_et_al:DagSemRep.335,
  author =	{Albers, Susanne and Sedgewick, Robert and Widmayer, Peter},
  title =	{{Data Structures (Dagstuhl Seminar 02091)}},
  pages =	{1--36},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{335},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.335},
  URN =		{urn:nbn:de:0030-drops-152176},
  doi =		{10.4230/DagSemRep.335},
}
Document
DOI: 10.4230/DagSemRep.119
`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9527)

Authors: Philippe Flajolet, Rainer Kemp, Helmut Prodinger, and Robert Sedgewick

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Philippe Flajolet, Rainer Kemp, Helmut Prodinger, and Robert Sedgewick. `Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9527). Dagstuhl Seminar Report 119, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1996)

Copy BibTex To Clipboard

@TechReport{flajolet_et_al:DagSemRep.119,
  author =	{Flajolet, Philippe and Kemp, Rainer and Prodinger, Helmut and Sedgewick, Robert},
  title =	{{`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9527)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{1996},
  type = 	{Dagstuhl Seminar Report},
  number =	{119},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.119},
  URN =		{urn:nbn:de:0030-drops-150079},
  doi =		{10.4230/DagSemRep.119},
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact