Search

Detection of computer-generated (CG) images can reveal the authenticity and originality of digital images. However, recent cutting-edge image generation methods make it very difficult to distinguish CG images from natural photographs. In this paper, a novel method based on color patterns and enhanced texture learning is proposed to tackle this problem. We designed and implemented the backbone network with a separation-fusion learning strategy by constructing a multi-branch neural network. The luminance and chrominance patterns in dual-color spaces (RGB and YCbCr) are leveraged to achieve a robust representation of image differences. A channel-spatial attention module and a global texture enhancement module are also integrated into a backbone network to enhance the learning of inherent traces. Experiments on several commonly used benchmark datasets and a newly constructed dataset with more realistic and diverse images demonstrate that the proposed algorithm outperforms state-of-the-art competitors by a large margin. [ABSTRACT FROM AUTHOR]

This research presents a new problem maximum scatter colored traveling salesman problem (MSCTSP), the objective of MSCTSP is to find Hamiltonian cycles with the minimal edge as max as possible, it is used to simulate the real-world applications of network and transport. Since MSCTSP has been proved to be a NP-hard problem, population-based algorithms can be used for solving it. However, the performances are not satisfactory. Thus, it is necessary to develop novel algorithms to obtain high quality feasible solution. Based on the above reason, the paper proposes a novel hybrid ITÖ (HITÖ) algorithm, which integrates the two new strategies: crossover operator and mutation strategy, into the standard ITÖ. In the iteration course of HITÖ, the dual-chromosome coding is used to code a feasible solution of MSCTSP, and the stochastic drift and volatility operators are used to explore and exploit new unknown region. During the process, drift operator is performed by crossover operator, volatility operator is carried out by mutation strategy, and they are both affected by activity intensity of particles which functionally depends on the radius and temperature. Experiments display HITÖ shows an improvement over comparative algorithms on solution quality. [ABSTRACT FROM AUTHOR]

Listing dense subgraphs is a fundamental task with a variety of network analytics applications. A lot of research has been done focusing on |$k$| -cliques, i.e. complete subgraphs on |$k$| nodes. However, requiring complete connectivity between the nodes of a subgraph may be too restrictive in many real applications. Hence, in this paper, we consider a natural relaxation of cliques, called |$k$| -diamonds and defined as cliques of size |$k$| with one missing edge. We first provide a sequential algorithm that, in |$O(nm^{(k-1)/2})$| time, counts and lists all the |$k$| -diamonds in large graphs, for any constant |$k \geq 4$|⁠. A parallel extension of the sequential algorithm is then proposed and analyzed in a MapReduce-style model, achieving the same local and total space usage of the state-of-the-art algorithms for |$k$| -cliques. The running time is optimal on dense graphs and |$O(\sqrt{m})$| larger than |$k$| -clique counting if the graph is sparse. Our algorithms compute induced diamonds by analyzing the structure of directed stars formed by the graph nodes and their neighbors. [ABSTRACT FROM AUTHOR]

State machines are widely used in industry and academia to capture behavioural models of control. They are included in popular notations, such as UML and its variants, and used (sometimes informally) to describe computational artefacts. In this paper, we present laws for state machines that we prove sound with respect to a process algebraic semantics for refinement, and complete, in that they are sufficient to reduce an arbitrary model to a normal form that isolates basic (action and control) elements. We consider two variants of UML-like state machines, both enriched with facilities to deal with time budgets, timeouts and deadlines over triggers and actions. In the first variant, machines are self-contained components, declaring all the variables, events and operations that they require or define. In contrast, in the second variant, machines are open, like in UML for instance. Laws for open state machines do not depend on a specific context of variables, events and operations, and normalization uses a novel operator for open-machine (de)composition. Our laws can be used in behaviour-preservation transformation techniques. Their applications are automated by a model-transformation engine. [ABSTRACT FROM AUTHOR]

In this paper, we study a new type of indoor queries, called the indoor trip planning query (iTPQ). We have observed that the existing methods for outdoor spaces cannot be applied directly to indoor spaces, due to the difference in the underlying networks. Outdoor spaces, which are normally represented as spatial road networks, are commonly modelled as a graph. In contrast, indoor spaces have distinct features (e.g. rooms, doors, hallways) that do not exist in road networks. So far, no specific solutions have been proposed for iTPQ. Even if outdoor techniques are revised for iTPQ, they fail to process iTPQ efficiently. In this paper, we propose an indoor-specific technique, based on the indoor VIP-Tree, called the VIP-Tree neighbor expansion (VNE) method, that also includes new pruning techniques in both pre-processing and query processing phases. Our experimental results show that our proposed method VNE outperforms other indoor and outdoor algorithms by several orders of magnitude in terms of processing time with low indexing cost. [ABSTRACT FROM AUTHOR]

Promoting recommender systems in real-world applications requires deep investigations with emphasis on their next generation. This survey offers a comprehensive and systematic review on recommender system development lifecycles to enlighten researchers and practitioners. The paper conducts statistical research on published recommender systems indexed by Web of Science to get an overview of the state of the art. Based on the reviewed findings, we introduce taxonomies driven by the following five phases: initiation (architecture and data acquisition techniques), design (design types and techniques), development (implementation methods and algorithms), evaluation (metrics and measurement techniques) and application (domains of applications). A layered framework of recommender systems containing market strategy, data, recommender core, interaction, security and evaluation is proposed. Based on the framework, the existing advanced humanized techniques emerged from computational intelligence and some inspiring insights from computational economics and machine learning are provided for researchers to expand the novel aspects of recommender systems. [ABSTRACT FROM AUTHOR]

