@conference {13369,
	title = {Flow Algorithms for Parallel Query Optimization},
	booktitle = {IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008},
	year = {2008},
	month = {2008/04/07/12},
	pages = {754 - 763},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We address the problem of minimizing the response time of a multi-way join query using pipelined (inter-operator) parallelism, in a parallel or a distributed environment. We observe that in order to fully exploit the parallelism in the system, we must consider a new class of ";interleaving"; plans, where multiple query plans are used simultaneously to minimize the response time of a query (or to maximize the tuple-throughput of the system). We cast the query planning problem in this environment as a ";flow maximization problem";, and present polynomial-time algorithms that (statically) find the optimal set of plans to use for a given query, for a large class of multi-way join queries. Our proposed algorithms also naturally extend to query optimization over web services. Finally we present an extensive experimental evaluation that demonstrates both the need to consider such plans in parallel query processing and the effectiveness of our algorithms.},
	keywords = {Casting, computational complexity, Cost function, Databases, Delay, distributed environment, Educational institutions, flow maximization algorithm, Interleaved codes, interoperator parallelism, minimisation, multiway join query response time minimization problem, parallel database, Parallel databases, parallel query optimization, Partitioning algorithms, pipeline processing, pipelined parallelism, polynomial-time algorithm, query planning problem, Query processing, Web service, Web services},
	isbn = {978-1-4244-1836-7},
	doi = {10.1109/ICDE.2008.4497484},
	author = {Deshpande, Amol and Hellerstein,L.}
}
@conference {13389,
	title = {Network-Aware Join Processing in Global-Scale Database Federations},
	booktitle = {IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008},
	year = {2008},
	month = {2008/04/07/12},
	pages = {586 - 595},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We introduce join scheduling algorithms that employ a balanced network utilization metric to optimize the use of all network paths in a global-scale database federation. This metric allows algorithms to exploit excess capacity in the network, while avoiding narrow, long-haul paths. We give a two- approximate, polynomial-time algorithm for serial (left-deep) join schedules. We also present extensions to this algorithm that explore parallel schedules, reduce resource usage, and define tradeoffs between computation and network utilization. We evaluate these techniques within the SkyQuery federation of Astronomy databases using spatial-join queries submitted by SkyQuery{\textquoteright}s users. Experiments show that our algorithms realize near-optimal network utilization with minor computational overhead.},
	keywords = {Astronomy, Computer networks, Concurrent computing, global-scale database federations, join scheduling algorithms, network utilization, network-aware join processing, parallel schedules, polynomial-time algorithm, Polynomials, Processor scheduling, Query processing, reduce resource usage, Scheduling algorithm, Spatial databases, spatial-join queries, Telecommunication traffic, Throughput},
	isbn = {978-1-4244-1836-7},
	doi = {10.1109/ICDE.2008.4497467},
	author = {Xiaodan Wang and Burns,R. and Terzis,A. and Deshpande, Amol}
}
@conference {14563,
	title = {Algorithmic graph minor theory: Decomposition, approximation, and coloring},
	booktitle = {Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on},
	year = {2005},
	month = {2005///},
	pages = {637 - 646},
	abstract = {At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.},
	keywords = {algorithmic graph minor theory, approximation algorithm, combinatorial polylogarithmic approximation, computational complexity, constant-factor approximation, graph algorithm, graph coloring, graph colouring, half-integral multicommodity flow, largest grid minor, maximization problem, minimization problem, polynomial-time algorithm, subexponential fixed-parameter algorithm, topological graph theory, treewidth},
	doi = {10.1109/SFCS.2005.14},
	author = {Demaine,E. D and Hajiaghayi, Mohammad T. and Kawarabayashi,K.}
}
