Vol. 38 · No. 1

Real-time Online Interactive Application (ROIA) is an emerging class of large-scale distributed application which can support millions of concurrent users around the world. Due to the dynamic changes in the number of concurrent users as well as the uncertainty of user operations, the dynamic load balancing is a key issue for ROIA. However, most of previous works are dedicated to the load balancing in a single ROIA without considering the variety of different type ROIAs. We take the advantage of differences between ROIAs and propose a new load balancing algorithm for multi-ROIA to improve the scalability of ROIA and increase the resource utilization of system. This paper firstly describes the motivation of the new load balancing algorithm, then presents the dynamic load balancing algorithm for multi-ROIA. Finally, the simulation results are also presented to show the efficiency and feasibility of the new algorithm.

Most of the previously known evaluation methods for deductive databases are either breadth-first or depth-first (and recursive). There are cases when these strategies are not the best ones. It is desirable to have an evaluation framework for stratified DatalogN that is goal-driven, set-at-a-time (as opposed to tuple-at-a-time) and adjustable w.r.t. flow-of-control strategies. These properties are important for efficient query evaluation on large and complex deductive databases. In this paper, by incorporating stratified negation into so-called query-subquery nets, we develop an evaluation framework, called QSQNSTR, with such properties for evaluating queries to stratified DatalogN databases. A variety of flow-of-control strategies can be used for QSQNSTR. The generic evaluation method QSQNSTR for stratified DatalogN is sound, complete and has a PTIME data complexity.

In this paper Roman and weak Roman domination problems on graphs are considered. Given that both problems are NP hard, a new heuristic approach, based on a Variable Neighborhood Search (VNS), is presented. The presented algorithm is tested on instances known from the literature, with up to 600 vertices. The VNS approach is justified since it was able to achieve an optimal solution value on the majority of instances where the optimal solution value is known. Also, for the majority of instances where optimization solvers found a solution value but were unable to prove it to be optimal, the VNS algorithm achieves an even better solution value.

This 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.

The problem of knowledge heterogeneity in the Semantic Web or in the context of information systems remains a major challenge for the scientific community, in particular when several ontologies developed independently and separately have to be exploited to exchange their knowledge. Several works have addressed the semantic heterogeneity issue in ontologies and proposed to align them with additional knowledge. Recently a formalism taking into account the challenge of applied techniques to represent and reason on aligned ontologies was proposed by the authors. The authors proposed a contribution that can be seen as an extension of existing work on the heterogeneous ontologies integration. This formalism allows dealing with contextual representation and reasoning where ontologies and alignments by pairs of ontologies are developed in different and incompatible context. In this paper, some aspects of multi-level networked knowledge are recalled, detailing its semantics and discussing the comparison of the two semantics, DL-approach and DDL-approach, according to certain criteria, in order to measure their relevance and to give to readers a way to choose one semantics rather than another according to the context or the intended application.

In 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.

Due to GPU's improved hardware performance, many researchers have tried to utilize the GPU for computer vision, image processing, cryptography, and artificial intelligence. As results, the GPU could successfully speed up algorithms from tens to hundreds of times in many cases. However, GPU programming is still known to be difficult because of its different characteristics from the traditional CPU programming. Also, it is hard to find the root causes of software failures because the failures are irreproducible in many cases. Our goal is to simplify the process of verifying intended actions when debugging GPGPU programs. To achieve this goal, we use the visualization method of executed codes because it can increase the human's understanding through seeing and analyzing the real actions by each thread. We developed a platform that can visualize the running OpenCL codes and algorithms that can identify data race, barrier divergence, and infinite loop in the GPU. To the best of our knowledge, this is the first study on the visualizations of OpenCL operations and detection of infinite loops in the programs. We also suggest an algorithm for detecting data race with GPU-specific lock-step execution and barrier function.

In 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.

Feature 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.

A 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.