Title
Providing concise database covers instantly by recursive tile samplingProviding concise database covers instantly by recursive tile sampling
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Research group
Advanced Database Research and Modeling (ADReM)
Publication type
conferenceObject
Publication
Berlin :Springer-verlag berlin,
Subject
Engineering sciences. Technology
Computer. Automation
Source (journal)
DISCOVERY SCIENCE, DS 2014
Source (book)
17th International Conference on Discovery Science (DS), OCT 08-10, 2014, Bled, SLOVENIA
Volume/pages
8777(2014), p. 216-227
ISSN
0302-9743
ISBN
978-3-319-11812-3
ISI
000360154800019
ISBN
978-3-319-11811-6
Carrier
E
Target language
English (eng)
Affiliation
University of Antwerp
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.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000360154800019&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000360154800019&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle