Publication
Title
Tiling databases
Author
Abstract
In this paper, we consider 0/1 databases and provide an alternative way of extracting knowledge from such databases using tiles. A tile is a region in the database consisting solely of ones. The interestingness of a tile is measured by the number of ones it consists of, i.e., its area. We present an efficient method for extracting all tiles with area at least a given threshold. A collection of tiles constitutes a tiling. We regard tilings that have a large area and consist of a small number of tiles as appealing summaries of the large database. We analyze the computational complexity of several algorithmic tasks related to finding such tilings. We develop an approximation algorithm for finding tilings which approximates the optimal solution within reasonable factors. We present a preliminary experimental evaluation on real data sets.
Language
English
Source (journal)
Lecture notes in computer science. - Berlin, 1973, currens
Publication
Berlin : 2004
ISSN
0302-9743 [print]
1611-3349 [online]
Volume/pages
3245(2004), p. 278-289
ISI
000224608200022
Full text (Publisher's DOI)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
External links
Web of Science
Record
Identification
Creation 15.04.2014
Last edited 21.11.2017