Computing and Informatics (E-Journal - Institute of Informatics, SAS, Bratislava)
Not a member yet
1506 research outputs found
Sort by
Eventual Consistency: Origin and Support
Get PDFEventual consistency is demanded nowadays in geo-replicated services that need to be highly scalable and available. According to the CAP constraints, when network partitions may arise, a distributed service should choose between being strongly consistent or being highly available. Since scalable services should be available, a relaxed consistency (while the network is partitioned) is the preferred choice. Eventual consistency is not a common data-centric consistency model, but only a state convergence condition to be added to a relaxed consistency model. There are still several aspects of eventual consistency that have not been analysed in depth in previous works: 1. which are the oldest replication proposals providing eventual consistency, 2. which replica consistency models provide the best basis for building eventually consistent services, 3. which mechanisms should be considered for implementing an eventually consistent service, and 4. which are the best combinations of those mechanisms for achieving different concrete goals. This paper provides some notes on these important topics
Annotating Web Tables with the Crowd
Get PDFThe Web contains a large amount of structured tables, most of which lacks header rows. Algorithmic approaches have been proposed to recover semantics for web tables by annotating column labels and identifying subject columns. However, state-of-the-art technology is not yet able to provide satisfactory accuracy and recall. In this paper, we present a hybrid machine-crowdsourcing framework that leverages human intelligence to improve the performance of web table annotation. In this framework, machine-based algorithms are used to prompt human workers with candidate lists of concepts, while an improved K-means algorithm based on novel integrative distance is proposed to minimize the number of tuples posed to the crowd. In order to recommend the most related tasks for human workers and determine the final answers more accurately, an evaluation mechanism is also implemented based on Answer Credibility which measures the probability of a worker's intuitive answer being the final answer for a task. The results of extensive experiments conducted on real-world datasets show that our framework can significantly improve annotation accuracy and time efficiency for web tables, and our task reduction and answer evaluation mechanism is effective and efficient for improving answer quality
A Stereo Approach to Wildfire Smoke Detection: The Improvement of the Existing Methods by Adding a New Dimension
Get PDFIn this paper, we present a novel approach to visual smoke detection based on stereo vision. General smoke detection is usually performed by analyzing the images from remote cameras using various computer vision techniques. The literature on smoke detection shows a variety of approaches, and the focus of this paper is the improvement of the general smoke detection process by introducing stereo vision. Two cameras are used to estimate the distance and size of the detected phenomena based on stereo triangulation. Using this information, the minimum size and overall dynamics of the detected regions are further examined to ensure the elimination of false alarms induced by various phenomena (such as the movement of objects located at short distances from the camera). Such false alarms could easily be detected by the proposed stereo system, allowing the increase of the sensitivity and overall performance of the detection. We analyzed the requirements of such system in terms of precision and robustness to possible error sources, especially when dealing with detection of smoke at various distances from the camera. For evaluation, three existing smoke detection methods were tested and the results were compared to their newly implemented stereo versions. The results demonstrated better overall performance, especially a decrease in false alarm rates for all tested methods
Energy Aware Resource Allocation for Clouds Using Two Level Ant Colony Optimization
Get PDFIn cloud environment resources are dynamically allocated, adjusted, and deallocated. When to allocate and how many resources to allocate is a challenging task. Resources allocated optimally and at the right time not only improve the utilization of resources but also increase energy efficiency, provider's profit and customers' satisfaction. This paper presents ant colony optimization (ACO) based energy aware solution for resource allocation problem. The proposed energy aware resource allocation (EARA) methodology strives to optimize allocation of resources in order to improve energy efficiency of the cloud infrastructure while satisfying quality of service (QoS) requirements of the end users. Resources are allocated to jobs according to their QoS requirements. For energy efficient and QoS aware allocation of resources, EARA uses ACO at two levels. First level ACO allocates Virtual Machines (VMs) resources to jobs whereas second level ACO allocates Physical Machines (PMs) resources to VMs. Server consolidation and dynamic performance scaling of PMs are employed to conserve energy. The proposed methodology is implemented in CloudSim and the results are compared with existing popular resource allocation methods. Simulation results demonstrate that EARA achieves desired QoS and superior energy gains through better utilization of resources. EARA outperforms major existing resource allocation methods and achieves up to 10.56 % saving in energy consumption
Exploration of Compiler Optimization Sequences Using a Hybrid Approach
Get PDFFinding a program-specific compiler optimization sequence is a challenge, due to the large number of optimizations provided by optimizing compilers. As a result, researchers have proposed design-space exploration schemes. This paper also presents a design-space exploration scheme, which aims to search for a compiler optimization sequence. Our hybrid approach relies on sequences previously generated for a set of training programs, with the purpose of finding optimizations and their order of application. In the first step, a clustering algorithm chooses optimizations, and in the second step, a metaheuristic algorithm discovers the sequence, in which the compiler will apply each optimization. We evaluate our approach using the LLVM compiler, and an I7 processor, respectively. The results show that we can find optimization sequences that result in target codes that, when executed on the I7 processor, outperform the standard optimization level O3, by an average improvement of 8.01 % and 6.07 %, on Polybench and cBench benchmark suites, respectively. In addition, our approach outperforms the method proposed by Purini and Jain, Best10, by an average improvement of 24.22 % and 38.81 %, considering the two benchmarks suites
Effort Estimation for Service-Oriented Computing Environments
Get PDFThe concept of service in Service-Oriented Architecture (SOA) makes possible to introduce other ideas like service composition, governance and virtualization. Each of these ideas, when exercised to an enterprise level, provides benefits in terms of cost and performance. These ideas bring many new opportunities for the project managers in making the estimates of effort required to produce SOA systems. This is because the SOA systems are different from traditional software projects and there is a lack of efficient metrics and models for providing a high level of confidence in effort estimation. Thus, in this paper, an efficient estimation methodology has been presented based on analyzing the development phases of past SOA based software systems. The objective of this paper is twofold: first, to study and analyze the development phases of some past SOA based systems; second, to propose estimation metrics based on these analyzed parameters. The proposed methodology is facilitated from the use of four regression(s) based estimation models. The validation of the proposed methodology is cross checked by comparing the predictive accuracy, using some commonly used performance measurement indicators and box-plots evaluation. The evaluation results of the study (using industrial data collected from 10 SOA based software systems) show that the effort estimates obtained using the multiple linear regression model are more accurate and indicate an improvement in performance than the other used regression models
SemPCA-Summarizer: Exploiting Semantic Principal Component Analysis for Automatic Summary Generation
Get PDFText summarization is the task of condensing a document keeping the relevant information. This task integrated in wider information systems can help users to access key information without having to read everything, allowing for a higher efficiency. In this research work, we have developed and evaluated a single-document extractive summarization approach, named SemPCA-Summarizer, which reduces the dimension of a document using Principal Component Analysis technique enriched with semantic information. A concept-sentence matrix is built from the textual input document, and then, PCA is used to identify and rank the relevant concepts, which are used for selecting the most important sentences through different heuristics, thus leading to various types of summaries. The results obtained show that the generated summaries are very competitive, both from a quantitative and a qualitative viewpoint, thus indicating that our proposed approach is appropriate for briefly providing key information, and thus helping to cope with a huge amount of information available in a quicker and efficient manner
Parameter Selection and Uncertainty Measurement for Variable Precision Probabilistic Rough Set
Get PDFIn this paper, we consider the problem of parameter selection and uncertainty measurement for a variable precision probabilistic rough set. Firstly, within the framework of the variable precision probabilistic rough set model, the relative discernibility of a variable precision rough set in probabilistic approximation space is discussed, and the conditions that make precision parameters α discernible in a variable precision probabilistic rough set are put forward. Concurrently, we consider the lack of predictability of precision parameters in a variable precision probabilistic rough set, and we propose a systematic threshold selection method based on relative discernibility of sets, using the concept of relative discernibility in probabilistic approximation space. Furthermore, a numerical example is applied to test the validity of the proposed method in this paper. Secondly, we discuss the problem of uncertainty measurement for the variable precision probabilistic rough set. The concept of classical fuzzy entropy is introduced into probabilistic approximation space, and the uncertain information that comes from approximation space and the approximated objects is fully considered. Then, an axiomatic approach is established for uncertainty measurement in a variable precision probabilistic rough set, and several related interesting properties are also discussed. Thirdly, we study the attribute reduction for the variable precision probabilistic rough set. The definition of reduction and its characteristic theorems are given for the variable precision probabilistic rough set. The main contribution of this paper is twofold. One is to propose a method of parameter selection for a variable precision probabilistic rough set. Another is to present a new approach to measurement uncertainty and the method of attribute reduction for a variable precision probabilistic rough set
Using Local Reduction for the Experimental Evaluation of the Cipher Security
Get PDFEvaluating the strength of block ciphers against algebraic attacks can be difficult. The attack methods often use different metrics, and experiments do not scale well in practice. We propose a methodology that splits the algebraic attack into a polynomial part (local reduction), and an exponential part (guessing), respectively. The evaluator uses instances with known solutions to estimate the complexity of the attacks, and the response to changing parameters of the problem (e.g. the number of rounds). Although the methodology does not provide a positive answer ("the cipher is secure"), it can be used to construct a negative test (reject weak ciphers), or as a tool of qualitative comparison of cipher designs. Potential applications in other areas of computer science are discussed in the concluding parts of the article
Hybrid Data Race Detection for Multicore Software
Get PDFMultithreaded programs are prone to concurrency errors such as deadlocks, race conditions and atomicity violations. These errors are notoriously difficult to detect due to the non-deterministic nature of concurrent software running on multicore hardware. Data races result from the concurrent access of shared data by multiple threads and can result in unexpected program behaviors. Main dynamic data race detection techniques in the literature are happens-before and lockset algorithms which suffer from high execution time and memory overhead, miss many data races or produce a high number of false alarms. Our goal is to improve the performance of dynamic data race detection, while at the same time improving its accuracy by generating fewer false alarms. We develop a hybrid data race detection algorithm that is a combination of the happens-before and lockset algorithms in a tool. Rather than focusing on individual memory accesses by each thread, we focus on sequence of memory accesses by each thread, called a segment. This allows us to improve the performance of data race detection. We implement several optimizations on our hybrid data race detector and compare our technique with traditional happens-before and lockset detectors. The experiments are performed with C/C++ multithreaded benchmarks using Pthreads library from PARSEC suite and large applications such as Apache web server. Our experiments showed that our hybrid detector is 15 % faster than the happens-before detector and produces 50 % less potential data races than the lockset detector. Ultimately, a hybrid data race detector can improve the performance and accuracy of data race detection, enhancing its usability in practice