NDLI: Bottom-up computation of sparse and Iceberg CUBE

Content Provider	ACM Digital Library
Author	Ramakrishnan, Raghu Beyer, Kevin
Abstract	We introduce the Iceberg-CUBE problem as a reformulation of the datacube (CUBE) problem. The Iceberg-CUBE problem is to compute only those group-by partitions with an aggregate value (e.g., count) above some minimum support threshold. The result of Iceberg-CUBE can be used (1) to answer group-by queries with a clause such as HAVING COUNT(*) >= X, where X is greater than the threshold, (2) for mining multidimensional association rules, and (3) to complement existing strategies for identifying interesting subsets of the CUBE for precomputation.We present a new algorithm (BUC) for Iceberg-CUBE computation. BUC builds the CUBE bottom-up; i.e., it builds the CUBE by starting from a group-by on a single attribute, then a group-by on a pair of attributes, then a group-by on three attributes, and so on. This is the opposite of all techniques proposed earlier for computing the CUBE, and has an important practical advantage: BUC avoids computing the larger group-bys that do not meet minimum support. The pruning in BUC is similar to the pruning in the Apriori algorithm for association rules, except that BUC trades some pruning for locality of reference and reduced memory requirements. BUC uses the same pruning strategy when computing sparse, complete CUBEs.We present a thorough performance evaluation over a broad range of workloads. Our evaluation demonstrates that (in contrast to earlier assumptions) minimizing the aggregations or the number of sorts is not the most important aspect of the sparse CUBE problem. The pruning in BUC, combined with an efficient sort method, enables BUC to outperform all previous algorithms for sparse CUBEs, even for computing entire CUBEs, and to dramatically improve Iceberg-CUBE computation.
Starting Page	359
Ending Page	370
Page Count	12
File Format	PDF
ISSN	01635808
DOI	10.1145/304181.304214
Journal	ACM SIGMOD Record (SGMD)
Volume Number	28
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1999-06-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bottom-up computation of sparse and Iceberg CUBE

Bottom-Up Computation of Sparse and Iceberg CUBEs (1999)

Bottom-up computation of sparse and Iceberg CUBE (1999)

Iceberg-cube computation with PC clusters

Abstract Bottom-Up Computation of Sparse and Iceberg CUBEs

PnP: sequential, external memory, and parallel iceberg cube computation

Star-cubing: Computing iceberg cubes by top-down and bottom-up integration (2003)

Star-cubing: Computing iceberg cubes by top-down and bottom-up integration (2003)

Star-Cubing: Computing Iceberg Cubes by Top-Down And Bottom-Up Integration (2003)

Bottom-up computation of sparse and Iceberg CUBE

Similar Documents

Bottom-up computation of sparse and Iceberg CUBE

Bottom-Up Computation of Sparse and Iceberg CUBEs (1999)

Bottom-up computation of sparse and Iceberg CUBE (1999)

Iceberg-cube computation with PC clusters

Abstract Bottom-Up Computation of Sparse and Iceberg CUBEs

PnP: sequential, external memory, and parallel iceberg cube computation

Star-cubing: Computing iceberg cubes by top-down and bottom-up integration (2003)

Star-cubing: Computing iceberg cubes by top-down and bottom-up integration (2003)

Star-Cubing: Computing Iceberg Cubes by Top-Down And Bottom-Up Integration (2003)

Bottom-up computation of sparse and Iceberg CUBE