Publication
Title
Providing concise database covers instantly by recursive tile sampling
Author
Abstract
Known pattern discovery algorithms for finding tilings (covers of 0/1-databases consisting of 1-rectangles) cannot be integrated in instant and interactive KD tools, because they do not satisfy at least one of two key requirements: a) to provide results within a short response time of only a few seconds and b) to return a concise set of patterns with only a few elements that nevertheless covers a large fraction of the input database. In this paper we present a novel randomized algorithm that works well under these requirements. It is based on the recursive application of a simple tile sample procedure that can be implemented efficiently using rejection sampling. While, as we analyse, the theoretical solution distribution can be weak in the worst case, the approach performs very well in practice and outperforms previous sampling as well as deterministic algorithms.
Language
English
Source (journal)
Lecture notes in computer science. - Berlin, 1973, currens
Source (book)
17th International Conference on Discovery Science (DS), OCT 08-10, 2014, Bled, SLOVENIA
Publication
Berlin : Springer-verlag berlin, 2014
ISBN
978-3-319-11812-3
Volume/pages
8777(2014), p. 216-227
ISI
000360154800019
Number
978-3-319-11811-6
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 05.10.2015
Last edited 13.08.2017
To cite this reference