Computing and Informatics (E-Journal - Institute of Informatics, SAS, Bratislava)
Not a member yet
1506 research outputs found
Sort by
Analysis of Iterated Greedy Heuristic for Vertex Clique Covering
Get PDFThe aim of the vertex clique covering problem (CCP) is to cover the vertices of a graph with as few cliques as possible. We analyse the iterated greedy (IG) algorithm for CCP, which was previously shown to provide strong empirical results for real-world networks. It is demonstrated how the techniques of analysis for randomised search heuristics can be applied to IG, and several practically relevant results are obtained. We show that for triangle-free graphs, IG solves CCP optimally in expected polynomial time. Secondly, we show that IG finds the optimum for CCP in a specific case of sparse random graphs in expected polynomial time with high probability. For Barabási-Albert model of scale-free networks, which is a canonical model explaining the growth of social, biological or computer networks, we obtain that IG obtains an asymptotically optimal approximation in polynomial time in expectation. Last but not least, we propose a slightly modified variant of IG, which guarantees expected polynomial-time convergence to the optimum for graphs with non-overlapping triangles
Cost-Efficient Scheduling for Deadline Constrained Grid Workflows
Get PDFCost optimization for workflow scheduling while meeting deadline is one of the fundamental problems in utility computing. In this paper, a two-phase cost-efficient scheduling algorithm called critical chain is presented. The proposed algorithm uses the concept of slack time in both phases. The first phase is deadline distribution over all tasks existing in the workflow which is done considering critical path properties of workflow graphs. Critical chain uses slack time to iteratively select most critical sequence of tasks and then assigns sub-deadlines to those tasks. In the second phase named mapping step, it tries to allocate a server to each task considering task's sub-deadline. In the mapping step, slack time priority in selecting ready task is used to reduce deadline violation. Furthermore, the algorithm tries to locally optimize the computation and communication costs of sequential tasks exploiting dynamic programming. After proposing the scheduling algorithm, three measures for the superiority of a scheduling algorithm are introduced, and the proposed algorithm is compared with other existing algorithms considering the measures. Results obtained from simulating various systems show that the proposed algorithm outperforms four well-known existing workflow scheduling algorithms
Personalizing a Concept Similarity Measure in the Description Logic ELH with Preference Profile
Get PDFConcept similarity measure aims at identifying a degree of commonality of two given concepts and is often regarded as a generalization of the classical reasoning problem of equivalence. That is, any two concepts are equivalent if and only if their similarity degree is one. However, existing measures are often devised based on objective factors, e.g. structural-based measures and interpretation-based measures. When these measures are employed to characterize similar concepts in an ontology, they may lead to unintuitive results. In this work, we introduce a new notion called concept similarity measure under preference profile with a set of formally defined properties in Description Logics. This new notion may be interpreted as measuring the similarity of two concepts under subjective factors (e.g. the agent's preferences and domain-dependent knowledge). We also develop a measure of the proposed notion and show that our measure satisfies all desirable properties. Two algorithmic procedures are introduced for top-down and bottom-up implementation, respectively, and their computational complexities are intensively studied. Finally, the paper discusses the usefulness of the approach to potential use cases
Object Mapping in the OPC-UA Protocol for Statically and Dynamically Typed Programming Languages
Get PDFTwo or more object-oriented components located in networked computers can form a distributed system to exchange information and execute methods. The most known approaches include object request broker architectures (e.g. CORBA), messaging-service architecture (e.g. based on ZMQ or JMS) or some variant of Service Oriented Architecture (e.g. SOAP). One of new approaches in the field is the OPC-UA protocol. While having common parts with all aforementioned architectures, it brings very rich and extensible information modelling capabilities, versatility and dynamic address space model, among others. This paper proposes a mapping of information model (applicable in the OPC-UA protocol) into class and object structure of an object-oriented programming language. Special attention is paid to whether given programming language is statically or dynamically typed, with examples and applications in C++ for the former case and Python for the latter. The study also covers the cases of using the proposed mapping at both server- and client-side of OPC-UA software
AHP Aided Decision-Making in Virtual Machine Migration for Green Cloud
Get PDFIn this study, an analytical hierarchy process based model is proposed to perform the decision-making for virtual machine migration towards green cloud computing. The virtual machine migration evaluation index system is established based on the process of constructing hierarchies for evaluation of virtual machine migration, and selection of task usage. A comparative judgment of two hierarchies has been conducted. In the experimental study, five-point rating scale has been adopted to map the raw data to the scaled rating score; this rating method is used to analyze the performance of each virtual machine and its task usage data. The results show a significant improvement in the decision-making process for the virtual machine migration. The deduced results are useful for the system administrators to migrate the exact virtual machine, and then switch on the power of physical machine that the migrated virtual machine resides on. Thus the proposed method contributes to the green cloud computing environment
Fine-Grained Access Control Systems Suitable for Resource-Constrained Users in Cloud Computing
Get PDFFor the sake of practicability of cloud computing, fine-grained data access is frequently required in the sense that users with different attributes should be granted different levels of access privileges. However, most of existing access control solutions are not suitable for resource-constrained users because of large computation costs, which linearly increase with the complexity of access policies. In this paper, we present an access control system based on ciphertext-policy attribute-based encryption. The proposed access control system enjoys constant computation cost and is proven secure in the random oracle model under the decision Bilinear Diffie-Hellman Exponent assumption. Our access control system supports AND-gate access policies with multiple values and wildcards, and it can efficiently support direct user revocation. Performance comparisons indicate that the proposed solution is suitable for resource-constrained environment
Performance Models for Frost Prediction in Public Cloud Infrastructures
Get PDFSensor Clouds have opened new opportunities for agricultural monitoring. These infrastructures use Wireless Sensor Networks (WSNs) to collect data on-field and Cloud Computing services to store and process them. Among other applications of Sensor Clouds, frost prevention is of special interest among grapevine producers in the Province of Mendoza - Argentina, since frost is one of the main causes of economic loss in the province. Currently, there is a wide offer of public cloud services that can be used in order to process data collected by Sensor Clouds. Therefore, there is a need for tools to determine which instance is the most appropriate in terms of execution time and economic costs for running frost prediction applications in an isolated or cluster way. In this paper, we develop models to estimate the performance of different Amazon EC2 instances for processing frosts prediction applications. Finally, we obtain results that show which is the best instance for processing these applications
An Efficient Itemset Representation for Mining Frequent Patterns in Transactional Databases
Get PDFIn this paper we propose very efficient itemset representation for frequent itemset mining from transactional databases. The combinatorial number system is used to uniquely represent frequent k-itemset with just one integer value, for any k ≥ 2. Experiments show that memory requirements can be reduced up to 300 %, especially for very low minimal support thresholds. Further, we exploit combinatorial number schema for representing candidate itemsets during iterative join-based approach. The novel algorithm maintains one-dimensional array rank, starting from k = 2nd iteration. At the index r of the array, the proposed algorithm stores unique integer representation of the r-th candidate in lexicographic order. The rank array provides joining of two candidate k-itemsets to be O(1) instead of O(k) operation. Additionally, the rank array provides faster determination which candidates are contained in the given transaction during the support count and test phase. Finally, we believe that itemset ranking by combinatorial number system can be effectively integrated into pattern-growth algorithms, that are state-of-the-art in frequent itemset mining, and additionally improve their performances
Streamed Data Analysis Using Adaptable Bloom Filter
Get PDFWith the coming up of plethora of web applications and technologies like sensors, IoT, cloud computing, etc., the data generation resources have increased exponentially. Stream processing requires real time analytics of data in motion and that too in a single pass. This paper proposes a framework for hourly analysis of streamed data using Bloom filter, a probabilistic data structure where hashing is done by using a combination of double hashing and partition hashing; leading to less inter-hash function collision and decreased computational overhead. When size of incoming data is not known, use of Static Bloom filter leads to high collision rate if data flow is too much, and wastage of storage space if data is less. In such cases it is difficult to determine the optimal Bloom filter parameters (m, k) in advance, thus a target threshold for false positives (f_p) cannot be guaranteed. To accommodate the growing data size, one of the major requirements in Bloom filter is that filter size m should grow dynamically. For predicting the array size of Bloom filter Kalman filter has been used. It has been experimentally proved that proposed Adaptable Bloom Filter (ATBF) efficiently performs peak hour analysis, server utilization and reduces the time and space required for querying dynamic datasets
On the Satisfiability of Quasi-Classical Description Logics
Get PDFThough quasi-classical description logic (QCDL) can tolerate the inconsistency of description logic in reasoning, a knowledge base in QCDL possibly has no model. In this paper, we investigate the satisfiability of QCDL, namely, QC-coherency and QC-consistency and develop a tableau calculus, as a formal proof, to determine whether a knowledge base in QCDL is QC-consistent. To do so, we repair the standard tableau for DL by introducing several new expansion rules and defining a new closeness condition. Finally, we prove that this calculus is sound and complete. Based on this calculus, we implement an OWL paraconsistent reasoner called QC-OWL. Preliminary experiments show that QC-OWL is highly efficient in checking QC-consistency