In this paper, we discuss certifying algorithms for zero-clairvoyant scheduling (ZCS) problems. ZCS problems are a class of real-time scheduling problems defined in the E-T-C scheduling framework [Subramani, K. (2005) A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. Comput. J., 48, 259–272]. In ZCS, the dispatcher has no knowledge of the execution time of a given job, even after the job has finished executing. A polynomial-time algorithm for ZCS was proposed in previous work of the first author [Subramani, K. (2007) A polynomial time algorithm for zero-clairvoyant scheduling. J. Appl. Logic, 5, 667–680]. However, the algorithm proposed therein is not certifying. The algorithm that we propose in this paper is certifying, in that it provides a structure that certifies the ‘yes’-instances and another structure that certifies the ‘no’-instances of ZCS problems. These structures make the discovery of implementation errors straightforward and greatly simplify the software development cycle. Moreover, the certifying algorithm has the same running time (asymptotically) as its non-certifying counterpart. We also show that the proposed certifying technique can be used to certify a class of mathematical programs called E-Quantified Polyhedral programs (E-QPPs). However, for E-QPPs, the proposed certifying algorithm has a higher asymptotic running time than its non-certifying counterpart. [ABSTRACT FROM AUTHOR]

Traditionally, the register allocation phase for clustered very long instruction words (VLIW) architecture is implemented independently from instruction scheduling and cluster assignment. However, independently performing register allocation, scheduling and cluster assignment could have negative effect on the other phases. The research of this paper is focused on register-file connected clustered VLIW (RFCC VLIW) architecture. In RFCC VLIW architecture, the number of access ports to the global register file from each cluster and the number of registers in the global register file are both limited, due to the consideration of limited chip area of embedded systems. Thus, the distribution of inter-cluster data transferring must be carefully arranged; otherwise, there will be conflicts, which harm the performance and energy consumption. This paper proposes an algorithm to take register pressure into consideration while performing instruction scheduling and cluster assignment, so as to optimize performance and energy for embedded systems with RFCC VLIW architecture. The result shows that our algorithm can significantly reduce the penalty of performance and energy consumption due to register pressure of global register file. [ABSTRACT FROM AUTHOR]

The superior performance of quantum computers in some problems lies in the direct use of quantum mechanics phenomena. This ability has originated the quantum-inspired evolutionary algorithms (QIEAs), which are classical algorithms (for classical computers) that exploit quantum mechanics principles to improve their performance. Several proposed QIEAs are able to outperform their traditional counterparts when applied to different kinds of problems. Aiming to exploit this new paradigm on genetic programming (GP), this paper introduces a novel QIEA model (quantum-inspired linear GP—QuaLiGP), which evolves machine code programs. QuaLiGP is inspired on multi-level quantum systems, and its operation is based on quantum individuals, which represent a superposition of all programs (solutions) of the search space. The tests use symbolic regression and binary classification as knowledge management problems to assess the QuaLiGP performance and compare it with Automatic Induction of Machine Code by Genetic Programming model, which is currently the most efficient GP model to evolve machine code. Results show that QuaLiGP outperforms the reference GP system for all these problems, by achieving better solutions from a smaller number of evaluations and by using fewer parameters and operators. This paper concludes that the quantum-inspired paradigm can be a competitive approach to evolve programs efficiently, encouraging improvements and extensions of QuaLiGP. [ABSTRACT FROM PUBLISHER]

In this paper we investigate the use of distributed graphics processing unit (GPU)-based architectures to accelerate pipelined wavefront applications—a ubiquitous class of parallel algorithms used for the solution of a number of scientific and engineering applications. Specifically, we employ a recently developed port of the LU solver (from the NAS Parallel Benchmark suite) to investigate the performance of these algorithms on high-performance computing solutions from NVIDIA (Tesla C1060 and C2050) as well as on traditional clusters (AMD/InfiniBand and IBM BlueGene/P). Benchmark results are presented for problem classes A to C and a recently developed performance model is used to provide projections for problem classes D and E, the latter of which represents a billion-cell problem. Our results demonstrate that while the theoretical performance of GPU solutions will far exceed those of many traditional technologies, the sustained application performance is currently comparable for scientific wavefront applications. Finally, a breakdown of the GPU solution is conducted, exposing PCIe overheads and decomposition constraints. A new k-blocking strategy is proposed to improve the future performance of this class of algorithm on GPU-based architectures. [ABSTRACT FROM PUBLISHER]

Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. In this paper, we introduce a technique to obtain a lower bound for dilation of an embedding. Moreover, we give algorithms to compute exact dilation of embedding circulant network into a triangular grid, Tower of Hanoi graph and Sierpinski gasket graph, proving that the lower bound obtained is sharp. [ABSTRACT FROM AUTHOR]

The distance transform is a basic operation in computer vision, pattern recognition and robotics. In this paper, we consider the city block (L1) distance metric. An algorithm for computing the city block distance transform on reconfigurable meshes is proposed in this paper. The time complexity and scalability of the algorithm are analysed. The results indicate that the algorithm is scalable and efficient. [ABSTRACT FROM AUTHOR]

