Search

Data cube computation is one of the most essential but expensive operations in data warehousing. Previous studies have developed two major approaches, top-down versus bottom-up. The former, represented by the MultiWay Array Cube (called the MultiWay) algorithm [30], aggregates simultaneously on multiple dimensions; however, it cannot take advantage of a priori pruning [2] when computing iceberg cubes (cubes that contain only aggregate cells whose measure values satisfy a threshold, called the iceberg condition). The latter, represented by BUC [6], computes the iceberg cube bottom-up and facilitates a priori pruning. BUC explores fast sorting and partitioning techniques; however, it does not fully explore multidimensional simultaneous aggregation. In this paper, we present a new method, Star-Cubing, that integrates the strengths of the previous two algorithms and performs aggregations on multiple dimensions simultaneously. It utilizes a star-tree structure, extends the simultaneous aggregation methods, and enables the pruning of the group-bys that do not satisfy the iceberg condition. Our performance study shows that Star-Cubing is highly efficient and outperforms the previous methods. Index Terms--Data warehouse, data mining, online analytical processing (OLAP).

As OLAP engines are widely used to support multidimensional data analysis, it is desirable to support in data cubes advanced statistical measures, such as regression and filtering, in addition to the traditional simple measures such as count and average. Such new measures will allow users to model, smooth, and predict the trends and patterns of data. Existing algorithms for simple distributive and algebraic measures are inadequate for efficient computation of statistical measures in a multidimensional space. In this paper, we propose a fundamentally new class of measures, compressible measures, in order to support efficient computation of the statistical models. For compressible measures, we compress each cell into an auxiliary matrix with a size independent of the number of tuples. We can then compute the statistical measures for any data cell from the compressed data of the lower-level cells without accessing the raw data. Time- and space-efficient lossless aggregation formulae are derived for regression and filtering measures. Our analytical and experimental studies show that the resulting system, regression cube, substantially reduces the memory usage and the overall response time for statistical analysis of multidimensional data. Index Terms--Aggregation, compression, data cubes, OLAP.

Researchers propose a revolutionary design for a parallel VLSI coprocessor (CoP) which can be programmed for recurring computing elements. The main objective in the design approach was to maintain a low, fixed bandwidth interconnect to the main memory in the CoP. Processor arrays have to be scalable to high performance with little impact on the main memory if they are to have wide application. The CoP design includes an access unit with a multiple queueing system and a processor array with regularly connected processing elements. Results demonstrate high performance levels.

In this paper, we present two learning mechanisms for artificial neural networks (ANN's) that can be applied to solve classification problems with binary outputs. These mechanisms are used to reduce the number of hidden units of an ANN when trained by the cascade-correlation learning algorithm (CAS). Since CAS adds hidden units incrementally as learning proceeds, it is difficult to predict the number of hidden units required when convergence is reached. Further, learning must be restarted when the number of hidden units is larger than expected. Our key idea in this paper is to provide alternatives in the learning process and to select the best alternative dynamically based on runtime information obtained. Mixed-mode learning (MM), our first algorithm, provides alternative output matrices so that learning is extended to find one of the many one-to-many mappings instead of finding a unique one-to-one mapping. Since the objective of learning is relaxed by this transformation, the number of learning epochs can be reduced. This in turn leads to a smaller number of hidden units required for convergence. Population-based learning for ANN's (PLAN), our second algorithm, maintains alternative network configurations to select at run time promising networks to train based on error information obtained and time remaining. This dynamic scheduling avoids training possibly unpromising ANN's to completion before exploring new ones. We show the performance of these two mechanisms by applying them to solve the two-spiral problem, a two-region classification problem, and the Pima Indian Diabetes Diagnosis problem.

The general parameter method (GPM) makes processor arrays of any lower dimension by using an algorithm's uniform-recurrence description. GPM searches polynomial complexity to develop optimal designs of algorithm-specific architectures. The design depends on computation time of recurrence, completion time, load time, and drain time of the processor array. The design principle is general nonmonotonic user-specified and nonlinear function. The method is compatible with the dependency method.

In this paper we present new methods for the automated learning of heuristics in knowledge-lean applications and for finding heuristics that can be generalized to unlearned domains. These applications lack domain knowledge for credit assignment; hence, operators for composing new heuristics are generally model-free, domain independent, and syntactic in nature. The operators we have used are genetics-based; examples of which include mutation and cross-over. Learning is based on a generate-and-test paradigm that maintains a pool of competing heuristics, tests them to a limited extent, creates new ones from those that perform well in the past, and prunes poor ones from the pool. We have studied three important issues in learning better heuristics: 1) anomalies in performance evaluation, 2) rational scheduling of limited computational resources in testing candidate heuristics in single-objective as well as multiobjective learning, and 3) finding heuristics that can be generalized to unlearned domains. We show experimental results in learning better heuristics for 1) process placement for distributed-memory multicomputers, 2) node decomposition in a branch-and-bound search, 3) generation of test patterns in VLSI circuit testing, and 4) VLSI cell placement and routing. Index Terms - Branch-and-bound search, generalization, genetics-based learning, heuristics, knowledge-lean applications, performance evaluation, process mapping, resource scheduling, VLSI circuit testing, VLSI placement and routing.

In this paper, we study a learning model for designing heuristics automatically under resource constraints. We focus on improving performance related heuristic methods (HM's) in knowledge lean application domains. We assume that learning is episodic, that the performance measures of an episode are dependent only on the final state reached in evaluating the corresponding test case and are independent of the intermediate decisions and internal states, and that the aggregate performance measures of the HM's involved are independent of the order of evaluation of test cases. The learning model is based on testing a population of competing HM's for an application problem, and switches from one to another dynamically, depending on the outcome of previous tests. Its goal is to find a good HM within the resource constraints, with proper trade-off between cost and quality. It complements existing point-based machine learning models that maintain only one incumbent HM, and that test the HM extensively before switching to alternative ones. It extends existing work on classifier systems by addressing issues related to delays in feedback, scheduling of tests of HM's under limited resources, anomalies in performance evaluation, and scalability of HM's. Finally, we describe our experience in applying the learning method on five application problems.