3 Search Results for "Roy, Amitabha"


Document
Keynote Abstract
Really Big Data: Analytics on Graphs with Trillions of Edges (Keynote Abstract)

Authors: Willy Zwaenepoel

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)


Abstract
Big graphs occur naturally in many applications, most obviously in social networks, but also in many other areas such as biology and forensics. Current approaches to processing large graphs use either supercomputers or very large clusters. In both cases the entire graph must reside in memory before it can be processed. We are pursuing an alternative approach, processing graphs from secondary storage. While this comes with a performance penalty, it makes analytics on very large graphs feasible on a small number of commodity machines. We have developed two systems, one for a single machine and one for a cluster of machines. X-Stream, the single machine solution, aims to make all secondary storage access sequential. It uses two techniques to achieve this goal, edge-centric processing and streaming partitions. Chaos, the cluster solution, starts from the observation that there is little benefit to locality when accessing data from secondary storage over a high-speed network. As a result, Chaos spreads graph data uniformly randomly over storage devices, and uses randomized access to achieve I/O balance. Chaos furthermore uses work stealing to achieve computational load balance. By using these techniques, it avoids the need for expensive partitioning during pre-processing, while still achieving good scaling behavior. With Chaos we have been able to process an 8-trillion-edge graph on 32 machines, a new milestone for graph size on a small cluster. I will describe both systems and their performance on a number of benchmarks and in comparison to state-of-the-art alternatives. This is joint work with Laurent Bindschaedler (EPFL), Jasmina Malicevic (EPFL) and Amitabha Roy (Intel Labs).

Cite as

Willy Zwaenepoel. Really Big Data: Analytics on Graphs with Trillions of Edges (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{zwaenepoel:LIPIcs.OPODIS.2016.3,
  author =	{Zwaenepoel, Willy},
  title =	{{Really Big Data: Analytics on Graphs with Trillions of Edges}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.3},
  URN =		{urn:nbn:de:0030-drops-70724},
  doi =		{10.4230/LIPIcs.OPODIS.2016.3},
  annote =	{Keywords: large graphs}
}
Document
Systems and Algorithms for Large-scale Graph Analytics (Dagstuhl Seminar 14462)

Authors: Eiko Yoneki, Amitabha Roy, and Derek Murray

Published in: Dagstuhl Reports, Volume 4, Issue 11 (2015)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14462 "Systems and Algorithms for Large-scale Graph Analytics". The seminar was a successful gathering of computer scientists from the domains of systems, algorithms, architecture and databases all of whom are interested in graph processing.

Cite as

Eiko Yoneki, Amitabha Roy, and Derek Murray. Systems and Algorithms for Large-scale Graph Analytics (Dagstuhl Seminar 14462). In Dagstuhl Reports, Volume 4, Issue 11, pp. 59-77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@Article{yoneki_et_al:DagRep.4.11.59,
  author =	{Yoneki, Eiko and Roy, Amitabha and Murray, Derek},
  title =	{{Systems and Algorithms for Large-scale Graph Analytics (Dagstuhl Seminar 14462)}},
  pages =	{59--77},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{11},
  editor =	{Yoneki, Eiko and Roy, Amitabha and Murray, Derek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.11.59},
  URN =		{urn:nbn:de:0030-drops-49700},
  doi =		{10.4230/DagRep.4.11.59},
  annote =	{Keywords: Large-scale graph processing, Graph structured data, Database, Graph algorithms, Parallel I/O, Parallel programming, Storage, Distributed systems, GPU}
}
Document
Uniqueness of Optimal Mod 3 Circuits for Parity

Authors: Frederic Green and Amitabha Roy

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)


Abstract
We prove that the quadratic polynomials modulo $3$ with the largest correlation with parity are unique up to permutation of variables and constant factors. As a consequence of our result, we completely characterize the smallest MAJ~$circ mbox{MOD}_3 circ { m AND}_2$ circuits that compute parity, where a MAJ~$circ mbox{MOD}_3 circ { m AND}_2$ circuit is one that has a majority gate as output, a middle layer of MOD$_3$ gates and a bottom layer of AND gates of fan-in $2$. We also prove that the sub-optimal circuits exhibit a stepped behavior: any sub-optimal circuits of this class that compute parity must have size at least a factor of $frac{2}{sqrt{3}}$ times the optimal size. This verifies, for the special case of $m=3$, two conjectures made by Due~{n}ez, Miller, Roy and Straubing (Journal of Number Theory, 2006) for general MAJ~$circ mathrm{MOD}_m circ { m AND}_2$ circuits for any odd $m$. The correlation and circuit bounds are obtained by studying the associated exponential sums, based on some of the techniques developed by Green (JCSS, 2004). We regard this as a step towards obtaining tighter bounds both for the $m ot = 3$ quadratic case as well as for higher degrees.

Cite as

Frederic Green and Amitabha Roy. Uniqueness of Optimal Mod 3 Circuits for Parity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{green_et_al:DagSemProc.07411.7,
  author =	{Green, Frederic and Roy, Amitabha},
  title =	{{Uniqueness of Optimal Mod 3 Circuits  for Parity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.7},
  URN =		{urn:nbn:de:0030-drops-13059},
  doi =		{10.4230/DagSemProc.07411.7},
  annote =	{Keywords: Circuit complexity, correlations, exponential sums}
}
  • Refine by Author
  • 2 Roy, Amitabha
  • 1 Green, Frederic
  • 1 Murray, Derek
  • 1 Yoneki, Eiko
  • 1 Zwaenepoel, Willy

  • Refine by Classification

  • Refine by Keyword
  • 1 Circuit complexity
  • 1 Database
  • 1 Distributed systems
  • 1 GPU
  • 1 Graph algorithms
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2008
  • 1 2015
  • 1 2017

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