Recently, wireless sensor networks (WSNs) have been widely used in many applications, such as Smart Grid. However, it is generally known that WSNs are energy limited, which makes WSNs vulnerable to malicious attacks. Among these malicious attacks, a sinkhole attack is the most destructive one, since only one sinkhole node can attract surrounding nodes with unfaithful routing information, and it executes severe malicious attacks, e.g. the selective forwarding attack. In addition, a sinkhole node can cause a large amount of energy wastes of surrounding nodes, which results in abnormal energy hole in WSNs. Thus, it is necessary to design an effective mechanism to detect the sinkhole attack. In this paper, we propose a novel Intrusion Detection Algorithm based on neighbor information against Sinkhole Attack (IDASA). Different from traditional intrusion detection algorithms, IDASA takes full advantage of neighbor information of sensor nodes to detect sinkhole nodes. In addition, we evaluate IDASA in terms of malicious node detection accuracy, packet loss rate, energy consumption and network throughput in MATLAB. Simulation results show that the performance of IDASA is better than that of other related algorithms. [ABSTRACT FROM AUTHOR]

Multimedia social networks (MSNs) services and tools provide a convenient platform for users to share multimedia contents, such as electronic book, digital image, audio and video, with each other. However, in an open network, uncontrolled sharing and transmission mode of digital content between users create considerable problems regarding digital rights management (DRM). This paper aims to explore potential paths on the propagation of copyrighted contents. An approach to mining credible potential paths is proposed for MSNs. The formal descriptions were primarily based on rough set theory for mining potential paths. Trust was also measured to find credible potential paths. We presented related algorithms for mining two kinds of paths between any two nodes. Finally, we conducted an experiment based on three non-overlapped sharing communities multiplied by 150 nodes. In the communities found by using a representative real-world MSN YouTube dataset, we further mine the general and credible potential paths based on the simulated trust assessment values. The proposed method could effectively and accurately mine two kinds of potential paths of copyrighted digital content distribution and sharing, which can help to resolve critical DRM issues. [ABSTRACT FROM AUTHOR]

In this paper, we propose a self-stabilizing distance-2 edge coloring algorithm for arbitrary graphs. The algorithm operates correctly under the distributed model and guarantees that two edges within distance 2 of each other receive distinct colors when the system stabilizes. It uses 2Δ (Δ − 1) + 1 colors and stabilizes in 4n + (2Δ (Δ − 1) + 2)m rounds, where n, m, respectively, denote the number of nodes and edges and Δ is the maximum degree of nodes in the graph. [ABSTRACT FROM AUTHOR]

Centrality indices are essential in network analysis and betweenness centrality, which is based on shortest paths, is one of the most important measures. It has been widely used in different areas like social network analysis, World Wide Web and route planning. However, even for mid-size networks, it is computationally expensive to compute exact betweenness scores. In this paper, we propose a generic randomized framework for unbiased estimation of betweenness scores. The proposed framework can be adapted with various sampling techniques and give algorithms with different characteristics. We discuss the conditions a promising sampling technique should satisfy to minimize the approximation error, and propose a sampling method that partially satisfies the conditions. We perform extensive experiments on synthetic networks as well as networks from the real world, and show that, compared with existing exact and inexact algorithms, our method works with higher accuracy or gives significant speedups. [ABSTRACT FROM AUTHOR]

Automated essay-scoring (AES) systems utilize computer techniques and algorithms to automatically rate essays written in an educational setting, by which the workload of human raters is greatly reduced. AES is usually addressed as a classification or regression problem, where classical machine learning algorithms such as K-nearest neighbor and support vector machines are applied. In this paper, we argue that essay rating is based on the comparison of writing quality between essays and treat AES rather as a ranking problem by capturing the difference in writing quality between essays. We propose a rank-based approach that trains an essay-rating model by learning to rank algorithms, which have been widely used in many information retrieval and social Web mining tasks. Various linguistic and statistical features are utilized to facilitate the learning algorithms. Extensive experiments on two public English essay datasets, Automated Student Assessment Prize and Chinese Learners English Corpus, show that our proposed approach based on pairwise learning outperforms previous classification or regression-based methods on all 15 topics. Finally, analysis on the importance of the features extracted reveals that content, organization and structure are the main factors that affect the ratings of essays written by native English speakers, while non-native speakers are prone to losing ratings on improper term usage, syntactic complexity and grammar errors. [ABSTRACT FROM AUTHOR]

Community detection is a long-standing yet very difficult task in social network analysis. It becomes more challenging as many online social networking sites are evolving into super-large scales. Numerous methods have been proposed for community detection from massive networks, but how to reconcile the partitioning efficiency and the community quality remains an open problem. In this paper, we attempt to address this challenge by introducing a COSine-pattern-based COMmunity extraction framework: COSCOM. The COSCOM adopts an extracting view of community detection. It first extracts the so-called asymptotically equivalent structures (AESs) from networks, from which the nodes are further partitioned into crisp communities using any of the existing methods. Specifically, we prove that an AES is a very tight group of nodes, and is actually a cosine pattern defined by the extended cosine similarity. A novel cosine-pattern mining algorithm based on the ordered anti-monotone of cosine similarity is thus proposed for the efficient extraction of AESs. Experiments on various real-world social networks demonstrate the advantage of the extracting view of community detection. In particular, COSCOM shows merits in detecting genuine communities by either internal or external validity. [ABSTRACT FROM AUTHOR]

