A theory of inductive query answering

Luc De Raedt, Manfred Jaeger, Sau Dan Lee, Heikki Mannila

    Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

    2 Citations (Scopus)

    Abstract

    We introduce the Boolean inductive query evaluation problem, which is concerned with answering inductive queries that are arbitrary Boolean expressions over monotonic and anti-monotonic predicates. Boolean inductive queries can be used to address many problems in data mining and machine learning, such as local pattern mining and concept-learning, and actually provides a unifying view on many machine learning and data mining tasks. Secondly, we develop a decomposition theory for inductive query evaluation in which a Boolean query Q is reformulated into k sub-queries that are the conjunction of a monotonic and an anti-monotonic predicate. The solution to each sub-query can be represented using a version space.We investigate how the number of version spaces k needed to answer the query can be minimized and define this as the dimension of the solution space and query. Thirdly, we generalize the notion of version spaces to cover Boolean queries, so that the solution sets form a closed Boolean-algebraic space under the usual set operations. The effects of these set operations on the dimension of the involved queries are studied.

    Original languageEnglish
    Title of host publicationInductive Databases and Constraint-Based Data Mining
    PublisherSpringer New York
    Pages79-103
    Number of pages25
    ISBN (Print)9781441977373
    DOIs
    Publication statusPublished - 2010
    MoE publication typeA3 Part of a book or another research book

    Fingerprint

    Dive into the research topics of 'A theory of inductive query answering'. Together they form a unique fingerprint.

    Cite this