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]

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]

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]

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]

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]

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]

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]

Recommender systems have been accompanied by many applications in both academia and industry. Among different algorithms used to construct a recommender system, collaborative filtering methods have attracted much attention and been used in many commercial applications. Incorporating the time into the recommendation algorithm can greatly enhance its performance. In this paper, we propose a novel time-aware model-based recommendation system. We show that future ratings of a user can be inferred from his/her rating history. We assume that there is cascade of information between the items such that rating an item can lead to other items being rated. There is indeed a hidden network structure among the items and each user tracks a sequence of items in this network. The dependencies between the items are modeled based on statistical diffusion models and the parameters are obtained through maximum-likelihood estimation. We show that under some mild assumptions, the estimation task becomes a convex optimization problem. A major advantage of the proposed method over classical recommender systems is the ability to include novel items in its recommendation lists besides providing accurate recommendations. The proposed model also results in personalized and diverse recommendations. Experimental evaluations show that the model can be trained based on the ratings of a limited number of users. Furthermore, the proposed model outperforms classical recommendation algorithms in terms of both accuracy and novelty. [ABSTRACT FROM AUTHOR]

We have created and evaluated an algorithm capable of deduplicating and clustering exact- and near-duplicate media items of type photo and video that get shared on multiple social networks in the context of events. This algorithm works in an entirely ad hoc manner without requiring any precalculation. When people attend events, they more and more share event-related media items publicly on social networks to let their social network contacts relive and witness the attended events. In the past, we have worked on methods to accumulate such public user-generated multimedia content in order to summarize events visually, for example, in the form of media galleries or slideshows. In this paper, first, we introduce social-network-specific reasons and challenges that cause near-duplicate media items. Second, we detail an algorithm for the task of deduplicating and clustering exactand near-duplicate media items stemming from multiple social networks. Finally, we evaluate the algorithm's strengths and weaknesses and thoroughly compare its performance with the state-ofthe- art feature detection algorithms SIFT, ASIFT and SURF and show that for the given use case it performs almost equally well accuracy-wise, but strongly outperforms speed-wise. [ABSTRACT FROM AUTHOR]

Community detection in social networks is one of the most active problems with lots of applications. Most of the existing works on the problem have focused on detecting the community considering only the closeness between community members. In the real world, however, it is also important to consider bad relationships between members. In this paper, we propose a new variant of the community detection problem, called friendly community search. In the proposed problem, for a given graph, we aim to not only find a densely connected subgraph that contains a given set of query nodes but also minimizes the number of nodes involved in bad relationships in the subgraph. We prove that is Non-deterministic Polynomial-time hard (NP-hard), and develop two novel algorithms, called GREEDY and STEINERSWAP that return the near optimal solutions. Experimental results show that two proposed algorithms outperform the algorithm adapted from an existing algorithm for the optimal quasi-clique problem. [ABSTRACT FROM AUTHOR]

An algorithm for very efficient compression of a set of natural language text files is presented. Not only a very good compression ratio is reached, the used compression method allows fast pattern matching in compressed text, which is an attractive property especially for search engines. Much information is stored in the form of a large collection of text files. The web search engines can store the web pages in the raw text form to build so-called snippets or to perform so-called positional ranking functions on them. Furthermore, there exist many other similar contexts such as the storage of emails, application logs or the databases of text files (literary works or technical reports). In this paper, we address the problem of the compression of a large collection of text files distributed in cluster of computers, where the single files need to be randomly accessed in very short time. The compression algorithm is based on a word-based approach and the idea of combination of two statistical models: global model (common for all the files of the set) and local model. The latter is built as a set of changes that transform the global model to the proper model of the single compressed file. [ABSTRACT FROM AUTHOR]

