Ordering, Indexing, and Searching Semantic Data: A Terminology Aware Index Structure

description logics;semantic data;semantic web;indexing;search;Computer Science

Pound, Jeffrey

University of Waterloo

关键词: description logics;    semantic data;    semantic web;    indexing;    search;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/3686/1/thesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Indexing data for efficient search capabilities is a core problem in many domains of computer science.As applications centered around semantic data sources become more common, the need for moresophisticated indexing and querying capabilities arises. In particular, the need to search forspecific information in the presence of a terminology or ontology (i.e. a set of logic based rules that describe concepts and their relations) becomes of particular importance, as the information a user seeks may exists as an entailment of the explicit data by means of the terminology. This varianton traditional indexing and search problems forms the foundation of a range of possible technologiesfor semantic data.In this work, we propose an ordering language for specifying partial orders over semantic data itemsmodeled as descriptions in a description logic. We then show how these orderings can be used as the basis of a search tree index for processing emph{concept searches} in the presence of a terminology. We study in detail the properties of the orderings and the associated index structure, and also explore a relationship between ordering descriptions called emph{order refinement}. A sound and complete procedure for deciding refinement is given. We also empirically evaluate a prototype implementation of our index structure, validating its potential efficacy in semantic query problems.