2 Search Results for "Zaniolo, Carlo"


Document
Declarative Algorithms in Datalog with Extrema: Their Formal Semantics Simplified

Authors: Carlo Zaniolo, Mohan Yang, Matteo Interlandi, Ariyam Das, Alexander Shkapsky, and Tyson Condie

Published in: OASIcs, Volume 64, Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)


Abstract
Recent advances are making possible the use of aggregates in recursive queries thus enabling the declarative expression classic algorithms and their efficient and scalable implementation. These advances rely the notion of Pre-Mappability (PreM) of constraints that, along with the seminaive-fixpoint operational semantics, guarantees formal non-monotonic semantics for recursive programs with min and max constraints. In this extended abstract, we introduce basic templates to simplify and automate task of proving PreM.

Cite as

Carlo Zaniolo, Mohan Yang, Matteo Interlandi, Ariyam Das, Alexander Shkapsky, and Tyson Condie. Declarative Algorithms in Datalog with Extrema: Their Formal Semantics Simplified. In Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018). Open Access Series in Informatics (OASIcs), Volume 64, pp. 9:1-9:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{zaniolo_et_al:OASIcs.ICLP.2018.9,
  author =	{Zaniolo, Carlo and Yang, Mohan and Interlandi, Matteo and Das, Ariyam and Shkapsky, Alexander and Condie, Tyson},
  title =	{{Declarative Algorithms in Datalog with Extrema: Their Formal Semantics Simplified}},
  booktitle =	{Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)},
  pages =	{9:1--9:3},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-090-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{64},
  editor =	{Dal Palu', Alessandro and Tarau, Paul and Saeedloei, Neda and Fodor, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2018.9},
  URN =		{urn:nbn:de:0030-drops-98758},
  doi =		{10.4230/OASIcs.ICLP.2018.9},
  annote =	{Keywords: Recursive Queries}
}
Document
An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits

Authors: Vladimir Braverman, Jonathan Katzman, Charles Seidell, and Gregory Vorsanger

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)


Abstract
In this paper, we provide the first optimal algorithm for the remaining open question from the seminal paper of Alon, Matias, and Szegedy: approximating large frequency moments. We give an upper bound on the space required to find a k-th frequency moment of O(n^(1-2/k)) bits that matches, up to a constant factor, the lower bound of Woodruff et. al for constant epsilon and constant k. Our algorithm makes a single pass over the stream and works for any constant k > 3. It is based upon two major technical accomplishments: first, we provide an optimal algorithm for finding the heavy elements in a stream; and second, we provide a technique using Martingale Sketches which gives an optimal reduction of the large frequency moment problem to the all heavy elements problem. We also provide a polylogarithmic improvement for frequency moments, frequency based functions, spatial data streams, and measuring independence of data sets.

Cite as

Vladimir Braverman, Jonathan Katzman, Charles Seidell, and Gregory Vorsanger. An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 531-544, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.APPROX-RANDOM.2014.531,
  author =	{Braverman, Vladimir and Katzman, Jonathan and Seidell, Charles and Vorsanger, Gregory},
  title =	{{An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{531--544},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.531},
  URN =		{urn:nbn:de:0030-drops-47217},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.531},
  annote =	{Keywords: Streaming Algorithms, Randomized Algorithms, Frequency Moments, Heavy Hitters}
}
  • Refine by Author
  • 1 Braverman, Vladimir
  • 1 Condie, Tyson
  • 1 Das, Ariyam
  • 1 Interlandi, Matteo
  • 1 Katzman, Jonathan
  • Show More...

  • Refine by Classification
  • 1 Information systems → Query languages

  • Refine by Keyword
  • 1 Frequency Moments
  • 1 Heavy Hitters
  • 1 Randomized Algorithms
  • 1 Recursive Queries
  • 1 Streaming Algorithms

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2014
  • 1 2018

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