The transmission control protocol (TCP) Friendly Rate Control (TFRC) protocol emulates a TCP-like slow start algorithm, which is known to cause two problems: (1) takes many round-trip times to reach the optimal operating point; (2) misleads the sender to send too many packets too quickly at the end of the slow start phase. In this paper, we propose a modified measurement-based slow start mechanism, called bandwidth estimate start (BE-start), to improve the start-up performance of the TFRC protocol. The BE-start employs an effective online bandwidth measurement technique to update the sending rate with appropriate value dynamically. By adapting to network conditions during the start-up phase, the sender is able to increase the sending rate quickly without incurring a risk of buffer overflow and multiple losses. Simulation experiments show that the BE-start can significantly improve the TFRC protocol performance under various bandwidths, buffer sizes and round-trip times. The method avoids both under-utilization due to premature slow start termination, as well as multiple losses due to increasing the sending rate too fast. [ABSTRACT FROM PUBLISHER]

In distance-based network indices, the distance between two vertices is measured by the length of shortest paths between them. A shortcoming of this measure is that when it is used in real-world networks, a huge number of vertices may have exactly the same closeness/eccentricity scores. This restricts the applicability of these indices as they cannot distinguish vertices. Furthermore, in many applications, the distance between two vertices not only depends on the length of shortest paths but also on the number of shortest paths between them. In this paper, first we develop a new distance measure, proportional to the length of shortest paths and inversely proportional to the number of shortest paths, that yields discriminative distance-based centrality indices. We present exact and randomized algorithms for computation of the proposed discriminative indices. Then, by performing extensive experiments, we first show that compared with the traditional indices, discriminative indices have usually much more discriminability. Then, we show that our randomized algorithms can very precisely estimate average discriminative path length and average discriminative eccentricity, using only few samples. Then, we show that real-world networks have usually a tiny average discriminative path length, bounded by a constant (e.g. 2). We refer to this property as the tiny-world property. Finally, we present a novel link prediction method that uses discriminative distance to decide which vertices are more likely to form a link in future, and show its superior performance. [ABSTRACT FROM AUTHOR]

Shadow detection is an important pre-processing step often used in scene interpretation or shadow removal applications. In this paper, we propose a single-image shadow detection method. Many other methods use multiple images; we use a quaternion representation of colour images to extract shadows from only one input image. The generation of the final binary shadow mask is done via automatic threshold selection. Evaluation is carried out qualitatively and quantitatively over three challenging datasets of indoor and outdoor natural images. The results of qualitative assessment were consistent with the statistical results, where the proposed method improves the performance of shadow detection when compared with state-of-the-art methods. [ABSTRACT FROM AUTHOR]

A graph G is pancyclic if it contains a cycle C of every length with 3≤l(C)≤|V(G)|3≤l(C)≤|V(G)|, where l(C) denotes the length of C and |V(G)||V(G)| denotes the number of vertices in G. In this paper, we propose an augmented pancyclicity problem for the n-dimensional crossed cube CQn, which is a popular variant of the hypercube network. Let dC(u,v)dC(u,v) denote the distance between any two distinct vertices u and v traversed by a cycle C in CQn, n≥4n≥4. Then, for any integer m with [n+/1/2]+1≤m≤2n-1[n+1/2]+1≤m≤2n-1, there exist cycles C of various lengths in CQn such that dC(u,v)=mdC(u,v)=m, where (i) 2m+1≤l(C)≤2n2m+1≤l(C)≤2n if n is odd and m=,n+1/2+1m=,n+12+1 and (ii) 2m≤l(C)≤2n2m≤l(C)≤2n otherwise. This result indicates that any two distinct vertices of crossed cubes can be embedded on cycles of various feasible lengths with keeping any feasible distance from each other. [ABSTRACT FROM AUTHOR]

The potential to promote market value by analysing graph-structured data is increasingly attracting businesses from a variety of industries, ranging from Internet companies to traditional enterprises. However, the query over large graphs easily and efficiently is still a critical problem in large scale distributed systems. Many proposed systems have to use low-level programming model, like Pregel, which requires a large amount of code optimization and maintenance work by developers. Although structural recursion has been studied as an efficient high-level programming model for graph transformations, it is not well exploited in practice to accelerate the parallel graph computing. To address the above problem, in this paper, we propose optimizations of structure recursion for distributed graphs to reduce the number of iterations during graph query processing in a distributed system. In order to improve query response time and throughput, subgraph based computation on structure recursive functions are used to replace typical vertex based evaluation approach. Meanwhile, we propose several redundancy rules to reduce graph size in parallel. We verify the performance of our system through evaluation on real datasets. The results show that, compared to the state-of-the-art approach (Tung and Hu (2015) Towards systematic parallelization of graph transformations over pregel, pp. 1-20. Springer), our algorithm achieves speedup over two times on query response time. [ABSTRACT FROM AUTHOR]

Crowdsourcing has become an important problem-solving technique, for both traditional and mobile applications. There have been work on crowdsourcing particular database operations to humans, and work on spatial crowdsourcing or mobile crowdsourcing, where the workers are mobile device users. This paper presents LogicCrowd which extends logic programming, commonly used for knowledge-based applications, with crowdsourcing capabilities by adding operators to connect to crowdsourcing platforms, thereby enabling crowdsourcing via logic programs and crowd-powered knowledge-based applications. In LogicCrowd, we also introduce a novel unification approach called crowd unification that automatically leverages human knowledge for comparisons through the crowdsourcing paradigm. In addition, LogicCrowd is built on a Prolog platform running on Android mobile devices, thereby enabling logic-based spatial and mobile crowdsourcing. Our proposed method for combining rule-based reasoning and crowdsourcing via LogicCrowd programs is demonstrated in a range of scenarios. Because energy is an important consideration for mobile platforms, we also investigate the energy characteristics of the crowdsourcing operators in our LogicCrowd prototype. Our experiments show the relationships between crowdsourcing operations and energy consumption, and illustrate the factors influencing energy consumption when using crowdsourcing. [ABSTRACT FROM AUTHOR]

