Computing and Informatics (E-Journal - Institute of Informatics, SAS, Bratislava)
Not a member yet
1506 research outputs found
Sort by
A Method for Learning a Petri Net Model Based on Region Theory
Get PDFThe deployment of robots in real life applications is growing. For better control and analysis of robots, modeling and learning are the hot topics in the field. This paper proposes a method for learning a Petri net model from the limited attempts of robots. The method can supplement the information getting from robot system and then derive an accurate Petri net based on region theory accordingly. We take the building block world as an example to illustrate the presented method and prove the rationality of the method by two theorems. Moreover, the method described in this paper has been implemented by a program and tested on a set of examples. The results of experiments show that our algorithm is feasible and effective
Checking Data-Flow Errors Based on The Guard-Driven Reachability Graph of WFD-Net
Get PDFIn order to guarantee the correctness of workflow systems, it is necessary to check their data-flow errors, e.g., missing data, inconsistent data, lost data and redundant data. The traditional Petri-net-based methods are usually based on the reachability graph. However, these methods have two flaws, i.e., the state space explosion and pseudo states. In order to solve these problems, we use WFD-nets to model workflow systems, and propose an algorithm for checking data-flow errors based on the guard-driven reachability graph (GRG) of WFD-net. Furthermore, a case study and some experiments are given to show the effectiveness and advantage of our method
Optimization of the Morpher Morphology Engine Using Knowledge Base Reduction Techniques
Get PDFMorpher is a novel morphological rule induction engine designed and developed for agglutinative languages. The Morpher engine models inflection using general string-based transformation rules and it can learn multiple arbitrary affix types, too. In order to scale the engine to training sets containing millions of examples, we need an efficient management of the generated rule base. In this paper we investigate and present several optimization techniques using rule elimination based on context length, support and cardinality parameters. The performed evaluation tests show that using the proposed optimization techniques, we can reduce the average inflection time to 0.52 %, the average lemmatization time to 2.59 % and the number of rules to 2.25 % of the original values, while retaining a high correctness ratio of 98 %. The optimized model can execute inflection and lemmatization in acceptable time after training millions of items, unlike other existing methods like Morfessor, MORSEL or MorphoChain
Study on Unsupervised Feature Selection Method Based on Extended Entropy
Get PDFFeature selection techniques are designed to find the relevant feature subset of the original features that can facilitate clustering, classification and retrieval. It is an important research topic in pattern recognition and machine learning. Feature selection is mainly partitioned into two classes, i.e. supervised and unsupervised methods. Currently research mostly concentrates on supervised ones. Few efficient unsupervised feature selection methods have been developed because no label information is available. On the other hand, it is difficult to evaluate the selected features. An unsupervised feature selection method based on extended entropy is proposed here. The information loss based on extended entropy is used to measure the correlation between features. The method assures that the selected features have both big individual information and little redundancy information with the selected features. At last, the efficiency of the proposed method is illustrated with some practical datasets
FingerPrint Based Duplicate Detection in Streamed Data
Get PDFIn computing, duplicate data detection refers to identifying duplicate copies of repeating data. Identifying duplicate data items in streamed data and eliminating them before storing, is a complex job. This paper proposes a novel data structure for duplicate detection using a variant of stable Bloom filter named as FingerPrint Stable Bloom Filter (FP-SBF). The proposed approach uses counting Bloom filter with fingerprint bits along with an optimization mechanism for duplicate detection. FP-SBF uses d-left hashing which reduces the computational time and decreases the false positives as well as false negatives. FP-SBF can process unbounded data in single pass, using k hash functions, and successfully differentiate between duplicate and distinct elements in O(k+1) time, independent of the size of incoming data. The performance of FP-SBF has been compared with various Bloom Filters used for stream data duplication detection and it has been theoretically and experimentally proved that the proposed approach efficiently detects the duplicates in streaming data with less memory requirements
Fuzzy Side Information Clustering-Based Framework for Effective Recommendations
Get PDFCollaborative filtering (CF) is the most successful and widely implemented algorithm in the area of recommender systems (RSs). It generates recommendations using a set of user-product ratings by matching similarity between the profiles of different users. Computing similarity among user profiles efficiently in case of sparse data is the most crucial component of the CF technique. Data sparsity and accuracy are the two major issues associated with the classical CF approach. In this paper, we try to solve these issues using a novel approach based on the side information (user-product background content) and the Mahalanobis distance measure. The side information has been incorporated into RSs to further improve their performance, especially in the case of data sparsity. However, incorporation of side information into traditional two-dimensional recommender systems would increase the dimensionality and complexity of the system. Therefore, to alleviate the problem of dimensionality, we cluster users based on their side information using k-means clustering algorithm and each user's similarity is computed using the Mahalanobis distance method. Additionally, we use fuzzy sets to represent the side information more efficiently. Results of the experimentation with two benchmark datasets show that our framework improves the recommendations quality and predictive accuracy of both traditional and clustering-based collaborative recommendations
Adaptive Reversible Data Hiding Scheme for Digital Images Based on Histogram Shifting
Get PDFExisting histogram based reversible data hiding schemes use only absolute difference values between the neighboring pixels of a cover image. In these schemes, maxima and minima points at maximum distance are selected in all the blocks of the image which causes shifting of the large number of pixels to embed the secret data. This shifting produces more degradation in the visual quality of the marked image. In this work, the cover image is segmented into blocks, which are classified further into complex and smooth blocks using a threshold value. This threshold value is optimized using firefly algorithm. Simple difference values between the neighboring pixels of complex blocks have been utilized to embed the secret data bits. The closest maxima and minima points in the histogram of the difference blocks are selected so that number of shifted pixels get reduced, which further reduces the distortion in the marked image. Experimental results prove that the proposed scheme has better performance as compared to the existing schemes. The scheme shows minimum distortion and large embedding capacity. Novelty of work is the usage of negative difference values of complex blocks for secret data embedding with the minimal number of pixel shifting
An Effective Metaheuristic for Multiple Traveling Repairman Problem with Distance Constraints
Get PDFMultiple Traveling Repairman Problem with Distance Constraints (MTRPD) is an extension of the NP-hard Multiple Traveling Repairman Problem. In MTRPD, a fleet of identical vehicles is dispatched to serve a set of customers with the following constraints. First, each vehicle's travel distance is limited by a threshold. Second, each customer must be visited exactly once. Our goal is to find the visiting order that minimizes the sum of waiting times. To solve MTRPD we propose to combine the Insertion Heuristic (IH), Variable Neighborhood Search (VNS), and Tabu Search (TS) algorithms into an effective two-phase metaheuristic that includes a construction phase and an improvement phase. In the former phase, IH is used to create an initial solution. In the latter phase, we use VNS to generate various neighborhoods, while TS is employed to mainly prohibit from getting trapped into cycles. By doing so, our algorithm can support the search to escape local optima. In addition, we introduce a novel neighborhoods’ structure and a constant time operation which are efficient for calculating the cost of each neighboring solution. To show the efficiency of our proposed metaheuristic algorithm, we extensively experiment on benchmark instances. The results show that our algorithm can find the optimal solutions for all instances with up to 50 vertices in a fraction of seconds. Moreover, for instances from 60 to 80 vertices, almost all found solutions fall into the range of 0.9 %-1.1 % of the optimal solutions' lower bounds in a reasonable duration. For instances with a larger number of vertices, the algorithm reaches good-quality solutions fast. Moreover, in a comparison to the state-of-the-art metaheuristics, our proposed algorithm can find better solutions
Application of Advanced Information and Communication Technologies in a Local Flood Warning System
Get PDFThis paper deals with the practical application of a local flood warning system. The system is built on the mathematical model of a selected area. The rainfall-runoff processes are simulated in real-time. The warning system is designed as an on-line, real-time data inputs-processing system so that it can provide a timely warning. The warning system is based on a mathematical model and it uses modern information and communication technology tools. For the system to work properly, it is absolutely necessary to adhere to a real mathematical model, and therefore a calibration on real historical data and direct measurements is required. This article describes the tasks of data collection, of building the mathematical model of the rainfall-runoff process, and the monitoring system design. The composed algorithm is able, based on the measured input data and the modeled situation, send a notification message to the monitoring centre and warn respective civil protection authorities via SMS messages
Investigation of Cloud Scheduling Algorithms for Resource Utilization Using CloudSim
Get PDFCompute Cloud comprises a distributed set of High-Performance Computing (HPC) machines to stipulate on-demand computing services to remote users over the internet. Clouds are capable enough to provide an optimal solution to address the ever-increasing computation and storage demands of large scientific HPC applications. To attain good computing performances, mapping of Cloud jobs to the compute resources is a very crucial process. Currently we can say that several efficient Cloud scheduling heuristics are available, however, selecting an appropriate scheduler for the given environment (i.e., jobs and machines heterogeneity) and scheduling objectives (such as minimized makespan, higher throughput, increased resource utilization, load balanced mapping, etc.) is still a difficult task. In this paper, we consider ten important scheduling heuristics (i.e., opportunistic load balancing algorithm, proactive simulation-based scheduling and load balancing, proactive simulation-based scheduling and enhanced load balancing, minimum completion time, Min-Min, load balance improved Min-Min, Max-Min, resource-aware scheduling algorithm, task-aware scheduling algorithm, and Sufferage) to perform an extensive empirical study to insight the scheduling mechanisms and the attainment of the major scheduling objectives. This study assumes that the Cloud job pool consists of a collection of independent and compute-intensive tasks that are statically scheduled to minimize the total execution time of a workload. The experiments are performed using two synthetic and one benchmark GoCJ workloads on a renowned Cloud simulator CloudSim. This empirical study presents a detailed analysis and insights into the circumstances requiring a load balanced scheduling mechanism to improve overall execution performance in terms of makespan, throughput, and resource utilization. The outcomes have revealed that the Sufferage and task-aware scheduling algorithm produce minimum makespan for the Cloud jobs. However, these two scheduling heuristics are not efficient enough to exploit the full computing capabilities of Cloud virtual machines