Brain tumor segmentation aims to separate the different tumor tissues such as active cells, necrotic core, and edema from normal brain tissues of White Matter (WM), Gray Matter (GM), and Cerebrospinal Fluid (CSF). MRI-based brain tumor segmentation studies are attracting more and more attention in recent years due to non-invasive imaging and good soft tissue contrast of Magnetic Resonance Imaging (MRI) images. With the development of almost two decades, the innovative approaches applying computer-aided techniques for segmenting brain tumor are becoming more and more mature and coming closer to routine clinical applications. The purpose of this paper is to provide a comprehensive overview for MRI-based brain tumor segmentation methods. Firstly, a brief introduction to brain tumors and imaging modalities of brain tumors is given. Then, the preprocessing operations and the state of the art methods of MRI-based brain tumor segmentation are introduced. Moreover, the evaluation and validation of the results of MRI-based brain tumor segmentation are discussed. Finally, an objective assessment is presented and future developments and trends are addressed for MRI-based brain tumor segmentation methods.
Malicious applications can be introduced to attack users and services so as to gain financial rewards, individuals' sensitive information, company and government intellectual property, and to gain remote control of systems. However, traditional methods of malicious code detection, such as signature detection, behavior detection, virtual machine detection, and heuristic detection, have various weaknesses which make them unreliable. This paper presents the existing technologies of malicious code detection and a malicious code detection model is proposed based on behavior association. The behavior points of malicious code are first extracted through API monitoring technology and integrated into the behavior; then a relation between behaviors is established according to data dependence. Next, a behavior association model is built up and a discrimination method is put forth using pushdown automation. Finally, the exact malicious code is taken as a sample to carry out an experiment on the behavior's capture, association, and discrimination, thus proving that the theoretical model is viable.
Many competing approaches exist in evaluating sensor network solutions differing by levels of ease of use, cost, control, and realism. Existing work concentrates on simulating network protocols or emulating processing units at the machine cycle level. However, little has been done to emulate the sensors and the physical environments that they monitor. The main contribution of this work is the design of WiserEmulator, an emulation framework for structural health monitoring, which gracefully balances the trade-offs between realism, controllability, and cost. WiserEmulator consists of two main components - a testbed of wireless sensor nodes and a software emulation environment. To emulate the excitation and response of piezo-electric transducers, as well as the wave propagation inside concrete structures, the COMSOL Multi-Physics software was utilized. Digitized sensing output from COMSOL was played back via a multi-channel Digital-to-Analog Converter (DAC) connected to the wireless sensor testbed. In addition to the emulation of concrete structures, WiSeREmulator also allows users to choose pre-stored data collected from field experiments and synthesized data. A user-friendly Graphical User Interface (GUI) was developed that facilitates intuitive configurations of experimental settings, control of the on-set and progression of the experiments, and real-time visualization of experimental results. We have implemented WiSeREmulator in MATLAB. This work advances the state of the art in providing low cost solutions to evaluating Cyber Physical Systems such as wireless structural health monitoring networks.
This paper deals with the Feedback Vertex Set problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance, the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of Feedback Vertex Set for a wide range of parameters. We survey known results and present several new complexity classifications. For example, we prove that Feedback Vertex Set is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP ? coNP/poly and the polynomial-time hierarchy collapses.
IEEE 802.11p/DSRC (Dedicated Short Range Communication) is considered to be a promising wireless communication standard for enhancing transportation safety and efficiency. However, IEEE 802.11p-based Vehicle-to-Vehicle (V2V) communication is still unreliable because of the complicating factors of high vehicle speed and complex radio environments. In this paper, we performed a data-based evaluation of V2V communication reliability, using real-world measurements in a typical urban expressway in Beijing. With respect to the characteristics of the urban expressway and our experimental data, we found road slope and traffic density to be the major environmental factors having a significant impact on the V2V communication’s Line-Of-Sight (LOS) conditions. On the basis of these two factors, we propose a fuzzy classification method for the LOS conditions, and separate the real-time communication environments into different LOS cases. For each LOS case, we quantify the metrics as received signal strength indication, packet delivery rate, and communication latency. The results reveal that the communication reliability in urban expressways is very unstable because of the changing LOS conditions. This study provides a useful reference for the IEEE 802.11p-based cooperative systems in urban expressways.
To simulate the passenger behavior in subway system, a Dynamic Parameters Cellular Automaton (DPCA) model is put forward in this paper. Pedestrian traffic flows during waiting, getting on or off, and traveling can be simulated. The typical scenario in Beijing Subway Line 13 is modeled to analyze the passenger behavior in subway system. By comparing simulation results with statistical ones, the correctness and practicality of the DPCA model are verified. At last, the additional results made by DPCA model can make contribution to passenger comfort analysis and pedestrian facility planning and guidance.
With the proliferation of smart grid research, the Advanced Metering Infrastructure (AMI) has become the first ubiquitous and fixed computing platform. However, due to the unique characteristics of AMI, such as complex network structure, resource-constrained smart meter, and privacy-sensitive data, it is an especially challenging issue to make AMI secure. Energy theft is one of the most important concerns related to the smart grid implementation. It is estimated that utility companies lose more than $25 billion every year due to energy theft around the world. To address this challenge, in this paper, we discuss the background of AMI and identify major security requirements that AMI should meet. Specifically, an attack tree based threat model is first presented to illustrate the energy-theft behaviors in AMI. Then, we summarize the current AMI energy-theft detection schemes into three categories, i.e., classification-based, state estimation-based, and game theory-based ones, and make extensive comparisons and discussions on them. In order to provide a deep understanding of security vulnerabilities and solutions in AMI and shed light on future research directions, we also explore some open challenges and potential solutions for energy-theft detection.
Transcription Factors (TFs) are a very diverse family of DNA-binding proteins that play essential roles in the regulation of gene expression through binding to specific DNA sequences. They are considered as one of the prime drug targets since mutations and aberrant TF-DNA interactions are implicated in many diseases. Identification of TF-binding sites on a genomic scale represents a critical step in delineating transcription regulatory networks and remains a major goal in genomic annotations. Recent development of experimental high-throughput technologies has provided valuable information about TF-binding sites at genome scale under various physiological and developmental conditions. Computational approaches can provide a cost-effective alternative and complement the experimental methods by using the vast quantities of available sequence or structural information. In this review we focus on structure-based prediction of transcription factor binding sites. In addition to its potential in genome-scale predictions, structure-based approaches can help us better understand the TF-DNA interaction mechanisms and the evolution of transcription factors and their target binding sites. The success of structure-based methods also bears a translational impact on targeted drug design in medicine and biotechnology.
Several public-key encryption schemes used to solve the problem of ciphertext data processing on the fly are discussed. A new targeted fully homomorphic encryption scheme based on the discrete logarithm problem is presented. Public-key encryption cryptosystems are classified to examine homomorphic encryption. Without employing techniques proposed by Gentry such as somewhat homomorphic and bootstrapping techniques, or relinearization technique proposed by Brakerski et al., a new method called "Double Decryption Algorithm" is employed in our cryptography to satisfy a fully or targeted fully homomorphic property. Inspired by ElGamal and BGN cryptography, we obtain the desired fully homomorphic property by selecting a new group and adding an extra component to the ciphertext. Proof of semantic security is also demonstrated.
Genome-Wide Association Studies (GWASs) aim to identify genetic variants that are associated with disease by assaying and analyzing hundreds of thousands of Single Nucleotide Polymorphisms (SNPs). Although traditional single-locus statistical approaches have been standardized and led to many interesting findings, a substantial number of recent GWASs indicate that for most disorders, the individual SNPs explain only a small fraction of the genetic causes. Consequently, exploring multi-SNPs interactions in the hope of discovering more significant associations has attracted more attentions. Due to the huge search space for complicated multi-locus interactions, many fast and effective methods have recently been proposed for detecting disease-associated epistatic interactions using GWAS data. In this paper, we provide a critical review and comparison of eight popular methods, i.e., BOOST, TEAM, epiForest, EDCF, SNPHarvester, epiMODE, MECPM, and MIC, which are used for detecting gene-gene interactions among genetic loci. In views of the assumption model on the data and searching strategies, we divide the methods into seven categories. Moreover, the evaluation methodologies, including detecting powers, disease models for simulation, resources of real GWAS data, and the control of false discover rate, are elaborated as references for new approach developers. At the end of the paper, we summarize the methods and discuss the future directions in genome-wide association studies for detecting epistatic interactions.
In the previous construction of attributed-based encryption for circuits on lattices, the secret key size was exponential to the number of AND gates of the circuit. Therefore, it was suitable for the shallow circuits whose depth is bounded. For decreasing the key size of previous scheme, combining the techniques of Two-to-One Recoding (TOR), and sampling on lattices, we propose a new Key-Policy Attribute-Based Encryption (KP-ABE) scheme for circuits of any arbitrary polynomial on lattices, and prove that the scheme is secure against chosen plaintext attack in the selective model under the Learning With Errors (LWE) assumptions. In our scheme, the key size is proportional to the number of gates or wires in the circuits.
Mass spectrometry is one of the widely utilized important methods to study protein functions and components. The challenge of mono-isotope pattern recognition from large scale protein mass spectral data needs computational algorithms and tools to speed up the analysis and improve the analytic results. We utilized nave Bayes network as the classifier with the assumption that the selected features are independent to predict mono-isotope pattern from mass spectrometry. Mono-isotopes detected from validated theoretical spectra were used as prior information in the Bayes method. Three main features extracted from the dataset were employed as independent variables in our model. The application of the proposed algorithm to publicMo dataset demonstrates that our nave Bayes classifier is advantageous over existing methods in both accuracy and sensitivity.
The main purpose of this paper is to exposit two very different, but very general, motivational schemes in the art of parameterization and a concrete example connecting them. We introduce a dynamic version of the Dominating Set problem and prove that it is fixed-parameter tractable (FPT). The problem is motivated by settings where problem instances evolve. It also arises in the quest to improve a natural greedy heuristic for the Dominating Set problem.
Kernelization algorithms for graph modification problems are important ingredients in parameterized computation theory. In this paper, we survey the kernelization algorithms for four types of graph modification problems, which include vertex deletion problems, edge editing problems, edge deletion problems, and edge completion problems. For each type of problem, we outline typical examples together with recent results, analyze the main techniques, and provide some suggestions for future research in this field.
An audio information retrieval model based on Manifold Ranking (MR) is proposed, and ranking results are improved using a Relevance Feedback (RF) algorithm. Timbre components are employed as the model's main feature. To compute timbre similarity, extracting the spectrum features for each frame is necessary; the large set of frames is clustered using a Gaussian Mixture Model (GMM) and expectation maximization. The typical spectra frame from GMM is drawn as data points, and MR assigns each data point a relative ranking score, which is treated as a distance instead of as traditional similarity metrics based on pair-wise distance. Furthermore, the MR algorithm can be easily generalized by adding positive and negative examples from the RF algorithm and improves the final result. Experimental results show that the proposed approach effectively improves the ranking capabilities of existing distance functions.
Protein sequence motifs extraction is an important field of bioinformatics since its relevance to the structural analysis. Two major problems are related to this field: (1) searching the motifs within the same protein family; and (2) assuming a window size for the motifs search. This work proposes the Hierarchically Clustered Hidden Markov Model (HC-HMM) approach, which represents the behavior and structure of proteins in terms of a Hidden Markov Model chain and hierarchically clusters each chain by minimizing distance between two given chains’ structure and behavior. It is well known that HMM can be utilized for clustering, however, methods for clustering on Hidden Markov Models themselves are rarely studied. In this paper, we developed a hierarchical clustering based algorithm for HMMs to discover protein sequence motifs that transcend family boundaries with no assumption on the length of the motif. This paper carefully examines the effectiveness of this approach for motif extraction on 2593 proteins that share no more than 25% sequence identity. Many interesting motifs are generated. Three example motifs generated by the HC-HMM approach are analyzed and visualized with their tertiary structure. We believe the proposed method provides a unique protein sequence motif extraction strategy. The related data mining fields using Hidden Markova Model may also benefit from this clustering on HMM themselves approach.
This study modeled the spread of an influenza epidemic in the population of Oran, Algeria. We investigated the mathematical epidemic model, SEIR (Susceptible-Exposed-Infected-Removed), through extensive simulations of the effects of social network on epidemic spread in a Small World (SW) network, to understand how an influenza epidemic spreads through a human population. A combined SEIR-SW model was built, to help understand the dynamics of infectious disease in a community, and to identify the main characteristics of epidemic transmission and its evolution over time. The model was also used to examine social network effects to better understand the topological structure of social contact and the impact of its properties. Experiments were conducted to evaluate the combined SEIR-SW model. Simulation results were analyzed to explore how network evolution influences the spread of desease, and statistical tests were applied to validate the model. The model accurately replicated the dynamic behavior of the real influenza epidemic data, confirming that the susceptible size and topological structure of social networks in a human population significantly influence the spread of infectious diseases. Our model can provide health policy decision makers with a better understanding of epidemic spread, allowing them to implement control measures. It also provides an early warning of the emergence of influenza epidemics.
When consumers make purchase decisions, they generally refer to the reviews generated by other consumers who have already purchased similar products in order to get more information. Online transaction platforms provide a highly convenient channel for consumers to generate and retrieve product reviews. In addition, consumers can also vote reviews perceived to be helpful in making their decision. However, due to diverse characteristics, consumers can have different preferences on products and reviews. Their voting behavior can be influenced by reviews and existing review votes. To explore the influence mechanism of the reviewer, the review, and the existing votes on review helpfulness, we propose three hypotheses based on the consumer perspective and perform statistical tests to verify these hypotheses with real review data from Amazon. Our empirical study indicates that review helpfulness has significant correlation and trend with reviewers, review valance, and review votes. In this paper, we also discuss the implications of our findings on consumer preference and review helpfulness.
Quality of Service (QoS)-based service selection is the key to large-scale service-oriented Internet of Things (IOT), due to the increasing emergence of massive services with various QoS. Current methods either have low selection accuracy or are highly time-consuming (e.g., exponential time complexity), neither of which are desirable in large-scale IOT applications. We investigate a QoS-based service selection method to solve this problem. The main challenges are that we need to not only improve the selection accuracy but also decrease the time complexity to make them suitable for large-scale IOT applications. We address these challenges with the following three basic ideas. First, we present a lightweight description method to describe the QoS, dramatically decreasing the time complexity of service selection. Further more, based on this QoS description, we decompose the complex problem of QoS-based service selection into a simple and basic sub-problem. Finally, based on this problem decomposition, we present a QoS-based service matching algorithm, which greatly improves selection accuracy by considering the whole meaning of the predicates. The traces-driven simulations show that our method can increase the matching precision by 69% and the recall rate by 20% in comparison with current methods. Moreover, theoretical analysis illustrates that our method has polynomial time complexity, i.e., O?(m2×n), where m and n denote the number of predicates and services, respectively.
Intuitively, not only do ratings include abundant information for learning user preferences, but also reviews ccompanied by ratings. However, most existing recommender systems take rating scores for granted and discard the wealth of information in accompanying reviews. In this paper, in order to exploit user profiles' information embedded in both ratings and reviews exhaustively, we propose a Bayesian model that links a traditional Collaborative Filtering (CF) technique with a topic model seamlessly. By employing a topic model with the review text and aligning user review topics with "user attitudes” (i.e., abstract rating patterns) over the same distribution, our method achieves greater accuracy than the traditional approach on the rating prediction task. Moreover, with review text information involved, latent user rating attitudes are interpretable and "cold-start” problem can be alleviated. This property qualifies our method for serving as a "recommender” task with very sparse datasets. Furthermore, unlike most related works, we treat each review as a document, not all reviews of each user or item together as one document, to fully exploit the reviews' information. Experimental results on 25 real-world datasets demonstrate the superiority of our model over state-of-the-art methods.
This study uses the Elaboration Likelihood Model (ELM) and social presence theory to examine the microblogging reposting mechanism. Subjective and objective data were collected from 216 respondents in a field experiment. The results indicate that information quality and source credibility of microblogging messages affect users' reposting intention by affecting their perceptions of the usefulness and enjoyment of the information. Perceived enjoyment has a greater impact on reposting intention than perceived usefulness. Furthermore, users are able to perceive social presence when interacting with microblogging messages. Social presence plays a full mediating role between information quality and perceived enjoyment, and a partial mediating role between information quality and perceived usefulness.
A Projection Pursuit Dynamic Cluster (PPDC) model optimized by Memetic Algorithm (MA) was proposed to solve the practical problems of nonlinearity and high dimensions of sample data, which appear in the context of evaluation or prediction in complex systems. Projection pursuit theory was used to determine the optimal projection direction; then dynamic clusters and minimal total distance within clusters (min TDc) were used to build a PPDC model. 17 agronomic traits of 19 tomato varieties were evaluated by a PPDC model. The projection direction was optimized by Simulated Annealing (SA) algorithm, Particle Swarm Optimization (PSO), and MA. A PPDC model, based on an MA, avoids the problem of parameter calibration in Projection Pursuit Cluster (PPC) models. Its final results can be output directly, making the cluster results objective and definite. The calculation results show that a PPDC model based on an MA can solve the practical difficulties of nonlinearity and high dimensionality of sample data.
Many cyber physical networks will involve ad hoc deployments utilizing peer-to-peer communications. Examples include transportation systems where a group of moving cars communicate in order to avoid collisions, teams of robotic agents that work together in support of disaster recovery, and sensor networks deployed for health-care monitoring, monitoring the operation of a factory plant or to coordinate and actuate mechanisms for energy conservation in a building. These networks may face a variety of threats that puncture their connectivity and, should their performance degrade, the result could be catastrophic. Consider, for example, a vehicular ad hoc network where communication assists collision avoidance. In such a case, degradation could lead to vehicle accidents. Therefore, in order to overcome network performance degradations and the puncture of a network (such as blackhole or jamming) which is under attack, we propose an algorithm called the Fiedler Value Power Adjustment Topology Adaption (FVPATA). FVPATA aims to dynamically adapt an ad hoc network’s topology, even if the attacker varies its location and in the case of an interference-style attack by increasing the interference power. The algorithm utilizes the formulation from the graph theory which works with the Fiedler value to guide each node in wireless ad hoc network utilizing power adjustments to enhance the network’s overall robustness. The advantage of the proposed mechanism is that it is a light-weight approach which is totally distributed, based on topology updates inherent in the Optimized Link State Routing (OLSR) protocol and, hence, it is unnecessary to introduce additional messages. Additionally, an algorithm was developed to resolve problems involving asymmetric links that arise in ad hoc networks by eliminating unnecessary energy consumption of Fiedler nodes. Simulation results using NS3 show that the proposed mechanism successfully decreases the average amount of hops used by 50% and the delay of flows when nodes are migrating at a modest rate below 60 m/min.
Polling system models have a wide range of important applications including time-sharing computer systems, industrial control, communications, and computer networks. In this paper, we propose a two-class priority-based polling system that uses gated and exhaustive services to achieve the priority-based scheme. This model is set up according to the method of the imbedded Markov chain theory and the generation function and explicitly analyzes key system performance characteristics including mean queue length, cyclic time, and throughput. Theoretical and simulation results are identical and demonstrate the efficiency of the model.
This study introduces a real-time controller design method under the effects of network time delay and external disturbance. The study first introduces the digital, virtual, intelligent trend of airplane assembly and reveals the status and problems of digital airplane assembly studies. The Cyber-Physical System (CPS) structure is then proposed for digital airplane assembly, and the real-time control issues are discussed. Then, the question of real-time control undertaken by a parallel robot is simplified to a control question with bounded time delay and complex interference, and a mathematical description is presented. Next, a robust H∞ controller with a disturbance degree of decay γ is designed according to the mathematical description. Finally, a simulation is conducted. All of the experiment results show the feasibility of the above proposed methods.
Chosen Ciphertext Attack (CCA) security on the standard model is widely accepted as the standard security notion for the public key cryptosystem. The existing CCA-secure public key cryptosystems on the standard model are expensive in terms of efficiency and practicality. In this paper, an efficient and practical public key cryptosystem is presented over the group of signed quadratic residues. It is provably secure against CCA on the standard model. Furthermore, public verifiability for this scheme is also realized in the way that projects the verification privacy key into public key on trapdoor pretending. It will be useful to devise efficient CCA-secure threshold and proxy re-encryption schemes on the standard model.
Community structure is one of the most important features in real networks and reveals the internal organization of the vertices. Uncovering accurate community structure is effective for understanding and exploiting networks. Tolerance Granulation based Community Detection Algorithm (TGCDA) is proposed in this paper, which uses tolerance relation (namely tolerance granulation) to granulate a network hierarchically. Firstly, TGCDA relies on the tolerance relation among vertices to form an initial granule set. Then granules in this set which satisfied granulation coefficient are hierarchically merged by tolerance granulation operation. The process is finished till the granule set includes one granule. Finally, select a granule set with maximum granulation criterion to handle overlapping vertices among some granules. The overlapping vertices are merged into corresponding granules based on their degrees of affiliation to realize the community partition of complex networks. The final granules are regarded as communities so that the granulation for a network is actually the community partition of the network. Experiments on several datasets show our algorithm is effective and it can identify the community structure more accurately. On real world networks, TGCDA achieves Normalized Mutual Information (NMI) accuracy 17.55% higher than NFA averagely and on synthetic random networks, the NMI accuracy is also improved. For some networks which have a clear community structure, TGCDA is more effective and can detect more accurate community structure than other algorithms.
With the growing aging population, age-related diseases have increased considerably over the years. In response to these, Ambient Assistive Living (AAL) systems are being developed and are continually evolving to enrich and support independent living. While most researchers investigate robust Activity Recognition (AR) techniques, this paper focuses on some of the architectural challenges of the AAL systems. This work proposes a system architecture that fuses varying software design patterns and integrates readily available hardware devices to create Wireless Sensor Networks (WSNs) for real-time applications. The system architecture brings together the Service-Oriented Architecture (SOA), semantic web technologies, and other methods to address some of the shortcomings of the preceding system implementations using off-the-shelf and open source components. In order to validate the proposed architecture, a prototype is developed and tested positively to recognize basic user activities in real time. The system provides a base that can be further extended in many areas of AAL systems, including composite AR.
Cyber-Physical System (CPS) and Cyber-Physical-Social System (CPSS) computing are now challenging existing research in many realms, including Intelligent Transportation Systems (ITS). In this survey, we highlight some advances in the coevolution of CPS, CPSS, and ITS, with an emphasis on traffic data. We first explain the hierarchical architecture of CPS-ITS in terms of five layers: perception, communication, computing, control, and application. Then, we analyze the characteristics of traffic data in CPS-ITS, and enumerate some new technologies for data operation and management. Two typical cases of CPS-ITS, vehicular-communication-based traffic control systems and smart parking systems, are illustrated to describe how CPS is changing our lives and influencing the development of future ITS.
With the rapid development of cloud computing and big data processing, an increasing number of application frameworks are being considered to run in a “cloud way”. This development brings about several challenges to the enterprise private cloud computing platform, e.g., being able to run most existing heterogeneous applications, providing scalability and elasticity support for newly emerged frameworks, and most importantly, sharing cluster resources effectively. In this paper, we propose a new service model, namely, Cluster as a Service (ClaaS), which is suitable for medium- and small-sized data centers to solve these problems in a relatively easy and general way. The idea behind this model is virtualizing the cluster environment for distributed application frameworks. Most applications can directly run in the virtual cluster environment without any modification, which is a great advantage. Based on lightweight containers, we implement a real system of ClaaS named Docklet to prove the feasibility of this service model. Meanwhile, we preliminarily design the definition of applications to make them easy to deploy. Finally, we present several examples and evaluate the entire system.
ID-based constant-round group key agreement protocols are efficient in both computation and communication, but previous protocols did not provide valid message authentication. An improvement based on attack analysis is proposed in this paper. The improved method takes full advantage of the data transmitted at various stages of the protocol. By guaranteeing the freshness of authentication messages, the authenticity of the generator of authentication messages, and the completeness of the authenticator, the improved protocol can resist various passive and active attacks. The forward secrecy of the improved protocol is proved under a Katz-Yung (KY) model. Compared with existing methods, the improved protocol is more effective and applicable.
Computational Social Choice is an interdisciplinary research area involving Economics, Political Science, and Social Science on the one side, and Mathematics and Computer Science (including Artificial Intelligence and Multiagent Systems) on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics, on the occasion of his 60th birthday.
Modern seismic sensors are capable of recording high precision vibration data continuously for several months. Seismic raw data consists of information regarding earthquake's origin time, location, wave velocity, etc. Currently, these high volume data are gathered manually from each station for analysis. This process restricts us from obtaining high-resolution images in real-time. A new in-network distributed method is required that can obtain a high-resolution seismic tomography in real time. In this paper, we present a distributed multigrid solution to reconstruct seismic image over large dense networks. The algorithm performs in-network computation on large seismic samples and avoids expensive data collection and centralized computation. Our evaluation using synthetic data shows that the proposed method accelerates the convergence and reduces the number of messages exchanged. The distributed scheme balances the computation load and is also tolerant to severe packet loss.
To satisfy the rapid growth of cloud technologies, a large number of web applications have been developed and deployed, and these applications are being run in clouds. Due to the scalability provided by clouds, a single web application may be concurrently visited by several millions or billions of users. Thus, the testing and performance evaluations of these applications are increasingly important. User model based evaluations can significantly reduce the manual work required, and can enable us to determine the performance of applications under real runtime environments. Hence, it has become one of the most popular evaluation methods in both industry and academia. Significant efforts have focused on building different kinds of models using mining web access logs, such as Markov models and Customer Behavior Model Graph (CBMG). This paper proposes a new kind of model, named the User Representation Model Graph (URMG), which is built based on CBMG. It uses an algorithm to refine CBMG and optimizes the evaluations execution process. Based on this model, an automatic testing and evaluation system for web applications is designed, implemented, and deployed in our test cloud, which is able to execute all of the analysis and testing operations using only web access logs. In our system, the error rate caused by random access to applications in the execution phase is also reduced, and the results show that the error rate of the evaluation that depends on URMG is 50% less than that which depends on CBMG.
Subspace appearance models are widely used in computer vision and image processing tasks to compactly represent the appearance variations of target objects. In order to ensure algorithm performance, they are typically stored in high-precision formats; this results in a large storage footprint, rendering redistribution costly and difficult. Since for most image and vision applications, pixel values are quantized to 8 bits by the acquisition apparatuses, we show that it is possible to construct a fixed-width, effectively lossless representation of the bases vectors, in the sense that reconstructions from the original bases and from the quantized bases never deviate by more than half of the quantization step-size. In addition to directly applying this result to losslessly compress individual models, we also propose an algorithm to compress appearance models by utilizing prior information on the modeled objects in the form of prior appearance subspaces. Experiments conducted on the compression of person-specific face appearance models demonstrate the effectiveness of the proposed algorithms.
High energy consumption is one of the key issues of cloud computing systems. Incoming jobs in cloud computing environments have the nature of randomness, and compute nodes have to be powered on all the time to await incoming tasks. This results in a great waste of energy. An energy-saving task scheduling algorithm based on the vacation queuing model for cloud computing systems is proposed in this paper. First, we use the vacation queuing model with exhaustive service to model the task schedule of a heterogeneous cloud computing system. Next, based on the busy period and busy cycle under steady state, we analyze the expectations of task sojourn time and energy consumption of compute nodes in the heterogeneous cloud computing system. Subsequently, we propose a task scheduling algorithm based on similar tasks to reduce the energy consumption. Simulation results show that the proposed algorithm can reduce the energy consumption of the cloud computing system effectively while meeting the task performance.
Vehicle Ad hoc NETworks (VANET) can enhance traffic safety and improve traffic efficiency through cooperative communication among vehicles, roadside infrastructure, and traffic management centers. To guarantee secure service provision in VANET, message authentication is important. Moreover, a vehicle user’s private information can also be leaked during service provision. A protection mechanism is needed to prevent such leakage. Therefore, we propose a conditional privacy-preserving and authentication scheme for secure service provision in VANETs. The proposed scheme not only satisfies the security requirements of VANETs, but also optimizes the calculation process of signature generation and verification. We carry out a detailed comparative analysis. The result shows that the proposed scheme is more efficient than existing schemes in terms of communication overhead and computational cost. Therefore, our scheme is suitable for secure service provision in VANETs.
Allele specific expression is essential for cellular programming and development and the diversity of cellular phenotypes. Traditional analysis methods utilize RNA and depend on single nucleotide polymorphisms, thus to suffer from limited amount of materials for analysis. The rapid development of next-generation sequencing technologies provides more comprehensive and powerful approaches to analyze the genomic, epigenetic, and transcriptomic data, and further to detect and measure allele specific expressions. It will potentially enhance the understanding of the allele specific expressions, their complexities, and the effect on biological processes. In this paper, we extensively review the state-of-art enabling technologies and tools to analyze, detect, and measure allele specific expressions, compare their features, and point out the future trend of the methods.
The widespread use of Location-Based Services (LBSs), which allows untrusted service providers to collect large quantities of information regarding users' locations, has raised serious privacy concerns. In response to these issues, a variety of LBS Privacy Protection Mechanisms (LPPMs) have been recently proposed. However, evaluating these LPPMs remains problematic because of the absence of a generic adversarial model for most existing privacy metrics. In particular, the relationships between these metrics have not been examined in depth under a common adversarial model, leading to a possible selection of the inappropriate metric, which runs the risk of wrongly evaluating LPPMs. In this paper, we address these issues by proposing a privacy quantification model, which is based on Bayes conditional privacy, to specify a general adversarial model. This model employs a general definition of conditional privacy regarding the adversary's estimation error to compare the different LBS privacy metrics. Moreover, we present a theoretical analysis for specifying how to connect our metric with other popular LBS privacy metrics. We show that our privacy quantification model permits interpretation and comparison of various popular LBS privacy metrics under a common perspective. Our results contribute to a better understanding of how privacy properties can be measured, as well as to the better selection of the most appropriate metric for any given LBS application.
Gene expression is a critical process in biological system that is influenced and modulated by many factors including genetic variation. Expression Quantitative Trait Loci (eQTL) analysis provides a powerful way to understand how genetic variants affect gene expression. For genome wide eQTL analysis, the number of genetic variants and that of genes are large and thus the search space is tremendous. Therefore, eQTL analysis brings about computational and statistical challenges. In this paper, we provide a comprehensive review of recent advances in methods for eQTL analysis in population-based studies. We first present traditional pairwise association methods, which are widely used in human genetics. To account for expression heterogeneity, we investigate the methods for correcting confounding factors. Next, we discuss newly developed statistical learning methods including Lasso-based models. In the conclusion, we provide an overview of future method development in analyzing eQTL associations. Although we focus on human genetics in this review, the methods are applicable to many other organisms.