Computing and Informatics (E-Journal - Institute of Informatics, SAS, Bratislava)
Not a member yet
1506 research outputs found
Sort by
Lightweight Fingerprints for Fast Approximate Keyword Matching Using Bitwise Operations
Get PDFWe aim to speed up approximate keyword matching with the use of a lightweight, fixed-size block of data for each string, called a fingerprint. These work in a similar way to hash values; however, they can be also used for matching with errors. They store information regarding symbol occurrences using individual bits, and they can be compared against each other with a constant number of bitwise operations. In this way, certain strings can be deduced to be at least within the distance k from each other (using Hamming or Levenshtein distance) without performing an explicit verification. We show experimentally that for a preprocessed collection of strings, fingerprints can provide substantial speedups for k = 1, namely over 2.5 times for the Hamming distance and over 30 times for the Levenshtein distance. Tests were conducted on synthetic and real-world English and URL data
Lossy Compressive Sensing Based on Online Dictionary Learning
Get PDFIn this paper, a lossy compression of hyperspectral images is realized by using a novel online dictionary learning method in which three dimensional datasets can be compressed. This online dictionary learning method and blind compressive sensing (BCS) algorithm are combined in a hybrid lossy compression framework for the first time in the literature. According to the experimental results, BCS algorithm has the best compression performance when the compression bit rate is higher than or equal to 0.5 bps. Apart from observing rate-distortion performance, anomaly detection performance is also tested on the reconstructed images to measure the information preservation performance
Assessment of Two Task Frameworks with Dependencies for Matrix Factorizations on a Multicore Architecture
Get PDFIn this study, we evaluate two task frameworks with dependencies for important application kernels coming from the numerical linear algebra. In this approach, the algorithms of the matrix factorization are considered, namely the tiled LU and the WZ factorizations both without pivoting. In tiled algorithms, the operations are represented as a sequence of small tasks which operate on square blocks (tiles) of the data. The dependencies among tasks are expressed as a direct acyclic graph and the runtime system runs the graph on a multicore architecture. The performance of applications based on the task dependencies is related to efficient compilers and the runtime systems. We report the performance and the scalability of two task frameworks with dependencies on the multicore architecture for the matrix factorizations. Namely, we compare OpenMP and Intel Thread Building Blocks. Our results show that the number of tiles in both factorizations always have an impact on the performance and the speedup. Both the frameworks show their suitability for efficient parallelization of such applications, although both have their own merits and flaws
Image Encryption Algorithm with Plaintext Related Chaining
Get PDFThis paper describes a plaintext related image encryption algorithm that utilizes the Mojette transform for computation of bins that are subsequently combined with pixels of the processed image. While the bins are computed solely from pixel intensities of a plain image and also the combination depends only on intensities of plain image pixels, the parameters of bins are rearranged according to used key. This design results in a great sensitivity of the proposed image encryption algorithm to both plain images and keys, which is verified by a set of experiments. The paper also tests the resistance of the proposal against statistical and differential attacks by means of commonly used measures as correlation coefficients, entropy, NPCR and UACI. Furthermore, the paper analyses computation speed reached by the proposed solution. Computed values of all parameters are discussed and then compared with results obtained by some recent plaintext related image encryption algorithms
A Probabilistic Extension of UML-B
Get PDFThis paper extends the graphical and formal language of UML-B to provide the ability to model probabilities. Discrete probabilities, interval probabilities, and stochastic delays are added to the UML-B's state-machine syntax, and their corresponding semantics are defined in Event-B. In addition, as a secondary contribution, UML-B (probabilistic) state-machine models are defined as MDP (Markov Decision Process) models in order to provide a means of quantitative verification in PRISM (Probabilistic Symbolic Model Checker). As an important feature of the proposed method, it does not change the Event-B syntax or semantics. To evaluate this work, as a case study, the Zeroconf protocol will be modeled in the extended UML-B using the Rodin tool, and its Event-B counterpart is converted to a PRISM model. The results of evaluations indicate that this study's additions provide the capability of modeling and verification of probabilistic and stochastic systems
Efficient Methods for Scheduling Jobs in a Simulation Model Using a Multicore Multicluster Architecture
Get PDFOver the past decade, the fast advance of network technologies, hardware and middleware, as well as software resource sophistication has contributed to the emergence of new computational models. Consequently, there was a capacity increasing for efficient and effective use of resources distributed aiming to integrate them, in order to provide a widely distributed environment, which computational capacity could be used to solve complex computer problems. The two most challenging aspects of distributed systems are resource management and task scheduling. This work contributes to minimize such problems by i) aiming to reduce this problem through the use of migration techniques; ii) implementing a multicluster simulation environment with mechanisms for load balancing; iii) plus, the gang scheduling implementation algorithms will be analyzed through the use of metrics, in order to measure the schedulers performance in different situations. Thus, the results showed a better use of resources, implying operating costs reduction
Dialogue Model Using Arguments for Consensus Decision Making Through Common Knowledge Formation
Get PDFArgumentation plays an important role in reasoning and allows the justification of opinions, especially when applied to collaborative decision making. Reaching consensus is not a trivial task where arguments exchanged in a dialogue and common knowledge are important for consensus. This paper presents a model of argumentative dialogue to support the formation of common knowledge in a group of agents that communicate by sending arguments, and proposes a semantics for consensus decision making. The output of the model is a weighted argumentation graph in which semantics is used to decide the preference of the group
Revisiting Multiple Pattern Matching
Get PDFWe consider the classical exact multiple string matching problem. The proposed solution is based on a combination of a few ideas: using q-grams instead of single characters, pattern superimposition, bit-parallelism and alphabet size reduction. We discuss the pros and cons of various alternatives to achieve the possibly best combination of techniques. The main contribution of this paper are different alphabet mapping methods that allow to reduce memory requirements and use larger q-grams. The experimental results show that the presented algorithm is competitive in most practical cases. One of the tests shows also that tailoring our scheme to search over a byte-encoded text results in speedups in comparison to searching over a plain text
HSIC Regularized LTSA
Get PDFHilbert-Schmidt Independence Criterion (HSIC) measures statistical independence between two random variables. However, instead of measuring the statistical independence between two random variables directly, HSIC first transforms two random variables into two Reproducing Kernel Hilbert Spaces (RKHS) respectively and then measures the kernelled random variables by using Hilbert-Schmidt (HS) operators between the two RKHS. Since HSIC was first proposed around 2005, HSIC has found wide applications in machine learning. In this paper, a HSIC regularized Local Tangent Space Alignment algorithm (HSIC-LTSA) is proposed. LTSA is a well-known dimensionality reduction algorithm for local homeomorphism preservation. In HSIC-LTSA, behind the objective function of LTSA, HSIC between high-dimensional and dimension-reduced data is added as a regularization term. The proposed HSIC-LTSA has two contributions. First, HSIC-LTSA implements local homeomorphism preservation and global statistical correlation during dimensionality reduction. Secondly, HSIC-LTSA proposes a new way to apply HSIC: HSIC is used as a regularization term to be added to other machine learning algorithms. The experimental results presented in this paper show that HSIC-LTSA can achieve better performance than the original LTSA
Learning SPARQL Queries from Expected Results
Get PDFWe present LSQ, an algorithm learning SPARQL queries from a subset of expected results. The algorithm leverages grouping, aggregates and inline values of SPARQL 1.1 in order to move most of the complex computations to a SPARQL endpoint. It operates by building and testing hypotheses expressed as SPARQL queries and uses active learning to collect a small number of learning examples from the user. We provide an open-source implementation and an on-line interface to test the algorithm. In the experimental evaluation, we use real queries posed in the past to the official DBpedia SPARQL endpoint, and we show that the algorithm is able to learn them, 82 % of them in less than a minute and asking the user just once