Skip to main content
Erschienen in: Computing 12/2012

01.12.2012

Optimization of decentralized multi-way join queries over pipelined filtering services

verfasst von: Efthymia Tsamoura, Anastasios Gounaris, Yannis Manolopoulos

Erschienen in: Computing | Ausgabe 12/2012

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The capability to optimize and execute complex queries over multiple remote services (e.g., web services) is of high significance for efficient data management in large scale distributed computing infrastructures, such as those enabled by grid and cloud computing technology. In this work, we investigate the optimization of queries that involve multiple data resources, each of which is processed by non-overlapping sets of remote filtering services. The main novelty of this work is the proposal of optimization algorithms that produce an ordering of calls to services so that the query response time is minimized. The distinctive features of our work lie in the consideration of direct, heterogenous links among services and of multiple data resources. To the best of our knowledge, there is no known algorithm for this problem and the evaluation results show that the proposed algorithms can yield significant performance improvements compared to naive approaches.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
7
Note that throughout the rest of the work, the terms filters and services are used interchangeably.
 
8
Note that we restrict our search space to single linear orderings per data resource; in [9] multiple parallel such orderings are examined, which is something we plan to explore in the future.
 
9
The processing cost and the selectivity of \(S^k_{join}\) when building \(\mathcal L ^j\) are given by \(\mathbf c ^k_{join}(j)\) and \(\varvec{\sigma }^k_{join}(j)\), respectively.
 
10
Details are provided in the Appendix.
 
11
In cases where \(S_{join}^k \in \mathcal W ^j\), then \(S_{join}^k\) is also added to \(\Phi ^j\).
 
12
This is done in a way similar to the one employed during the second phase of the algorithm presented in Sect. 4
 
