@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 {14579,
	title = {A SIMD solution to the sequence comparison problem on the MGAP},
	booktitle = {International Conference on Application Specific Array Processors, 1994. Proceedings},
	year = {1994},
	month = {1994/08/22/24},
	pages = {336 - 345},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Molecular biologists frequently compare an unknown biosequence with a set of other known biosequences to find the sequence which is maximally similar, with the hope that what is true of one sequence, either physically or functionally, could be true of its analogue. Even though efficient dynamic programming algorithms exist for the problem, when the size of the database is large, the time required is quite long, even for moderate length sequences. In this paper, we present an efficient pipelined SIMD solution to the sequence alignment problem on the Micro-Grain Array Processor (MGAP), a fine-grained massively parallel array of processors with nearest-neighbor connections. The algorithm compares K sequences of length O(M) with the actual sequence of length N, in O(M+N+K) time with O(MN) processors, which is AT-optimal. The implementation on the MGAP computes at the rate of about 0.1 million comparisons per second for sequences of length 128},
	keywords = {AT-optimal algorithm, Biological information theory, biology computing, biosequence comparison problem, computational complexity, Computer science, Costs, database size, Databases, DNA computing, dynamic programming, dynamic programming algorithms, fine-grained massively parallel processor array, Genetics, Heuristic algorithms, maximally similar sequence, MGAP parallel computer, Micro-Grain Array Processor, Military computing, molecular biology, molecular biophysics, Nearest neighbor searches, nearest-neighbor connections, Parallel algorithms, pipeline processing, pipelined SIMD solution, sequence alignment problem, sequences},
	isbn = {0-8186-6517-3},
	doi = {10.1109/ASAP.1994.331791},
	author = {Borah,M. and Bajwa,R. S and Hannenhalli, Sridhar and Irwin,M. J}
}
@article {16768,
	title = {A pipeline N-way join algorithm based on the 2-way semijoin program},
	journal = {IEEE Transactions on Knowledge and Data Engineering},
	volume = {3},
	year = {1991},
	month = {1991/12//},
	pages = {486 - 495},
	abstract = {The semijoin has been used as an effective operator in reducing data transmission and processing over a network that allows forward size reduction of relations and intermediate results generated during the processing of a distributed query. The authors propose a relational operator, two-way semijoin, which enhanced the semijoin with backward size reduction capability for more cost-effective query processing. A pipeline N-way join algorithm for joining the reduced relations residing on N sites is introduced. The main advantage of this algorithm is that it eliminates the need for transferring and storing intermediate results among the sites. A set of experiments showing that the proposed algorithm outperforms all known conventional join algorithms that generate intermediate results is included},
	keywords = {2-way semijoin program, backward size reduction, Bandwidth, Computer networks, Costs, Data communication, data transmission, Database systems, database theory, Delay, distributed databases, distributed query, forward size reduction, intermediate results, Local area networks, network, Parallel algorithms, pipeline N-way join algorithm, pipeline processing, Pipelines, programming theory, Query processing, Relational databases, relational operator, SITES, Workstations},
	isbn = {1041-4347},
	doi = {10.1109/69.109109},
	author = {Roussopoulos, Nick and Kang,H.}
}
