Abstract
We study the problem of evaluating conjunctive queries composed of triple patterns over RDF data stored in distributed hash tables. Our goal is to develop algorithms that scale to large amounts of RDF data, distribute the query processing load evenly and incur little network traffic. We present and evaluate two novel query processing algorithms with these possibly conflicting goals in mind. We discuss the various tradeoffs that occur in our setting through a detailed experimental evaluation of the proposed algorithms.
This work was supported in part by the European Commission project Ontogrid (http://www.ontogrid.net/).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aberer, K.: P-Grid: A Self-Organizing Access Structure for P2P Information Systems. In: Batini, C., Giunchiglia, F., Giorgini, P., Mecella, M. (eds.) CoopIS 2001. LNCS, vol. 2172. Springer, Heidelberg (2001)
Aberer, K., Alima, L.O., Ghodsi, A., Girdzijauskas, S., Hauswirth, M., Haridi, S.: The essence of P2P: A reference architecture for overlay networks. In: IEEE P2P 2005 (2005)
Aberer, K., Cudré-Mauroux, P., Hauswirth, M.: Start making sense: The chatty web approach for global semantic agreements. Journal of Web Semantics 1(1) (December 2003)
Aberer, K., Cudre-Mauroux, P., Hauswirth, M., Pelt, T.V.: GridVine: Building Internet-Scale Semantic Overlay Networks. In: WWW 2004 (2004)
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Bawa, M., Gionis, A., Garcia-Molina, H., Motwani, R.: The Price of Validity in Dynamic Networks. In: SIGMOD 2004 (2004)
Bernstein, P.A., Giunchiglia, F., Kementsietsidis, A., Mylopoulos, J., Serafini, L., Zaihrayeu, I.: Data Management for Peer-to-Peer Computing: A Vision. In: WebDB 2002 (2002)
Cai, M., Frank, M., Szekely, J.C.P.: MAAN: A Multi-Attribute Addressable Network for Grid Information Services. In: Grid 2003 (2003)
Cai, M., Frank, M.R., Yan, B., MacGregor, R.M.: A Subscribable Peer-to-Peer RDF Repository for Distributed Metadata Management. Journal of Web Semantics 2(2), 109–130 (2004)
Fikes, R., Hayes, P., Horrocks, I.: OWL-QL: A Language for Deductive Query Answering on the Semantic Web. Journal of Web Semantics 2(1), 19–29 (2004)
Gribble, S., Halevy, A., Ives, Z., Rodrig, M., Suciu, D.: What Can Peer-to-Peer Do for Databases, and Vice Versa. In: WebDB 2001 (2001)
Huebsch, R., Hellerstein, J.M., Lanham, N., Loo, B.T., Shenker, S., Stoica, I.: Querying the Internet with PIER. In: Aberer, K., Koubarakis, M., Kalogeraki, V. (eds.) VLDB 2003. LNCS, vol. 2944. Springer, Heidelberg (2003)
Idreos, S.: Distributed evaluation of continuous equi-join queries over large structured overlay networks. Master’s thesis (2005)
Idreos, S., Tryfonopoulos, C., Koubarakis, M.: Distributed Evaluation of Continuous Equi-join Queries over Large Structured Overlay Networks. In: ICDE 2006 (2006)
Kaoudi, Z., Miliaraki, I., Magiridou, M., Papadakis-Pesaresi, A., Koubarakis, M.: Storing and querying RDF data in Atlas. In: Demo Papers ESWC 2006 (2006)
Karger, D., Ruhl, M.: Simple Efficient Load Balancing Algorithms for Peer to Peer Systems. In: SPAA 2004 (2004)
Karvounarakis, G., Alexaki, S., Christophides, V., Plexousakis, D., Scholl, M.: RQL: A Declarative Query Language for RDF. In: WWW 2002 (2002)
Liarou, E., Idreos, S., Koubarakis, M.: Publish/Subscribe with RDF Data over Large Structured Overlay Networks. In: Moro, G., Bergamaschi, S., Joseph, S., Morin, J.-H., Ouksel, A.M. (eds.) DBISP2P 2005 and DBISP2P 2006. LNCS, vol. 4125, pp. 135–146. Springer, Heidelberg (2007)
Nejdl, W., Wolf, B., Qu, C., Decker, S., Sintek, M., Naeve, A., Nilsson, M., Palmer, M., Risch, T.: EDUTELLA: A P2P Networking Infrastructure Based on RDF. In: WWW 2002 (2002)
Nejdl, W., Wolpers, M., Siberski, W., Schmitz, C., Schlosser, M., Brunkhorst, I., Loser, A.: Super-Peer-Based Routing and Clustering Strategies for RDF-Based Peer-To-Peer Networks. In: WWW 2003 (2003)
Prud’hommeaux, E., Seaborn, A.: SPARQL Query Language for RDF (2005), http://www.w3.org/TR/rdf-sparql-query/
Seaborne, A.: Rdql - a query language for RDF. W3C Member Submission (2004)
Staab, S., Stuckenschmidt, H.: Semantic Web and Peer-to-Peer. Springer, Heidelberg (2006)
Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for internet applications. In: SIGCOMM 2001 (2001)
Stuckenschmidt, H., Vdovjak, R., Broekstra, J., Houben, G.-J.: Towards Distributed Processing of RDF Path Queries. International Journal of Web Engineering and Technology 2(2/3), 207–230 (2005)
Tryfonopoulos, C., Idreos, S., Koubarakis, M.: LibraRing: An Architecture for Distributed Digital Libraries Based on DHTs. In: Rauber, A., Christodoulakis, S., Tjoa, A.M. (eds.) ECDL 2005. LNCS, vol. 3652. Springer, Heidelberg (2005)
Tryfonopoulos, C., Idreos, S., Koubarakis, M.: Publish/Subscribe Functionality in IR Environments using Structured Overlay Networks. In: SIGIR 2005 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liarou, E., Idreos, S., Koubarakis, M. (2006). Evaluating Conjunctive Triple Pattern Queries over Large Structured Overlay Networks. In: Cruz, I., et al. The Semantic Web - ISWC 2006. ISWC 2006. Lecture Notes in Computer Science, vol 4273. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11926078_29
Download citation
DOI: https://doi.org/10.1007/11926078_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49029-6
Online ISBN: 978-3-540-49055-5
eBook Packages: Computer ScienceComputer Science (R0)