Name
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's users. Experiments show that our algorithms realize near-optimal network utilization with minor computational overhead. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/ICDE.2008.4497467 | ICDE |
Keywords | Field | DocType |
long-haul path,network-aware join processing,reduce resource usage,network path,global-scale database federations,network utilization,skyquery federation,global-scale database federation,balanced network utilization,parallel schedules,astronomy databases,polynomial-time algorithm,excess capacity,near-optimal network utilization,query processing,spatial-join queries,join scheduling algorithms,polynomials,optimization,computer networks,schedules,astronomy,user experience,scheduling algorithm,concurrent computing,dynamic programming,clustering algorithms,throughput,databases | Hash join,Data mining,Overhead (computing),Dynamic programming,Scheduling (computing),Computer science,Sort-merge join,Schedule,Concurrent computing,Throughput,Database,Distributed computing | Conference |
ISSN | ISBN | Citations |
1084-4627 | 978-1-4244-1837-4 | 13 |
PageRank | References | Authors |
0.71 | 33 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaodan Wang | 1 | 326 | 32.31 |
| Randal Burns | 2 | 1955 | 115.15 |
| Andreas Terzis | 3 | 2449 | 169.59 |
| Amol Deshpande | 4 | 4085 | 258.89 |