DROPS

Document

Algorithmic Techniques for Processing Data Streams

Authors: Elena Ikonomovska and Mariano Zelke

Published in: Dagstuhl Follow-Ups, Volume 5, Data Exchange, Integration, and Streams (2013)

Abstract

We give a survey at some algorithmic techniques for processing data streams. After covering the basic methods of sampling and sketching, we present more evolved procedures that resort on those basic ones. In particular, we examine algorithmic schemes for similarity mining, the concept of group testing, and techniques for clustering and summarizing data streams.

Cite as

Elena Ikonomovska and Mariano Zelke. Algorithmic Techniques for Processing Data Streams. In Data Exchange, Integration, and Streams. Dagstuhl Follow-Ups, Volume 5, pp. 237-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{ikonomovska_et_al:DFU.Vol5.10452.237,
  author =	{Ikonomovska, Elena and Zelke, Mariano},
  title =	{{Algorithmic Techniques for Processing Data Streams}},
  booktitle =	{Data Exchange, Integration, and Streams},
  pages =	{237--274},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-61-3},
  ISSN =	{1868-8977},
  year =	{2013},
  volume =	{5},
  editor =	{Kolaitis, Phokion G. and Lenzerini, Maurizio and Schweikardt, Nicole},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol5.10452.237},
  URN =		{urn:nbn:de:0030-drops-42968},
  doi =		{10.4230/DFU.Vol5.10452.237},
  annote =	{Keywords: streaming algorithm, sampling, sketching, group testing, histogram}
}

Document

DOI: 10.4230/LIPIcs.STACS.2008.1312

Weighted Matching in the Semi-Streaming Model

Authors: Mariano Zelke

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract

We reduce the best known approximation ratio for finding a weighted matching of a graph using a one-pass semi-streaming algorithm from 5.828 to 5.585. The semi-streaming model forbids random access to the input and restricts the memory to $mathcal{O(ncdotmbox{polylog,n)$ bits. It was introduced by Muthukrishnan in 2003 and is appropriate when dealing with massive graphs.

Cite as

Mariano Zelke. Weighted Matching in the Semi-Streaming Model. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 669-680, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{zelke:LIPIcs.STACS.2008.1312,
  author =	{Zelke, Mariano},
  title =	{{Weighted Matching in the Semi-Streaming Model}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{669--680},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1312},
  URN =		{urn:nbn:de:0030-drops-13128},
  doi =		{10.4230/LIPIcs.STACS.2008.1312},
  annote =	{Keywords: Semi-streaming algorithm, matching, approximation algorithm, graph algorithm}
}

Search Results

Documents authored by Zelke, Mariano

Algorithmic Techniques for Processing Data Streams

Abstract

Cite as

Weighted Matching in the Semi-Streaming Model

Abstract

Cite as

Thanks for your feedback!

Could not send message