Computing and Informatics (E-Journal - Institute of Informatics, SAS, Bratislava)
Not a member yet
1506 research outputs found
Sort by
Data-Dependency Formalism for Developing Peer-to-Peer Applications
Get PDFDeveloping peer-to-peer (P2P) applications became increasingly important in software development. Nowadays, a large number of organizations from many different sectors and sizes depend more and more on collaboration between actors to perform their tasks. These P2P applications usually have a recursive behavior that many modeling approaches cannot describe and analyze (e.g. finite-state approaches). In this paper, we present an approach that combines component-based development with well-understood methods and techniques from the field of Attribute Grammars and Data-Flow Analysis in order to construct an abstract representation (i.e. Data-Dependency Graph) for P2P applications, and then perform data-flow analyzes on it. This approach embodies a formalism called DDF (Data-Dependency Formalism) to capture the behavior of P2P applications and construct their Data-Dependency Graphs. Various properties can be inferred and computed at the proposed level of data abstraction, including some properties that model checking cannot compute if the system presents a recursive behavior. As examples, we present two algorithms: one to resolve the deadlock problem and another for dominance analysis
A Practical Index for Approximate Dictionary Matching with Few Mismatches
Get PDFApproximate dictionary matching (checking if a pattern occurs in a collection of strings) is a classic problem with applications in e.g. spellchecking, online catalogs, and web searchers. We present a simple solution called split index, which is based on the Dirichlet principle, for matching a keyword with few mismatches, and experimentally show that it offers competitive space-time tradeoffs. Our implementation in the C++ language is focused mostly on data compaction, which is beneficial for the search speed. We compare our solution with other algorithms and we show that it is faster when the Hamming distance is used. Query times in the order of 1 microsecond were reported for one mismatch for a few-megabyte natural language dictionary on a medium-end PC. We also demonstrate that a basic compression technique consisting in q-gram substitution can significantly reduce the index size (up to 50 % of the input text size for the DNA sequences)
Comparison of Filter Techniques for Two-Step Feature Selection
Get PDFIn the last decade, the processing of the high dimensional data became inevitable task in many areas of research and daily life. Feature selection (FS), as part of the data processing methodology, is an important step in knowledge discovery. This paper proposes nine variation of two-step feature selection approach with filter FS employed in the first step and exhaustive search in the second step. The performance of the proposed methods is comparatively analysed from the stability and predictive performance point of view. As the obtained results indicate the choice of the filter FS in the first stage has strong influence on the resulting stability. Here, the choice of univariate Pearson correlation coefficient based FS method appears to provide the most stable results
Learning Agent for a Service-Oriented Context-Aware Recommender System in Heterogeneous Environment
Get PDFTraditional recommender systems provide users with customized recommendations of products or services. They employ various technologies and algorithms in order to search and select the best options available while taking into account the user's context. Increasingly often, such systems run on devices in heterogeneous environments (including mobile devices) making use of their functionalities: various sensors (e.g. movement, light), wireless data transmission technologies and positioning systems (e.g. GPS) among others. In this paper, we propose an innovative recommender system that determines the best service (including photo and movie conversion) and simultaneously accommodates the context of the device in a heterogeneous environment. The system allows the choice between various service providers that make their resources available using cloud computing as well as having the services performed locally. In order to determine the best possible recommendation for users, we employ the concept of learning agents, which has not been thoroughly researched in connection with recommender systems so far
New Method for Constructing a Visibility Graph-Network in 3D Space and a New Hybrid System of Modeling
Get PDFThis paper describes a new method for constructing a visibility graph in 3D space. We use a method for predicting porosity of hardened specimens. We also use an intelligent system method to predict porosity of hardened specimens. Visibility graphs have many applications, one of which is the analysis of trend lines of market graphs. It is possible to use 2D visibility graphs for such analysis and the construction for 2D visibility graphs is well known; however, in this paper, we will present a new method for the construction of 3D visibility graphs. 3D visibility computations are central to any computer graphics application. Drawing graphs as nodes connected by links in 3D space is visually compelling but computationally difficult. Thus, the construction of 3D visibility graphs is highly complex and requires professional computers or supercomputers. This article describes a new method for analysing 3D visibility graphs. We develop new method for draws 3D visibility graphs for analysing microstructure pictures of robot laser-hardened specimens. The microstructure of robot laser-hardened specimens is very complex; however, we can present it using 3D visibility graphs. New method for the construction of 3D visibility graphs is very useful in many cases, including: illumination and rendering, motion planning, pattern recognition, computer graphics, computational geometry and sensor networks and the military and automotive industries. We use this new algorithm for determination complexity of porosity of the microstructure of robot laser-hardened specimens. For predicting surface porosity of hardened specimens we use neural network, genetic algorithm and multiple regression. With intelligent system we increase production of process of laser hardening, because we decrease time of process and increase topographical property of materials. Hybrid evolutionary computation is a generic, flexible, robust, and versatile method for solving complex global optimization problems and can also be used in practical applications. This paper explores the use of an intelligent system with such a hybrid method to improve existing hybrids. It describes a new hybrid method based on the cycle integration method
Novel Approach for Detection and Removal of Moving Cast Shadows Based on RGB, HSV and YUV Color Spaces
Get PDFCast shadow affects computer vision tasks such as image segmentation, object detection and tracking since objects and shadows share the same visual motion characteristics. This unavoidable problem decreases video surveillance system performance. The basic idea of this paper is to exploit the evidence that shadows darken the surface which they are cast upon. For this reason, we propose a simple and accurate method for detection of moving cast shadows based on chromatic properties in RGB, HSV and YUV color spaces. The method requires no a priori assumptions regarding the scene or lighting source. Starting from a normalization step, we apply canny filter to detect the boundary between self-shadow and cast shadow. This treatment is devoted only for the first sequence. Then, we separate between background and moving objects using an improved version of Gaussian mixture model. In order to remove these unwanted shadows completely, we use three change estimators calculated according to the intensity ratio in HSV color space, chromaticity properties in RGB color space, and brightness ratio in YUV color space. Only pixels that satisfy threshold of the three estimators are labeled as shadow and will be removed. Experiments carried out on various video databases prove that the proposed system is robust and efficient and can precisely remove shadows for a wide class of environment and without any assumptions. Experimental results also show that our approach outperforms existing methods and can run in real-time systems
Copyright Protection for Digital Images on Portable Devices
Get PDFThe astonishing rapid diffusion of portable devices (i.e. smartphones, tablets, etc.) has had a big, and often positive, impact on our every-day life. These devices have new advanced features developed specifically because of user demand. For example, it is now possible to publish directly the pictures obtained by means of the internal camera of a smartphone on our social network accounts, or on an image hosting service. It is therefore important to have tools, on the portable devices, that can prove the ownership of the pictures and to use them before publishing images. Digital watermarking techniques are commonly used for the copyright protection of images and videos. We have developed a tool for portable devices based on the Android OS that allows the embedding of a digital visible or invisible watermark into a digital image
New Algorithms for Balancing Energy Consumption and Performance in Computational Clusters
Get PDFIn this paper, we propose new real-time measurement-based scheduling algorithms to achieve a trade-off between the energy efficiency and the performance capability of computational clusters. An investigation is performed using a specific scenario of computing clusters with realistic parameters. Numerical results show that a trade-off between the performance and the energy efficiency can be controlled by the proposed algorithms
On the Communication Cost of MDS Erasure Codes in Distributed Storage Systems
Get PDFDistributed storage systems store some redundant data to keep the degree of availability of the stored data constant and also to increase the system's resistance against failures. This type of systems usually use pure replication or methods based on RAID systems as redundancy schemes. In this paper, we study the communication cost of a distributed data storage system using Maximum Distance Separable (MDS) erasure codes. Our focus is reduction of the cost of one-to-many communication used in data reconstruction/repair initialization and update operations. We propose the use of two different communication approaches on the area of distributed storage systems for the above operations; Steiner tree approach and multi-shortest path approach. We also analyse these two communication approaches empirically and theoretically. Our theoretical results indicate that Steiner tree approach has lower message usage, whereas, multi-shortest path approach has lower time usage for data reconstruction/repair initialization operations. On the other hand, Steiner tree approach has better message and time metrics for the data update process. Furthermore, our experimental results support these theoretical results. Thus, users can choose between the two approaches depending on their needs and priorities
Efficient String Edit Similarity Join Algorithm
Get PDFString similarity join is a basic and essential operation in many applications. In this paper, we investigate the problem of string similarity join with edit distance constraints. A trie-based edit similarity join framework has been proposed recently. The main advantage of existing trie-based algorithms is support for similarity join on short strings. The main problem is when joining long and distant strings. These methods generate and maintain lots of similar prefixes called active nodes which need to be further removed in a subsequent pruning phase. With large edit distance, the number of active nodes becomes quite large. In this paper, we propose a new trie-based join algorithm called PreJoin, which improves upon current trie-based join methods. It efficiently finds all similar string pairs using a novel active-node generation method, which minimizes the number of generated active nodes by applying the pruning heuristics early in the generation process. The performance of PreJoin is scaled in two different ways: First, a dynamic reordering of the trie index is used to accelerate the search for similar string pairs. Second, a partitioning method of string space is used to improve performance on large edit distance thresholds. Experiments show that our approach is highly efficient for processing short as well as long strings, and outperforms the state-of-the-art trie-based join approaches by a factor five