Deep pushdown transducers (DPDT) are deterministic with respect to depth, but they lack strict determinism. The aim of this paper is to address the open problem of determinism in DPDT, as discussed in [1], by proposing a deterministic DPDT (DDPDT). Furthermore, we also explore a parallel variant of a DDPDT. The proposed deterministic models are strictly deterministic as well as deterministic with respect to depth. We support this discussion of these transducers with numerical examples. Furthermore, relationships among deterministic transducers, non-strict deterministic transducers and their parallel variants will be discussed. [ABSTRACT FROM AUTHOR]

In this paper, we consider a single-machine scheduling problem with a deteriorating and resource-dependent maintenance activity, that is, the duration of the maintenance is assumed to be dependent both on its starting time and on the resource allocated to it. Our goal is to determining the schedule of jobs, the position to schedule the maintenance activity and the amount of additional resource allocated to it such that the total cost of the total absolute differences in completion times and the resource are minimized. We show that the problem remains polynomially solvable. [ABSTRACT FROM AUTHOR]

Effective server consolidation in cloud has significantly become one of the major challenges. The determination of over-utilized and under-utilized servers and migration needs to work cordially with energy conservation and optimal resource usage. Clustering of servers makes easy retrieval of servers for best possible allocation of tasks. The paper focuses on the clustering of servers in effective manner using Expectation Maximization (EM) concept. It presents an algorithm using EM as a phase for the server consolidation in cloud. Employing EM for clustering makes more uniform clustering of servers leading to improved allocation of resource requests. The results of the proposed scheme have been compared with existing K-means, Fuzzy C-Means and Spectral clustering. The proposed EM algorithm performance is better in terms of handling of probabilistic constraints, guaranteeing convergence with well-separated components. [ABSTRACT FROM AUTHOR]

Gravitational search algorithm (GSA) is a stochastic search algorithm based on the law of gravity and mass which is widely used nowadays for efficient solution of optimization problems. For the purpose of enhancing the performance of original GSA, this paper proposes a new GSA called Bird Flock Gravitational Search Algorithm (BFGSA) based on the collective response of birds. Although GSA performs well in many problems, algorithms in this category lack mechanisms which add diversity to exploration in the search process. Our proposed algorithm introduces a new mechanism into GSA to add diversity, a mechanism which is inspired by the collective response behavior of birds. This mechanism performs its diversity enhancement through three main major steps including initialization, identification of the nearest neighbors and orientation change. The initialization is to generate candidate populations for the second steps and the orientation change updates the position of objects based on the nearest neighbors. Due to the collective response mechanism, the BFGSA explores a wider range of the search space and thus escapes sub-optimal solutions. The efficiency and robustness of the proposed algorithm is demonstrated using multiple traditional and newly composed benchmark functions presented in CEC2005 competition and the results are compared with recent variants of the original particle swarm optimization and state-of-the-art GSA algorithms. Furthermore, we applied BFGSA to a real-world application of data clustering. The results show that BFGSA improves the performance of the original GSA and obtains the best results compared with our selected GSA-type algorithms in benchmarking experiments and clustering experiments. [ABSTRACT FROM AUTHOR]

Matrix separation has a wide range of potential applications and many approaches have been devised to solve it. Especially, for applications involving large-scale data, such as vision tasks, improving the scalability of algorithms has attracted much attention. Reviewing these methods, they mainly involve convex optimization and factorization optimization. Convex optimization models become increasingly costly as the matrix size and rank grow. Factorization optimization models, to a large extent, reduce the computational complexity of matrix separation. &#84671-filtering applied the generalized Nyström to matrix separation, and proposed the seed-based convex optimization. In this paper, to benefit from the seed strategy, we propose matrix separation based on Low-Rank Matrix Fitting (LMaFit)-Seed, which is an algorithm on low-rank factorization optimization, to enhance the scalability in solving the problems of large-scale matrix separation and to be less timeconsuming. We evaluate the proposed method and demonstrate comparisons with several state-ofthe- art methods on synthetic data simulations and real sequences experiments. [ABSTRACT FROM AUTHOR]

Person re-identification consists in recognizing the same person across non-overlapping camera views at different times and locations. It presents an important yet challenging task for intelligent video surveillance systems due to the large variations of pose, viewpoint, lighting and occlusion between the different camera views. Although a variety of algorithms have been presented in the past few years, most of them usually assume a pre-cropped bounding box of fully visible people taken from two different cameras to perform the re-identification process. However, in real-world video surveillance systems several challenges need to be addressed such as re-identifying truncated people and alleviating the hash lighting variation of the different camera views. In this paper, we propose an adaptive person re-identification approach that re-identifies a person irrespective of his status, i.e. truncated or fully visible, based on the apparent salient body regions driven by their robust appearance characteristics in a large camera network. The proposed approach has been experimentally validated on the High Definition Analytics (HDA) and viewpoint invariant perdestrian recognition data sets which include several re-identification challenges. The outcomes of this evaluation show promising results and demonstrate the effectiveness of our approach compared to other state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

