Computing and Informatics (E-Journal - Institute of Informatics, SAS, Bratislava)
Not a member yet
1506 research outputs found
Sort by
Multilevel Algebraic Approach for Performance Analysis of Parallel Algorithms
Get PDFIn order to solve a problem in parallel we need to undertake the fundamental step of splitting the computational tasks into parts, i.e. decomposing the problem solving. A whatever decomposition does not necessarily lead to a parallel algorithm with the highest performance. This topic is even more important when complex parallel algorithms must be developed for hybrid or heterogeneous architectures. We present an innovative approach which starts from a problem decomposition into parts (sub-problems). These parts will be regarded as elements of an algebraic structure and will be related to each other according to a suitably defined dependency relationship. The main outcome of such framework is to define a set of block matrices (dependency, decomposition, memory accesses and execution) which simply highlight fundamental characteristics of the corresponding algorithm, such as inherent parallelism and sources of overheads. We provide a mathematical formulation of this approach, and we perform a feasibility analysis for the performance of a parallel algorithm in terms of its time complexity and scalability. We compare our results with standard expressions of speed up, efficiency, overhead, and so on. Finally, we show how the multilevel structure of this framework eases the choice of the abstraction level (both for the problem decomposition and for the algorithm description) in order to determine the granularity of the tasks within the performance analysis. This feature is helpful to better understand the mapping of parallel algorithms on novel hybrid and heterogeneous architectures
ACP Semantics for Petri Nets
Get PDFThe paper deals with algebraic semantics for Petri nets, based on process algebra ACP. The semantics is defined by assigning a special variable to every place of given Petri net, expressing the process initiated in the place. Algebraic semantics of the Petri net is then defined as a parallel composition of all the variables, where corresponding places hold tokens within the initial marking. Resulting algebraic specification preserves operational behavior of the original net-based specification
From Parsed Corpora to Semantically Related Verbs
Get PDFA comprehensive repository of semantic relations between verbs is of great importance in supporting a large area of natural language applications. The aim of this paper is to automatically generate a repository of semantic relations between verb pairs using Distributional Memory (DM), a state-of-the-art framework for distributional semantics. The main idea of our method is to exploit relationships that are expressed through prepositions between a verbal and a nominal event in text to extract semantically related events. Then using these prepositions, we derive relation types including causal, temporal, comparison, and expansion. The result of our study leads to the construction of a resource for semantic relations, which consists of pairs of verbs associated with their probable arguments and significance scores based on our measures. Experimental evaluations show promising results on the task of extracting and categorising semantic relations between verbs
A Method to Overcome the Ambiguities in Shallow Parse and Transfer Machine Translation
No full textThe manuscript proposes a new architecture for a Shallow Parsing and Shallow Transfer Rule-Based Machine Translation System. The newly proposed architecture omits the disambiguation module in the starting phases of the translation pipeline and stores all translation candidates generated by the ambiguous process in the morphological analysis phase. The architecture is based on multigraphs. We propose a simplified version of k-best shortest path algorithm for this special case of directed multigraph. The k-best set is ranked using a trigram language model. The empirical evaluation shows that the new architecture produces better translation quality results with constant delay in time
Process Matching: Performance Trade-Off Between Summary and Full-Length Descriptions
Get PDFBusiness process models are used by modeling experts to concisely depict the workflow of an organization that plays a pivotal role in the development of ERP systems. A growing number of organizations also maintain the textual process descriptions of these process models as the descriptions are understandable across the board. A recent study has revealed that these textual descriptions can also be used for an accurate process model search. However, the use of textual descriptions is a resource-intensive task due to the sheer size of the descriptions. To that end, in this paper, we have proposed an approach that relies on the use of summary textual descriptions, instead of full-length descriptions, to enhance the performance of process matching. To evaluate the proposed approach, we have used four diverse text summarization techniques, including a state-of-the-art deep learning based technique, for generating summary descriptions, and seven text-matching techniques for finding relevant process specifications. Our empirical study has established that the Vector Space Model is the most effective technique for process matching. Furthermore, the use of Lingo generated summaries, at a compression rate of 50 %, can achieve a higher efficiency as well as effectiveness than the full-length textual process descriptions
Mining Query Plans for Finding Candidate Queries and Sub-Queries for Materialized Views in BI Systems Without Cube Generation
Get PDFMaterialized views are important for optimizing Business Intelligence (BI) systems when they are designed without data cubes. Selecting candidate queries from large number of queries for materialized views is a challenging task. Most of the work done in the past involves finding out frequent queries from the past workload and creating materialized views from such queries by either manually analyzing workload or using approximate string matching algorithms using query text. Most of the existing methods suggest complete queries but ignore query components such as sub queries for creation of materialized views. This paper presents a novel method to determine on which queries and query components materialized views can be created to optimize aggregate and join queries by mining database of query execution plans which are in the form of binary trees. The proposed algorithm showed significant improvement in terms of more number of optimized queries because it is using the execution plan tree of the query as a basis of selection of query to be optimized using materialized views rather than choosing query text which is used by traditional methods. For selecting a correct set of queries to be optimized using materialized views, the paper proposes efficient specialized frequent tree component mining algorithm with novel heuristics to prune search space. These frequent components are used to determine the possible set of candidate queries for creation of materialized views. Experimentation on standard, real and synthetic data sets, and also the theoretical basis, proved that the proposed method is able to optimize a large number of queries with less number of materialized views and showed a significant improvement in performance compared to traditional methods
Suffix Arrays with a Twist
Get PDFThe suffix array is a classic full-text index, combining effectiveness with simplicity. We discuss three approaches aiming to improve its efficiency even more: changes to the navigation, data layout and adding extra data. In short, we show that i) the way how we search for the right interval boundary impacts significantly the overall search speed, ii) a B-tree data layout easily wins over the standard one, iii) the well-known idea of a lookup table for the prefixes of the suffixes can be refined with using compression, iv) caching prefixes of the suffixes in a helper array can pose another practical space-time tradeoff
Developing and Evaluating ECM Data Persistence Architecture
Get PDFA conceptual data persistence architecture and methodology to evaluate its performance is created. Results of the empirical research indicate that the architecture created is convenient for high intensity processing of large ECM data volumes. The synthesis of SQL and NoSQL technology allows to handle high volume transactions on current data and full-text search on large sets of history data. The history data is moved from SQL to NoSQL data store thus allowing to use a cluster of commodity hardware to store major volume of ECM data. Scaling out (increasing a number of cluster nodes) is less expensive than scaling up (buying a more powerful server hardware) that is normally needed to upgrade SQL database
Petri Nets at Modelling and Control of Discrete-Event Systems with Nondeterminism - Part 2
Get PDFDiscrete-Event Systems (DES) are discrete in nature. Petri Nets (PN) are one of the most widespread tools for DES modelling, analyzing and control. Different kinds of PN can be used for such purposes. Some of them were described in [3], being the first part of this paper. Here, the applicability of Labelled PN (LbPN) and Interpreted PN (IPN) for modelling and control of nondeterministic DES, especially with uncontrollable and/or unobservable transitions in the models, will be pointed out. Moreover, another kinds of nondeterminism in DES (errors, failures) will be modelled, and the possibilities of the error recovery of failed system will be presented
Group-Based Asynchronous Distributed Alternating Direction Method of Multipliers in Multicore Cluster
Get PDFThe distributed alternating direction method of multipliers (ADMM) algorithm is one of the effective methods to solve the global consensus optimization problem. Considering the differences between the communication of intra-nodes and inter-nodes in multicore cluster, we propose a group-based asynchronous distributed ADMM (GAD-ADMM) algorithm: based on the traditional star topology network, the grouping layer is added. The workers are grouped according to the process allocation in nodes and model similarity of datasets, and the group local variables are used to replace the local variables to compute the global variable. The algorithm improves the communication efficiency of the system by reducing communication between nodes and accelerates the convergence speed by relaxing the global consistency constraint. Finally, the algorithm is used to solve the logistic regression problem in a multicore cluster. The experiments on the Ziqiang 4000 showed that the GAD-ADMM reduces the system time cost by 35 % compared with the AD-ADMM