Skip to main content
SpringerLink
Log in

An Evolutionary Perspective on Approximate RDF Query Answering

  • Conference paper
Scalable Uncertainty Management (SUM 2008)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 5291))

Included in the following conference series:

Abstract

RDF is increasingly being used to represent large amounts of data on the Web. Current query evaluation strategies for RDF are inspired by databases, assuming perfect answers on finite repositories. In this paper, we focus on a query method based on evolutionary computing, which allows us to handle uncertainty, incompleteness and unsatisfiability, and deal with large datasets, all within a single conceptual framework. Our technique supports approximate answers with “anytime” behaviour. We present scalability results and next steps for improvement.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Aleman-Meza, B., Hakimpour, F., Arpinar, I., Sheth, A.: SwetoDblp ontology of computer science publications. Journal of Web Semantics 5(3), 151–155 (2007)

    Google Scholar 

  2. Banzhaf, W.: Interactive evolution. In: Handbook of Evolutionary Computation, ch. 2.10. IOP Press (1997)

    Google Scholar 

  3. Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7), 422–426 (1970)

    Article  MATH  Google Scholar 

  4. Boncz, P., Manegold, S., Kersten, M.L.: Database architecture optimized for the new bottleneck: Memory access. In: Proceedings of the International Conference on Very Large Data Bases (VLDB), pp. 54–65 (1999)

    Google Scholar 

  5. Broder, A., Mitzenmacher, M.: Network applications of Bloom filters: A survey. Internet Mathematics 1, 485–509 (2005)

    MathSciNet  Google Scholar 

  6. Broekstra, J., Kampman, A., van Harmelen, F.: Sesame: A generic architecture for storing and querying RDF and RDF Schema. In: Horrocks, I., Hendler, J. (eds.) ISWC 2002. LNCS, vol. 2342, pp. 54–68. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  7. Cantú-Paz, E.: A survey of parallel genetic algorithms. Calculateurs Paralleles, Reseaux et Systemes Repartis 10(2), 141–171 (1998)

    Google Scholar 

  8. Craenen, B., Eiben, A., Marchiori, E.: Solving constraint satisfaction problems with heuristic-based evolutionary algorithms. In: Proceedings of the Congress on Evolutionary Computation, pp. 1571–1577 (2000)

    Google Scholar 

  9. Deutsch, P., Gailly, J.-L.: ZLIB compressed data format specification v3.3. RFC 1950 (1996)

    Google Scholar 

  10. Ding, L., Finin, T.: Characterizing the Semantic Web on the web. In: Cruz, I., Decker, S., Allemang, D., Preist, C., Schwabe, D., Mika, P., Uschold, M., Aroyo, L.M. (eds.) ISWC 2006. LNCS, vol. 4273. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  11. Dolog, P., Stuckenschmidt, H., Wache, H., Diederich, J.: Relaxing RDF queries based on user and domain preferences. Journal on Intelligent Information Systems (2008)

    Google Scholar 

  12. Eiben, A.E., van der Hauw, J.K.: Adaptive penalties for evolutionary graph coloring. In: Proceedings of the European Conference on Artificial Evolution, pp. 95–108 (1997)

    Google Scholar 

  13. Eiben, A.E., van Hemert, J.I., Marchiori, E., Steenbeek, A.G.: Solving binary constraint satisfaction problems using evolutionary algorithms with an adaptive fitness function. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 201–210. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  14. Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Springer, Berlin (2003)

    MATH  Google Scholar 

  15. Fensel, D., van Harmelen, F., Andersson, B., et al.: Towards LarKC: a platform for web-scale reasoning. In: Proceedings of the International Conference on Semantic Computing (2008)

    Google Scholar 

  16. Gaasterland, T., Godfrey, P., Minker, J.: An overview of cooperative answering. Journal on Intelligent Information Systems 1(2), 123–157 (1992)

    Article  Google Scholar 

  17. Harth, A., Decker, S.: Optimized index structures for querying RDF from the web. In: Proceedings of the Latin-American Web Congress (LA-Web), pp. 71–80 (2005)

    Google Scholar 

  18. Harth, A., Umbrich, J., Hogan, A., Decker, S.: YARS2: A federated repository for querying graph structured data from the web. In: Aberer, K., Choi, K.-S., Noy, N., Allemang, D., Lee, K.-I., Nixon, L., Golbeck, J., Mika, P., Maynard, D., Mizoguchi, R., Schreiber, G., Cudré-Mauroux, P. (eds.) ASWC 2007 and ISWC 2007. LNCS, vol. 4825, Springer, Heidelberg (2007)

    Google Scholar 

  19. He, J., Yu, X.: Conditions for the convergence of evolutionary algorithms. Journal of Systems Architecture 47(7), 601–612 (2001)

    Article  Google Scholar 

  20. Heinz, S., Zobel, J., Williams, H.E.: Burst tries: A fast, efficient data structure for string keys. ACM Transactions on Information Systems 20(2), 192–223 (2002)

    Article  Google Scholar 

  21. Hurtado, C.A., Poulovassilis, A., Wood, P.T.: Query relaxation in RDF. Journal on Data Semantics 10, 31–61 (2008)

    Article  Google Scholar 

  22. Klyne, G., Carroll, J.J. (eds.): Resource Description Framework: Concepts and Abstract Syntax. W3C Recommendation (2004)

    Google Scholar 

  23. Muñoz, S., Pérez, J., Gutierrez, C.: Minimal deductive systems for RDF. In: Franconi, E., Kifer, M., May, W. (eds.) ESWC 2007. LNCS, vol. 4519. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  24. Oren, E., Delbru, R., Catasta, M., Cyganiak, R., et al.: Sindice.com: A document-oriented lookup index for open linked data. International Journal of Metadata, Semantics and Ontologies 3(1) (to appear, 2008a)

    Google Scholar 

  25. Oren, E., Guéret, C., Schlobach, S.: Anytime query answering in RDF through evolutionary algorithms. In: Proceedings of the International Semantic Web Conference (ISWC) (to appear, 2008b)

    Google Scholar 

  26. Pérez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. In: Cruz, I., Decker, S., Allemang, D., Preist, C., Schwabe, D., Mika, P., Uschold, M., Aroyo, L.M. (eds.) ISWC 2006. LNCS, vol. 4273. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  27. Prud’hommeaux, E., Seaborne, A. (eds.): SPARQL Query Language for RDF. W3C Recommendation (2007)

    Google Scholar 

  28. Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., et al.: Chord: A scalable peer-to-peer lookup service for internet applications. SIGCOMM Comput. Commun. Rev. 31(4), 149–160 (2001)

    Article  Google Scholar 

  29. Teytaud, O., Gelly, S.: General lower bounds for evolutionary algorithms. In: Parallel Problem Solving from Nature, pp. 21–32. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  30. Zobel, J., Heinz, S., Williams, H.E.: In-memory hash tables for accumulating text vocabularies. Information Processing Letters 80(6), 271–277 (2001)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Vrije Universiteit Amsterdam, de Boelelaan 1081a, Amsterdam, The Netherlands

    Christophe Guéret, Eyal Oren, Stefan Schlobach & Martijn Schut

Authors
  1. Christophe Guéret
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eyal Oren
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stefan Schlobach
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Martijn Schut
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. DEIS, Univ. della Calabria, 87036, Rende, Italy

    Sergio Greco

  2. Computing Laboratory, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK

    Thomas Lukasiewicz

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Guéret, C., Oren, E., Schlobach, S., Schut, M. (2008). An Evolutionary Perspective on Approximate RDF Query Answering. In: Greco, S., Lukasiewicz, T. (eds) Scalable Uncertainty Management. SUM 2008. Lecture Notes in Computer Science(), vol 5291. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87993-0_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-87993-0_18

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-87992-3

  • Online ISBN: 978-3-540-87993-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation