Dimitris Fotakis

Prof. Dimitris Fotakis

Computer Science Division, School of Electrical and Computer Engineering, National Technical University of Athens, 9, Iroon Polytechniou str., 15780 Athens, Greece
orcid

Research Focus & Metrics

Academic Career Length

31Years (1996-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 December 2005 in Theoretical Computer Science
Verified
Journal Article
Closed access
Dimitris FotakisDimitris Fotakis
Dimitris Fotakis
Spyros KontogiannisSpyros Kontogiannis
Spyros Kontogiannis
PSPaul Spirakis
Paul Spirakis

13 December 2004 in Theory of Computing Systems
Verified
Journal Article
Closed access
PDF file
Dimitris FotakisDimitris Fotakis
Dimitris Fotakis
RPRasmus Pagh
Rasmus Pagh
PSPeter Sanders
Peter Sanders
PSPaul Spirakis
Paul Spirakis

25 June 2002
Verified
Book Chapter
Closed access
PDF file
Dimitris FotakisDimitris Fotakis
Dimitris Fotakis
Spyros KontogiannisSpyros Kontogiannis
Spyros Kontogiannis
EKElias Koutsoupias
Elias Koutsoupias
MMMarios Mavronicolas
Marios Mavronicolas
PSPaul Spirakis
Paul Spirakis

1 April 2013
Verified
Conference Paper
Closed access
FAFoto N. Afrati
Foto N. Afrati
Dimitris FotakisDimitris Fotakis
Dimitris Fotakis
JUJeffrey D. Ullman
Jeffrey D. Ullman
The theme of this paper is how to find all instances of a given “sample” graph in a larger “data graph,” using a single round of map-reduce. For the simplest sample graph, the triangle, we improve upon the best known such algorithm. We then examine the general case, considering both the communication cost between mappers and reducers and the total computation cost at the reducers. To minimize communication cost, we exploit the techniques of [1] for computing multiway joins (evaluating conjunctive queries) in a single map-reduce round. Several methods are shown for translating sample graphs into a union of conjunctive queries with as few queries as possible. We also address the matter of optimizing computation cost. Many serial algorithms are shown to be “convertible,” in the sense that it is possible to partition the data graph, explore each partition in a separate reducer, and have the total computation cost at the reducers be of the same order as the computation cost of the serial algorithm.

24 October 2007 in Algorithmica
Verified
Journal Article
Closed access
PDF file
Dimitris FotakisDimitris Fotakis
Dimitris Fotakis

1 August 2009 in Theoretical Computer Science
Verified
Journal Article
Closed access
Dimitris FotakisDimitris Fotakis
Dimitris Fotakis
Spyros KontogiannisSpyros Kontogiannis
Spyros Kontogiannis
EKElias Koutsoupias
Elias Koutsoupias
MMMarios Mavronicolas
Marios Mavronicolas
PSPaul Spirakis
Paul Spirakis