Vol. 37 · No. 2

Meta-programming paradigm and policy-based design are less known programming techniques in Digital Signal Processing (DSP) community, used to coding in pure C or assembly language. Major software components, like C++ STL, have proven usefulness of such paradigms in providing top performance of highly optimised native code, along with abstraction and modularity necessary in complex software projects. This paper describes composition of DSP code using these techniques, bringing as an example implementation of Feedback Delay Network (FDN) artificial reverberation algorithm. The proposed approach was proven to be practical, especially in case of prototyping computationally intense algorithms. To provide further performance insight, we discuss the techniques in context of other optimisation methods, like Single Instruction Multiple Data (SIMD) instruction sets usage and exploitation of superscalar architecture capabilities.

In this study, an analytical hierarchy process based model is proposed to perform the decision-making for virtual machine migration towards green cloud computing. The virtual machine migration evaluation index system is established based on the process of constructing hierarchies for evaluation of virtual machine migration, and selection of task usage. A comparative judgment of two hierarchies has been conducted. In the experimental study, five-point rating scale has been adopted to map the raw data to the scaled rating score; this rating method is used to analyze the performance of each virtual machine and its task usage data. The results show a significant improvement in the decision-making process for the virtual machine migration. The deduced results are useful for the system administrators to migrate the exact virtual machine, and then switch on the power of physical machine that the migrated virtual machine resides on. Thus the proposed method contributes to the green cloud computing environment.

Concurrent workflow scheduling algorithm works in three phases, namely rank computation, tasks selection, and resource selection. In this paper, we introduce a new ranking algorithm that computes the rank of a task, based on its successor rank and its predecessors average communication time, instead of its successors rank. The advantage of this ranking algorithm is that two dependent tasks are assigned to the same machine and as a result the scheduled length is reduced. The task selection phase selects a ready task from each workflow and creates a task pool. The resource selection phase initially assigns tasks using min-min heuristic, after initial assignment, tasks are moved from the highly loaded machines to the lightly loaded machines. Our resource selection algorithm increases the load balance among the resources due to tasks assignment heuristic and reassignment of tasks from the highly loaded machines. The simulation results show that our proposed scheduling algorithm performs better over existing approaches in terms of load balance, makespan and turnaround time.

For the sake of practicability of cloud computing, fine-grained data access is frequently required in the sense that users with different attributes should be granted different levels of access privileges. However, most of existing access control solutions are not suitable for resource-constrained users because of large computation costs, which linearly increase with the complexity of access policies. In this paper, we present an access control system based on ciphertext-policy attribute-based encryption. The proposed access control system enjoys constant computation cost and is proven secure in the random oracle model under the decision Bilinear Diffie-Hellman Exponent assumption. Our access control system supports AND-gate access policies with multiple values and wildcards, and it can efficiently support direct user revocation. Performance comparisons indicate that the proposed solution is suitable for resource-constrained environment.

Evaluating the strength of block ciphers against algebraic attacks can be difficult. The attack methods often use different metrics, and experiments do not scale well in practice. We propose a methodology that splits the algebraic attack into a polynomial part (local reduction), and an exponential part (guessing), respectively. The evaluator uses instances with known solutions to estimate the complexity of the attacks, and the response to changing parameters of the problem (e.g. the number of rounds). Although the methodology does not provide a positive answer (``the cipher is secure''), it can be used to construct a negative test (reject weak ciphers), or as a tool of qualitative comparison of cipher designs. Potential applications in other areas of computer science are discussed in the concluding parts of the article.

Media, image processing, and geometric-based systems and applications need data structures to model and represent different geometric entities and objects. These data structures have to be time efficient and compact in term of space. Many structures in use are proposed to satisfy those constraints. This paper introduces a novel compact data structure inspired by the XOR-linked lists. The subject of this paper concerns the triangular data structures. Nevertheless, the underlying idea could be used for any other geometrical subdivision. The ability of the bitwise XOR operator to reduce the number of references is used to model triangle and vertex references. The use of the XOR combined references needs to define a context from which the triangle is accessed. The direct access to any triangle is not possible using only the XOR-linked scheme. To allow the direct access, additional information are added to the structure. This additional information permits a constant time access to any element of the triangulation using a local resolution scheme. This information represents an additional cost to the triangulation, but the gain is still maintained. This cost is reduced by including this additional information to a local sub-triangulation and not to each triangle. Sub-triangulations are calculated implicitly according to the catalog-based structure. This approach could be easily extended to other representation models, such as vertex-based structures or edge-based structures. The obtained results are very interesting since the theoretical gain is estimated to 38

