The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSciOnDemand powered search:

HistogramBased Compression of Databases and Data Cubes
Abstract
Histograms have been extensively studied and applied in the context of Selectivity Estimation (Kooi, 1980; Muralikrishna & DeWitt, 1998; PiatetskyShapiro et al., 1984; Poosala et al., 1996; Poosala, 1997), and are effectively implemented in commercial systems (e.g., Oracle Database, IBM DB2 Universal Database, Microsoft SQL Server) to query optimization purposes. In statistical databases (Malvestuto, 1993; Shoshani, 1997), histograms represent a method for approximating probability distributions. They have also been used in data mining activities, intrusion detection systems, scientific databases, that is, in all those applications which (i) operate on huge numbers of detailed records, (ii) extract useful knowledge only from condensed information consisting of summary data, (iii) but are not usually concerned with detailed information. Indeed, histograms can reach a surprising efficiency and effectiveness in approximating the actual distributions of data starting from summarized information. This has led the research community to investigate the use of histograms in the fields of database management systems (Acharya et al., 1999; Bruno et al., 2001; Gunopulos et al., 2000; Ioannidis & Poosala, 1999; Kooi, 1980; Muralikrishna & DeWitt, 1998; PiatetskyShapiro et al., 1984; Poosala, 1997; Poosala & Ioannidis, 1997), online analytical processing (OLAP) systems (Buccafurri et al., 2003; Cuzzocrea, 2005a; Cuzzocrea & Wang, 2007; Furfaro et al., 2005; Poosala & Ganti, 1999), and data stream management systems (Guha et al., 2001; Guha et al., 2002; Thaper et al., 2002), where, specifically, compressing data is mandatory in order to obtain fast answers and manage the endless arrival of new information, as no bound can be given to the amount of information which can be received. Histograms are data structures obtained by partitioning a data distribution (or, equally, a data domain) into a number of mutually disjoint blocks, called buckets, and then storing, for each bucket, some aggregate information of the corresponding range of values, like the sum of values in that range (i.e., applying the SQL aggregate operator SUM), or the number of occurrences (i.e., applying the SQL aggregate operator COUNT), such that this information retains a certain “summarizing content.” Figure 1 shows an instance of a histogram built on a twodimensional data cube (leftside of the figure), represented as a matrix. The corresponding (twodimensional) histogram (rightside of the figure) is obtained by (i) partitioning the matrix into some rectangular buckets which do not overlap, and (ii) storing for each soobtained bucket the sum of the measure attributes it contains.
Related Content
Christine Kosmopoulos.
© 2022.
22 pages.

Melkamu Beyene, Solomon Mekonnen Tekle, Daniel Gelaw Alemneh.
© 2022.
21 pages.

Rajkumari Sofia Devi, Ch. Ibohal Singh.
© 2022.
21 pages.

Ida Fajar Priyanto.
© 2022.
16 pages.

Murtala Ismail Adakawa.
© 2022.
27 pages.

Shimelis Getu Assefa.
© 2022.
17 pages.

Angela Y. Ford, Daniel Gelaw Alemneh.
© 2022.
22 pages.