Given two strings X and Y and a constraining string P, a string Z is called a constrained longest common subsequence of X and Y with respect to P if Z is the longest common subsequence of X and Y such that P is a subsequence of Z. In this paper, we propose an O(r x min{mN, nM})-time algorithm for solving this problem, where m, n and r are the lengths of X, Y and P, respectively, and M and N are the number of runs of the run-length-encoded strings of X and Y, respectively. [ABSTRACT FROM AUTHOR]

Concept drifts usually originate from many causes instead of only one, which result in two types of concept drifts: abrupt drifts and gradual drifts. From the point of view of speed, concept drifts pose strong challenges for data stream mining. In this paper, we propose a selective detector ensemble to detect both abrupt and gradual drifts. We first present our detector ensemble construction method, and then introduce how to use this ensemble to detect concept drifts with the proposed early-find-early-report rule. To evaluate the performance of our method, we compare it with four drift detection methods on eight publicly available data sets containing various concept drifts. The experimental results show that compared with those benchmarks, our ensemble method can effectively improve the recall and false negative rate without significantly increasing the false positive rate, and has stronger generalization ability than those single-change-indicator-based methods. [ABSTRACT FROM PUBLISHER]

Semi-extended regular expressions are regular expressions with intersection, union, concatenation and Kleene closure operators. The aim of this paper is the metamorphosis of semi-extended regular expressions to deterministic finite automata. The proposed algorithm is based on the follow-positions of symbols present in the semi-extended regular expression. Comparison demonstrates that the deterministic finite automaton generated using the proposed algorithm is smaller than the earlier existing approaches in the literature. Finally, to expound upon this metamorphosis, we provide the reader with numerical examples. [ABSTRACT FROM PUBLISHER]

Given a set of clients C, a set of facilities F and a query q∈F, a reverse k-nearest neighbor (RkNN) query retrieves every client c∈C for which q is one of the k closest facilities. In the past few years, RkNN queries have received significant research attention due to their wide range of applications. In this paper, we study the problem of continuous monitoring of RkNN queries in road networks. The state-of-the-art technique is sensitive toward the movement of clients, e.g. whenever a client that is inside the so-called unpruned region changes its location, the existing technique requires expensive verification of whether the client is an RkNN of q or not. To address this problem, we utilize the novel concept of influence zone, which is a region in the network such that a client c is the RkNN if and only if it lies inside this zone. This significantly improves performance because the problem of continuously monitoring RkNN queries is reduced to the problem of continuously monitoring the clients that are inside this zone. Based on several non-trivial observations, we present an efficient algorithm to compute the influence zone. Our extensive experimental study demonstrates that our algorithm is more than an order of magnitude faster than the state-of-the-art algorithm. [ABSTRACT FROM PUBLISHER]

We review the problem of finding contained rewritings (CRs) for XPath queries using XPath views. CR is proposed to cater for data integration scenarios, where views are unlikely to be complete due to the limited coverage of data sources, and hence equivalent rewritings are impossible to be found. As a result, we are usually required to find a maximal contained rewriting (MCR) for a query to provide the best possible answers. An MCR is a set of CRs, and may contain redundant CRs. Obviously, evaluating redundant CRs on materialized views is unnecessary. In this paper, we first address how to find the irredundant maximal contained rewriting (IMCR), i.e. all the irredundant CRs. We show that the existing approach ignores a type of situation, and turns out to be not sufficient. As a result, the only safe solution is a brute-force pairwise containment check for all the CRs. We then propose some heuristics to speed up the brute-force comparisons. When a materialized view is given, we propose how to evaluate the IMCR on the materialized view, which, to our knowledge, is the first work on optimizing the evaluation of a set of produced CRs on the materialized view by considering the inherent structural characteristics of the CRs. Our experiments show the effectiveness and efficiency of our algorithms. [ABSTRACT FROM AUTHOR]

