Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Fast Subsumption Between Rooted Labeled Trees
verfasst von : Olivier Carloni
Erschienen in: Knowledge Science, Engineering and Management
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
This paper presents two data structures designed to efficiently query a set of rooted labeled trees (forest) defined in a language based on a relational vocabulary \(\varSigma \) and provided with a set-theoretic semantics and a subsumption relation matching the existential conjunctive fragment of the description logic \(\mathcal {ALC}\). Given a tree query with q nodes and a forest with n nodes, after showing the equivalence between subsumption and homomorphism, an \(O(q \cdot n)\) algorithm is proposed to compute all homomorphisms/subsumptions from the query to the forest. Then, are presented the two search data structures for faster homomorphism/subsumption retrieval. The first one provides a query time of O(q) for a structure size of \(O(2^n)\); and the second one provides a trade-off between the query time of \(O(k^2 \cdot q)\) and the structure size of \(O(k^2\cdot |\varSigma | \cdot 2^{\lceil n/k \rceil })\), for a fixed integer k.