• English
  • Deutsch
  • Log In
    Password Login
    Research Outputs
    Fundings & Projects
    Researchers
    Institutes
    Statistics
Repository logo
Fraunhofer-Gesellschaft
  1. Home
  2. Fraunhofer-Gesellschaft
  3. Konferenzschrift
  4. Providing concise database covers instantly by recursive tile sampling
 
  • Details
  • Full
Options
2014
Conference Paper
Title

Providing concise database covers instantly by recursive tile sampling

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.
Author(s)
Moens, S.
Boley, Mario  
Goethals, B.
Mainwork
Discovery science. 17th international conference, DS 2014  
Conference
International Conference on Discovery Science (DS) 2014  
International Conference on Algorithmic Learning Theory (ALT) 2014  
DOI
10.1007/978-3-319-11812-3_19
Language
English
Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS  
  • Cookie settings
  • Imprint
  • Privacy policy
  • Api
  • Contact
© 2024