The assembly of numerous applications can proceed only if all the parts for assembly are available. The completion time is determined largely by the time of manufacture of the final component. The setup times are included in the job processing time. It is unreasonable to assume that the setup process dominates the overall production process. Such activities are frequently encountered in process manufacturing, in which an initial setup is followed by a lengthy, uninterrupted production process. Motivated by these observations, we examine a multi-machine order scheduling problem with a sum-of-job-processing-times-based learning environment to minimize the number of tardy jobs. Dominance rules and a lower bound are first derived and applied in the branch-and-bound algorithm to identify the optimal solution. Afterward, a genetic algorithm and the particle swarm optimization method are employed to find a near-optimal solution. In addition, the experimental results of all proposed algorithms are provided. [ABSTRACT FROM AUTHOR]

In a multi-state system, because of performance degradation or partial failure, the system or its components could exist in a series of intermediate states between the perfect state and the failure state. These intermediate states will directly influence the system reliability. To address this problem, the fuzzy colored Petri nets (FCPNs) method is proposed. The model fully characterizes the multi-state reliability through fuzzy state information and the dynamic transition between state nodes in the fuzzy colored Petri nets, and the weighted threshold will change with the dynamic change of fuzzy information and node state changes. Therefore, the adaptive fuzzy reasoning algorithm of threshold adjustment is proposed, which provides sufficient model guidance for multistate system reliability analysis and performance optimization. Multi-state reliability is verified, which shows that the FCPNs and the parameter adjustment strategy are reasonable and effective and improve the overall performance of the multi-state system. [ABSTRACT FROM AUTHOR]

