Imprecise RDQL: towards generic retrieval in ontologies using similarity joins

ABSTRACT

Traditional semantic web query languages support a logic-based access to the semantic web. They offer a retrieval (or reasoning) of data based on facts. On the traditional web and in databases, however, exact querying often provides an incomplete answer as queries are overspecified or the mix of multiple ontologies/modelling differences requires "interpretational flexibility." Therefore, similarity measures or ranking approaches are frequently used to extend the reach of a query. This paper extends this idea to the semantic web. It introduces iRDQL---a semantic web query language with support for similarity joins. It is an extension of traditional RDQL (RDF Data Query Language) that enables the users to query for similar resources ranking the results using a similarity measure. We show how iRDQL allows to extend the reach of a query by finding additional results. We quantitatively evaluated four similarity measures for their usefulness in iRDQL in the context of an OWL-S semantic web service retrieval test collection and compared the results to a specialized OWL-S matchmaker. Initial results of iRDQL indicate that it is indeed useful for extending the reach of queries and that it is able to improve recall without overly sacrificing precision. We also found that our generic iRDQL approach was only slightly outperformed by the specialized algorithm.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: A. Bernstein, E. Kaufmann, C. Bürki, and M. Klein. How Similar Is It? Towards Personalized Similarity Measures in Ontologies. In 7. Internationale Tagung Wirtschaftsinformatik, February 2005.
• 3: A. Bernstein, E. Kaufmann, and C. Kiefer. SimPack: A Generic Java Library for Similarity Measures in Ontologies. Technical report, University of Zurich, Department of Informatics. http://www.ifi.unizh.ch/ddis/staff/goehring/btw/files/ddis-2005.01.pdf, 2005.
• 4: Alexander Borgida , Ronald J. Brachman , Deborah L. McGuinness , Lori Alperin Resnick, CLASSIC: a structural data model for objects, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.58-67, June 1989, Portland, Oregon, United States
• 5: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 6: J. J. Carroll, I. Dickinson, C. Dollin, D. Reynolds, A. Seaborne, and K. Wilkinson. Jena: Implementing the Semantic Web Recommendations. Technical report, HP Labs, 2003.
• 7: William W. Cohen, Data integration using similarity joins and a word-based information representation language, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.288-321, July 2000 [doi>10.1145/352595.352598]
• 8: D. Gentner and J. Medina. Similarity and the Development of Rules. Cognition, 65:263--297, 1998.
• 9: M. Klusch. OWLS-TC-v1: OWL-S Service Retrieval Test Collection. http://projects.semwebcentral.org/projects/owls-tc/, 2005.
• 10: M. Klusch, B. Fries, M. Khalid, and K. Sycara. OWLS-MX: Hybrid Semantic Web Service Retrieval. Arlington, VA, USA, 2005.
• 11: V. I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady, 10:707--710, 1966.
• 12: J. Lin. Divergence Measures Based on the Shannon Entropy. IEEE Transactions on Information Theory, 37(1):145--151, 1991.
• 13: P. W. Lord, R. D. Stevens, A. Brass, and C. A. Goble. Investigating semantic similarity measures across the gene ontology: the relationship between sequence and annotation. Bioinformatics, 19(10):1275--83, 2003.
• 14: D. Martin, M. Burstein, J. Hobbs, O. Lassila, D. McDermott, S. McIlraith, S. Narayanan, M. Paolucci, B. Parsia, T. Payne, E. Sirin, N. Srinivasan, and K. Sycara. OWL-S: Semantic Markup for Web Services. http://www.w3.org/Submission/OWL-S/, November 2004.
• 15: Tommaso Di Noia , Eugenio Di Sciascio , Francesco M. Donini , Marina Mongiello, A system for principled matchmaking in an electronic marketplace, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775198]
• 16: E. Prud'hommeaux and A. Seaborne. SPARQL Query Language for RDF. http://www.w3.org/TR/rdf-sparql-query/, 2005.
• 17: RDF Core Working Group. RDF Primer. http://www.w3.org/TR/rdf-primer/, 2004.
• 18: H J Schek , M H Scholl, The relational model with relation-valued attributes, Information Systems, v.11 n.2, p.137-147, 1986 [doi>10.1016/0306-4379(86)90003-7]
• 19: A. Seaborne. Jena Tutorial--A Programmer's Introduction to RDQL. http://jena.sourceforge.net/tutorial/RDQL/, 2004.
• 20: A. Seaborne. RDQL--A Query Language for RDF. http://www.w3.org/Submission/RDQL/, 2004.
• 21: Ellen M. Voorhees, Query expansion using lexical-semantic relations, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.61-69, July 03-06, 1994, Dublin, Ireland

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Keywords:
RDQL, evaluation, imprecise queries, information retrieval, matchmaking, semantic web, service matchmaking, similarity, similarity joins, similarity measures