2 Search Results for "Zelke, Mariano"


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-dev.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
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-dev.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}
}
  • Refine by Author
  • 2 Zelke, Mariano
  • 1 Ikonomovska, Elena

  • Refine by Classification

  • Refine by Keyword
  • 1 Semi-streaming algorithm
  • 1 approximation algorithm
  • 1 graph algorithm
  • 1 group testing
  • 1 histogram
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2013

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