source: liacs/dbdm/dbdm_5/report.tex@ 71

\documentclass{report}

\title{Databases and Data Mining --- Assignment 5}
\author{Rick van der Zwet}


\begin{document}
\newcommand{\question}[2]{\begin{quotation}\noindent{\Large``}#1. #2{\Large''}\end{quotation}}
\maketitle

\question{1a}{Propose an algorithm, in pseudo-code, for the following: The automatic
generation of a concept hierarchy for numerical data based on the equal-width
partitioning rule.}

\question{1b}{Propose an algorithm, in pseudo-code, for the following: The automatic
generation of a concept hierarchy for numerical data based on the equal-frequency
partitioning rule.}

\question{2}{Suppose that a data warehouse consists of four dimensions,
    date, spectator, location, and game, and two measures, count, and charge, where
    charge is the fare that a spectator pays when watching a game on a given date.
    Spectators may be students, adults, or seniors, with each category having its own
    charge rate.}
\question{2a}{Draw a star schema diagram for the data warehouse.}
\question{2b}{Starting with the base cuboid [date, spectator, location, game], what specific
        OLAP operations should one perform in order to list the total charge paid by
        student spectators at GM\_Place 2004?}
\question{2c}{Bitmap indexing is useful in data warehousing. Taking this cube as an example,
        briefly discuss advantages and problems of using a bitmap index structure.}

\question{3}{A data cube, C, has n dimensions, and each dimension
    has exactly p distinct values in the base cuboid. Assume that there are no concept
    hierarchies associated with the dimensions. What is the maximum number of cells
    possible (including both base cells and aggregate cells) in the data cube, C?}

\question{4}{The Apriori algorithm uses prior knowledge of subset support properties.}
\question{4a}{Prove that all nonempty subsets of a frequent itemset must also be frequent.}
\question{4b}{Given frequent itemset l and subset s of l, prove that the confidence of the rule “s’
         => (l-s’)” cannot be more than the confidence of the rule “s => (l – s)” where s’
         is a subset of s.}
\question{5}{An optimization in frequent item set mining is mining closed patterns, or mining max
    patterns instead. Describe the main differences of mining closed patterns and mining
    max patterns.}

\question{6}{The price of each item in a store is nonnegative. For
each of the following cases, identify the kinds of constraint they represent (e.g.
antimonotonic, monotonic, succinct) and briefly discuss how to mine such association
rules efficiently:}

\question{6a}{Containing one free item and other items the sum of whose prices is at least \$190.}
\question{6b}{Where the average price of all the items is between \$120 and \$520.}

\question{7}{Suppose a city has installed hundreds of surveillance cameras at strategic locations in
busy streets. All the captured video (each stream being 640 pixels x 480 pixels, 24-
bits (RGB) per pixel, 25fps) is streamed to a central observation post in real time.
Describe an efficient system that would allow real time data mining and continuously
querying these video streams for abnormal events, such as explosions, people in
panic, etc.. Also discuss the computational costs and the memory requirements of
your system.}
\question{8}{A flight data warehouse for a travel agent consists of six
dimensions: traveler, departure (city), departure\_time, arrival (city), arrival\_time,
and flight; and two measures count, and avg\_fare, where avg\_fare stores the concrete
fare at the lowest level but the average fare at the other levels. Suppose the cube is
fully materialized. Starting with the base cuboid [traveler, departure, departure\_time,
arrival, arrival\_time, flight], what specific OLAP operations (e.g roll-up flight to
airline, etc.) should one perform in order to list the average fare per month for each
business traveler who flies American Airlines (AA) from Los Angeles (LA) in the
year 2007?}
\question{9}{In graph mining what would be the advantage of the described apriori-based approach
over the pattern growth based approach (see lecture slides) and vice versa.}

\bibliography{report}

\end{document}