Summary: We describe efficient algorithms for adaptive multi-scale approximation of functions that are sampled with non-uniform density and / or have important small-scale details limited to small regions of your domain. Our algorithms are very general, independent of the shape of the domain, the mesh, and the approximation base. A multi-scale base is generically defined as a hierarchy of uni-scale bases, whose elements have progressively smaller supports and are arranged more densely in the domain. An adaptive multiscale base is a subset of a complete base, which excludes elements that contribute very little to the approximation. We tested our algorithms with a Bézier heraldic finite element base in regular triangular meshes. Tests show that the size of the adaptive base can be 1/100 the size of a complete uni-scale base with the same spatial resolution, resulting in huge savings in computing time. (Previous versions of these algorithms were described in the PhD thesis of the first author.)
Abstract: We describe efficient algorithms for adaptive multiscale approximation of functions that are sampled with uneven density and / or have important small-scale detail limited to small portions of their domain. Our algorithms are very general, independent of domain shape, mesh, and approximation basis. A full multiscale basis is defined generically as a hierarchy of single-scale bases, whose elements have progressively smaller supports and are arranged more densely over the domain. An adaptive multiscale basis is a subset of a full one, that excludes elements that contribute very little to the approximation. We tested our algorithms with a hierarchical basis of finite Bézier elements on regular triangular meshes. The tests show that the size of the adaptive basis can be about 1/100 of the size of a full single-scale basis of the same spatial resolution, leading to enormos savings in computation time. (Earlier versions of these algorithms were described in the Ph. D. Thesis of the first author.).
Summary: Phylogeny of Images it is the problem of reconstructing the structure that represents the history of generating semantically similar images, for example, duplicate-close images. Typical image phylogeny algorithms divide the problem into two steps: estimating the dissimilarity between each pair of images, and reconstructing the phylogenetic structure. Given that the calculation of dissimilarity directly impacts the reconstruction of phylogeny, we propose new approaches to the standard formulation of the calculation of dissimilarity in Image Phylogeny, seeking to improve the effectiveness in estimating the history of relationships between duplicate-close images. This new formulation explores different families of color adjustment functions, local gradients and mutual information such as dissimilarity. The results obtained with this new formulation surpass the existing methods in the literature, allowing a better analysis of kinship relationships in a set of images, which enables better solutions taking advantage of phylogeny, in problems such as copyright control and problems in forensic analysis of digital documents.
Abstract: Image Phylogeny is the problem of reconstructing the structure that represents the history of generation of semantically similar images (eg, near-duplicate images). Typical Image Phylogeny approaches break the problem into two steps: the estimation of the dissimilarity between each pair of images, and the current reconstruction of the phylogeny structure. Given that the dissimilarity calculation directly impacts the phylogeny reconstruction, we propose new approaches to the standard dissimilarity calculation formulation in image phylogeny, aiming at improving the accuracy when estimating the historical relationships between near-duplicates. The new formulations explore a different family of color adjustment, local gradient, and mutual information processes. The obtained results with the new formulations remarkably outperform the existing counterparts in the literature allowing a much better analysis of the parenthood relationships in a set of images better enabling the deployment of phylogeny solutions to tackle traitor tracing, copyright enforcement, and digital forensics problems.
Summary: We present an efficient algorithm for multivariate approximation by weighted least squares in the presence of outliers (anomalous data). The algorithm iteratively builds a self-consistent probabilistic interpretation of the data; specifically, the mean and variance of the two populations (inliers and outliers), the approximation adjusted by least squares, and the probability that each point is an inlier. An original feature of this algorithm is that, at each iteration, it adjusts the sampled values given according to the estimated probabilities, before recalculating the least squares approximation. This approach is more efficient than the most obvious alternative of including the probabilities in the least squares system matrix. The convergence of the method is demonstrated by empirical theses.
Abstract: We describe an efficient algorithm for robust multivariate weighted least squares approximation in the presence of outliers. The algorithm iteratively constructs a self-consistent probabilistic interpretation of the data; specifically, the mean and variance of the two populations (inliers and outliers), the least squares fitted approximation, and the probability that each data point is an inlier. An original feature of this algorithm is that, at each iteration, it adjusts the given sampled values according to the estimated probabilities, before re-computing the least squares approximation. This approach is more efficient than the most obvious alternative of including the probabilities in the matrix of the least squares system. The convergence of the method is demonstrated with empirical tests.
Summary: This technical report contains summaries of 21 papers presented at X Workshop of Thesis, Dissertations and Scientific Initiation Work in Progress (WTD), from the Computing Institute (IC) of the State University of Campinas (Unicamp) in 2015. The Workshop it took place on the 3rd and 4th of August 2015 and had more than 250 participants, including listeners, presenters of work and organizers. On the occasion there were 27 oral presentations and 8 posters. Students were given the possibility to choose the form of presentation (oral, poster, or both), as well as to choose whether to publish their work in the proceedings of the event. The publication of abstracts, in the form of a technical report, aims to disseminate the work in progress and record, in a succinct way, the state of the art of the research of the Institute of Computing in 2015.
Abstract: Software Product Lines (SPLs) are emerging techniques where several artifacts are reused (domain), and some are customized (variation points). An SPL can bind variation points statically (compilation time) or dynamically (runtime). Dynamic Software Product Lines (DSPLs) use dynamic bind to adapt to the environment or requirements changes. DSPLs are commonly used to build dependable systems, defined as systems with the ability to avoid service failures more frequent or severe than is acceptable. Main dependability attributes are availability, confidentiality, integrity, reliability, maintainability, and safety. To better understand this context, a Systematic Mapping Study (SMS) was applied searching proposals that include dependability attributes in DSPLs. Our results suggest that few studies handle dependability in DSPL context. We selected only nine primary studies in this context. Also, four of them provide explicit support for SOA and were analyzed as a secondary result.
Abstract: Many applications today rely on multiple services, whose results are combined to form the application's response. In such contexts, the most unreliable service and the slowest service determine the application's reliability and response time, respectively. State-machine replication and atomic broadcast are fundamental abstractions to build highly available services. In this paper, we consider the latency variability of atomic broadcast protocols. This is important because atomic broadcast has a direct impact on the response time of services. We study four high performance atomic broadcast protocols representative of different classes of protocol design and characterize their latency tail distribution under different workloads. Next, we assess how key design features of each protocol can possibly be related to the observed latency tail distributions. Our observations hint at request batching as a simple yet effective way to shorten the latency tails of some of the studied protocols; an improvement within the reach of application implementers. Indeed, our observation is not only verified experimentally, it allows us to assess which of the protocol's key design principles favor the construction of latency predictable protocols.
Abstract: In this work we provide theoretical basis for the design of static and dynamic platforms that can exhibit a suitable architecture for automatic in-depth malware analysis. We show how formal methods involving static and dynamic program analysis, decision procedures and automated verification techniques can be used to build such architectures. We present automatic formal specification, classification and detection methods for malware analysis. We provide several methods to generate formal malware signatures capable of capturing and modelizing the core of the malicious behavior in a sound and concise way. We propose to generate malware invariants and abstract models directly from the specified malware code in order to use them as semantic aware signatures. Importantly, these invariants and abstracted structures would remain unchanged in many obfuscated versions of the code. Then, we present formal model extraction methods in order to model the program being inspected. These computational models are basically abstract call graphs and pushdown systems annoted with invariants at each system call locations. Thus, for each specification methods and formal models introduced, we are able to reduce the problem of malware detection to classical problem very standard for the formal method research community. We also present a host-based intrusion detection systems, where system calls are preceded by the check of pre-computed invariants. We prove that any malware analysis or intrusion detection system will be strongly re-enforced by the presence of pre-computed invariants, and will also be weakened by their absence. The research security community will benefit from mathematical formalisms that could serve as a scientific basis for their classification. The other main purpose of this paper is to enlight the formal method research community about writing static malware analyzer using several formal techniques and combined logics.
Abstract: This Technical Report presents the implementation details and usage guidelines of FDPE framework. FDPE provides fast and accurate dynamic power estimation for gate-level digital circuits using Liberty characterization data and Verilog simulator. This framework enables accurate power estimation and achieves a speed-up of three orders of magnitude over Spice. FDPE also enables dynamic power estimation for large scale circuits that are unfeasible to run in Spice simulations. In addition, FDPE has the following advantages over similar tools: ease of use, flexibility, low-cost, and public availability.
Instituto de Computação :: State University of Campinas
Av. Albert Einstein, 1251 - Cidade Universitária Zeferino Vaz • 13083-852 Campinas, SP - Brazil • Phone: [19] 3521-5838 |