A major factor affecting the readability of a graph drawing is its resolution. In the graph drawing literature, the resolution of a drawing is either measured based on the angles formed by consecutive edges incident on a common vertex (angular resolution) or by the angles formed at edge crossings (crossing resolution). In this paper, we introduce the notion of ‘total resolution’, that is, the minimum of the angular and crossing resolution. To the best of our knowledge, this is the first time where the problem of maximizing the total resolution of a graph over all its drawings is studied. The main contribution of the paper consists of drawings of asymptotically optimal total resolution for complete graphs (circular drawings) and for complete bipartite graphs (two-layered drawings). In addition, we present and experimentally evaluate a force-directed-based algorithm that constructs drawings of large total resolution. [ABSTRACT FROM AUTHOR]

In testing systems with distributed interfaces/ports, we may place a separate tester at each port. It is known that this approach can introduce controllability problems which have received much attention in testing from finite state machines. Message sequence charts (MSCs) form an alternative, commonly used, language for modelling distributed systems. However, controllability problems in testing from MSCs have not been thoroughly investigated. In this paper, controllability problems in MSC test cases are analysed with three notions of observability: local, tester and global. We identify two types of controllability problem in MSC-based testing. It transpires that each type of controllability problem is related to a type of MSC pathology. Controllability problems of timing are caused by races but not every race causes controllability problems; controllability problems of choice are caused by non-local choices and not every non-local choice causes controllability problems. We show that some controllability problems of timing are avoidable and some controllability problems of choice can be overcome when testers have better observational power. Algorithms are provided to tackle both types of controllability problems. Finally, we show how one can overcome controllability problems using a coordination service with status messages based on algorithms developed in this paper. [ABSTRACT FROM PUBLISHER]

Causal discovery is highly desirable in science and technology. In this paper, we study a new research problem of discovery of causal relationships in the context of streaming features, where the features steam in one by one. With a Bayesian network to represent causal relationships, we propose a novel algorithm called causal discovery from streaming features (CDFSF) which consists of a two-phase scheme. In the first phase, CDFSF dynamically discovers causal relationships between each feature seen so far with an arriving feature, while in the second phase CDFSF removes the false positives of each arrived feature from its current set of direct causes and effects. To improve the efficiency of CDFSF, using the symmetry properties between parents (causes) and children (effects) in a faithful Bayesian network, we present a variant of CDFSF, S-CDFSF. Experimental results validate our algorithms in comparison with the existing algorithms of causal relationship discovery. [ABSTRACT FROM PUBLISHER]

The COordinate Rotation DIgital Computer (CORDIC) algorithm is a famous technique for realizing complex arithmetic functions using simple shift-add operations. This paper presents a novel completely scaling-free CORDIC algorithm in rotation mode for high performance hyperbolic computations. We target algorithm level improvements to achieve low area and power-delay product on FPGA. Instead of complex search algorithms, we use the most significant one bit detection technique for micro-rotation sequence identification, which helps in significantly reducing the number of pipelining stages. The proposed technique uses mathematical identities to extend the range of convergence. The eight-staged pipelined architecture implementation requires a ROM in the preprocessing unit for storing the initial coordinate values, while the ROM for storing the elementary angles is eliminated. The FPGA implementation of the proposed processor requires 46.35% less gates and has 31.81% less delay when compared with Xilinx Core IP-CORDIC v3.0. Moreover, on an average it consumes 75.96% less power when compared with Xilinx CORDIC v3.0. Hence, the proposed technique provides an area–power-delay efficient VLSI implementation for calculating hyperbolic functions and exponents. The detailed algorithm design, along with FPGA implementation and area and time complexities, is presented in this paper. [ABSTRACT FROM AUTHOR]

In many pattern recognition applications, first decision trees are used due to their simplicity and easily interpretable nature. In this paper, we propose a new decision tree learning algorithm called univariate margin tree where, for each continuous attribute, the best split is found using convex optimization. Our simulation results on 47 data sets show that the novel margin tree classifier performs at least as good as C4.5 and linear discriminant tree (LDT) with a similar time complexity. For two-class data sets, it generates significantly smaller trees than C4.5 and LDT without sacrificing from accuracy, and generates significantly more accurate trees than C4.5 and LDT for multiclass data sets with one-vs-rest methodology. [ABSTRACT FROM AUTHOR]

In wireless ad hoc and sensor networks, energy is a scarce resource and a considerable amount of energy is dissipated due to interference. Therefore, interference is one of the major challenges in wireless ad hoc and sensor networks. It alters or disrupts a message as it is being transmitted along a channel between source and destination. Since the messages are disrupted when the interference occurs, they have to be detected and the interfered messages have to be retransmitted. In this paper, we propose central and distributed heuristic algorithms for reducing average interference in a receiver-centric interference model. In the literature, the minimum spanning tree (MST) algorithm is generally used through the interference coverage graph directly or indirectly in order to generate minimum average interference topology. Our algorithm, dynamic average interference (DAI), however, generates lower average interference as well as more sparse topology than MST. We realized that if the transmission ranges of nodes are taken into consideration at each stage of the topology control algorithm, the interference of links are changed dynamically. This interference changing enables up to 22% more energy saving than the MST algorithm. Thus, DAI provides energy saving by reducing the interference as far as possible in generated topology. [ABSTRACT FROM AUTHOR]