Literatur
1.
Zurück zum Zitat Papazoglou MP, Traverso P (2007) Service-oriented computing: state of the art and research challenges. Computer 40:38–45CrossRef Papazoglou MP, Traverso P (2007) Service-oriented computing: state of the art and research challenges. Computer 40:38–45CrossRef
2.
Zurück zum Zitat Oinn T, Greenwood M, Addis M, Alpdemir N, Ferris J, Glover K, Goble C, Goderis A, Hull D, Marvin D, Li P, Lord P, Pocock M, Senger M, Stevens R, Wipat A, Wroe C (2006) Taverna: lessons in creating a workflow environment for the life sciences. Concurr Comput Practice Experience 18(10):1067–1100CrossRef Oinn T, Greenwood M, Addis M, Alpdemir N, Ferris J, Glover K, Goble C, Goderis A, Hull D, Marvin D, Li P, Lord P, Pocock M, Senger M, Stevens R, Wipat A, Wroe C (2006) Taverna: lessons in creating a workflow environment for the life sciences. Concurr Comput Practice Experience 18(10):1067–1100CrossRef
3.
Zurück zum Zitat Taylor I, Shields M, Wang I (2004) Resource management for the Triana peer-to-peer services. In: Nabrzyski J, Schopf JM, Weglarz J (eds) Grid resource management. Kluwer Academic Publishers, Norwell, MA, pp 451–462 Taylor I, Shields M, Wang I (2004) Resource management for the Triana peer-to-peer services. In: Nabrzyski J, Schopf JM, Weglarz J (eds) Grid resource management. Kluwer Academic Publishers, Norwell, MA, pp 451–462
4.
Zurück zum Zitat Deelman E, Singh G, Su M-H, Blythe J, Gil Y, Kesselman C, Mehta G, Vahi K, Berriman GB, Good J, Laity A, Jacob JC, Katz DS (2005) Pegasus: a framework for mapping complex scientific workflows onto distributed systems. Sci Progr J 13(3):219–237 Deelman E, Singh G, Su M-H, Blythe J, Gil Y, Kesselman C, Mehta G, Vahi K, Berriman GB, Good J, Laity A, Jacob JC, Katz DS (2005) Pegasus: a framework for mapping complex scientific workflows onto distributed systems. Sci Progr J 13(3):219–237
5.
Zurück zum Zitat Antonioletti M, Atkinson MP, Baxter R, Borley A, Hong NPC, Collins B, Hardman N, Hume AC, Knox A, Jackson M, Krause A, Laws S, Magowan J, Paton NW, Pearson D, Sugden T, Watson P, Westhead M (2005) The design and implementation of grid database services in OGSA-DAI. Concurr Pract Experience 17(2–4):357–376CrossRef Antonioletti M, Atkinson MP, Baxter R, Borley A, Hong NPC, Collins B, Hardman N, Hume AC, Knox A, Jackson M, Krause A, Laws S, Magowan J, Paton NW, Pearson D, Sugden T, Watson P, Westhead M (2005) The design and implementation of grid database services in OGSA-DAI. Concurr Pract Experience 17(2–4):357–376CrossRef
6.
Zurück zum Zitat Lynden S, Mukherjee A, Hume AC, Fernandes AAA, Paton NW, Sakellariou R, Watson P (2009) The design and implementation of ogsa-dqp: A service-based distributed query processor. Future Generation Computer Systems 25(3):224–236CrossRef Lynden S, Mukherjee A, Hume AC, Fernandes AAA, Paton NW, Sakellariou R, Watson P (2009) The design and implementation of ogsa-dqp: A service-based distributed query processor. Future Generation Computer Systems 25(3):224–236CrossRef
7.
Zurück zum Zitat Craddock T, Lord P, Harwood C, Wipat A (2006) E-science tools for the genomic scale characterisation of bacterial secreted proteins. All hands meeting, pp 788–795 Craddock T, Lord P, Harwood C, Wipat A (2006) E-science tools for the genomic scale characterisation of bacterial secreted proteins. All hands meeting, pp 788–795
8.
Zurück zum Zitat Wang C, Chen M-S (1996) On the complexity of distributed query optimization. IEEE Trans Knowl Data Eng 8(4):650–662CrossRef Wang C, Chen M-S (1996) On the complexity of distributed query optimization. IEEE Trans Knowl Data Eng 8(4):650–662CrossRef
9.
Zurück zum Zitat Srivastava U, Munagala K, Widom J, Motwani R (2006) Query optimization over web services. In: Proceedings of the 32nd conference on very large databases (VLDB), pp 355–366 Srivastava U, Munagala K, Widom J, Motwani R (2006) Query optimization over web services. In: Proceedings of the 32nd conference on very large databases (VLDB), pp 355–366
10.
Zurück zum Zitat Van Den Hengel A, Dick A, Detmold H, Cichowski A, Hill R (2007) Finding camera overlap in large surveillance networks. In: Proceedings of the 8th Asian conference on computer vision, vol part I, pp 375–384 Van Den Hengel A, Dick A, Detmold H, Cichowski A, Hill R (2007) Finding camera overlap in large surveillance networks. In: Proceedings of the 8th Asian conference on computer vision, vol part I, pp 375–384
11.
Zurück zum Zitat Deshpande A, Guestrin C, Hong W, Madden S (2005) Exploiting correlated attributes in acquisitional query processing. In: Proceedings of the 21st international conference on data engineering (ICDE), pp 143–154 Deshpande A, Guestrin C, Hong W, Madden S (2005) Exploiting correlated attributes in acquisitional query processing. In: Proceedings of the 21st international conference on data engineering (ICDE), pp 143–154
12.
Zurück zum Zitat Lin W, Sun M-T, Poovendran R, Zhang Z (2010) Group event detection with a varying number of group members for video surveillance. IEEE Trans Circuits Syst Video Technol 20(8):1057–1067CrossRef Lin W, Sun M-T, Poovendran R, Zhang Z (2010) Group event detection with a varying number of group members for video surveillance. IEEE Trans Circuits Syst Video Technol 20(8):1057–1067CrossRef
13.
Zurück zum Zitat Gibbons PB, Karp B, Ke Y, Nath S, Seshan S (2003) Irisnet: an architecture for a worldwide sensor web. IEEE Pervasive Computing 2(4):22–33CrossRef Gibbons PB, Karp B, Ke Y, Nath S, Seshan S (2003) Irisnet: an architecture for a worldwide sensor web. IEEE Pervasive Computing 2(4):22–33CrossRef
14.
Zurück zum Zitat Kansal A, Nath S, Liu J, Zhao F (2007) Senseweb: an infrastructure for shared sensing. IEEE MultiMedia 14(4):8–13CrossRef Kansal A, Nath S, Liu J, Zhao F (2007) Senseweb: an infrastructure for shared sensing. IEEE MultiMedia 14(4):8–13CrossRef
15.
Zurück zum Zitat Deshpande A, Hellerstein L (2008) Flow algorithms for parallel query optimization. In: Proceedings of the 24th international conference on data engineering (ICDE), pp 754–763 Deshpande A, Hellerstein L (2008) Flow algorithms for parallel query optimization. In: Proceedings of the 24th international conference on data engineering (ICDE), pp 754–763
16.
Zurück zum Zitat Babu S, Motwani R, Munagala K, Nishizawa I, Widom J (2004) Adaptive ordering of pipelined stream filters. In: Proceedings of the 2004 ACM SIGMOD international conference on management of data, pp 407–418 Babu S, Motwani R, Munagala K, Nishizawa I, Widom J (2004) Adaptive ordering of pipelined stream filters. In: Proceedings of the 2004 ACM SIGMOD international conference on management of data, pp 407–418
17.
Zurück zum Zitat Viglas SD, Naughton JF, Burger J (2003) Maximizing the output rate of multi-way join queries over streaming information sources. In: Proceedings of the 29th international conference on very large data bases (VLDB), pp 285–296 Viglas SD, Naughton JF, Burger J (2003) Maximizing the output rate of multi-way join queries over streaming information sources. In: Proceedings of the 29th international conference on very large data bases (VLDB), pp 285–296
18.
Zurück zum Zitat Tsamoura E, Gounaris A, Manolopoulos Y (2011) Decentralized execution of linear workflows over web services. Future Gener Comput Syst 27(3):341–347CrossRef Tsamoura E, Gounaris A, Manolopoulos Y (2011) Decentralized execution of linear workflows over web services. Future Gener Comput Syst 27(3):341–347CrossRef
19.
Zurück zum Zitat Ledlie J, Gardner P, Seltzer M (2007) Network coordinates in the wild. In: Proceedings of the 4th USENIX conference on networked systems design& implementation, p 22 Ledlie J, Gardner P, Seltzer M (2007) Network coordinates in the wild. In: Proceedings of the 4th USENIX conference on networked systems design& implementation, p 22
20.
Zurück zum Zitat Bianculli D, Ghezzi C (2007) Monitoring conversational web services. In: Proceedings of the 2nd international workshop on service oriented, software engineering, pp 15–21 Bianculli D, Ghezzi C (2007) Monitoring conversational web services. In: Proceedings of the 2nd international workshop on service oriented, software engineering, pp 15–21
21.
Zurück zum Zitat Parker R, Rardin R (1984) Guaranteed performance heuristics for the bottleneck travelling salesman problem. Oper Res Lett 2(6):269–271MathSciNetMATHCrossRef Parker R, Rardin R (1984) Guaranteed performance heuristics for the bottleneck travelling salesman problem. Oper Res Lett 2(6):269–271MathSciNetMATHCrossRef
22.
Zurück zum Zitat Culler D (2003) Planetlab: an open, community driven infrastructure for experimental planetary-scale services. In: USENIX symposium on internet technologies and systems Culler D (2003) Planetlab: an open, community driven infrastructure for experimental planetary-scale services. In: USENIX symposium on internet technologies and systems
23.
Zurück zum Zitat Kossmann D (2000) The state of the art in distributed query processing. ACM Comput Surv 32(4): 422–469 Kossmann D (2000) The state of the art in distributed query processing. ACM Comput Surv 32(4): 422–469
24.
Zurück zum Zitat Krishnamurthy R, Boral H, Zaniolo C (1986) Optimization of nonrecursive queries. In: Proceedings of the 12th international conference on very large data, bases, pp 128–137 Krishnamurthy R, Boral H, Zaniolo C (1986) Optimization of nonrecursive queries. In: Proceedings of the 12th international conference on very large data, bases, pp 128–137
25.
Zurück zum Zitat Condon A, Deshpande A, Hellerstein L, Wu N (2009) Algorithms for distributional and adversarial pipelined filter ordering problems. ACM Trans Algorithm 5(2):24–34MathSciNet Condon A, Deshpande A, Hellerstein L, Wu N (2009) Algorithms for distributional and adversarial pipelined filter ordering problems. ACM Trans Algorithm 5(2):24–34MathSciNet
26.
Zurück zum Zitat Liu Z, Parthasarathy S, Ranganathan A, Yang H (2008) Generic flow algorithm for shared filter ordering problems. In: Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems (PODS), pp 79–88 Liu Z, Parthasarathy S, Ranganathan A, Yang H (2008) Generic flow algorithm for shared filter ordering problems. In: Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems (PODS), pp 79–88
27.
Zurück zum Zitat Ganguly S, Hasan W, Krishnamurthy R (1992) Query optimization for parallel execution. In: Proceedings of the 1992 ACM SIGMOD international conference on management of data, pp 9–18 Ganguly S, Hasan W, Krishnamurthy R (1992) Query optimization for parallel execution. In: Proceedings of the 1992 ACM SIGMOD international conference on management of data, pp 9–18
28.
Zurück zum Zitat Kossmann D, Stocker K (2000) Iterative dynamic programming: a new class of query optimization algorithms. ACM Trans Database Syst 25(1):43–82CrossRef Kossmann D, Stocker K (2000) Iterative dynamic programming: a new class of query optimization algorithms. ACM Trans Database Syst 25(1):43–82CrossRef
29.
Zurück zum Zitat Li J, Deshpande A, Khuller S (2009) Minimizing communication cost in distributed multi-query processing. In: Proceedings of the 21st international conference on data engineering (ICDE), pp 772–783 Li J, Deshpande A, Khuller S (2009) Minimizing communication cost in distributed multi-query processing. In: Proceedings of the 21st international conference on data engineering (ICDE), pp 772–783
Metadaten
Titel
Optimization of decentralized multi-way join queries over pipelined filtering services
verfasst von
Efthymia Tsamoura
Anastasios Gounaris
Yannis Manolopoulos
Publikationsdatum
01.12.2012
Verlag
Springer Vienna
Erschienen in
Computing / Ausgabe 12/2012
Print ISSN: 0010-485X
Elektronische ISSN: 1436-5057
DOI
https://doi.org/10.1007/s00607-012-0209-9