14988396
Exploring the energy-time tradeoff in high-performance computing
High-performance computing is and has always been performance oriented. However, a consequence of the push towards maximum performance is increased energy consumption, especially at supercomputing centers. Moreover, as peak performance is rarely attained, some of this energy consumption results in little or no performance gain. In addition, large energy consumption costs the government a significant amount of money and wastes natural resources. This paper investigates the tradeoff between energy and performance. Through the use of processors that support frequency and voltage scaling, we measured the performance and energy consumption of programs from three popular benchmark sets. We took multiple measurements for each program using different frequency and voltage settings. Results show that for many programs, a significant decrease in energy is possible with a small increase in time. We believe that this justifies further investigation into parallel HPC (e.g., MPI) applications.
108674
Sample Selection for Maximal Diversity
The problem of selecting a sample subset sufficient to preserve diversity arises in many applications. One example is in the design of recombinant inbred lines (RIL) for genetic association studies. In this context, genetic diversity is measured by how many alleles are retained in the resulting inbred strains. RIL panels that are derived from more than two parental strains, such as the collaborative cross (Churchill et al., 2004), present a particular challenge with regard to which of the many existing lab mouse strains should be included in the initial breeding funnel in order to maximize allele retention. A similar problem occurs in the study of customer reviews when selecting a subset of products with a maximal diversity in reviews. Diversity in this case implies the presence of a set of products having both positive and negative ranks for each customer. In this paper, we demonstrate that selecting an optimal diversity subset is an NP-complete problem via reduction to set cover. This reduction is sufficiently tight that greedy approximations to the set cover problem directly apply to maximizing diversity. We then suggest a slightly modified subset selection problem in which an initial greedy diversity solution is used to effectively prune an exhaustive search for all diversity subsets bounded from below by a specified coverage threshold. Extensive experiments on real datasets are performed to demonstrate the effectiveness and efficiency of our approach.
11841640
Accelerating Profile Queries in Elevation Maps
Elevation maps are a widely used spatial data representation in geographical information systems (GIS). Paths on elevation maps can be characterized by profiles, which describe relative elevation as a function of distance. In this research, we address the inverse of this mapping - given a profile, how to efficiently find paths that could have generated it. This is called the profile query problem. Profiles have a wide variety of uses that include registering tracking information, or even other maps, to a given map. We describe a probabilistic model to characterize the maximal likelihood that a point lying on a path matches the query profile. Propagation of such probabilities to neighboring points can effectively prune the search space. This model enables us to efficiently answer queries of arbitrary profiles with user-specified error tolerances. When compared to existing spatial index methods, our approach supports more flexible queries with orders of magnitude speedup.
2768791
Finding representative set from massive data
In the information age, data is pervasive. In some applications, data explosion is a significant phenomenon. The massive data volume poses challenges to both human users and computers. In this project, we propose a new model for identifying representative set from a large database. A representative set is a special subset of the original dataset, which has three main characteristics: It is significantly smaller in size compared to the original dataset. It captures the most information from the original dataset compared to other subsets of the same size. It has low redundancy among the representatives it contains. We use information-theoretic measures such as mutual information and relative entropy to measure the representativeness of the representative set. We first design a greedy algorithm and then present a heuristic algorithm that delivers much better performance. We run experiments on two real datasets and evaluate the effectiveness of our representative set in terms of coverage and accuracy. The experiments show that our representative set attains expected characteristics and captures information more efficiently.
268487
Mining non-redundant high order correlations in binary data
Many approaches have been proposed to find correlations in binary data. Usually, these methods focus on pair-wise correlations. In biology applications, it is important to find correlations that involve more than just two features. Moreover, a set of strongly correlated features should be non-redundant in the sense that the correlation is strong only when all the interacting features are considered together. Removing any feature will greatly reduce the correlation.In this paper, we explore the problem of finding non-redundant high order correlations in binary data. The high order correlations are formalized using multi-information, a generalization of pairwise mutual information. To reduce the redundancy, we require any subset of a strongly correlated feature subset to be weakly correlated. Such feature subsets are referred to as Non-redundant Interacting Feature Subsets (NIFS). Finding all NIFSs is computationally challenging, because in addition to enumerating feature combinations, we also need to check all their subsets for redundancy. We study several properties of NIFSs and show that these properties are useful in developing efficient algorithms. We further develop two sets of upper and lower bounds on the correlations, which can be incorporated in the algorithm to prune the search space. A simple and effective pruning strategy based on pair-wise mutual information is also developed to further prune the search space. The efficiency and effectiveness of our approach are demonstrated through extensive experiments on synthetic and real-life datasets.
765245
CARE: Finding Local Linear Correlations in High Dimensional Data
Finding latent patterns in high dimensional data is an important research problem with numerous applications. Existing approaches can be summarized into 3 categories: feature selection, feature transformation (or feature projection) and projected clustering. Being widely used in many applications, these methods aim to capture global patterns and are typically performed in the full feature space. In many emerging biomedical applications, however, scientists are interested in the local latent patterns held by feature subsets, which may be invisible via any global transformation. In this paper, we investigate the problem of finding local linear correlations in high dimensional data. Our goal is to find the latent pattern structures that may exist only in some subspaces. We formalize this problem as finding strongly correlated feature subsets which are supported by a large portion of the data points. Due to the combinatorial nature of the problem and lack of monotonicity of the correlation measurement, it is prohibitively expensive to exhaustively explore the whole search space. In our algorithm, CARE, we utilize spectrum properties and effective heuristic to prune the search space. Extensive experimental results show that our approach is effective in finding local linear correlations that may not be identified by existing methods.
18214781
Fast mode decision algorithm for intraprediction in H.264/AVC video coding
The H.264/AVC video coding standard aims to enable significantly improved compression performance compared to all existing video coding standards. In order to achieve this, a robust rate-distortion optimization (RDO) technique is employed to select the best coding mode and reference frame for each macroblock. As a result, the complexity and computation load increase drastically. This paper presents a fast mode decision algorithm for H.264/AVC intraprediction based on local edge information. Prior to intraprediction, an edge map is created and a local edge direction histogram is then established for each subblock. Based on the distribution of the edge direction histogram, only a small part of intraprediction modes are chosen for RDO calculation. Experimental results show that the fast intraprediction mode decision scheme increases the speed of intracoding significantly with negligible loss of peak signal-to-noise ratio.
41075889
Efficient Compression of Multi-view Video Using Hierarchical B Pictures
3D and free viewpoint video are new types of natural video media that expand the user's sensation far beyond what is offered by traditional media. As video compression is a key issue in traditional video communications and the use of multi video streams makes it even more important for such applications. In this paper, we presented an investigation of the multi- view video coding structures with focus on exploiting hierarchical B pictures. We demonstrate hierarchical B pictures prediction structures, and present the advantage of several multi-view video coding prediction schemes. This demonstration will show the benefits of using hierarchical B pictures based on H.264/AVC. The simulation results demonstrate that the objective quality can be improved with the advanced MVC prediction structures in comparison to the simulcast coding structures.
22420647
Adaptive intra-frame quantization for very low bit rate video coding
This paper presents, for I-frames, a generic relationship among the quantization value, data bits, and their spatial complexity. This relationship provides a mechanism to select the quantization value for an I-frame (with different spatial complexity) at given bit budget before actually encoding it. Therefore it helps to adaptively distribute the bit budget among I-, P- and B-frames in a sequence. Experiments show that the adaptive intra frame quantization algorithm reduces the number of frame skippings significantly with comparable average PSNRs, and thus improves the overall subjective quality of the reconstructed video.
35879153
Fast Rate-Distortion Optimization in H.264/AVC Video Coding
One of the new features in the H.264/AVC encoder is the use of Lagrangian Rate-Distortion Optimised (RDO) mode decision at the macroblock (MB) level. This brute-force algorithm searches through the 10 different MB coding modes to obtain the best one for encoding that MB, and is hence computationally expensive. This paper proposes a novel algorithm where the RDO can be reorganized in a better order such that the most likely MB modes will be tried first, and an early termination of the RDO process will be used once the calculated rate-distortion cost (RDcost) is below a preset threshold. The preset threshold is dependent on the RDcost of previous and neighbouring MBs that have been coded. This is based on the observation that the RDcost of an MB in the current frame is highly correlated to a co-located MB in the previous frame. Experimental results have shown that the new algorithm has dramatically reduced the encoding times of up to 61.8%, with negligible increases in bit-rates or PSNR.
7351167
Fast intermode decision in H.264/AVC video coding
The new video coding standard, H.264/MPEG-4 AVC, uses variable block sizes ranging from 4/spl times/4 to 16/spl times/16 in interframe coding. This new feature has achieved significant coding gain compared to coding a macroblock (MB) using fixed block size. However, this feature results in extremely high computational complexity when brute force rate distortion optimization (RDO) algorithm is used. This paper proposes a fast intermode decision algorithm to decide the best mode in intercoding. It makes use of the spatial homogeneity and the temporal stationarity characteristics of video objects. Specifically, spatial homogeneity of a MB is decided based on the MB's edge intensity, and temporal stationarity is decided by the difference of the current MB and it colocated counterpart in the reference frame. Based on the homogeneity and stationarity of the video objects, only a small number of intermodes are selected in the RDO process. The experimental results show that the fast intermode decision algorithm is able to reduce on the average 30% encoding time, with a negligible peak signal-to-noise ratio loss of 0.03 dB or, equivalently, a bit rate increment of 0.6%.