The adoption of radio frequency identification (RFID) tags and devices facilitates the observation and monitoring of event patterns, while highly temporal restrained RFID data further make events complicated. Although the existing Pub/Sub systems can help distributed applications monitor and disseminate interesting events, they are unable to express RFID-related events directly. Extending a system for new RFID requirements not only needs a lot of work, but also provides no performance guarantees. It is, therefore, necessary to design and implement an effective and efficient Pub/Sub system in order to capture and disseminate RFID-related events. This paper presents a composite subscription specification for RFID-related application scenarios. It enables the subscription of predicates for RFID code as well as various complex events. Moreover, this paper proposes the algorithms for RFID-code subscription matching and complex events detection which have been implemented in our Pub/Sub system, OncePubSub. Also, experiments were conducted to quantify the performance and overhead of the above algorithms. Performance evaluation results indicate that OncePubSub is more efficient than SIENA- and JESS-based systems. [ABSTRACT FROM PUBLISHER]

A new method to generate tests for deterministic implementations of deterministic finite state machines is proposed. The method is generic, taking a wide class of testing strategies as a parameter, and able to support both transition-oriented and fault-model-driven testing. For a given specification machine, it builds a graph encoding the given strategy and then generates a test by solving on the graph a generalization of the Rural Postman Problem. Only the first phase is domain specific and therefore precisely described in the paper. The second phase is considered a responsibility of graph specialists, though we provide guidelines for solving the most commonly encountered special case. The strategy encoding produced in the first phase is such that the second phase automatically handles, in an integrated manner, the following optimization concerns: absolute avoidance of forbidden transitions, maximum avoidance of transitions which are for some reason considered undesirable, subtest choice, subtest ordering and subtest connection, possibly with overlapping. The method accepts multi-criteria transition cost functions. If both its phases are executed precisely, it generates a test optimal with respect to the adopted strategy, and a strategy for generating absolutely optimal tests is also given. For the cases where the complexity of the first phase or of the resulting graph is problematic, guidelines for systematically conducting the phase in an approximate way are provided. [ABSTRACT FROM AUTHOR]

This paper develops a new theory and model for information and sensor validation. The model represents relationships between variables using Bayesian networks and utilizes probabilistic propagation to estimate the expected values of variables. If the estimated value of a variable differs from the actual value, an apparent fault is detected. The fault is only apparent since it may be that the estimated value is itself based on faulty data. The theory extends our understanding of when it is possible to isolate real faults from potential faults and supports the development of an algorithm that is capable of isolating real faults without deferring the problem to the use of expert provided domain-specific rules. To enable practical adoption for real-time processes, an any time version of the algorithm is developed, that, unlike most other algorithms, is capable of returning improving assessments of the validity of the sensors as it accumulates more evidence with time. The developed model is tested by applying it to the validation of temperature sensors during the start-up phase of a gas turbine when conditions are not stable; a problem that is known to be challenging. The paper concludes with a discussion of the practical applicability and scalability of the model. [ABSTRACT FROM AUTHOR]

This paper introduces a novel technique to obtain a schedule for a cyclic data-flow graph (DFG) onto a multiprocessor system. The optimality criteria considered in this scheduling technique are the maximum throughput, minimum input–output (I/O) delay, and minimum hardware resources. In this technique, an all-pair longest path algorithm is used to evaluate the relative firing times of the nodes of the given DFG. The proposed technique for finding these times is quite simple to implement and it has lower time complexity than all the previously proposed techniques. The technique is tested on various benchmark problems to demonstrate its optimal performance. All the optimality criteria are achieved on all the tested benchmarks. However, finding a minimum hardware resource schedule is an NP complete problem, and thus cannot be theoretically ensured. A formal proof of achieving both the throughput and the I/O delay optimality simultaneously is given, and an efficient technique to ensure this is also presented. This technique is quite simple and can be used to ensure delay optimality in any scheduling technique. [ABSTRACT FROM PUBLISHER]

Graph grammars may be used as natural and powerful syntax-definition formalisms for visual programming languages. Yet most graph-grammar parsing algorithms presented so far are either unable to recognize interesting visual languages or tend to be inefficient (with exponential time complexity) when applied to graphs with a large number of nodes and edges. This paper presents a context-sensitive graph grammar called reserved graph grammar, which can explicitly and completely describe the syntax of a wide range of diagrams using labeled graphs. The parsing algorithm of a reserved graph grammar uses a marking mechanism to avoid ambiguity in parsing and has polynomial time complexity in most cases. The paper defines a constraint condition under which a graph defined in a reserved graph grammar can be parsed in polynomial time. An algorithm for checking the condition is also provided. [ABSTRACT FROM PUBLISHER]

This paper describes an algorithm and associated tool for checking a network of communicating processes, defined using the algebraic language of CSP, against a set-theoretic specification, expressed in terms of event traces and refusal sets. [ABSTRACT FROM PUBLISHER]

As one of the counting-based topological indices, the number of subtrees and its variations has received much attention in recent years. In this paper, using generating functions, we investigate and derive formulas for this index of hexagonal and phenylene chains. We also present graphtheoretical algorithms for enumerating subtrees of these two chains. Extremal values and graphs with respect to the subtree number among all hexagonal and phenylene chains with n hexagons are also determined. As an application, we briefly examine the subtree densities of these two chains. [ABSTRACT FROM AUTHOR]

