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 more
sophisticated indexing and querying capabilities arises. In particular, the need to search for
specific 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 variant
on traditional indexing and search problems forms the foundation of a range of possible technologies
for semantic data.
In this work, we propose an ordering language for specifying partial orders over semantic data items
modeled 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.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/3686 |
| Date | January 2008 |
| Creators | Pound, Jeffrey |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0019 seconds