The aim of the vertex clique covering problem (CCP) is to cover the vertices of a graph with as few cliques as possible. We analyse the iterated greedy (IG) algorithm for CCP, which was previously shown to provide strong empirical results for real-world networks. It is demonstrated how the techniques of analysis for randomised search heuristics can be applied to IG, and several practically relevant results are obtained. We show that for triangle-free graphs, IG solves CCP optimally in expected polynomial time. Secondly, we show that IG finds the optimum for CCP in a specific case of sparse random graphs in expected polynomial time with high probability. For Barabási-Albert model of scale-free networks, which is a canonical model explaining the growth of social, biological or computer networks, we obtain that IG obtains an asymptotically optimal approximation in polynomial time in expectation. Last but not least, we propose a slightly modified variant of IG, which guarantees expected polynomial-time convergence to the optimum for graphs with non-overlapping triangles.

Column-oriented data are well suited for compression. Since values of the same column are stored contiguously on disk, the information entropy is lower if compared to the physical data organization of conventional databases. There are many useful light-weight compression techniques targeted at specific data types and domains, like integers and small lists of distinct values, respectively. However, compression of textual values formed by skewed and high-cardinality words is usually restricted to variations of the LZ compression algorithm. So far there are no empirical evaluations that verify how other sophisticated compression methods address columnar data that store text. In this paper we shed a light on this subject by revisiting concepts of those algorithms. We also analyse how they behave in terms of compression and speed when dealing with textual columns where values appear in adjacent positions.

The paper addresses the self-healing aspects of the monitoring systems. Nowadays, when the complex distributed systems are concerned, the monitoring system should become ``intelligent'' – as the first step it can guide the user what should be monitored. The next level of the ``intelligence'' can be described by the term ``self-healing''. The goal is to provide the capability that a decision made automatically by the monitoring system should force the system under monitoring to behave more stable, reliable and predictable. In the paper a new monitoring system is presented: AgeMon is an agent based, distributed monitoring system with strictly defined roles which can be performed by the agents. In the paper we discuss self-healing in the context of monitoring. When the self-healing of the monitoring system is concerned, a good example is the case where it is possible to lose the monitoring data due to the storage problems. AgeMon can handle such problems and automatically elects substitute persistence agents to store the data.

If the control system besides the standard control functions also realizes the functions (known as safety functions), failures of which can influence safety of the controlled process, then the control system may be a source of risk for assets, that are within the scope of the controlled process. Early detection of these failures and subsequent negation of their effects can have a significant influence on the safety integrity level of the safety function and thus also on the elimination of risks related to the controlled process. Therefore, the diagnostics is the means which, if appropriately applied, can increase not only the availability, but also the safety of the control system. The paper deals with using the homogeneous Markov chains to influence the evaluation of on-line diagnostics on the hardware safety integrity of the safety function, depending on the application method of several simultaneously operating diagnostics mechanisms and their basic parameters – the failures diagnostic coverage coefficient and the failure diagnostics time.

In this paper, we present a novel approach to visual smoke detection based on stereo vision. General smoke detection is usually performed by analyzing the images from remote cameras using various computer vision techniques. The literature on smoke detection shows a variety of approaches, and the focus of this paper is the improvement of the general smoke detection process by introducing stereo vision. Two cameras are used to estimate the distance and size of the detected phenomena based on stereo triangulation. Using this information, the minimum size and overall dynamics of the detected regions are further examined to ensure the elimination of false alarms induced by various phenomena (such as the movement of objects located at short distances from the camera). Such false alarms could easily be detected by the proposed stereo system, allowing the increase of the sensitivity and overall performance of the detection. We analyzed the requirements of such system in terms of precision and robustness to possible error sources, especially when dealing with detection of smoke at various distances from the camera. For evaluation, three existing smoke detection methods were tested and the results were compared to their newly implemented stereo versions. The results demonstrated better overall performance, especially a decrease in false alarm rates for all tested methods.

In written documents, the summary is a brief description of important aspects of a text. The degree of similarity between the summary and the content of a document provides reliability about the summary. Some efforts have been done in order to automate the evaluation of a summary. ROUGE metrics can automatically evaluate a summary, but it needs a model summary built by humans. The goal of this study is to find a quantitative relation between an article content and its summary using ROUGE tests without a model summary built by humans. This work proposes a method for automatic text summarization to evaluate a summary (ASHuR) based on extraction of sentences. ASHuR extracts the best sentences of an article based on the frequency of concepts, cue-words, title words, and sentence length. Extracted sentences constitute the essence of the article; these sentences construct the model summary. We performed two experiments to assess the reliability of ASHuR. The first experiment compared ASHuR against similar approaches based on sentences extraction; the experiment placed ASHuR in the first place in each applied test. The second experiment compared ASHuR against human-made summaries, which yielded a Pearson correlation value of 0.86. Assessments made to ASHuR show reliability to evaluate summaries written by users in collaborative sites (e.g. Wikipedia) or to review texts generated by students in online learning systems (e.g. Moodle).