With the development of distributed energy generators and storages, the sustainability of a microgrid comprised of multiple electricity users is significantly increased. Maximizing the efficiency of generated renewable energy is vital to running a sustainable microgrid as it indicates reducing the usage of thermal electricity purchased from the macrogrid. To this end, the excessive renewable energy of a user should be shared with others who are short of energy. Unfortunately, coordinating the transfers of renewable energy among the users in a microgrid is particularly difficult, given the rational nature of users, the stochastic nature of renewable energy and the dynamic nature of energy demand of each user. In this paper, we consider the coupled problem of maximizing the renewable energy efficiency of a sustainable microgrid as well as stimulating rational users to share excessive renewable energy. We propose a near-optimal scheduling algorithm, which determines the amounts of renewable energy transferred among users in an online fashion. We also design an efficient pricing mechanism for the trade of energy among users based on double auction. We rigorously prove that our online scheduling algorithm is approximately optimal and the pricing mechanism guarantees the property of individual rationality of users. Comprehensive simulation results demonstrate the efficacy of our online algorithm and incentive mechanism. [ABSTRACT FROM AUTHOR]

The PPM data compression scheme has set the performance standard in lossless compression of text throughout the past decade. PPM is a finite-context statistical modelling technique that can be viewed as blending together several fixed-order context models to predict the next character in the input sequence. This paper gives a brief introduction to PPM, and describes a variant of the algorithm, called PPM*, which exploits contexts of unbounded length. Although requiring considerably greater computational resources (in both time and space), this reliably achieves compression superior to the benchmark PPMC version. Its major contribution is that it shows that the full information available by considering all substrings of the input string can be used effectively to generate high-quality predictions. Hence, it provides a useful tool for exploring the bounds of compression. [ABSTRACT FROM AUTHOR]

White-box cryptography aims at implementing a cipher to protect its key from being extracted in an untrusted environment, where the attacker has full access to the execution of the cryptographic software. In 2002, Chow et al. proposed the original white-box implementation of AES. Afterwards, various white-box implementations were presented. However, they were all badly broken because of a weakness of the implemented cryptographic algorithms: every parameter of the cryptographic operations is fixed except the round keys. In this paper, we present an AES-like cipher based on key-dependent S-boxes. The new cipher is designed to meet the design criteria of AES and hence provides a security level comparable to AES to resist black-box attacks. Moreover, we present a white-box implementation for our AES-like cipher, which is sufficient to withstand existing white-box attacks. [ABSTRACT FROM AUTHOR]

Auction mechanism has been widely applied to cognitive radio networks to motivate spectrum redistribution among unlicensed users and spectrum holders, in which unlicensed users with cognitive radio capability can access the licensed spectrum by compensating spectrum holders with monetary payment. However, most of prior studies on auction are mainly restricted to channel allocation with the assumption of fixed transmitting power and/or neglecting spectrum holders’ interference restrictions. Few of them jointly considers the channel and power allocation. Additionally, power allocation may cause non-identical interference relationships among unlicensed users due to the variable interference ranges. In this paper, we propose two truthful double auction schemes under single-channel demand and multi-channel demand, respectively.We theoretically prove that the two auction schemes both achieve the desired economic properties. Results from numerical evaluation demonstrate our analysis. [ABSTRACT FROM AUTHOR]

With the increasing popularity of the Internet video streaming services (e.g. YouTube and Netflix), content delivery networks (CDNs) are heavily used to stream video contents to users, and consume more and more power and bandwidths in recent years. In this paper, we investigate the problem of saving a video streaming CDN’s operating expense, including both its energy cost and the traffic cost. From our measurement study on the CDN infrastructure of Youku, which is the largest video site in China, we find that there exists an inherent conflict between improving a video streaming CDN’s energy efficiency for power saving, and maintaining the CDN’s ISP-friendly server selection policy. To address this problem, we propose a cost-aware capacity provisioning algorithm, which dynamically plans the service capacities of a CDN’s server clusters in numerous ISPs, and optimizes its overall operating cost regarding both the energy consumptions and the cross-ISP traffics. By using the workload derived from real-world measurement and applying actual power and bandwidth price parameters, we show with experiments that our approach can significantly reduce a video streaming CDN’s overall operating cost, and avoid frequent server switches effectively. To our best knowledge, this work is the first one that identifies and resolves the inherent conflict between a CDN’s energy efficiency and its ISP-friendly policy. [ABSTRACT FROM AUTHOR]

In this paper, we study the first-order consensus algorithm in the small-world Farey graph where agents are driven by white noise, aiming to unveil the effect of small-world topology on the robustness of the consensus algorithm. We characterize the coherence of the Farey graph in terms of the H2-norm of the system, the square of which equals the steady-state variance and thus captures how closely agents track the consensus value. Based on the particular network structure, we derive an exact expression for the coherence in the Farey graph, whose dominant behavior scales logarithmically with the system size. To uncover the role of small-world topology, we also derive an analytical solution for the coherence of first-order consensus in the regular ring lattice sharing the same average degree as the Farey graph, whose dominant term grows linearly with the system size, implying that the small-world structure strongly affects the performance of the consensus algorithm. [ABSTRACT FROM AUTHOR]

This section presents a review of several papers on computer science. They include "Hardware-Oriented Algorithms for Rendering Order-Independent Transparency," by M. Amor, M. Bóo, E. J. Padrón, and D. Bartz, "Instruction-Level Parallelism Through Microthreading--A Scalable Approach to Chip Multiprocessors," by K. Bousias, N. Hasasneh, and C. Jesshope, and "Using Control Dependencies for Space-Aware Bytecode Verification," by C. Bernardeschi, G. Lettieri, L. Martini, and P. Masci.