This work proposes DUELMERGE, a stable merging algorithm that is asymptotically optimal in the number of comparisons and performs O (n log2 (n) moves. Unlike other partition-based algorithms, we only allow blocks of equal sizes to be swapped, which reduces the number of moves required. We performed experiments comparing DUELMERGE against a number of baselines including RECMERGE, the standard merging solution for programming languages such as C, and some more recent approaches. The results show that our proposed algorithm performs fewer moves than other stable solutions. Experiments employing DUELMERGE within MergeSort confirmed our positive results in terms of moves, comparisons and runtime. [ABSTRACT FROM AUTHOR]

We study the problem of constructing a binary heap in an array using only a small amount of additional space. Let N denote the size of the input, M the capacity of the cache, and B the width of the cache lines of the underlying computer, all measured as numbers of elements. We show that there exists an in-place heap-construction algorithm that runs in ϴ(N) worst-case time and performs at most 1.625N + o(N) element comparisons, 1.5N + o(N) element moves, N B + O(N M · lgN) cache misses, and 1.375N + o(N) branch mispredictions. The same bound for the number of element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their algorithm requires ϴ(N) pointers. For a tuning parameter S, the idea is to divide the input into a top tree of size ϴ(N S) such that each of its leaves root a bottom tree of size ϴ(S). When S = ϴ(lgN /g/gN), we can convert the bottom trees into heaps one by one by packing the extra space needed in a few words, and subsequently use Floyd's sift-down procedure to adjust the heap order at the upper levels. In addition to our theoretical findings, we also compare different heap-construction alternatives in practice. [ABSTRACT FROM AUTHOR]

We consider practical implementations of compressed bitvectors, which support rank and select operations on a given bit-string, while storing the bit-string in compressed form. Our approach relies on variable-to-fixed encodings of the bit-string, an approach that has not yet been considered systematically for practical encodings of bitvectors. We show that this approach leads to fast practical implementations with low redundancy (i.e. the space used by the bitvector in addition to the compressed representation of the bit-string), and is a flexible and promising solution to the problem of supporting rank and select on moderately compressible bit-strings, such as those encountered in real-world applications. [ABSTRACT FROM AUTHOR]

In this article, we identify a flaw in Huang et al.'s public key encryption with authorized equality test (The Computer Journal, 2015). More precisely, we point out that the proof of the indistinguishability under adaptive chosen ciphertext attack (IND-CCA2) security for their scheme has a serious flaw. We illustrate this flaw by presenting a polynomial time CCA2 attack on their scheme. We also provide a solution to correct this flaw by modifying their scheme slightly. Our solution is quite efficient because it provides security against CCA2 attack by exploiting only the hash computation of a two times longer input without any increase in the sizes of ciphertexts and warrants. [ABSTRACT FROM AUTHOR]

Online community detection is essential for social network analysis. Modularity is a quality function used to measure the strength of the community structure discovered with social networks. Existing methods detect community structures through modularity analysis. However, the existing modularities are unable to identify community structures correctly when communities are very different in size, in particular, when the size of some communities is very small compared with others. To address this problem, we propose the concept of a coupling coefficient between two communities and define a new modularity, MC modularity, to evaluate the quality of the discovered community structures. This method can provide adequate measures for the quality of community structures. In addition, we develop the DC_MC algorithm to detect community structures based on the concept of MC modularity. An algorithm for shifting a group of nodes, instead of one node at a time, amongst communities also is designed to achieve optimal results. The effectiveness and efficacy of the approach we proposed have been demonstrated through a set of experiments involving real data benchmarks and synthetic data sets that are purpose-built for evaluating different types of networks. [ABSTRACT FROM AUTHOR]

Energy demand in a smart grid is directly related to energy consumption, as defined by user needs and comfort experience. This article presents a multi-agent architecture for smart control of space heating and cooling processes, in an attempt to enable flexible ways of monitoring and adjusting energy supply and demand. In this proposed system, control agents are implemented in order to perform temperature set-point delegation for heating and cooling systems in a building, offering a means to observe and learn from both the environment and the occupant. Operation of the proposed algorithms is compared with traditional algorithms utilized for room heating, using a simulated model of a residential building and real data about user behaviour. The results show (i) the performance of machine learning for the occupancy forecasting problem and for the problem of calculating the time to heat or cool a room; and (ii) the performance of the control algorithms, with respect to energy consumption and occupant comfort. The proposed control agents make it possible to significantly improve an occupant comfort with a relatively small increase in energy consumption, compared with simple control strategies that always maintain predefined temperatures. The findings enable the smart grid to anticipate the energy needs of the building. [ABSTRACT FROM AUTHOR]

Wireless sensor networks (WSNs) are vulnerable to the unfavorable funneling effect. The optimization of WSN clustering is a natural way to suppress the funneling effect. WSN clusters involve the edge effect that was undervalued in existing techniques. We propose an optimal clustering routing protocol GreenOCR to reduce the detrimental influence of the funnel effect and minimize the energy consumption in WSNs. Our work focuses on the approximate unequal optimal clustering and dropping energy consumption arising from the edge effect. First, according to the data repeat rate among overlapped clusters, we estimate the actual data compression ratio to offset the negative influence of the edge effect and save WSN energy. Secondly, we reduce the issue of minimizing the total energy consumption in a WSN to a nonlinear programming (NLP). We have proved that this NLP problem is NP complete. Third, we turn over to exploring an approximate optimal clustering and propose an approximate optimal clustering algorithm. A GreenOCR enabled WSN clustering minimizes the energy consumption in the whole network and extends the lifetime of the WSN. The simulation experiment shows that GreenOCR outperforms its rivals in alleviating the funnel effect. [ABSTRACT FROM AUTHOR]

A great amount of fault-based testing strategies have been proposed to generate test cases for detecting certain types of faults in Boolean specifications. However, most of the previous studies on these strategies were focused on the Boolean expressions in the disjunctive normal form (DNF), even the irredundant DNF (IDNF)--little work has been conducted to comprehensively investigate their performance on general Boolean specifications. In this study, we conducted a series of experiments to evaluate and compare 18 fault-based testing strategies using over 4000 randomly generated fault-seeded Boolean expressions. In the experiments, a testing strategy is regarded as effective and efficient if it can detect most of the seeded faults using a small number of test cases. Our experimental results show that if a testing strategy is highly effective and efficient when testing the Boolean expressions in the IDNF, it also shows high effectiveness and efficiency on general Boolean expressions. It is found that one family of fault-based testing strategies, namely MUMCUT, normally deliver the best performance among all the 18 strategies. Our study provides an in-depth understanding and insight of fault-based testing for general Boolean expressions. [ABSTRACT FROM AUTHOR]

A2-layer drawing of a bipartite graph G is a drawing such that the vertices of each partition set are drawn as points of a distinct horizontal line (called a layer) and the edges are drawn as straight-line segments. We study 2-layer drawings where edges can cross only at right angles; these drawings are called 2-layer right angle crossing drawings (2-layer RAC drawings for short). We focus on the following problem, which we call the maximum 2-layer RAC subgraph (M2LRacS) problem. Given a bipartite graph G, compute a subgraph H of G such that: (i) H admits a 2-layer RAC drawing and (ii) H has the maximum number of edges among the subgraphs of G that satisfy (i). We study this problem both in the no-fixed-layer setting, where no restriction is given on the vertex ordering on each layer, and in the 1-?xed-layer setting, where the ordering of the vertices of one of the two layers is given as part of the input and cannot be changed. The M2LRacS problem is known to be NP-hard in the no-fixed-layer setting (Di Giacomo, E., Didimo, W., Eades, P. and Liotta, G. (2011) 2-Layer Right Angle Crossing Drawings. Proc. IWOCA 2011, Lecturer Notes in Computer Science 7056, pp. 156-169; Di Giacomo, E., Didimo, W., Eades, P. and Liotta, G. (2014) 2-layer right angle crossing drawings. Algorithmica, 68, 954-997), but no algorithm has been proposed so far to solve it. We prove that the M2LRacS problem remains NP-hard even in the 1-?xed-layer setting, and provide different heuristics to solve it in the two settings; one of these heuristics is a 3-approximation algorithm for the no-fixed-layer setting. Also, we present the results of an experimental study that compares our heuristics and shows the effectiveness of the 3-approximation algorithm in practice. [ABSTRACT FROM AUTHOR]

Given a text or database T, the circular pattern discovery (CPD) problem is to identify 'interesting' circular patterns in T. Here, no specific input pattern is provided, and what is interesting is typically defined in terms of constraints in the search. We propose two algorithms for the CPD problem. The first algorithm uses suffix trees and suffix links to solve the exact CPD problem in O(m2²N) time, where m2 is the maximum length of the circular patterns and N is the total length of the sequence database. The second algorithm uses suffix arrays to solve the more challenging approximate CPD (ACPD) problem in O(km2²N²) worst case, and O(km2²N²) on average, where k is the maximum allowed error(s). By exploiting the nature of the ACPD problem, the complexity is reduced to O(m2²N²) time in the worst case, and O(m2²N) on average. [ABSTRACT FROM AUTHOR]

The notions of identity-based multi-proxy signature, proxy multi-signature and multi-proxy multi-signature have been proposed to facilitate public key certificate management of these kinds of signatures by merely employing signer's identities in place of the public keys and their certificates. In the literature, most identity-based multi-proxy signature, proxy multi-signature and multi-proxy multi-signature schemes are based on bilinear pairings. Without incorporating bilinear pairings, Tiwari and Padhye proposed an identity-based proxy multi-signature scheme in 2011. Subsequently, an identity-based multi-proxy multi-signature scheme was proposed by Tiwari et al. in 2012. First, we review identity-based (multi)-proxy multi-signature schemes without bilinear pairings and show that unfortunately, they are insecure in their security models. Secondly, we propose an identity-based multi-proxy multi-signature scheme without bilinear pairings, where identity-based multi-proxy signature and proxy multi-signature schemes are its special cases. Then, we prove that they are secure under Rivest, Shamir and Adleman (RSA) assumption in the random oracle model by presenting a new Forking Lemma. The proposal and its special cases are the first identity-based multi-proxy signature, proxy multi-signature and multi-proxy multi-signature from RSA assumption. [ABSTRACT FROM AUTHOR]