Unmanned aerial vehicle (UAV)-enhanced mobile edge computing (U-MEC) integrates flexible deployment and wide coverage, effectively reducing computation latency for edge network devices. Whereas, optimization models that only consider a few or tens of nodes will hide the performance deficiencies of high-complexity algorithms in large-scale IoT networks. This paper aims to investigate the binary task offloading problem based on minimizing the shrinkage ratio in large-scale IoT networks. By optimizing the computation mode selection, bandwidth, and computing resource allocation of users, the goal is to maximize the sum of benefits brought to all users by the U-MEC network. To address the challenging mixed-integer nonlinear programming (MINLP) problem, an efficient solution based on the region coverage and a posterior method that eliminates unknown hovering constraints is adopted to decompose the problem into multiple independent small-scale subproblems. For each subproblem, the coordinate descent (CD) technique and a greedy strategy are employed, which is based on Karush-KuhnTucker (KKT) conditions to provide the closed-form solutions of bandwidth and computing resource allocation at the edge server. Experimental results demonstrate the effectiveness of our approach in terms of solution accuracy and execution time.

In the emerging microservice-based architecture of cloud HPC systems, a challenging problem of critical importance for system service capability is how we can schedule microservices to minimize the end-to-end response time for user requests while keeping cost within the specified budget. We address this problem for multi-instance microservices requested by a single application to which no existing result is known to our knowledge. We propose an effective two-stage solution of first allocating budget (resources) to microservices within the budget constraint and then deploying microservice instances on servers to minimize system operational overhead. For budget allocation, we formulate it as the Discrete Time Cost Tradeoff (DTCT) problem which is NP-hard, present a linear program (LP) based algorithm, and provide a rigorous proof of its worst-case performance guarantee of 4 from the optimal solution. For microservice deployment, we show that it is harder than the NP-hard problem of 1-D binpacking through establishing its mathematical model, and propose a heuristic algorithm of Least First Mapping that greedily places microservice instances on fewest possible servers to minimize system operation cost. The experiment results of extensive simulations on DAG-based applications of different sizes demonstrate the superior performance of our algorithm in comparison with the existing approaches. • Formulate the problem of budget allocation to multi-instance microservices as the Discrete Time Cost Tradeoff (DTCT) problem, a well-known NP-hard problem. • Transform this problem to a linear program (LP) and present an approximation algorithm to minimize microservice completion time by determining the desired number of instances for each microservice within the given budget constraint. • Provide a rigorous proof of worst-case performance guarantee of 4 of our algorithm. • Present a heuristic algorithm of Least First Mapping for the problem of microservice deployment to place the microservice instances on fewest possible servers at minimum system operation cost. • Experimentally validate our algorithm and demonstrate its superiority to the existing approaches in terms of maximum completion time of microservices under budget constraint and the number of launched servers.

In contemporary data center networks (DCNs), scheduling groups of parallel flows (coflows) has emerged as a critical task for improving application-level communication efficiency. Recently, research interest has shifted to hybrid-switched DCN architectures that integrate optical circuit switches (OCSs) and electrical packet switches (EPSs) to respectively manage both high-volume and low-volume traffic efficiently. To minimize the overall communication latency, it is essential to effectively coordinate coflows over hybrid network links. The complexity of this task, however, is substantially greater than that of scheduling on monolithic network links of either OCS or EPS. The complexity arises from allocating flows between OCS and EPS in a coordinated way, while considering both the reconfiguration delay of circuit switching in OCS and the bandwidth limitation of packet switching in EPS, and completing the transmission in the shortest time. The current solutions for scheduling coflows in hybrid-switched DCNs are primarily based on heuristics and lack formal performance guarantees. In this paper, we first establish a coflow scheduling framework for hybrid-switched DCNs, which can transform any given circuit schedule (denoted as SC) designed for pure OCS into a corresponding hybrid scheduling scheme SH. On this basis, we further present two approximation algorithms w.r.t SC under two primary reconfiguration models (i.e., all-stop model and not-all-stop model) of OCS to minimize the coflow completion time (CCT) in a hybrid-switched DCN. Theoretical analysis demonstrates that our algorithms can achieve the optimal traffic partitioning for hybrid switch environments w.r.t SC. Furthermore, we theoretically prove that the proposed algorithms can transform any SC for pure OCS with an approximation rate of λ into a corresponding coflow scheduling scheme SH tailored for hybrid switches with the approximation rate of λ+1. Extensive simulations utilizing Facebook data traces show that our algorithm performs well in minimizing the CCT compared to state-of-the-art schemes.

In service oriented high-performance computing (HPC) clusters, end users have various Quality of Service (QoS) requirements. Most of the existing research work focuses on quantitative QoS requirements, such as deadlines, for rigid jobs. While, in many cases, it is more convenient for users to qualitatively state QoS requirements (such as performance-sensitive) at the submission of their jobs. Almost all kinds of QoS requirements will be greatly impacted by job scheduling, which determine the degree of job parallelism, execution time and waiting time, etc. Most modern parallel applications are moldable in the sense that they can choose a resource allocation before execution. Traditional sequential job scheduling mechanism with fixed resource allocation appears to be an obstacle to improve QoS for end users. To address this issue, we propose a novel qualitative QoS-aware sub-queue simultaneous scheduling method for moldable parallel jobs (with variable resource allocation) on HPC Clusters. We first define the qualitative QoS models for end users, then present our sub-queue simultaneous scheduling method, including job sequencing and resource allocation algorithms for a set of moldable parallel jobs on multi-core clusters. Our method can efficiently sequence queuing jobs and allocate appropriate resources for simultaneously running some performance-sensitive jobs in a sub-queue rather than running them one by one. Experimental results demonstrate the effectiveness of our method to improving QoS for end users.

Traffic offloading via WiFi networks is an effective way to alleviate drone cellular network congestion. Existing studies are based on a limited model which assumes the presence of only a single drone and a single WiFi network in the region. We study the more general scenario of traffic offloading using multiple WiFi networks in the cellular networks composed of multiple drones which requires collaborative service provision, and address the problem of jointly minimizing the total distance traveled by the drones and the maximum latency. We propose an effective approach to solving this problem by combining optimization and machine learning. We first determine the user-drone allocation by applying meanshift clustering [1], solve the UAV navigation problem by Bellman-Floyd’s minimum-cost maximum-flow algorithm [2], and then deploy reinforcement learning to compute the optimal percentages of traffic offloading for different users. Simulation results demonstrate that our algorithm avoids violating the constraints and keeps the maximum delay in an acceptable range.

The characteristics of Federated Learning (FL) make FL highly susceptible to malicious poisoning attacks from adversaries. Existing FL defense methods can detect attacks of fixed poisoning patterns, hence are lack of flexibility. Additionally, they typically remove the malicious node models upon detection, leading to a certain degree of data loss. To address these issues, we propose a novel defense method against backdoor attacks in FL systems, effectively enhancing their robustness to malicious poisoning attacks. Specifically, we introduce a malicious update detection method based on feature activation matrices. This method compares the distribution differences of updates from different clients on the same validation data and detects malicious clients based on the outlier rates of their updates. Furthermore, to mitigate the data loss caused by the removal of malicious clients, the server assesses the distance between the distribution of feature activation matrices from the client’s historical updates and the overall model distribution in the current iteration. Based on this distance, the server performs model recovery to a certain extent. Extensive experiments on two benchmark datasets demonstrate that our method accurately detects malicious clients under various state-of-the-art model poisoning attacks. Additionally, the model recovery method provides a notable improvement to the system, ensuring the robustness and performance of the FL system.

To resolve the performance bottlenecks of power consumption and bandwidth shortage in data center networks (DCNs) using the traditional Electronic Packet Switching (EPS), Optical Circuit Switching (OCS) technology has gained extensive attention in recent years and showed great promises for the development of next-generation data centers capable of supporting escalating network traffic. In this context, coflow scheduling emerges as a pivotal technique for enhancing data transmission efficiency in DCNs. Nonetheless, the intrinsic constraints of OCS networks, such as port limitations and reconfiguration delays, introduce novel challenges to coflow scheduling. There are two optical path reconfiguration modes in OCS: All-Stop in which reconfiguration of a path will block the communications of all paths, and Not-All-Stop in which only the path under reconfiguration is blocked. Most of the existing studies focus on coflow scheduling in All-Stop mode, and little has been done for online scenarios in Not-All-Stop mode. This study delves into the online multi-coflow scheduling problem within DCNs supported by Not-All-Stop mode OCS, aiming to minimize the average Coflow Completion Time (CCT). We introduce an effective online algorithm comprising two main components: a coflow interscheduling priority strategy that takes full consideration of Not-All-Stop mode’s characteristics and network fairness, and a coflow intra-scheduling greedy algorithm (R-Greedy) that focuses on maximizing network resource utilization to determine the specific scheduling plans. The effectiveness of our algorithm is demonstrated through extensive simulation experiments.

Summary Burst‐buffering is a promising storage solution that introduces an intermediate high‐throughput storage buffer layer to mitigate the I/O bottleneck problem that the current high‐performance computing (HPC) platforms suffer. The existing Markov‐Chain based probabilistic I/O scheduling utilizes the load state of burst‐buffers and the periodic characteristics of applications to reduce I/O congestion due to the limited capacity of burst‐buffers. However, this probabilistic approach requires consistent I/O characteristics of applications, including similar I/O duration and long application length, in order to obtain an accurate I/O load estimation. These consistency conditions do not often hold in realistic situations. In this paper, we propose a generic framework of dynamic probabilistic I/O scheduling based on application clustering (DPSAC) to make applications meet the consistency requirements. According to the I/O phase length of each application, our scheme first deploys a one‐dimensional K‐means clustering algorithm to cluster the applications into clusters. Next, it calculates the expected workload of each cluster through the probabilistic model of applications and then partitions the burst‐buffers proportionally. Then, to handle dynamic changes (join and exit) of applications, it updates the clusters based on a heuristic strategy. Finally, it applies the probabilistic I/O scheduling, which is based on the distribution of application workload and the state of burst‐buffers, to schedule I/O for all the concurrent applications to mitigate I/O congestion. The simulation results on synthetic data show that our DPSAC is effective and efficient.

A Structural Hole Spanner (SHS) is a set of nodes in a network that act as a bridge among different otherwise disconnected communities. Numerous solutions have been proposed to discover SHSs that generally require high run time on large-scale networks. Another challenge is discovering SHSs across different types of networks for which the traditional one-model-fit-all approach fails to capture the inter-graph difference, particularly in the case of diverse networks. Therefore, there is an urgent need of developing effective solutions for discovering SHSs in large-scale and diverse networks. Inspired by the recent advancement of graph neural network approaches on various graph problems, we propose graph neural network-based models to discover SHS nodes in large scale networks and diverse networks. We transform the problem into a learning problem and propose an efficient model GraphSHS, that exploits both the network structure and node features to discover SHS nodes in large scale networks, endeavouring to lessen the computational cost while maintaining high accuracy. To effectively discover SHSs across diverse networks, we propose another model Meta-GraphSHS based on meta-learning that learns generalizable knowledge from diverse training graphs (instead of directly learning the model) and utilizes the learned knowledge to create a customized model to identify SHSs in each new graph. We theoretically show that the depth of the proposed graph neural network model should be at least Ω(n/logn) to accurately calculate the SHSs discovery problem. We evaluate the performance of the proposed models through extensive experiments on synthetic and real-world datasets. Our experimental results show that GraphSHS discovers SHSs with high accuracy and is at least 167.1 times faster than the comparative methods on large-scale real-world datasets. In addition, Meta-GraphSHS effectively discovers SHSs across diverse synthetic networks with an accuracy of 96.2%.

Unmanned aerial vehicles (UAVs) have emerged as crucial components in advancing mobile edge computing (MEC), leveraging their proximity to edge nodes and scalable nature. This synergy holds significant promise within the Internet of Things (IoT) and Beyond 5G (B5G) domains. In this article, we concentrate on optimizing the shrinking ratio, a Quality of Experience (QoE) metric, within large-scale IoT networks empowered by UAV-enhanced MEC via joint optimizing task offloading, resource allocation, and UAV trajectories. This joint optimization problem presents significant challenges due to the intertwined nature of multiuser computing mode selection and strong coupling between user equipments (UEs) waiting time and UAV trajectory. To tackle these challenges, we formulate the problem as a mixed integer nonlinear programming (MINLP) problem and propose an iterative algorithm named BTOU by decomposing the original problem into two subproblems using the block coordinate descent (BCD) framework. For the task offloading and resource allocation subproblem, we present two algorithms: one employs a low-complexity greedy game-theoretic approach suitable for a large number of UEs, while the other leverages the penalty successive convex approximation (PSCA) technique along with first-order Taylor expansion approximation to achieve high-solution quality. For the UAV trajectory planning subproblem, we transform it into a Miller-Tucker–Zemlin (MTZ) model and devise a solution strategy. Extensive simulation results validate the effectiveness of our proposed algorithm, showcasing rapid convergence and a notable improvement in QoE of over 10% compared to benchmark methods.

Mobile edge computing (MEC) integrated with wireless power transfer (WPT) has became a promising trend to shorten task delay and prolong battery life of wireless devices (WDs). Introducing the relay technique to WPT-MEC system can improve offloading capability and energy efficiency, particularly in the scenarios of poor wireless channel conditions between the server and WDs. In this paper, we focus on maximizing the energy efficiency (EE) of a multi-user relay-aided WPT-MEC system. The joint optimization of the configuration of relay, wireless charge time fraction, and decision of WDs’ offloading strategy presents significant challenges due to the combination of multi-user computing mode selection and strong coupling of transmission time allocation for each WD. To address these challenges, we formulate the problem as a mixed integer nonlinear programming (MINLP) problem and propose an efficient iterative algorithm called MSRA to solve it. Our approach leverages Dinkelbach’s method to transform the original problem into a tractable problem. Furthermore, we employ the alternating direction method of multipliers (ADMM) technique to decompose the problem into multiple subproblems, thereby avoiding the combination of computing mode selection at each WD and hence enabling parallel computation. Within each iteration step of the ADMM-based algorithm, we develop a DAI-Based algorithm to handle the strong coupling with offloading time allocation that incorporates a Bisection Search algorithm with constant time complexity and solves a standard convex problem. Extensive simulation results demonstrate the effectiveness of our proposed algorithm as evidenced by its rapid convergence and impressive energy efficiency imporvement of over 15% compared to benchmark methods.

As a promising technique for offloading computation tasks from mobile devices, Unmanned Aerial Vehicle (UAV)-assisted Mobile Edge Computing (MEC) utilizes UAVs as computational resources. A popular method for enhancing the quality of service (QoS) of UAV-assisted MEC systems is to jointly optimize UAV deployment and computation task offloading. This imposes the challenge of dynamically adjusting UAV deployment and computation offloading to accommodate the changing positions and computational requirements of mobile devices. Due to the real-time requirements of MEC computation tasks, finding an efficient joint optimization approach is imperative. This paper proposes an algorithm aimed at minimizing the average response delay in a UAV-assisted MEC system. The approach revolves around the joint optimization of UAV deployment and computation offloading through convex optimization. We break down the problem into three sub-problems: UAV deployment, Ground Device (GD) access, and computation tasks offloading, which we address using the block coordinate descent algorithm. Observing the$NP$-hardness nature of the original problem, we present near-optimal solutions to the decomposed sub-problems. Simulation results demonstrate that our approach can generate a joint optimization solution within seconds and diminish the average response delay compared to state-of-the-art algorithms and other advanced algorithms, with improvements ranging from 4.70% to 42.94%.

Federated Learning (FL), a secure and emerging distributed learning paradigm, has garnered significant interest in the Internet of Things (IoT) domain. However, it remains vulnerable to adversaries who may compromise privacy and integrity. Previous studies on privacy-preserving FL (PPFL) have demonstrated limitations in client model personalization and resistance to poisoning attacks, including Byzantine and backdoor attacks. In response, we propose a novel PPFL framework, FedRectify, that employs a personalized dual-layer approach through the deployment of Trusted Execution Environments and an interactive training strategy. This strategy facilitates the learning of personalized client features via private and shared layers. Furthermore, to improve model’s robustness to poisoning attacks, we introduce a novel aggregation method that employs clustering to filter out outlier model parameters and robust regression to assess the confidence of cluster members, thereby rectifying poisoned parameters. We theoretically prove the convergence of FedRectify and empirically validate its performance through extensive experiments. The results demonstrate that FedRectify converges 1.47-2.63 times faster than state-of-the-art methods when countering Byzantine attacks. Moreover, it can rapidly reduce the attack success rate to a low level between 10% and 40% in subsequent rounds when confronting bursty backdoor attacks.

Scheduling of coflows, each a collection of parallel flows sharing the same objective, is an important task of data transmission that arises in the networks supporting data-intensive applications such as data center networks (DCNs). The hybrid switch design combining the optical circuit switch (OCS) and electrical packet switch (EPS) for transmitting high-volume and low-volume traffic separately has received considerable research attention. To support this design, efficient scheduling of coflows on hybrid network links is crucial for reducing the overall communication time. However, because it needs to consider both reconfiguration delay of circuit switching in the OCS and bandwidth limitation of packet switching in the EPS, coflow scheduling on hybrid network links is more challenging than on monotonic network links of either OCS or EPS. The existing coflow scheduling algorithms in hybrid switches are all heuristic and provide no performance guarantees. In this work, we first propose an approximation algorithm with a worst-case performance guarantee of$2\tau$, where$\tau\le N$is the maximum number of non-zero elements of each row and column of coflow’s demand matrix, for single coflow scheduling in an$N\times N$hybrid switch to minimize the coflow completion time (CCT). We then extend the algorithm for scheduling multiple coflows to minimize the total weighted CCT with a provable performance guarantee of$\mu\tau_{\max}$, where$\mu=4M\cdot\frac{w_{\max}}{w_{\min}}$,$\tau_{\max}=\max_{1\le m\le M}\tau_{m}\leq N$,$w_{\max}$and$w_{\min}$are respectively the maximum and minimum weights of the$M$coflows. Extensive simulations using Facebook data traces show that our algorithms outperform the state-of-the-art coflow scheduling schemes. Specifically, our algorithms transmit a single coflow up to 1.08$\times$faster than Solstice (hybrid switch) and 1.42$\times$faster than Reco-Sin (pure OCS), and multiple coflows up to 1.11$\times$faster than Solstice and 1.17$\times$faster than Reco-Mul$+$(pure OCS).

Workflow tasks are time-sensitive and their task completion utility, i.e., value of task completion, is inversely proportional to their completion time. Existing solutions to the NP-hard problem of utility-maximization task scheduling were achieved under the assumptions of linear Time Utility Function (TUF), i.e., utility is inversely proportional to completion time following a linear function, and prior knowledge of task execution time, which is unrealistic for many applications and dynamic systems. This paper proposes a novel model of combining greedy optimization with machine learning for scheduling time-sensitive tasks with convex TUF and unknown task execution time on heterogeneous cloud servers offline nonpreemptively to maximize the total utility of input tasks. For a set of time-sensitive tasks with data dependencies, we first employ multi-layer perceptron neural networks to predict task execution time by utilizing historical data. Then, by solving a linear program after relaxing the disjunctive constraint introduced by the nonpreemption requirement to calculate maximum utility increment, we propose a novel greedy algorithm of marginal incremental utility maximization that jointly determines the task-to-processor allocation plan and tasks' execution sequence on each processor. We then show that our algorithm has an expected approximation ratio of$\frac{(e-1)(\tau -2)}{e\tau }$for convex TUF and$\frac{e-1}{3e}\approx 0.21$for linear TUF, where$\tau$is the ratio of total completion utility over total delay cost under optimal scheduling. Our result presents the first polynomial-time approximation solution for this problem that achieves a performance guarantee of bounded ratio for convex TUF and constant ratio for linear TUF respectively. Extensive experiment results through both simulation and real cloud implementation demonstrate significant performance improvement of our algorithm over the known results.

Nowadays, with the rise of location-based services, the personalized sequential POI recommendation has become a pivotal element for enhancing customer experiences. Although many previous POI recommendation models have shown promising results and improvements in this area, several challenges still exist in this field. Firstly, the previous sequential recommenders do not well-utilize the geographical features that are highly affecting the user’s future choices of visits. Furthermore, the self-attention mechanism, which is a popular method used in sequential POI recommendation, has a limitation in treating the input user sequence as an unordered set. Using positional embedding is a typical way to overcome this limitation. However, the use of such embeddings may potentially restrict the model’s ability to learn meaningful patterns in user preferences among POIs. To address these challenges, we propose GeoMixer, a novel MLP-based sequential POI recommender that incorporates travel routing distance to capture geographical features and leverages Multi-layer Perceptron (MLP) architecture to model the spatial and sequential patterns in the sequential POI recommendations. By adopting MLP mixing layers, GeoMixer has the capability of memorizing the chronological order of the input POIs without the positional embedding and can emphasize the important latent features of each POI. The use of the travel routing information improves the model’s ability of capturing spatial patterns during the model learning process. Extensive experiments on real-world datasets show that GeoMixer outperforms state-of-theart methods in various metrics, highlighting the significance of incorporating travel routing distance and leveraging MLP architecture in sequential POI recommendation systems.

To adapt to the emerging microservice-based architectures, user application requests are transformed from the traditional service-based monolithic configuration to that of multi-stage inner-dependent microservices. However, in a cloud-edge continuum, the distribution of microservices introduces extra communication overhead that could violate the Service Level Objectives (SLOs). Existing microservice-based resource allocation techniques have either considered only the case that instances belonging to the same microservice are deployed on the same server, or have not considered the case with SLO constraints. In this paper, we consider the case where instances belonging to the same microservice can be deployed across servers with SLO constraints. We propose a novel linear program (LP) based resource configurator to determine the desired number of instances of each microservice that edge servers should resource based on performance estimation for application requests such that the total cost of allocated resources of all needed microservices is minimized under the constraint that the maximum microservice completion time satisfies the given service level objective (SLO). We prove that our resource configurator achieves the worst-case performance guarantee ${(\sqrt 2 + 1)^2}$ by rigorous derivation. In comparison with the state-of-the-art microservice allocation methods, experimental results show that our proposed resource configurator reduces the computational resource usage by 7.6%, and the memory resources by 11.3% while guaranteeing the SLOs.

Successful information propagation from source to destination in Vehicular Adhoc Network (VANET) can be hampered by the presence of neighbouring attacker nodes causing unwanted packet dropping. Potential attackers change their behaviour over time and remain undetected due to the adhoc nature of VANET. Capturing the dynamic attacker behaviour and updating the corresponding neighbourhood information without compromising the quality of service requirements is an ongoing challenge. This work proposes a Reinforcement Learning (RL) based neighbour selection framework for VANET with an adaptive trust management system to capture the behavioural changes of potential attackers and to dynamically update the neighbourhood information. In contrast to existing works, we consider trust and link-life time in unison as neighbour selection criteria to achieve trustworthy communication. Our adaptive trust model takes into account the social relationship, time and confidence in trust observation to avoid four types of attackers. To update the neighbourhood information, our framework sets the learning rate of the RL agent according to the velocities of the neighbour nodes to improve the model’s adaptability to network topology changes. Results demonstrate that our method can take less number of hops to the destination for large network sizes while can response is up to 54% faster compared to a baseline method. Also, the proposed model can outperform the other baseline method by reducing the packet dropping rate up to 57% caused by the attacker.

Interdependent dimensions including categorical and continuous variables can be seen commonly as heterogeneous behavioral data in the real world. Mixed-type objects are more or less associated in terms of certain coupling relationships. The usual representation of such behavioral data is an information table with explicit behavior exterior dimensions (i.e. the original attributes to describe data heterogeneity), assuming the independence of dimensions and the independence of objects. However, both variables and objects are actually very often interdependent on one another either explicitly or implicitly in functional and semantic manners. Limited research has been done in analyzing such interactions among dimensions and those relationships among objects, leading to the learning results to be more local than global. This paper proposes the interdependence analysis to capture the functional multifarious relationships among attributes and among objects in heterogeneous data by addressing the coupling context and coupling weights in unsupervised learning. Such global couplings consider the interactions within discrete dimensions, within numerical attributes and across them, as well as the relationships within an individual object and between multiple objects, to form the attribute-based and object-based coupled data representation schemes based on feature conversion and neighborhood calculation. In addition, we interpret both the representation models via implicit behavior interior dimensions (i.e. the newly defined attributes to model data interdependence) to explain the intrinsic rationales for the superiority of our proposed methods. This work explicitly models the coupling of multiple attributes and the coupling of multiple objects for heterogeneous data sets, demonstrated by various data mining and machine learning applications, such as cluster structure analysis, data clustering evaluation, and data density comparison. Moreover, the sensitivity study is carried out to tune the neighborhood parameter and weight parameter, and the scalability analysis is explored to test the robustness of both models. Extensive experiments on a series of synthetic data sets and multiple UCI data sets show that our proposed framework can effectively capture the global couplings of both heterogeneous variables and mixed-type objects, and is superior to the traditional way as well as the state-of-the-art approaches, which is also verified by statistical analysis.

In shared data center networks, communications among users can be modeled as coflows, each comprising of a group of parallel data transmission flows. Efficient and fair scheduling of coflows is critical for improving both system performance and user satisfaction at the application level. Existing coflow scheduling methods maximizing efficiency (coflow completion time, CCT) and fairness (service isolation) simultaneously require prior knowledge of coflow (flow) size that is however not known before completion of coflow execution in reality, which limits their applicability. For information-agnostic scheduling, known results focus either solely on efficiency or fairness, but not both due to the hardness of achieving the desired compromise between them. In this paper, we first present an information-aware non-preemptive coflow scheduling algorithm, and show its provable long-term isolation guarantee under reasonable assumptions. We then adapt this algorithm to information-agnostic online coflow scheduling by combining limited multiplexing with Deep Reinforcement Learning (DRL) framework to achieve long-term isolation guarantee toward fair network sharing and lower average weighted CCT simultaneously. The simulation results show that our algorithm outperforms the state-of-the-art results of both fairness-optimal scheduling (NC-DRF) by 4.92in terms of average weighted CCT and performance-optimal scheduling (Aalo) in the metric of maximum normalized CCT. This fully demonstrates the superiority of our method in simultaneous optimization of efficiency and fairness for information-agnostic coflow scheduling.

Summary The traditional support vector machine technique (SVM) has drawbacks in dealing with imbalanced data. To address this issue, in this paper we propose an algorithm of improved clustering with stratified sampling technique (CSS) to improve the classification performance of SVMs on imbalanced datasets. Instead of applying a single type of sampling method as used in the literature, our algorithm treats different type of classes with different sampling methods. For minority classes, the algorithm uses oversampling method by adding noise which obeys normal distribution around every support vector to generate new samples. For majority classes, samples are first divided into different clusters by applying first the improved clustering by fast search to find of density peaks (CFSFDP) to obtain latent structure information in each majority class and then stratified sampling method is applied to extract samples from each subcluster of the majority class. Moreover, we further extend this method into an ensemble classifiers that use multiple base SVM classifiers for prediction. The experimental results of classification on several imbalanced classification datasets show that our CSS is more effective than the state‐of‐the‐art sampling methods.

Abstract In view of the stability and reliability of energy supply, distinct from the time‐varying and uncertainty of energy harvesting systems, adopting mobile vehicles to replenish energy of sensors has become a research hotspot. While some existing studies on the mobile recharging problem ignored the limited energy capacity carried by mobile vehicle and the difference in energy consumption rates of sensors, in this work, we propose an adaptive real‐time on‐demand charging scheduling scheme that maximizes energy efficiency (CSS‐MEE) for Rechargeable Wireless Sensor Networks. In CSS‐MEE, we aim to achieve a compromise between maximizing charging energy efficiency and maximizing charging throughput for solving the on‐demand mobile charging problem. Due to the limited energy capacity of the mobile charger, CSS‐MEE uses both full‐charge mode and adaptive charging mode, depending on the number of charging requests. It combines charging node selection with dispatch path feasibility determination, which takes into account the location‐generated charging cost and energy‐driven charging priority, to ensure the charging efficiency. Extensive simulations are conducted to demonstrate the advantages of CSS‐MEE. Compared with existing approaches, simulation results show that CSS‐MEE achieves better performance in terms of charging throughput, average charging latency, charge scheduling times, and charging efficiency.

Parallel and distributed computing has been the basis to many emerging areas, such as smart networks, cloud computing, big data analysis, and blockchain technology.Without the development of parallel and distributed computing technologies and various types of systems, it is not possible to meet the requirement on efficiency, accuracy, scalability, and reliability for various critical applications that support our modern economy and society.While parallel and distributed computing played a vital role in modern science, engineering, biology, medicine, pharmacy, astronomy, geology, and archaeology, its application has also been extended to business, finance, economics, management, government, and defense, covering all aspects of our modern society and life.Furthermore, parallel and distributed computing has emerged in recent advances of many hotspot research directions including artificial intelligence, machine learning, Internet of Things, bioinformatics, digital medicine, cybersecurity, and social computing, resulting in numerous ground-breading discoveries that are changing our society and life.

Paths in a given network represent the occurrence sequences of nodes in many real world applications, such as disease transmission chains, object trajectories and data access sequences. In this paper, we address the problem of publishing edge-privacy preserved path information for a single path such that legitimate users with the full knowledge of the network can reconstruct the path with the published information, but not adversaries, even if they have the maximum background knowledge of all the vertices and all edges but one (on the path) of the network. Existing studies on edge privacy against inference attacks focus on publishing either differential privacy (DP) noise injected graph statistics or DP edge perturbed graph topology to achieve edge differential privacy preservation. However, none of them provides an assurance on both edge privacy and data utility. To effectively protect edge privacy and maintain data utility, we propose a novel scheme of DP augmentation instead of DP perturbation as did in existing work, that publishes a simple-topology graph containing an augmented path with fake edges and vertices applying differential privacy to protect the actual path, such that only the legitimate users are able to reconstruct the actual path with high probability. We theoretically analyse the performance of our algorithm in terms of output quality on differential privacy and utility, and execution efficiency. We also conduct extensive experimental evaluations on a high-performance cluster system to validate our analytical results.

In a large cloud data center HPC system, a critical problem is how to allocate the submitted tasks to heterogenous servers for achieving the goal of maximize systems net gain defined as the value of completed tasks minus system operation cost. We consider this problem in the online setting that tasks arrive in batches and propose a novel deep reinforcement learning (DRL) enhanced greedy algorithm of two-stage scheduling interacting task sequencing and task allocation. For task sequencing we deploy a DRL module to make prediction for the best allocation sequence for each arriving batch of tasks based on knowledge (allocation strategies) learnt from prior batches. For task allocation, we propose a greedy strategy that allocates tasks to servers one by one online following the allocation sequence to maximally increase the total gain. We show that our greedy strategy has a performance guarantee of competitive ratio 1/(1+k) to the optimal offline solution, which improves the existing result for the same problem, where k is upper bounded by the maximum cost-to-gain ratio of each task. While our DRL module enhances the greedy by providing the likely-optimal allocation sequence for each batch of arriving tasks, our greedy strategy bounds DRLs prediction error within a proven performance guarantee for any allocation sequence, enabling a better solution quality than that obtainable from both DRL and greedy optimization alone. Extensive experiment evaluation results in both simulation and real application environments demonstrate the effectiveness and efficiency of our proposed algorithm. Compared with the state-of-the-art baselines, our algorithm increases the system gain by about 10% to 30%. Our algorithm provides an interesting example of joining machine-learning and greedy optimization techniques to improve ML-based solutions with a worst-case performance guarantee for solving hard optimization problems.

Structural Hole (SH) spanners are the set of users who bridge different groups of users and are vital in numerous applications. Despite their importance, existing work for identifying SH spanners focuses only on static networks. However, real-world networks are highly dynamic where the underlying structure of the network evolves continuously. Consequently, we study SH spanner problem for dynamic networks. We propose an efficient solution for updating SH spanners in dynamic networks. Our solution reuses the information obtained during the initial runs of the static algorithm and avoids the recomputations for the nodes unaffected by the updates. Experimental results show that the proposed solution achieves a minimum speedup of 3.24 over recomputation. To the best of our knowledge, this is the first attempt to address the problem of maintaining SH spanners in dynamic networks.

Iterative clustering around representative points is an effective technique for clustering and helps us learn insights behind data to support various important applications. Unfortunately, it also provides security holes which may allow adversaries to infer the privacy of individuals with some background knowledge. To protect individual privacy against such inference attacks, preserving differential privacy for iterative clustering algorithms has been extensively studied. Existing differentially private clustering algorithms adopt the same framework to compute differentially private centroids iteratively by running Lloyd's k-means algorithm to obtain the actual centroids, then perturbing them with a differential privacy mechanism. These algorithms suffer from the problem of no convergence guarantee, i.e., they provide no guarantee of termination at a solution of Lloyd's algorithm within a bounded number of iterations. This problem severely impacts their clustering quality and execution efficiency. To address this problem, this article follows the same centroid updating pattern as existing work in interactive settings; however we propose a novel framework for injecting differential privacy into the actual centroids. Specifically, to ensure convergence, we maintain the perturbed centroids of the previous iterationt-1 to compute a convergence zone for each cluster in the current iterationt, where we inject differential privacy noise. To achieve a satisfactory convergence rate, we further control the orientation of centroid movement in each cluster using two strategies: one takes the orientation of centroid movement from iterationt-1 to iterationt(past knowledge); the other uses the additional information of the orientation from iterationt+1 (future knowledge). We prove that, in the expected case, our algorithm (in both strategies) converges to a solution of Lloyd's algorithm in at most twice as many iterations as Lloyd's algorithm. Furthermore, when using both past and future knowledge, we prove that our algorithm converges to the same solution as Lloyd's algorithm (for the same initial centroids) with high probability, at the cost of a slower convergence speed compared to using only past knowledge due to duplicated operations in each iteration required for computing the future knowledge. We perform experimental evaluations on seven widely used real-world datasets. The experimental results show that our algorithm outperforms the state-of-the-art methods for interactive differentially private clustering with a guaranteed convergence and better clustering quality whilst meeting the same differential privacy requirements.

Short Message Service (SMS) is a widely used communication medium for mobile applications, such as banking, social networking, and e-commerce. Applications of SMS services also include real-time broadcasting messages, such as notification of natural disasters (e.g., bushfires and hurricane) and terrorist attacks, and sharing the current whereabouts to other users, such as notifying urgent business meeting information, transmitting quick information in the battlefield to multiple users, notifying current location to our friends and sharing market information. However, traditional SMS is not designed with security in mind (e.g., messages are not securely sent). It is also possible to extract international mobile subscriber identity of the mobile user. In the literature, there is no known protocol that could enable secure transmission of SMS from one user to multiple users simultaneously. In this paper, we introduce a batch verification authentication and key agreement protocol, BVPSMS, which provides end-to-end message security over an insecure communication channel between different mobile subscribers. Specifically, the proposed protocol securely transmits SMS from one mobile user to many other users simultaneously. The reliability of the protocol is discussed along with an algorithm to detect malicious user requests in a batch. We then evaluate the performance of the proposed protocol in terms of communication and computation overheads, protocol execution time, and batch and re-batch verification times. The impacts of the user mobility, and the time, space and cost complexity analysis are also discussed. We then present a formal security proof of the proposed protocol. To the best of our knowledge, this is the first provably-secure batch verification protocol that delivers end-to-end SMS security using symmetric keys.

Session-based recommendation is a challenging problem due to the inherent uncertainty of user behavior and the limited historical click information. Latent factors and the complex dependencies within the user’s current session have an important impact on the user's main intention, but the existing methods do not explicitly consider this point. In this paper, we propose a novel model, Interest Shift and Latent Factors Combination Model (ISLF), which can capture the user's main intention by taking into account the user’s interest shift (i.e. long-term and short-term interest) and latent factors simultaneously. In addition, we experimentally give an explicit explanation of this combination in our ISLF. Our experimental results on three benchmark datasets show that our model achieves state-of-the-art performance on all test datasets.

The vulnerability of mobile ad-hoc networks (MANETs) to various kinds of attacks such as active route interfering and denial of service has brought increasing concerns in the deployment of MANETs. The black-hole Attack is a notorious attack that absorbs data packets by the malicious node and results in denial of service in the network. This paper proposes a Markov chain based stochastic model to simulate data transmission in MANETs using the RTS/CTS handshaking mechanism for characterizing the effect of black-hole attacks. Through simulation evaluation, we analyze the effect of black-hole attacks on major network performance metrics for the multi-hop routing protocol applying the proposed data transmission model.

Imbalanced classification problem is a hot issue in data mining and machine learning. Traditional classification algorithms are proposed based on some form of symmetry hypothesis of class distribution, whose main purpose is to improve the overall classification performance. It is difficult to obtain ideal classification result when handling imbalanced datasets. In order to improve the classification performance of imbalanced datasets, this paper proposes a cluster-based under-sampling algorithm (CUS) according to the important characteristic of support vector machines (SVM) classification relying on support vector. Firstly, majority class is divided into different clusters using improved clustering by fast search and find of density peaks (CFSFDP) algorithm. The improved clustering algorithm can realize automatic selection of clustering centers, which overcomes the limitation of the original algorithm. Then the minority class and each cluster of the majority class are used to construct training set to get the support vector of each cluster by support vector machine. Retaining support vectors for each cluster and deleting non-support vectors are to construct a new majority class sample points to obtain relatively balanced datasets. Finally, the new datasets are classified by support vector machines and the performance is evaluated by cross validation sets. The experimental results show that CUS algorithm is effective.

Equipped with more convenient facilities and features, online social networks have become the most popular platform for people's communication. It is increasingly important to model information propagation in such networks. Most of the state-of-the-art algorithms of information diffusion model focus on individual-level diffusion and does not consider the impact of social relations on user's expression, making them either unable to uncover diffusion patterns accurately or unable to capture dynamically changing topics of text stream in social networks. To address these issues, we proposed a dynamic community-level diffusion model (DCDM) in this paper to capture diffusion patterns based on coordinated dynamic semantic analysis by multiple topic-word distribution and structure analysis. Comparative experiments are conducted on the real dataset from Tweet. Experimental results show our diffusion model outperforms the state-of-the-art methods.

To maintain the durability of data collection and improve charging efficiency for a mobile wireless charging vehicle (WCV) in Wireless Rechargeable Sensor Networks (WRSNs), a grid-based joint routing and energy replenish scheme (GRER) is proposed in this paper, aiming to achieve energy balance and maximize recharging benefit. Based on WCV charging service, network is firstly divided into several virtual grids with the help of minimum coverage area idea and a simple concurrent multi-hop chain-based routing protocol is proposed for forming data transmission links. Then, WCV visits and charges nodes using an angle expansion-based breadth-first strategy (AEBF) within the limited battery capacity. Simulation results demonstrate that GRER outperforms FCFS, NJNP, LADP and RCSS schemes in regards to network lifetime, energy balance and charging efficiency.

To alleviate energy hole problem inherent in static Base station (BS) scheme and extend network work of battery-restricted wireless rechargable sensor networks, a joint mobile data col-lection and adaptive charging scheduling (MDC-ACS) scheme based on virtual grid is proposed in this paper, aiming to achieve whole network energy balance and high charging effi-ciency. In MDC-ACS scheme, network is firstly divided into several grids and several rendezvous are determined using geo-graphic information. Then, mobile data collector (MDC) moves in grids for data collection within the application delay and moving trajectory is guided by rendezvous. Due to the limited battery capacity of mobile wirelsee charging vehicle (WCV) and its energy consumption while cruising, an adaptive charging schedule scheme is proposed for maximizing recharging benefit. With extensive simulation, we demonstrate that MDC-ACS scheme can achieve better charging benefit and reduce average charging delay.

Along with the increased convenience of our daily life thanks to the proliferation of location-based service (LBS), such as finding restaurants and booking taxi, concerns on privacy disclosure risks in sharing our locations with LBS have also increased and become a major bottleneck that obstacles the widespread of adoption of LBS [1]. To preserve privacy in LBS, k-anonymity was applied to conceal people's sensitive information against re-identification attacks [2]. Unfortunately, the k-anonymity technique relies on predefined background knowledge of an adversary. Once the adversary has different auxiliary information, we cannot guarantee any privacy preservation against such an adversary. To address the privacy leakage problem of the naive k-anonymity, a combination of k-anonymity and location's query frequency algorithm, the Caching-aware Dummy Selection Algorithm (CaDSA), were proposed [3]. CaDSA anonymises locations in a given area by grouping them with similar query frequency during a fixed time period, say one day. However, considering in the real-life situation location's query frequency often varies in different time slots even in a single day, privacy will clearly lose if we roughly group locations according to a fixed time period as CaDSA. Consequently, in this paper, we propose a Temporal Caching-aware Dummy Location Selection Algorithm (T-CaDLSA) that considers the differences among location's query frequencies over different time slots within a given time period (day). Both mathematical and experimental evaluations show that to achieve the same data utility, our method outperforms the existing work in privacy guarantee.

As a fundamental optimization problem, the problem of packing a given set of objects into the fewest possible bins has both important theoretical significance in algorithms and operations research and great application values for resource allocation, particularly in cloud computing and data center management. In this paper we address the multidimensional online bin packing problem and present an algorithm based on the ROUNDdM algorithm proposed by Csirik & Van Vliet. The ROUNDdM algorithm is a generalisation of the harmonic partitioning scheme and guarantees a worst case approximation ratio of 1.691d for d-dimensions and an average case ratio of 1.2899d. Our HYBRID-ROUNDdM algorithm uses a harmonic based hybrid partitioning scheme and improves this average case approximation ratio to 1.0797d while guaranteeing the same worst case approximation ratio.

Burst-Buffers is a high throughput, small size intermediate storage system integrated between computing nodes and permanent storage system to mitigate the I/O bottleneck problem in modern High Performance Computing (HPC) platforms. This system, however, is unable to effectively handle variable-intensity I/O bursts resulted by unpredictable concurrent accesses to the shared Parallel File System (PFS). In this paper, we introduce a probabilistic I/O scheduling method that takes into account of the burst-buffer load state and instantaneous I/O load distribution of the system based on the probabilistic model of applications to relieve the I/O congestion when I/O load exceeds the PFS bandwidth caused by dynamic application interference. The proposed scheduling method for limited-size Burst-Buffers deployed HPC platforms makes online decision of probabilistic selection of concurrent I/O requests for going through (to PFS), buffering (to Burst-Buffers) or declination in accordance to both the available I/O bandwidth and the current buffer state in order to maximize system efficiency or minimize application dilation. Extensive experiment results on actual characteristic synthetic data show that our method handles the I/O congestion effectively.

Summary Huge energy consumption of large‐scale cloud data centers damages environments with excessive carbon emission. More and more data center operators are seeking to reduce carbon footprint via various types of renewable energy. However, the intermittent availability of renewable energy sources makes it quite challenging to cooperate with dynamically arriving workload. Meanwhile, the different natures (eg, price and carbon emission) of multiple energy sources also bring more challenges to achieve an optimal trade‐off among carbon emission, power cost, and service level agreement (SLA). In this paper, we study the problem of reducing the long‐term energy cost for geo‐distributed cloud centers, where multiple sources of renewable energy are considered and SLA requirement and carbon budget are satisfied. To tackle the randomness of workload arrival, varying electricity price, and intermittent supply of renewable energy, we first formulate the cost minimization problem as a constraint stochastic optimization problem. Second, based on Lyapunov optimization technique, we propose an online control algorithm to solve it and provide the rigorous theory analysis to demonstrate its performance. By converting the long‐term optimization problem to a mixed integer linear programming problem in each time slot, we analyze its inherent structure and propose an efficient algorithm to solve it based on Brenner's method. Our proposed algorithm makes online decisions rely only on the current system state and achieve cost emission trade‐off. Finally, the effectiveness of our algorithm is evaluated by extensive simulations based on real‐world data traces.

The increasing intensity and variety of computation in solving modern science, engineering, and social application problems have brought numerous challenges to parallel and distributed computing and enriched its research content in multiple folds from architecture design to computation paradigm and security with the focuses on computation efficiency for problem solving, data protection for large-scale applications, and energy efficiency for power savings and environment protection.The objective of this Special Section is to show some representative research results on these focuses.This Special Section includes three extended papers primarily selected from the papers presented at the 17th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2016).We received 10 papers submitted to this Special Section, among which three papers are finally selected after at least two rounds of strict review.

Many cloud center operators are turning to leverage on-site renewable energy to reduce power cost for sustainable development consideration. But how to effectively coordinate the intermittent renewable energy with the workload remains to be a great challenge. This paper investigates the problem of power cost minimization under the constraints of different SLAs of delay-tolerant workload and non-delay workload for green data center in smart grid. To handle the randomness of workload, electricity price and renewable energy availability, we formulate a constrained stochastic problem with the consideration of the affection of zero price in smart grid. Then we propose a low-complexity Online workload Scheduling algorithm with Delay Guarantee (OSDG) which makes online scheduling decision based on the system current state and guarantees a bounded worst scheduling delay for delay-tolerant workload. The rigorous theoretical analysis demonstrates that our algorithm achieves a [0 (1/v), O (V)] cost-delay tradeoff. Extensive simulations based on real-world trace are done to evaluate the performance of our algorithm in reality. The results show that OSDG achieves about 4.9% improvement compared with the baseline algorithms.

Collaborative Filtering (CF) is a successful technique that has been implemented in recommender systems and Privacy Preserving Collaborative Filtering (PPCF) aroused increasing concerns of the society. Current solutions mainly focus on cryptographic methods, obfuscation methods, perturbation methods and differential privacy methods. But these methods have some shortcomings, such as unnecessary computational cost, lower data quality and hard to calibrate the magnitude of noise. This paper proposes a (k, p, I)-anonymity method that improves the existing k-anonymity method in PPCF. The method works as follows: First, it applies Latent Factor Model (LFM) to reduce matrix sparsity. Then it improves Maximum Distance to Average Vector (MDAV) microaggregation algorithm based on importance partitioning to increase homogeneity among records in each group which can retain better data quality and (p, I)-diversity model where p is attacker's prior knowledge about users' ratings and I is the diversity among users in each group to improve the level of privacy preserving. Theoretical and experimental analyses show that our approach ensures a higher level of privacy preserving based on lower information loss.

Comparisons between community detection methods are mostly based on their accuracies in recovering the built-in community structure in artificial benchmark networks. Current community detection benchmarks assign a fixed fraction of inter-community links, referred to as the mixing fraction, for every community in the same network. We first show in this paper that the variation in community mixing fractions has different impacts on the performances of different community detection methods that could change the decision to select a particular detecting algorithm. To comprehensively compare community detection methods, we therefore need a benchmark that generates heterogeneous community mixing fractions, which is not currently available. We address this gap by generalizing the state-of-the-art Lancichinetti-Fortunato-Radicchi benchmark to generate networks with heterogeneous community mixing fractions. Using our new benchmark, we can quantify the impact of the variation in community mixing fractions on existing community detection methods and re- evaluate the performance of the detecting algorithms as a function of the heterogeneity among the mixing fractions. Furthermore, we show that the heterogeneous community mixing tests using our generalized benchmark reflect better the performance that would be expected on real networks than the homogeneous community mixing tests using the original benchmark.

Topology control based on appropriate cluster head election can drastically reduce energy consumption, balance traffic load on sensor nodes and extends the lifetime of the network. In this paper, an efficient data gathering multihop routing approach based on fixed-group for wireless sensor networks is proposed. Our proposed protocol, FGMRP (Fixed-Group based Multi-hop Routing Protocol), divides the monitoring area into several groups according to node intimacy, optimizes energy consumption among nodes in each group by performing adaptive cluster head round-robin rotations based on residual energy, concentration and centrality, and balances energy consumption among groups through a fitness routing algorithm which considers node residual energy, forwarding distance and radial angle. Simulation results show that the FGMRP protocol effectively balances the energy consumption among nodes, achieves better monitoring performance and significantly increases network lifetime as compared to the existing routing protocols, taking monitoring quality, the amount of data acquisition and network lifetime as evaluation indices.

Search result diversification is effective way to tackle query ambiguity and enhance result novelty. In the context of large information networks, diversifying search result is also critical for further design of applications such as link prediction and citation recommendation. In previous work, this problem has mainly been tackled in a way of implicit query intent. To further enhance the performance, we propose an explicit search result diversification method that explicitly encode query intent and represent nodes as representation vectors by a novel nonnegative matrix factorization approach, and the diversity of the results node account for the query relevance and the novelty w.r.t. these vectors. To learn representation vectors for networks, we derive the multiplicative update rules to train the nonnegative matrix factorization model. Finally, we perform a comprehensive evaluation on our proposals with various baselines. Experimental results show the effectiveness of our proposed solution, and verify that attributes do help improve diversification performance.

Distributed data aggregation via summation (counting) helped us to learn the insights behind the raw data. However, such computing suffered from a high privacy risk of malicious collusion attacks. That is, the colluding adversaries infer a victim's privacy from the gaps between the aggregation outputs and their source data. Among the solutions against such collusion attacks, Distributed Differential Privacy (DDP) shows a significant effect of privacy preservation. Specifically, a DDP scheme guarantees the global differential privacy (the presence or absence of any data curator barely impacts the aggregation outputs) by ensuring local differential privacy at the end of each data curator. To guarantee an overall privacy performance of a distributed data aggregation system against malicious collusion attacks, part of the existing work on such DDP scheme aim to provide an estimated lower bound of privacy budget for the global differential privacy. However, there are two main problems: low data utility from using a large global function sensitivity; unknown privacy guarantee when the aggregation sensitivity of the whole system is less than the sum of the data curator's aggregation sensitivity. To address these problems while ensuring distributed differential privacy, we provide a new lower bound of privacy budget, which works with an unconditional aggregation sensitivity of the whole distributed system. Moreover, we study the performance of our privacy bound in different scenarios of data updates. Both theoretical and experimental evaluations show that our privacy bound offers better global privacy performance than the existing work.

The virtual machine (VM) placement problem is a major issue in optimizing resource ulitization of cloud data centers. With the rapid development of cloud computing, efficient algorithms are needed to reduce the power consumption and save energy in data centers. Many models and algorithms are designed with a objective to minimize the number of physical machines (PMs) used in a cloud data center. In this paper, we take into account the execution time of the PM, and formulat a new optimization problem of VM placement, which aims to minimize the total execution time of the PMs. We discuss the NP-hardness of the problem, and present heuristic algorithms to solve it in both offline and online scenarios. Furthermore, we conduct experiments to evaluate the performance of the proposed algorithms and the result show that our methods are able to perform better than other commonly used algorithms.

In a mobile network, wireless data broadcast over$m$channels (frequencies) is a powerful means for distributed dissemination of data to clients who access the channels through multi-antennae equipped on their mobile devices. The$\delta$-antennae largest weight data retrieval ($\delta$ALWDR) problem is to compute a schedule for downloading a subset of data items that has a maximum total weight using$\delta$antennae in a given time interval. In this paper, we first give a linear programming (LP) relaxation for$\delta$ALWDR and show that it is polynomial-time solvable when every data item appears at most once. We also show that when there exist data items with multiple occurrences, the integrality gap of this LP formula is 2. We then present an approximation algorithm of ratio$1-\frac{1}{e}$for the$\delta$-antennae$\gamma$-separated largest weight data retrieval ($\delta$A$\gamma$LWDR) problem, a weaker version of$\delta$ALWDR where each block of up to$\gamma$data (time) slots is separated by a vacant slot on all channels, applying the techniques called collectively randomized LP rounding and layered DAG construction. We show that$\delta$A$\gamma$LWDR is${\mathcal NP}-$complete even for the simple case of$\gamma =2$,$m=3$, and equal-weight data items each appearing up to 3 times. Our algorithm runs in time$O(2^{\gamma}m^{7}T^{3.5}L)$, where$T$is the number of time slots, and$L$is the maximum length of the input. Then, from the simple observation that a ratio$\alpha$approximation solution to$\delta$A$\gamma$LWDR implies a ratio$\alpha -\epsilon$approximation solution to$\delta$ALWDR for any fixed$\epsilon >0$, we immediately have an approximation algorithm of ratio$1-\frac{1}{e}-\epsilon$for$\delta$ALWDR. Our algorithm has the same approximation ratio as the known result in[15]which holds only for$\delta =1$, with a significantly lower time complexity of$O(2^{\frac{1}{\epsilon}}\frac{1}{\epsilon}m^{7}T^{3.5}L)$(improved from$O(\epsilon ^{3.5}m^{\frac{3.5}{\epsilon}}T^{3.5}L)$of[15]). As a by-product, we also give a fixed-parameter tractable (fpt-)algorithm of time complexity$O(2^{B}m^{7}T^{3.5}L)$for$\delta$ALWDR, where$B$is the number of time slots that contain data items with multiple occurrences.

We consider the problem of search result diversification for streams of short texts. Diversifying search results in short text streams is more challenging than in the case of long documents, as it is difficult to capture the latent topics of short documents. To capture the changes of topics and the probabilities of documents for a given query at a specific time in a short text stream, we propose a dynamic Dirichlet multinomial mixture topic model, called D2M3, as well as a Gibbs sampling algorithm for the inference. We also propose a streaming diversification algorithm, SDA, that integrates the information captured by D2M3 with our proposed modified version of the PM-2 (Proportionality-based diversification Method -- second version) diversification algorithm. We conduct experiments on a Twitter dataset and find that SDA statistically significantly outperforms state-of-the-art non-streaming retrieval methods, plain streaming retrieval methods, as well as streaming diversification methods that use other dynamic topic models.

Clouds, such as Amazon Infrastructure-as-a-Service (IaaS) clouds and EMC Hybrid Cloud, impose growing requirements of resource-efficiency scheduling. The bounded flexible scheduling (BFS) problem is one of the problems proposed to meet such requirements. In BFS, we are given a set of identical machines and a set of jobs, each of which is with a value, a workload, a deadline and a parallelism degree, i.e., the maximum number of machines on which the job can execute concurrently. The problem is to compute an assignment of the given jobs to the machines, such that the total value of the jobs successfully completed by their deadlines is maximized. This paper presents a factor C/C-k approximation algorithm for BFS, where k is the maximum parallelism degree and C is the capacity of the system (i.e., the number of machines). Since C ≫ k in BFS, our result significantly improves the known best approximation ratio of (2C-k/C-k)(1-ϵ) for tight deadlines [17], and C/C-k · s/s-1/s for loose deadlines [18] on a slackness ratios > 1 that is the maximum ratio between a job's earliest actual finish time and its deadline. We first propose feasibility condition to determine whether an instance of BFS is feasible, i.e., whether there exists a scheduling according to which all jobs can finish before their deadlines, which is the key to achieve the ratio improvement of our algorithm. To prove the correctness of the feasibility condition, we give a simple linear program (LP) for a weaker version of BFS, and show that it is with an integral polyhedron and hence the version of BFS is polynomial-time solvable. Then we present a greedy algorithm and its equivalent primal-dual algorithm for the complementary problem of BFS. Both algorithms have an approximation ratio of C/C-k, and time complexity O(n2+ nT), where n is the number of jobs and T is the number of time slots. As a by-product, we show that the BFS admits a polynomial-time approximation scheme (PTAS) when T is fixed.

Huge energy consumption of large-scale cloud data centers damages the environment with excessive carbon emission. More and more data center operators are seeking to reduce carbon footprint via various types of renewable energy sources. However, the intermittent availability of renewable energy source makes it quite challenging to cooperate the dynamic workload arrivals. In this paper, we investigate how to coordinate multi-type renewable energy (e.g. wind power and solar power) in order to reduce the long-term energy cost with spatio-temporal diversity of electricity price for geo-distributed cloud data centers under the constraints of service level agreement (SLA) and carbon footprints. To tackle the randomness of workload arrival, dynamic electricity price change and renewable energy generation, we first formulate the minimizing energy cost problem into a constrained stochastic optimization problem. Then, based on Lyapunov optimization technique, we design an online control algorithm which can work without long-term future system information for solving the problem. Finally, we evaluate the effectiveness of the algorithm with extensive simulations based on real-world workload traces, electricity price and historic climate data.

Data streams classification poses three major challenges, namely, infinite length, concept-drift, and featureevolution. The first two issues have been widely studied. However, most existing data stream classification techniques ignore the last one. DXMiner [17], the first model which addresses featureevolution by using the past labeled instances to select the top ranked features based on a scores computed by a formula. This semi-supervised feature selection method depends on the quality of the past classification and neglects the possible correlation among different features, thus unable to produce an optimal feature subset which deteriorates the accuracy of classification. Multi-Cluster Feature Selection (MCFS) [5] proposed for static data classification and clustering applies unsupervised feature selection to address the feature-evolution problem, but suffers from the high computational cost in feature selection. In this paper, we apply MCFS in the DXMiner framework to handle each window of data in a data stream for dynamic data stream-classification. With unsupervised feature selection, our method produces the optimal feature subset and hence improves DXMiner on the classification accuracy. We further improve the time complexity of the feature selection process in MCFS by using the locality sensitive hashing forest (LSH Forest) [4]. The empirical results indicate that our approach outperforms stateof-the-art streams classification techniques in classifying real-life data streams.

Collaborative Filtering (CF) is a successful technology that has been implemented in E-commerce recommender systems. However, the risks of shilling attacks have already aroused increasing concerns of the society. Current solutions mainly focus on attack detection methods and robust CF algorithms that have flaws of unassured prediction accuracy. Furthermore, attack detection methods require a threshold to distinguish normal users from fake users and suffer from the problems of false positive if the threshold is too high and false negative if too low. This paper proposes a soft-decision method, Neighbor Selection with Variable-Length Partitions (VLPNS), to reduce false positive rate through marking suspicious fakers instead of deleting them directly such that misclassified normal users can still contribute to the similarity calculation. The method works as follows: First, it gets user's suspicion probability by applying SVM. It then generates partitions of variable sizes from which different numbers of neighbors can be selected by using the bisecting c-means clustering algorithm. Finally, it chooses neighbors considering the user's suspicion degree and similarity with target user at the same time. Theoretical and experimental analysis show that our approach ensures an excellent prediction accuracy against shilling attacks.

The randomization methods that are applied for privacy-preserving data mining are commonly subject to reconstruction, linkage, and semantic-related attacks. Some existing works employed random noise addition to realize probabilistic anonymity, aiming only at linkage attacks. Random noise addition is vulnerable to reconstruction attacks, and is unable to achieve semantic closeness, particularly on high-dimensional data, to prevent semantic-related attacks. For linkage attacks, the main security vulnerability of their proposed probabilistic anonymity lies in the assumption that the attacker had a priori knowledge of the quasi-identifiers of all individuals. When only some individuals leak their quasi-identifiers, the proposed model will become incapable, because the attacker can deploy a different linkage attack that has not been studied before. This type of attack is much easier to deploy and is thus very harmful. In this paper, we propose new frameworks of probabilistic (1, k)and (k, k)-anonymity to defend against all these linkage attacks, and realize the frameworks on a hybrid randomization model. The model is also secure against reconstruction attacks. We further achieve statistical semantic closeness of high-dimensional data to prevent semantic-related attacks on the model. The frameworks also allow us to re-design the traditional K-nearest neighbor algorithm to leverage the introduced data uncertainty and improve the mining results. This paper demonstrates the promising applications in large-scale and high-dimensional data mining in clouds, by providing high efficiency and security to protect data privacy, guaranteeing high data utility for mining purposes, on-time processing, and non-interactive data publishing.

The neighbourhood-based Collaborative Filtering is a widely used method in recommender systems. However, the risks of revealing customers' privacy during the process of filtering have attracted noticeable public concern recently. Specifically, kNN attack discloses the target user's sensitive information by creating k fake nearest neighbours by non-sensitive information. Among the current solutions against kNN attack, the probabilistic methods showed a powerful privacy preserving effect. However, the existing probabilistic methods neither guarantee enough prediction accuracy due to the global randomness, nor provide assured security enforcement against kNN attack. To overcome the problems of current probabilistic methods, we propose a novel approach, Probabilistic Partitioned Neighbour Selection, to ensure a required security guarantee while achieving the optimal prediction accuracy against kNN attack. In this paper, we define the sum of k neighbours' similarity as the accuracy metric α, the number of user partitions, across which we select the k neighbours, as the security metric β. Differing from the present methods that globally selected neighbours, our method selects neighbours from each group with exponential differential privacy to decrease the magnitude of noise. Theoretical and experimental analysis show that to achieve the same security guarantee against kNN attack, our approach ensures the optimal prediction accuracy.

Border surveillance for intrusion detection is an important application of wireless sensor networks. Given a set of mobile sensors and their initial positions, how to move these sensors to a region border to achieve barrier coverage energy-efficiently is challenging. In this paper, we study the 2-D MinMax barrier coverage problem of moving n sensors in a two-dimensional plane to form a barrier coverage of a specified line segment in the plane while minimizing the maximum sensor movement for the sake of balancing battery power consumption. Previously, this problem was shown to be NP-hard for the general case. It was an open problem whether the problem is polynomial-time solvable for the case when sensors have a fixed number of sensing ranges. We study a special case of great practical significance that the sensors have the same sensing range and present an O(n3log n) time algorithm. Our algorithm computes a permutation of the left and right endpoints of the moving ranges of all the sensors forming a barrier coverage and minimizes the maximum sensor movement distance by characterizing permutation switches that are critical. To the best of our knowledge, this is the first result for solving the 2-D MinMax barrier coverage problem for the case that all sensors have a uniform sensing range.

Let G=(V, E) be a digraph with nonnegative integral cost and delay on each edge, s and t be two vertices, and D ∈ Z+/o be a delay bound, the k disjoint Restricted Shortest Path (k RSP) problem is to compute k disjoint paths between s and t with the total cost minimized and the total delay bounded by D. In this paper, we first present a pseudo-polynomial-time algorithm with a bifactor approximation ratio of (1,2), then improve the algorithm to polynomial time with a bifactor ratio of (1+ε,2+ε) for any fixed ε>0, which is better than the current best approximation ratio (O(1+λ), O(1 + ln 1/λ)) for any fixed λʌ0. To the best of our knowledge, this is the first constant-factor algorithm that almost strictly obeys kRSP constraint.

In the emerging environment of the Internet of Things (IoT), through the connection of billions of radio frequency identification (RFID) tags and sensors to the Internet, applications will generate an unprecedented number of transactions and amount of data that require novel approaches in mining useful information from RFID trajectories. RFID data usually contain a considerable degree of uncertainty caused by various factors such as hardware flaws, transmission faults and environment instability. In this paper, we propose an efficient clustering algorithm that is much less sensitive to noise and outliers than the existing methods. To better facilitate the emerging cloud computing resources, our algorithm is designed cloud-friendly so that it can be easily adopted in a cloud environment. The scalability and efficiency of the proposed algorithm are demonstrated through an extensive set of experimental studies.

Combinatorial Map (CM) is becoming increasingly popular due to its power in modeling topological structures with subdivided objects, which is widely used in the fields of social network, computer vision, social media and so on. However, due to its specific structural properties, an unprotected release of a combinatorial map may cause the identity disclosure problem, which is a major privacy breach revealing the identification of entities with certain background knowledge known by an adversary. In this paper, we discuss the privacy preserving problem in publishing private combinatorial maps. We first formalize a specific anonymizing model to deal with dart-related attacks, and discuss an efficient metric to quantify information loss incurred in the perturbation. Then we propose an efficient method for the dart anonymization problem to prevent a CM from the attack. Our approaches are efficient and practical, and have been validated by extensive experiments on two sets of synthetic data.

Let G = (V, E) be a given graph with nonnegative integral edge cost and delay, S ⊆ V be a terminal set and r ∈ S be the selected root. The shallow-light Steiner tree (SLST) problem is to compute a minimum cost tree spanning the terminals of S, such that the delay between r and every other terminal is bounded by a given delay constraint D ∈ ℤ0+. It is known that the SLST problem is NP-hard and unless NP ⊆ DTIME(nlog log n) there exists no approximation algorithm with ratio (1, γ log2 n) for some fixed γ > 0 [12]. Nevertheless, under the same assumption it admits no approximation ratio better than (1, γ log2n) for some fixed γ > 0 even when D = 2 [2]. This paper first gives an exact algorithm with time complexity O(3tnD + 2tn2D2+ n3D3), where n and t are the numbers of vertices and terminals of the given graph respectively. This is a pseudo polynomial time parameterized algorithm with respect to the parameterization “number of terminals”. Later, this algorithm is improved to a parameterized approximation algorithm with a time complexity O(3tn2/∈ + 2tn4/∈2+ n6/∈3) and a bifactor approximation ratio (1 + ∈, 1). That is, for any small real number ∈ > 0, the algorithm computes a Steiner tree with delay and cost bounded by (1 + ∈)D and the optimum cost respectively.

We initiate the study of the reliable resource allocation (RRA) problem. In this problem, we are given a set of sites ℱ each with an unconstrained number of facilities as resources. Every facility at site i ∈ ℱ has an opening cost and a service reliability pi. There is also a set of clients 𝒞 to be allocated to facilities. Every client j ∈ 𝒞 accesses a facility at i with a connection cost and reliability lij. In addition, every client j has a minimum reliability requirement (MRR) rj for accessing facilities. The objective of the problem is to decide the number of facilities to open at each site and connect these facilities to clients such that all clients’ MRRs are satisfied at a minimum total cost. The unconstrained fault-tolerant resource allocation problem studied in Liao and Shen [(2011) Unconstrained and Constrained Fault-Tolerant Resource Allocation. Proceedings of the 17th Annual International Conference on Computing and Combinatorics (COCOON), Dallas, Texas, USA, August 14–16, pp. 555–566. Springer, Berlin] is a special case of RRA. Both of these resource allocation problems are derived from the classical facility location theory. In this paper, for solving the general RRA problem, we develop two equivalent primal-dual algorithms where the second one is an acceleration of the first and runs in quasi-quadratic time. In the algorithm's ratio analysis, we first obtain a constant approximation factor of 2+2√2 and then a reduced ratio of 3.722 using a factor revealing program, when lij's are uniform on i (partially uniform) and rj's are uniform above the threshold reliability that a single access to a facility is able to provide. The analysis further elaborates and generalizes the inverse dual-fitting technique introduced in Xu and Shen [(2009) The Fault-Tolerant Facility Allocation Problem. Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), Honolulu, HI, USA, December 16–18, pp. 689–698. Springer, Berlin]. Moreover, we formalize this technique for analyzing the minimum set cover problem. For a special case of RRA, where all rj's and lij's are uniform, we derive its approximation ratio through a novel reduction to the uncapacitated facility location problem. The reduction demonstrates some useful and generic linear programming techniques.

Efficient attribute reduction in large-scale incomplete decision systems is a challenging problem. The computation of tolerance classes induced by the condition attributes in the incomplete decision system is a key part among all existing attribute reduction algorithms. Moreover, updating attribute reduction for dynamically-increasing decision systems has attracted much attention, in view of that incremental attribute reduction algorithms in a dynamic incomplete decision system have not yet been sufficiently discussed so far. In this paper, we first introduce a simpler way of computing tolerance classes than the classical method. Then we present an incremental attribute reduction algorithm to compute an attribute reduct for a dynamically-increasing incomplete decision system. Compared with the non-incremental algorithms, our incremental attribute reduction algorithm can compute a new attribute reduct in much shorter time. Experiments on four data sets downloaded from UCI show that the feasibility and effectiveness of the proposed incremental algorithm.

Given a set of data items broadcasting at multiple parallel channels, where each channel has the same broadcast pattern over a time period, and a set of client's requested data items, the data retrieval problem requires to find a sequence of channel access to retrieve the requested data items among the channels such that the total access latency is minimized, where both channel access (to retrieve a data item) and channel switch are assumed to take a single time slot. As an important problem of information retrieval in wireless networks, this problem arises in many applications such as e-commerce and ubiquitous data sharing, and is known two conflicts: requested data items are broadcast at same time slots or adjacent time slots in different channels. Although existing studies focus on this problem with one conflict, there is little work on this problem with two conflicts. So this paper proposes efficient algorithms from two views: single antenna and multiple antennae. Our algorithm adopts a novel approach that wireless data broadcast system is converted to DAG, and applies set cover to solve this problem. Through Experiments, this result presents currently the most efficient algorithm for this problem with two conflicts.

Recently, the development of cloud computing has received considerable attention. For cloud service providers, packing VMs onto a small number of servers is an effective way to reduce energy costs, so as to improve the efficiency of the data center. However allocating too many VMs on a physical machine may cause some hot spots which violate the SLA of applications. Load balancing of the entire system is hence needed to guarantee the SLA. In this paper, we present a simulated-annealing load balancing algorithm for solving the resource allocation and scheduling problem in a cloud computing environment. Experimental results show that this method is able to achieve load balancing, and performs better than the round robin and basic simulated-annealing algorithms.

Cloud computing is becoming increasingly popular due to its power in providing high-performance and flexible service capabilities. More and more internet users have accepted this innovative service model and been using various cloud-based services every day. However, these service-using data is quite valuable for marketing purposes, as it can reflect a user's interest and service-using pattern. Therefore, the privacy issues have been brought out. Recently, many studies focus on access control and other traditional security problems in cloud, and little studied on the topic of the private service data publishing. In this paper, we study the private service data publishing problem by representing the data with a hyper graph, which is quite efficient to illustrate complex relationships among users. We first formulate the problem with a popular background knowledge attack model named rank attack, and then provide an anonymization-based method to prevent the released data from such attacks. We also take data utility into consideration by defining specific information loss metrics. The performances of the methods have been validated by two sets of synthetic data.

As Cloud Computing becomes popular, more and more data owners prefer to store their data into the cloud for great flexibility and economic savings. In order to protect the data privacy, sensitive data usually have to be encrypted before outsourcing, which makes effective data utilization a challenging task. Although traditional searchable symmetric encryption schemes allow users to securely search over encrypted data through keywords and selectively retrieve files of interest without capturing any relevance of data files or search keywords, and fuzzy keyword search on encrypted data allows minor typos and format inconsistencies, secure ranked keyword search captures the relevance of data files and returns the results that are wanted most by users. These techniques function unilaterally, which greatly reduces the system usability and efficiency. In this paper, for the first time, we define and solve the problem of privacy-preserving ranked fuzzy keyword search over encrypted cloud data. Ranked fuzzy keyword search greatly enhances system usability and efficiency when exact match fails. It returns the matching files in a ranked order with respect to certain relevance criteria (e.g., keyword frequency) based on keyword similarity semantics. In our solution, we exploit the edit distance to quantify keyword similarity and dictionary-based fuzzy set construction to construct fuzzy keyword sets, which greatly reduces the index size, storage and communication costs. We choose the efficient similarity measure of "coordinate matching", i.e., as many matches as possible, to obtain the relevance of data files to the search keywords.

Given $n_{f}$ sites, each equipped with one facility, and $n_{c}$ cities, fault tolerant facility location (FTFL) [K. Jain and V. V. Vazirani, APPROX '$00$: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, Spinger, New York, 2000, pp. 177--183] requires computing a minimum-cost connection scheme such that each city connects to a specified number of facilities. When each city connects to exactly one facility, FTFL becomes the classical uncapacitated facility location problem (UFL) that is well-known NP hard. The current best solution to FTFL admits an approximation ratio 1.7245 due to Byrka, Srinivasan, and Swamy applying the dependent rounding technique announced recently [Proceedings of IPCO, 2010, pp. 244--257], which improves the ratio 2.076 obtained by Swamy and Shmoys based on LP rounding [ACM Trans. Algorithms, 4 (2008), pp. 1--27]. In this paper, we study a variant of the FTFL problem, namely, fault tolerant facility allocation (FTFA), as another generalization of UFL by allowing each site to hold multiple facilities and show that we can obtain better solutions for this problem. We first give two algorithms with 1.81 and 1.61 approximation ratios in time complexity $O(mR\log m)$ and $O(Rn^{3})$, respectively, where $R$ is the maximum number of facilities required by any city, $m=n_{f}n_{c}$, and $n=\max\{n_{f},n_{c}\}$. Instead of applying the dual-fitting technique that reduces the dual problem's solution to fit the original problem as used in the literature [K. Jain et al., Journal of the ACM, 50 (2003), pp. 795--824; K. Jain, M. Mahdian, and A. Saberi, STOC'02: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, New York, 2002, pp. 731--740; A. Saberi et al., Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Springer, New York, 2001, pp. 127--137], we propose a method called inverse dual-fitting that alters the original problem to fit the dual solution and show that this method is more effective for obtaining solutions of multifactor approximation. We show that applying inverse dual-fitting and factor-revealing techniques our second algorithm is also (1.11,1.78)- and (1,2)-approximation simultaneously. These results can be further used to achieve solutions of 1.52-approximation to FTFA and 4-approximation to the fault tolerant k-facility allocation problem in which the total number of facilities is bounded by $k$. These are currently the best bifactor and single-factor approximation ratios for the problems concerned.

For a given undirected (edge) weighted graph G = (V, E), a terminal set S ⊆ V and a root r ∈ S, the rooted k-vertex connected minimum Steiner network (kVSMNr) problem requires to construct a minimum-cost subgraph of G such that each terminal in S \ {R} is k-vertex connected to τ. As an important problem in survivable network design, the kVSMNτproblem is known to be NP-hard even when k 1/4 1 [14]. For k 1/4 3 this paper presents a simple combinatorial eight-approximation algorithm, improving the known best ratio 14 of Nutov [20]. Our algorithm constructs an approximate 3VSMNτthrough augmenting a two-vertex connected counterpart with additional edges of bounded cost to the optimal. We prove that the total cost of the added edges is at most six times of the optimal by showing that the edges in a 3VSMNτcompose a subgraph containing our solution in such a way that each edge appears in the subgraph at most six times.

Data publishing based on hypergraphs is becoming increasingly popular due to its power in representing multirelations among objects. However, security issues have been little studied on this subject, while most recent work only focuses on the protection of relational data or graphs. As a major privacy breach, identity disclosure reveals the identification of entities with certain background knowledge known by an adversary. In this paper, we first introduce a novel background knowledge attack model based on the property of hyperedge ranks, and formalize the rank-based hypergraph anonymization problem. We then propose a complete solution in a two-step framework: rank anonymization and hypergraph reconstruction. We also take hypergraph clustering (known as community detection) as data utility into consideration, and discuss two metrics to quantify information loss incurred in the perturbation. Our approaches are effective in terms of efficacy, privacy, and utility. The algorithms run in near-quadratic time on hypergraph size, and protect data from rank attacks with almost the same utility preserved. The performances of the methods have been validated by extensive experiments on real-world datasets as well. Our rank-based attack model and algorithms for rank anonymization and hypergraph reconstruction are, to our best knowledge, the first systematic study to privacy preserving for hypergraph-based data publishing.

In the emerging environment of the Internet of things (IoT), through the connection of billions of radio frequency identification (RFID) tags and sensors to the Internet, applications will generate an unprecedented number of transactions and amount of data that require novel approaches in RFID data stream processing and management. Unfortunately, it is difficult to maintain a distributed model without a shared directory or structured index. In this paper, we propose a fully distributed model for federated RFID data streams. This model combines two techniques, namely, tilted time frame and histogram to represent the patterns of object flows. Our model is efficient in space and can be stored in main memory. The model is built on top of an unstructured P2P overlay. To reduce the overhead of distributed data acquisition, we further propose several algorithms that use a statistically minimum number of network calls to maintain the model. The scalability and efficiency of the proposed model are demonstrated through an extensive set of experiments.

The multicast problem in multi-channel multi-radio wireless mesh networks has received much attention recently. Most recent studies on this problem focus on improving the network throughput. However, many real-world applications require routing algorithms to achieve low-delay and low-loss. In this paper, we tackle the problem of constructing a robust minimum-cost multicast tree that tolerates link interference. To save bandwidth resource and alleviate the interference in the communication, we propose a robust multicast algorithm for multi-channel multi-radio wireless mesh networks. Our experimental results show that our algorithm is very efficient to achieve better performances in network throughput and end-to-end delay than previous studies.

For a given graph G with distinct vertices s, t and a given delay constraint D ∈ R+, the k-disjoint restricted shortest path (kRSP) problem of computing k-disjoint minimum cost stpaths with total delay restrained by D, is known to be NP-hard. Bifactor approximation algorithms have been developed for its special case when k = 2, while no approximation algorithm with constant single factor or bifactor ratio has been developed for general k. This paper firstly presents a (k, (1 + ε)H(k))-approximation algorithm for the kRSP problem by extending Orda's factor(1.5, 1.5) approximation algorithm [9]. Secondly, this paper gives a novel linear programming (LP) formula for the kRSP problem. Based on LP rounding technology, this paper rounds an optimal solution of this formula and obtains an approximation algorithm within a bifactor ratio of (2, 2). To the best of our knowledge, it is the first approximation algorithm with constant bifactor ratio for the kRSP problem. Our results can be applied to serve applications in networks which require quality of service and robustness simultaneously, and also have broad applications in construction of survivable networks and fault tolerance systems.

Combining manifold ranking with active learning (MRAL for short) is one popular and successful technique for relevance feedback in content-based image retrieval (CBIR). Despite the success, conventional MRAL has two main drawbacks. First, the performance of manifold ranking is very sensitive to the scale parameter used for calculating the Laplacian matrix. Second, conventional MRAL does not take into account the redundancy among examples and thus could select multiple examples that are similar to each other. In this work, a novel MRAL framework is presented to address the drawbacks. Concretely, we first propose a self-tuning manifold ranking algorithm that can adaptively calculate the Laplacian matrix via a local scaling mechanism, and then develop a hybrid active learning algorithm by integrating three well-known selective sampling criteria, which is able to effectively and efficiently identify the most informative and diversified examples for the user to label. Experiments on 10,000 Corel images show that the proposed method is significantly more effective than some existing approaches.

Many real applications, such as network traffic monitoring, intrusion detection, satellite remote sensing, and electronic business, generate data in the form of a stream arriving continuously at high speed. Clustering is an important data analysis tool for knowledge discovery. Compared with traditional clustering algorithms, clustering stream data is an important and challenging problem which has attracted many researchers. Clustering stream data is facing two main challenges. First, as the data is continuously arriving with high rate and the computer storage capacity is limited, raw data can only be scaned in one pass. Second, stream data is always changing with time, so viewing a data stream as a set of static data can deteriorate the clustering quality. In fact, users are more concerned with the evolving behaviors of clusters which can help people making correct decisions. This paper proposes a density-grid based clustering algorithm, PKS-Stream-I, for stream data. It is an optimization of PKS-Stream in density detection period selection, sporadic grid detection and removal. Empirical results show the proposed method yields out better performance.

Chord is a popular and successful topology for Peer-to-Peer (P2P) data sharing. However, the conventional chord is challenged by two main drawbacks. First, it fails to consider the physical topology of the P2P network for designing the lookup solution, which may bring tremendous delay to network routing. Second, its performance of is usually limited by the high space complexity of data storage and thus data retrieval may suffer further network delay. In this work, we propose an improved chord based on Counting Bloom Filter and topology aware lookup to address the drawbacks. We first apply counting Bloom filter for data storage to reduce the space complexity. We then develop a topology-aware lookup mechanism to further speed up the search for local resources. Simulation results show that our improved chord scheme is significantly more efficient than the conventional chord method.

Random Projection (RP) has raised great concern among the research community of privacy-preserving data mining, due to its high efficiency and utility, e.g., keeping the euclidean distances among the data points. It was shown in [33] that, if the original data set composed of m attributes is multiplied by a mixing matrix of k\times m (m>;k) which is random and orthogonal on expectation, then the k series of perturbed data can be released for mining purposes. Given the data perturbed by RP and some necessary prior knowledge, to our knowledge, little work has been done in reconstructing the original data to recover some sensitive information. In this paper, we choose several typical scenarios in data mining with different assumptions on prior knowledge. For the cases that an attacker has full or zero knowledge of the mixing matrix R, respectively, we propose reconstruction methods based on Underdetermined Independent Component Analysis (UICA) if the attributes of the original data are mutually independent and sparse, and propose reconstruction methods based on Maximum A Posteriori (MAP) if the attributes of the original data are correlated and nonsparse. Simulation results show that our reconstructions achieve high recovery rates, and outperform the reconstructions based on Principal Component Analysis (PCA). Successful reconstructions essentially mean the leakage of privacy, so our work identify the possible risks of RP when it is used for data perturbations.

For an undirected and weighted graph G = (V, E) and a terminal set S ⊆ V , the 2-connected Steiner minimal network (SMN) problem requires to compute a minimum-weight subgraph of G in which all terminals are 2-connected to each other. This problem has important applications in design of survivable networks and fault-tolerant communication, and is known MAXSNP-hard [7], a harder subclass of NP-hard problems for which no polynomial-time approximation scheme (PTAS) is known. This paper presents an efficient algorithm of O(|V|2|S|3) time for computing a 2-vertex connected Steiner network (2VSN) whose weight is bounded by two times of the optimal solution 2-vertex connected SMN (2VSMN). It compares favorably with the currently known 2-approximation solution to the 2VSMN problem based on that to the survivable network design problem [10], [16], with a time complexity reduction of O(|V|5|E|7) for strongly polynomial time and O(|V|5γ) for weakly polynomial time where -y is determined by the sizes of input. Our algorithm applies a novel greedy approach to generate a 2VSN through progressive improvement on a set of vertex-disjoint shortest path pairs incident with each terminal of S. The algorithm can be directly deployed to solve the 2-edge connected SMN problem at the same approximation ratio within time O(|V|2|S|2). To the best of our knowledge, this result presents currently the most efficient 2-approximation algorithm for the 2-connected Steiner minimal network problem.

Data publishing based on hyper graphs is becoming increasingly popular due to its power in representing multi-relations among objects. However, security issues have been little studied on this subject, while most recent work only focuses on the protection of relational data or graphs. As a major privacy breach, identity disclosure reveals the identification of entities with certain background knowledge known by an adversary. In this paper, we first introduce a novel background knowledge attack model based on the property of hyper edge ranks, and formalize the rank-based hyper graph anonymization problem. We then propose a complete solution in a two-step framework, with taking community preservation as the objective data utility. The algorithms run in near-quadratic time on hyper graph size, and protect data from rank attacks with almost same utility preserved. The performances of the methods have been validated by extensive experiments on real-world datasets as well.

We present the first efficient approximation algorithm for the Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem [13] with uniform fault tolerance levels. UFTRA is a relaxation of the classical Fault-Tolerant Facility Location problem [11]. Based on the fundamental primal-dual theory [25], our primal-dual algorithm achieves an approximation ratio of 1.861 while it can be implemented in quasi-linear time. Besides the significant improvement in runtime over all previous work, the solution quality of the algorithm matches the work in [28] using a phase-greedy algorithm and improves the result of [29] adopting the linear program rounding technique. Built on this algorithm, we also show that the capacitated UFTRA (CUFTRA) problem introduced in [13] achieves 3.722-approximation in quasi-linear time. In this paper, before the presence of the main algorithm and its extensive theoretical analysis, we provide some necessary background knowledge of the problem. This includes the problem's mathematical model formulation, the primal-dual theory applied to this formulation, and the problem's abstract system model with its potential application domains such as content distribution networks and cloud computing.

Traffic matrix describes the traffic volumes traversing the network from the input nodes to the exit nodes over a measured period. Such a matrix is very hard, if not intractable, to be obtained for a large network. We apply a new technique to analyze the traffic matrix by use of diffusion wavelet in this paper. It is shown that diffusion wavelet can do an efficient multi-resolution analysis on TM. The original TM can be reconstructed by choosing the diffused traffic in a particular level. This paper also shows there are a lot of potential applications by use of diffusion wavelet-based analysis on traffic matrix.

Double-loop networks are extensions of ring networks and are widely used in the design and implementation of local area networks and parallel processing architectures. However, embedding of other types of networks on double-loop networks has not been well studied due to the topological complexity of double-loop networks. The traditional L-shape [CHECK END OF SENTENCE], designed to compute the diameter of double-loop networks, is not effective to solve the embedding problem. We propose a novel tessellation approach to partition the geometric plane of double-loop networks into a set of parallelogram tiles, called P-shape. Based on the characteristics of P-shape, we design a simple embedding scheme, namely, P-shape embedding, that embeds meshes and tori on double-loop networks in a systematic way. Under P-shape embedding, we evaluate the embedding metrics of dilation, average dilation, and congestion, which depend heavily on the parameters of P-shape. A main merit of P-shape embedding is that a large fraction of embedded mesh/torus edges have edge dilation 1, resulting in a low average dilation. These are the first results, to our knowledge, for embedding meshes and tori on double-loop networks which is of great significance due to the popularity of these architectures. Our P-shape construction bridges between regular graphs and double-loop networks, and provides a powerful tool for studying double-loop networks.

As an integral part of data security, identity disclosureis a major privacy breach, which reveals the identification of entities with certain background knowledge known by an adversary. Most recent studies on this problem focus on the protection of relational data or simple graph data (i.e. undirected, un weighted and acyclic). However, a weighted graph can introduce much more unique information than its simple version, which makes the disclosure easier. As more real-world graphs or social networks are released publicly, there is growing concern about privacy breaching for the entities involved. In this paper, we first formalize a general anonymizing model to deal with weight-related attacks, and discuss an efficient metric to quantify information loss incurred in the perturbation. Then we consider a very practical attack based on the sum of adjacent weights for each vertex, which is known as volume in graph theory field. We also propose a complete solution for the weight anonymization problem to prevent a graph from volume attack. Our approaches are efficient and practical, and have been validated by extensive experiments on both synthetic and real-world datasets.

Geographic routing is an attractive localized routing scheme for wireless sensor networks (WSNs) due to its desirable scalability and efficiency. Maintaining neighborhood information for packet forwarding can achieve a high efficiency in geographic routing, but may not be appropriate for WSNs in highly dynamic scenarios where network topology changes frequently due to nodes mobility and availability. We propose a novel online routing scheme, called Energy-efficient Beaconless Geographic Routing (EBGR), which can provide loop-free, fully stateless, energy-efficient sensor-to-sink routing at a low communication overhead without the help of prior neighborhood knowledge. In EBGR, each node first calculates its ideal next-hop relay position on the straight line toward the sink based on the energy-optimal forwarding distance, and each forwarder selects the neighbor closest to its ideal next-hop relay position as the next-hop relay using the Request-To-Send/Clear-To-Send (RTS/CTS) handshaking mechanism. We establish the lower and upper bounds on hop count and the upper bound on energy consumption under EBGR for sensor-to-sink routing, assuming no packet loss and no failures in greedy forwarding. Moreover, we demonstrate that the expected total energy consumption along a route toward the sink under EBGR approaches to the lower bound with the increase of node deployment density. We also extend EBGR to lossy sensor networks to provide energy-efficient routing in the presence of unreliable communication links. Simulation results show that our scheme significantly outperforms existing protocols in wireless sensor networks with highly dynamic network topologies.

Data Swapping is a popular value-invariant data perturbation technique. The quality of a data swapping method is measured by how well it preserves data privacy and data utility. As swapping data globally is computationally impractical, to guarantee its performance in these metrics appropriate, localization schemes are often conducted in advance. Equi-depth partitioning is preferred by most of the existing data perturbation techniques as it provides uniform privacy protection for each data tuple. However, this method performs ineffectively for two types of applications: one is to maintain statistics based on equi-width partitioning, such as the multivariate histogram with equal bin width, and the other is to preserve parametric statistics, such as covariance, in the context of sparse data with non-uniform distribution. As a natural solution for the above application, this paper explores the possibility of using data swapping with equi-width partitioning for private data publication, which has been little used in data perturbation due to the difficulty of preserving data privacy. With extensive theoretical analysis and experimental results, we show that, Equi-Width Swapping (EWS)can achieve a similar performance in privacy preservation to that of Equi-Depth Swapping (EDS) if the number of partitions is sufficiently large (e. g. ¿ = ¿N, where N is the size of dataset). Our experimental results in both synthetic and real-world data validate our theoretical analysis.

We propose an approximation algorithm for the problem of Fault-Tolerant Facility Location which is implemented in a distributed and asynchronous manner within O(n) rounds of communication. Here n is the number of vertices in the network. As far as we know, the performance guarantee of similar algorithms (centralized) remains unknown except a special case where all cities have a uniform connectivity requirement. In this paper, we assume the shortest-path routing scheme deployed, as well as a constant (given) size of R, which represents the distinct levels of fault-tolerant capability provided by the system (i. e distinct connectivity requirements), and prove that the cost of our solution is no more than |R| · F* + 2 · C* in the general case, where F* and C* are respectively the facility cost and connection cost in an optimal solution. Further more, extensive numerical experiments showed that the quality of our solutions is comparable to the optimal solutions when |R| is no more than 10.

Anomaly-based intrusion detection is about the discrimination of malicious and legitimate behaviors on the basis of the characterization of system normality in terms of particular observable subjects. As the system normality is constructed solely from an observed sample of normally occurring patterns, anomaly detectors always suffer excessive false alerts. Adaptability is therefore a desirable feature that enables an anomaly detector to alleviate, if not eliminate, such annoyance. To achieve that, we either design self-learning anomaly detectors to capture the drifts of system normality or develop postprocessing mechanisms to deal with the outputs. As the former methodology is usually scenario- and application-specific, in this article, we focus on the latter one. In particular, our design starts from three key observations: (1) most of anomaly detectors are threshold based and parametric, that is, configurable by a set of parameters; (2) anomaly detectors differ in operational environment and operational capability in terms of detection coverage and blind spots; (3) an intrusive anomaly may leave traces across multiple system layers, incurring different observable events of interest. Firstly, we present a statistical framework to formally characterize and analyze the basic behaviors of anomaly detectors by examining the properties of their operational environments. The framework then serves as a theoretical basis for developing an adaptive middleware, which is called M-AID, to optimally integrate a number of observation-specific parameterizable anomaly detectors. Specifically, M-AID treats these fine-grained anomaly detectors as a whole and casts their collective behaviors in a framework which is formulated as a Multiagent Partially Observable Markov Decision Process (MPO-MDP). The generic anomaly detection models of M-AID are thus automatically inferred via a reinforcement learning algorithm which dynamically adjusts the behaviors of anomaly detectors in accordance with a reward signal that is defined and quantified by a suit of evaluation metrics. Fundamentally, the distributed and autonomous architecture enables M-AID to be scalable, dependable, and adaptable, and the reward signal allows security administrators to specify cost factors and take into account the operational context for taking rational response. Finally, a host-based prototype of M-AID is developed, along with comprehensive experimental evaluation and comparative studies.

With the emergence of various advanced networks that comprise a group of geographically distributed servers, such as content delivery networks (CDNs) and peer-to-peer (P2P) systems, coordinated en-route Web caching in multiserver networks becomes increasingly attractive but remains of great challenge as solutions for single-server networks become invalid here. In this paper, we first establish mathematical formulation for this problem that takes into account all requests (to any server) that pass through the intermediate nodes on a response path and caches the requested object optimally among these nodes so that system's total gain is maximized. Then, we derive efficient dynamic programming-based methods for finding optimal solutions to the problem for the unconstrained case and two QoS-constrained cases, respectively. For each case, we present a caching scheme to illustrate application of the corresponding method. Finally, we evaluate the proposed schemes on different performance metrics through extensive simulation experiments. The experiment results show that our proposed schemes can yield a steady performance improvement and achieve desired QoS in a multiserver network. To the best of our knowledge, these are the first results for solving the problem of coordinated en-route Web caching in multiserver networks.

Many applications require performing set operations without publishing individual datesets. In this article, we address this problem for five fundamental set operations including set intersection, cardinality of set intersection, element reduction, overthreshold set-union, and subset relation. Our protocols are obtained in the universally composable security framework, in the assumption of the probabilistic polynomial time bounded adversary, which actively controls a fixed set of t parties and the assumption of an authenticated broadcast channel. Our constructions utilize building blocks of nonmalleable NonInteractive Zero-Knowledge (NIZK) arguments, which are based on a ( t + 1, N )-threshold version ( N is the number of parties in the protocol) of the boneh-goh-nissim (BGN) cryptosystem whose underlying group supports bilinear maps, in the assumption that the public key and shares of the secret key have been generated by a trusted dealer. The previous studies were all based on the stand-alone model with the same assumptions on the adversary, broadcast channel, and key generation. For the first four operations, we propose protocols that improve the previously known results by an O ( N ) factor in the computation and communication complexities. For the subset relation, our protocol is the first one secure against the active adversary. Our constructions of NIZK have independent interest in that, though also mentioned as building blocks, the previous work did not illustrate how to construct them. We construct these NIZK with an additional nonmalleable property, the same complexity as claimed in the previous work, and also an improvement on the communication complexity.

We address the problems of privacy-preserving duplicate tuple matching (PPDTM) and privacy-preserving threshold attributes matching (PPTAM) in the scenario of a horizontally partitioned database among N parties, where each party holds a private share of the database's tuples and all tuples have the same set of attributes. In PPDTM, each party determines whether its tuples have any duplicate on other parties' private databases. In PPTAM, each party determines whether all attribute values of each tuple appear at least a threshold number of times in the attribute unions. We propose protocols for the two problems using additive homomorphic cryptosystem based on the subgroup membership assumption, e.g., Paillier's and ElGamal's schemes. By analysis on the total numbers of modular exponentiations, modular multiplications and communication bits, with a reduced computation cost which dominates the total cost, by trading off communication cost, our PPDTM protocol for the semihonest model is superior to the solution derivable from existing techniques in total cost. Our PPTAM protocol is superior in both computation and communication costs. The efficiency improvements are achieved mainly by using random numbers instead of random polynomials as existing techniques for perturbation, without causing successful attacks by polynomial interpolations. We also give detailed constructions on the required zero-knowledge proofs and extend our two protocols to the malicious model, which were previously unknown.

Unbalanced energy consumption is an inherent problem in wireless sensor networks characterized by multihop routing and many-to-one traffic pattern, and this uneven energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of maximizing network lifetime through balancing energy consumption for uniformly deployed data-gathering sensor networks. We formulate the energy consumption balancing problem as an optimal transmitting data distribution problem by combining the ideas of corona-based network division and mixed-routing strategy together with data aggregation. We first propose a localized zone-based routing scheme that guarantees balanced energy consumption among nodes within each corona. We then design an offline centralized algorithm with time complexity O(n) (n is the number of coronas) to solve the transmitting data distribution problem aimed at balancing energy consumption among nodes in different coronas. The approach for computing the optimal number of coronas in terms of maximizing network lifetime is also presented. Based on the mathematical model, an energy-balanced data gathering (EBDG) protocol is designed and the solution for extending EBDG to large-scale data-gathering sensor networks is also presented. Simulation results demonstrate that EBDG significantly outperforms conventional multihop transmission schemes, direct transmission schemes, and cluster-head rotation schemes in terms of network lifetime.

Probability density estimation is a very important technology which has been widely used in data mining and data analysis. In this paper, we generalize the traditional Parzen window method to data streams and propose a new method of tilted Parzen window (TPW) for probability density estimation. To adapt to the evolvement of the data streams, we use the tilted window size that is proportional to datapsilas arrival time instead of the fixed window size. Theoretical analysis shows that the tilted Parzen window method is a valid method for estimating the probability density function (pdf) for data streams. We also propose a new strategy for discarding the historical data in data streams. We prove that this strategy can describe the probability density changes more accurately than the conventional discarding strategy. Empirical results on synthetic data set demonstrate the effectiveness and efficiency of this method.

Energy-constraint is a crucial problem in wireless sensor networks (WSNs). Many sensor node (SN) placement schemes and routing protocols are proposed to address this problem. In this paper, we first present how to place SNs by use of a minimal number to maximize the coverage area when the communication radius of the SN is not less than the sensing radius, which results in the application of regular topology to WSNs deployment. With nodes placed at an equal distance and equipped with an equal power supply, we discuss the energy imbalance problem and then give the mathematical formulation for maximizing network lifetime in grid-based WSNs. The formulation shows the problem of maximizing network lifetime is a non-linear programming problem and NP-hard even in the 1-D case. We discuss several heuristic solutions and show that the halving shift data collection scheme is the best solution among them. We also generalize the maximizing network lifetime problem to the randomly-deployed WSNs which shows the significance of our mathematical formulation for this crucial problem.

No abstract available.

Hypercube communication is one of the most versatile and efficient communication patterns shared by a large number of computational problems. In this paper, we study routing and wavelength assignment for realizing hypercube communications on WDM optical networks including linear arrays and rings with the consideration of communication directions. Specifically, we consider this problem for both bidirectional and unidirectional hypercube communications. For each case, we identify a lower bound on the number of wavelengths required, and present a simple embedding scheme and wavelength assignment algorithm that uses a provably near-optimal number of wavelengths. By realizing hypercube computations in optical networks, the hypercube computation speed can be significantly improved compared with the traditional electronic networks.

This paper introduces a novel geographic routing protocol called Energy-Efficient Geographic Routing (EEGR) for wireless sensor networks. In EEGR, both geographic information and transceiver power characteristics are employed to make forwarding decisions, thereby enabling an energy-aware localized routing strategy. We prove that EEGR is loop-free and derive the bounds on hop count for sensor- to-sink packet delivery. In particular, we analyze the energy dissipation under EEGR and present the approximated expected energy consumption for sensor-to-sink data delivery when nodes are uniformly deployed. Simulation results demonstrate that EEGR can provide near-optimal energy- efficient routing only based on local information.

Unbalanced energy consumption is an inherent problem in wireless sensor networks where some nodes may be overused and die out early, resulting in a short network lifetime. In this paper, we investigate the problem of balancing energy consumption for data gathering sensor networks. Our key idea is to exploit the tradeoff between hop-by-hop transmission and direct transmission to balance energy dissipation among sensor nodes. By assigning each node a transmission probability which controls the ratio between hop-by-hop transmission and direct transmission, we formulate the energy consumption balancing problem as an optimal transmission probability allocation problem. We discuss this problem for both chain networks and general networks. Moreover, we present the solution to compute the optimal number of sections in terms of maximizing the network lifetime. Numerical results demonstrate that our methods outperform the traditional hop-by-hop and direct transmission schemes and achieve significant lifetime extension especially for dense sensor networks.

When datasets are distributed on different sources, finding out their intersection while preserving the privacy of the datasets is a widely required task. In this paper, we address the privacy preserving set intersection (PPSI) problem, in which each of the N parties learns no elements other than the intersection of their N private datasets. We propose an efficient protocol in the malicious model, where the adversary may control arbitrary number of parties and execute the protocol for its own benefit. A related work in [12] has a correctness probability of ( v;1)ldquo (f is the size of the encryption scheme's plaintext space), a computation complexity of' 0(N2 S2lgf) (S is the size of each party's data set). Our PPSI protocol in the malicious model has a correctness probability iquest/C a/-1)JV~1 plusmnmiddotd achieves a computation cost of 0{c2S2lgM) (c is the number of malicious parties and c < N eurordquo I).

Coordinated en-route Web caching has been studied extensively in the recent years. In that scheme, all requests are destined to one server and the requested object is selectively cached at nodes on the route of each response message. In this paper, we extend the scheme to a p-server network and optimize the caching decision by considering all requests that pass through individual nodes on a route, including those destined to servers not on the route. We present an efficient method to find the optimal solution to this problem using dynamic programming technique. Our method can be used for coordinated en-route caching in a p-server network of arbitrary topology.

Abstract Advances in the Internet and the computer industry have created many new application areas for network routing such as Grid computing and also brings new challenges to traditional routing techniques. In this paper we propose a mobile agent‐based routing model in vulnerable networks for these applications. To characterize the behaviors of mobile agents and their effects on the network performance, we analyze the population distribution of mobile agents as a measurement of the computational resource consumption. Our analysis reveals theoretical insights into the statistical behaviors of mobile agents and provides useful tools for effectively managing mobile agents in large networks. Copyright © 2006 John Wiley & Sons, Ltd.

Transparent data replication is a promising technique for improving the system performance of a large distributed network. Transcoding is an important technology which adapts the same multimedia object to diverse mobile appliances; thus, users' requests for a specified version of a multimedia object could be served by a more detailed version cached according to transcoding. Therefore, it is particularly of theoretical and practical necessity to determine the proper version to be cached at each node such that the specified objective is achieved. In this paper, we address the problem of multimedia object placement for transparent data replication. The performance objective is to minimize the total access cost by considering both transmission cost and transcoding cost. We present optimal solutions for different cases for this problem. The performance of the proposed solutions is evaluated with a set of carefully designed simulation experiments for various performance metrics over a wide range of system parameters. The simulation results show that our solution consistently and significantly outperforms comparison solutions in terms of all the performance metrics considered

In this paper, we study the problem of data gathering in multi-hop wireless sensor networks. To tackle the high degree of channel contention and high probability of packet collision induced by bursty traffic, we introduce a novel model based on random channel access scheme for data gathering. In our model, both data delivery reliability and latency are considered, and our goal is to tune the attempt probability for each sensor node so that the data gathering duration can be minimized on condition that each link in the data gathering tree can provide guaranteed per-hop packet delivery reliability. We formulate this problem as an optimization problem and propose a distributed heuristic algorithm which exploits only two hop neighbors information to solve it for tree networks. We evaluate the algorithm and the model by simulations, and results show that our algorithm has low computational complexity and our model can provide a good trade-off between reliability and latency for data gathering

A new rearrangeable nonblocking photonic multi- log2N network DM(N) is introduced. It is shown that DM(N) network simultaneously possesses many good properties, including those of existing rearrangeable nonblocking multi-log2N networks and new ones such as O (log N) -time fast parallel self-routing and nonblocking multiple-multicast.

Hypercube communication is one of the most versatile and efficient communication patterns for parallel computation. Routing and wavelength assignments for realizing hypercube communications on WDM linear arrays, rings, meshes and tori have been discussed in our past researches. In this paper, we study routing and wavelength assignment for realizing hypercube communications on WDM chordal ring networks of degree 3. We design embedding scheme and derive the number of wavelengths required for different chord length. Based on embedding scheme of double cycle embedding, we also provide the analysis of chord length with optimal number of wavelengths to realize hypercube communications on 3-degree chordal rings. Results show that the wavelength requirement for realizing hypercube communications on optical networks has been further reduced on optical 3-degree chordal ring networks compared with some topologies discussed before. Our results have both theoretical and practical significance as WDM optical networks have an increasing popularity

Data aggregation is a widely used technique in wireless sensor networks. The security issues, data confidentiality and integrity, in data aggregation become vital when the sensor network is deployed in a hostile environment. There has been many related work proposed to address these security issues. In this paper we survey these work and classify them into two cases: hop-by-hop encrypted data aggregation and end-to-end encrypted data aggregation. We also propose two general frameworks for the two cases respectively. The framework for end-to-end encrypted data aggregation has higher computation cost on the sensor nodes, but achieves stronger security, in comparison with the framework for hop-by-hop encrypted data aggregation

Dual-server coordinated en-route caching is important because of its basic features as multi-server en-route caching. In this paper, multi-server coordinated en-route caching is formulated as an optimization problem of minimizing total access cost, including transmission cost for all access demands and caching cost of all caches. We first discuss an algorithm for single-server en-route caching in tree networks and then show that this is a special case of another algorithm for dual-server en-route caching in tree networks whose time complexity is O(nh)

The maximal rates and the minimal delays are basic problems of space-time block codes from complex orthogonal designs. Liang systematically solved the problem on the maximal rates of complex orthogonal designs, and posed an open problem on the minimal delays. Recently, the authors gave the negative answer for the open problem. In this letter, we give lower bounds on the minimal delays.

More and more sensor networks will be deployed in the place where people are living, studying, and working. These sensor networks bring us the convenience of accessing information anytime and anywhere, whereas put our voice, motion, or even body temperature under surveillance. Under the circumstances of pervasively deployed sensor networks, people will have a dynamic concern about their privacy. At the same time, sensors will become invisible or should be hidden due to the privacy of themselves. This paper discusses privacy issues in pervasive sensor networks and proposes a general scheme for people in the environment of pervasive sensor networks, so that they can be aware of whether they should be alert on their privacy activities. Based on the protocol of secure two-party point-inclusion problem, the scheme has the characteristics of generality and confidentiality.

Topology information of a multicast network benefits significantly to many applications such as resource management, loss and congestion recovery. In this paper we propose a new algorithm, namely binary hamming distance and hop count based classification algorithm (BHC), to infer multicast network topology from end-to-end measurements. The BHC algorithm identifies multicast network topology using hamming distance of the sequences on receipt/loss of probe packets maintained at each pair of nodes and incorporating the hop count available at each node. We analyze the inference accuracy of the algorithm and prove that the algorithm can obtain accurate inference at higher probability than previous algorithms for a finite number of probe packets. We implement the algorithm in a simulated network and validate the algorithm's performance in accuracy and efficiency.

An autonomic detection coordinator is developed in this paper, which constructs a multi-layered boundary to defend against host-based intrusive anomalies by correlating several observation-specific anomaly detectors. Two key observations facilitate the model formulation: first, different anomaly detectors have different detection coverage and blind spots; second, diverse operating environments provide different kinds of information to reveal anomalies. After formulating the cooperation between basic detectors as a partially observable Markov decision process, a policy-gradient reinforcement learning algorithm is applied to search in an optimal cooperation manner, with the objective to achieve broader detection coverage and fewer false alerts. Furthermore, the coordinator's behavior can be adjusted easily by setting a reward signal to meet the diverse demands of changing system situations. A preliminary experiment is implemented, together with some comparative studies, to demonstrate the coordinator's performance in terms of admitted criteria.

In this paper, we address present an optimal solution for the problem of multimedia object placement for hybrid transparent data replication. The performance objective is to minimize the total access cost by considering both transmission cost and transcoding cost. The performance of the proposed solution is evaluated with a set of carefully designed simulation experiments for various performance metrics over a wide range of system parameters. The simulation results show that our solution consistently and significantly outperforms comparison solutions in terms of all the performance metrics considered.

Mobile agent-based technology has attracted considerable interest in both academia and industry in recent years. Many agent-based execution models have been proposed and their effectiveness have been demonstrated in the literature. However, these models require a high overhead to achieve the reliable execution of mobile agents. In this paper, we propose a new mobile agent-based execution model, which is based on a surveillant mechanism. Extensive theoretical analysis of a stochastic nature is provided to evaluate the performance of our model, including the transaction time from node to node, the life expectancy of mobile agents, and the population distribution of mobile agents. The analytical results reveal new theoretical insights into the fault-tolerant execution of mobile agents and show that our model outperforms the existing fault-tolerant models. Our model provides an efficient way to increase overall performance and a promising method in achieving mobile agent system reliability.

One of the important techniques to monitor and control large-scale networks today is to implement only at the end. However end-based control needs to have the knowledge of network internal characteristics. The paper proposes a novel approach to discover network internal characteristics from end-to-end multicast traffic measurements, which requires no support from internal routers. Our approach is based on Hamming distance of sequences on receipt/loss of probe packets maintained at each pair of nodes. As we discuss in this paper, our approach mainly focuses on identification of network internal characteristics of routing topology and loss performance. The simulation shows that the Hamming distance-based approach can discover the routing topology which is more accurate and efficient with a finite number of probe packets than before. The Hamming distance matrix proposed in this paper can also effectively discover the loss performance of the network.

Barni's wavelet-based watermarking algorithm using a pixel-wise masking model shows great superiority over other methods in terms of the watermark imperceptibility and robustness against attacks including filtering, noise addition and compression. However, this algorithm adds the watermark into the three largest detail subbands, which gives the attackers the opportunity to remove it completely by just discarding these subbands. Moreover, Barni's pixel-masking model only uses the coarsest approximation subband to compute the local brightness and texture activity, which is usually too small to contain enough information. Following this pixel-wise masking idea, a new watermarking algorithm is presented in this paper, in which an improved version of the pixel-masking model that better describes the behavior of the HVS is designed, and a novel watermark embedder that adds the watermark into the most attack-resilient coefficients of all the detail subbands is proposed. Experiments verify that our algorithm is more robust than Barni's method.

Transcoding is an important technology which adapts the same multimedia object to diverse mobile appliances; thus, users' requests for a specified version of a multimedia object could be served by a more detailed version cached according to transcoding. Therefore, it is of particularly theoretical and practical necessity to determine the proper versions to be cached at a node such that the specified objective is achieved. In this paper, we address the problem of multimedia object placement. The performance objective is to minimize the total access cost by considering both transmission cost and transcoding cost. We present an optimal dynamic programming-based solution for this problem. The performance of the proposed solutions is evaluated with a set of carefully designed simulation experiments for various performance metrics over a wide range of system parameters. The simulation results show that our solution consistently and significantly outperforms comparison solutions in terms of all the performance metrics considered.

Fast Fourier Transform(FFT) represents a common communication pattern shared by a large class of scientific and engineering problems and wavelength assignment is a key issue to increase efficiency and reduce cost in Wavelength Division Multiplexing (WDM) optical networks. In this paper, we propose a new scheme for the wavelength assignment of parallel FFT communication pattern on WDM linear arrays. By lattice embedding, the number of wavelengths required to realize parallel FFT communication pattern on WDM linear arrays significantly improves the known result. Our proposed embedding method also provides a new approach to the hypercube layout problem considering connections dimension by dimension rather than all connections as in the traditional approach.

A novel blind logo-watermarking algorithm for copyright protection of JPEG-compressed images is proposed. A visually meaningful grayscale logo is encoded by the (255, 9) BCH code into a codeword that is embedded as the watermark into the wavelet domain of the host image using a pixel-wise masking model. A trellis is generated with a specific path corresponding to that codeword. At the receiving end where the watermarked image is stored in a JPEG file, the codeword is recovered approximately through running the viterbi decoder on the trellis even without reference to the original host data, and then decoded back to the embedded logo by the (255, 9) BCH codec. Thanks to the BCH code’s powerful error correction capability and human vision system’s great tolerance to image noise, the extracted logo, possibly degraded, contains much more convincing information than that of a randomly-generated numerical sequence that is widely used in traditional watermarking strategies. Experimental results of successfully hiding a 32 × 32, grayscale logo into 512 × 512 JPEG-compressed images verify our algorithm’s practical performance.

In multiple-precision algorithms, the design and implementation of division is the most complicated. On the basis of some classical algorithms, this paper introduces an efficient improved algorithm. This algorithm omits the most majority of normalization of classical algorithms and uses integer arithmetic instead of floating-point data. By analyzing the algorithm and comparing the arithmetic cost, we conclude that this algorithm is at least three times faster than the most efficient previous solution. Key words: multiple-precision, algorithm, division.

Uncertain information will often exist in a complicated system which may result from many reasons. The accuracy of the conclusion will definitely be influenced without taking this uncertain information into consideration in the process of decision-making. By considering these uncertain factors, the solution proposed in the essay to multi-objective fuzzy optimization dynamic programming makes itself more universal.

Research on non-structural system group decision-making problems largely depends on the knowledge and experience of the experts for tactical analysis. The usual method of voting may result in a great loss of information in case of much renunciation, and the accuracy of voting can therefore be directly influenced.This paper proposes a new solution to non-structural system group decision-making problems by taking advantage of the characteristics of correlate and the information easy to lose to make an overall analysis of the ayes, blackballs and renunciation polls for an accurate result.

The maximal rates and the minimal delays are basic problems of space-time block codes from complex orthogonal designs. Liang [5] systematically solved the problem on the maximal rates for a special kind of complex othogonal designs, and posed an open problem on the minimal delays. Recently, Kan & Shen [3] gave a negative answer for the open problem. In the paper, we prove that the maximal code rates that Liang gave in [5] also hold for more general complex orthogonal designs.

This paper surveys the state of the art of agentbased fault tolerance techniques. Existing mobile agent-based fault-tolerant techniques are identified on prevent mobile agents from being blocked by a failure.

The problem of secure two-party vector dominance requires the comparison of two vectors in an "all-or-nothing" way. In this paper we provide a solution to this problem based on the semi-honest model. It is reduced to the problem of privacy preserving prefix test, and an additive threshold homomorphic encryption is used to protect those privacies while computing the results of all of the prefix tests. Our solution has advantages of efficiency and security in comparison with other solutions.

Topology is important for any type of networks because it has great impact on the performance of the network. For wireless sensor networks (WSN), regular topologies, which can help to efficiently save energy and achieve long networking lifetime, have been well studied in [1, 4, 5, 7, 9]. However, little work is focused on routing in patterned WSNs except the shortest path routing with the knowledge of global location information. In this paper, we propose a routing protocol based on random walk. It doesn’t require global location information. Moreover, the random walk routing achieves load balancing property inherently for WSNs which is difficult to achieve for other routing protocols. We also prove that the random walk routing consumes the same amount of energy as the shortest path routing in the scenarios where the message required to be sent to the base station is in comparatively small size with the inquiry message among neighboring nodes. Since in many applications of WSNs, sensor nodes often send only beeplike small messages to the base station to report their status, our proposed random walk routing is a viable scheme. Though the random walk routing provides load balancing in the WSN, the nodes near to the base station (BS) are inevitably under heavier burden than the nodes far from the base station. Therefore we further propose a density-aware deployment scheme to guarantee that the heavy-load nodes do not affect the network lifetime even if they are exhausted.

For the problem of decision tree classification with privacy concerns, we propose several efficient secure multi-party computation protocols to construct a privacy preserving ID3 algorithm over horizontally partitioned data among multiple parties. Our algorithm presents the first solution to privacy preserving decision tree classification among more than two parties. We also make a performance comparison with the existing solution, which is only applicable to the twoparty case. The result shows that our solution has a significantly better performance.

Segmentation is a crucial precursor to most medical image analysis applications. This paper presents a new three-dimensional adaptive region growing algorithm for the automatic segmentation of three-dimensional images. The principle of our algorithm is to obtain a satisfactory segment result by self-tuning the homogeneity constraint step by step, which effectively resolves the dilemma of threshold auto-selection. Novel homogeneity and leakage detection criteria are designed to improve accuracy and robustness. Cavities auto-filling algorithm is also proposed to eliminate the interior cavities. Our algorithm was tested by segmenting lungs from 3D throat CT images and compared with manual segmentation and traditional 3D region growing. Results demonstrate that our algorithm greatly outperforms traditional 3D region growing method and its segment result is close to that of manual segmentation.

As two different research topics with much overlap, dependability and security of computer/communication systems have respective long and rich history. The development of the techniques for their modeling and analysis thus have followed distinct but convergent paths. In essence, diverse attributes and the fundamental difference between the nature of the failures bring in different concerns for dependability and security analysis during their modeling process. Taking the understanding of the basic concepts/attributes as a point of departure, this paper intend to carry out a comparative study on the analytical models of computer system dependability and security. Also, by examining the state-of-the-art quantitative techniques and sound modeling methodologies for dependability evaluation, e.g., combinatorial and stochastic methods, we attempt to explore why and how those methods can be extended to evaluate computer system security. Furthermore, we take our developed autonomic detection coordinator (for intrusion detection) as a case study to conduct the comparative analysis.

In this paper, we address the problem of cache replacement for transcoding proxy caching. First, an efficient cache replacement algorithm is proposed. Our algorithm considers both the aggregate effect of caching multiple versions of the same multimedia object and cache consistency. Second, a complexity analysis is presented to show the efficiency of our algorithm. Finally, some preliminary simulation experiments are conducted to compare the performance of our algorithm with some existing algorithms. The results show that our algorithm outperforms others in terms of the various performance metrics.

We propose a new highly scalable wavelet transform-based image coder, called S-SPECK, on the extension of a well-known zero-block image coder SPECK, by achieving not only distortion scalability, resolution scalability, and region of interest (ROI) retrievability, but also excellent compression performance with very low computational complexity. Though new features have been introduced into S-SPECK, our coder is quite competitive with SPECK on compression performance (peak signal-to-noise ratio) and computational complexity (encoding and decoding times) at various bit rates for standard test images. A novel quality layer formatting method is implemented in S-SPECK, which is much simpler and faster than PCRD used in JPEG2000. Extensive experiments have verified all our claims for S-SPECK.

X. Liang systematically investigated orthogonal designs with maximal rates, gave the maximal rates of complex orthogonal designs and a concrete construction procedure for complex orthogonal designs with the maximal rates. He also posed an open problem on the minimal decoding delays of complex orthogonal designs with maximal rates, and proved that the problem is correct for less than or equal to six transmit antennas. In this correspondence, we give a counterexample for the open problem for n=8 and prove that the minimal delay for complex orthogonal designs with eight columns is 56. Hence, we give a negative answer for the open problem.

It was conjectured by Koetter and Vardy that if the k characteristic generators of a linear code C are linearly independent, then the corresponding n-k characteristic generators of the dual code C/sup /spl perp// are also linearly independent. In this correspondence, we prove that the conjecture is true for self-dual codes and cyclic codes.

Web caching is an important technology for improving the scalability of Web services. One of the key problems in coordinated enroute Web caching is to compute the locations for storing copies of an object among the enroute caches so that some specified objectives are achieved. In this article, we address this problem for tree networks, and formulate it as a maximization problem. We consider this problem for both unconstrained and constrained cases. The constrained case includes constraints on the cost gain per node and on the number of object copies to be placed. We present dynamic programming-based solutions to this problem for different cases and theoretically show that the solutions are either optimal or convergent to optimal solutions. We derive efficient algorithms that produce these solutions. Based on our mathematical model, we also present a solution to coordinated enroute Web caching for autonomous systems as a natural extension of the solution for tree networks. We implement our algorithms and evaluate our model on different performance metrics through extensive simulation experiments. The implementation results show that our methods outperform the existing algorithms of either coordinated enroute Web caching for linear topology or object placement (replacement) at individual nodes only.

Transcoding is a promising technology that allows systems to effect a quality-versus-size tradeoff on multimedia objects. As audio and video applications have proliferated on the Internet, caching in transcoding proxies has become an important technique for improving network performance, especially in mobile networks. This article addresses the problem of coordinated enroute multimedia object caching in transcoding proxies for tree networks. We formulate this problem as an optimization problem based on our proposed model, in which multimedia object caching decisions are made on all enroute caches along the routing path by integrating both object placement and replacement policies and cache status information along the routing path of a request is used to determine the optimal locations for caching multiple versions of the same multimedia object. We propose an optimal solution using dynamic programming to compute the optimal locations. We also extend this solution to solve the same problem for several constrained cases, including constraints on the cost gain per node and on the number of versions to be placed. Our model is evaluated on different performance metrics through extensive simulation experiments. The implementation results show that our model significantly outperforms existing models that consider Web caching in transcoding proxies either on a single path or at individual nodes.

To break the strong assumption that most of the training data for intrusion detectors are readily available with high quality, conventional SVM, Robust SVM and one-class SVM are modified respectively in virtue of the idea from Online Support Vector Machine (OSVM) in this paper, and their performances are compared with that of the original algorithms.Preliminary experiments with 1998 DARPA BSM data set indicate that the modified SVMs can be trained online and the results outperform the original ones with less support vectors(SVs) and training time without decreasing detection accuracy.Both of these achievements benefit an effective online intrusion detection system significantly.

The use of multicast inference on end-to-end measurement has recently been proposed as a means of obtaining the underlying multicast topology. We analyze the algorithm of binary loss tree classification with hop count (HBLT). We compare it with the binary loss tree classification algorithm (BLT) and show that the probability of misclassification of HBLT decreases more quickly than that of BLT as the number of probing packets increases. The inference accuracy of HBLT is always 1 (the inferred tree is identical to the physical tree) in the case of correct classification, whereas that of BLT is dependent on the shape of the physical tree and inversely proportional to the number of internal nodes with a single child. Our analytical result shows that HBLT is superior to BLT, not only on time complexity, but also on misclassification probability and inference accuracy.

Mobile agent-based technology has attracted considerable interest in both academia and industry in recent years. Fault tolerance is of paramount importance to integrate mobile agent-based technology into today's e-society. In this paper, we propose a mobile agent-based fault-tolerant execution model and analyze the stochastic nature of mobile agents, including the transaction time from node to node, the life expectancy of mobile agents, and the population distribution of mobile agents. Our approach exploits a new way to design fault-tolerant mobile agent-driven system. Our analysis provides useful tools for effectively estimating the performance of agent-driven systems.

Pearlman's SPECK image coding algorithm is a distortion scalable coder which achieves excellent compression performance with very low computational complexity. However, SPECK has no resolution and ROI (region of interest) scalabilities In this paper, we extend it to a novel highly scalable image coder named S-SPECK through an efficient strategy of grouping the wavelet coefficients according to their resolution levels mid relationship with ROIs. The proposed new coder not only retains all the advantages of SPECK, but also implements resolution and ROI scalabilities, which, we believe, is a better alternative than JPEG2000 for some applications. Extensive experiments have been conducted to verify all our claims.

Given its strong similarity to the human visual system, the wavelet transform has been applied in watermarking successfully. However, due to its sensitivity to rotation, scaling and translation, the wavelet-based watermarking algorithms are vulnerable to geometrical attacks. In this paper, we design a novel wavelet-based watermarking scheme resilient to geometrical attacks using a rotation-invariant log-polar mapping to eliminate all the effects of the geometrical operations in the input image before computing its discrete wavelet transform. A pixel-wise masking method used in the wavelet domain to scale the watermark is applied in order to achieve the best compromise between the requirements of robustness and imperceptibility for the embedded watermark. Experimental results demonstrate the advantages of our scheme, particularly its robustness against geometrical attacks.

Web caching is an important technique for reducing web traffic, user access latency, and server load and cache replacement plays an important role in the functionality of web caching. In this paper we propose an improved GreedyDual (GD) cache document replacement algorithm, which considers update frequency as a factor in its utility function. We use both trace data and statistical data to simulate our proposed algorithm. The experimental results show that our improved GD algorithm can outperform the existing GD algorithm over the performance metrics considered.

Vertical stacking of optical banyan networks is an attractive scheme for building nonblocking (crosstalk-free) optical switching networks. The resulting networks, namely vertically stacked optical banyan (VSOB) networks, preserve all the good properties of banyan networks, but increase the hardware cost significantly. In this paper, we study the blocking probabilities of VSOB networks under random routing strategy, and develop a model to compute the blocking probabilities with respect to the number of planes in the networks. Our model calculates the blocking probabilities stage by stage recursively, and it depicts accurately the blocking behaviors of VSOB networks under random routing. The proposed model is significant because it reveals the inherent relationships between blocking probability and network hardware cost in terms of the number of planes, and provides network developers a quantitative guidance to find a desirable tradeoff between blocking probability and hardware cost. An important conclusion drawn from our work that has practical applications is that the hardware cost of a VSOB network can be reduced dramatically if a predictable and almost negligible non-zero blocking probability is allowed.

Banyan networks are attractive for constructing directional coupler (DC)-based optical switching networks for their small depth and self-routing capability. Crosstalk between optical signals passing through the same DC is an intrinsic drawback in DC-based optical networks. Vertical stacking of multiple copies of an optical banyan network is a novel scheme for building nonblocking (crosstalk-free) optical switching networks. The resulting network, namely vertically stacked optical banyan (VSOB) network, preserves all the properties of the banyan network, but increases the hardware cost significantly. Though much work has been done for determining the minimum number of stacked copies (planes) required for a nonblocking VSOB network, little is known on analyzing the blocking probabilities of VSOB networks that do not meet the nonblocking condition (i.e., with fewer stacked copies than required by the nonblocking condition). In this paper, we analyze the blocking probabilities of VSOB networks and develop their upper and lower bounds with respect to the number of planes in the networks. These bounds depict accurately the overall blocking behaviors of VSOB networks and agree with the conditions of strictly nonblocking and rearrangeably nonblocking VSOB networks respectively. Extensive simulation on a network simulator with both random routing and packing strategy has shown that the blocking probabilities of both strategies fall nicely within our bounds, and the blocking probability of packing strategy actually matches the lower bound. The proposed bounds are significant because they reveal the inherent relationships between blocking probability and network hardware cost in terms of the number of planes, and provide network developers a quantitative guidance to trade blocking probability for hardware cost. In particular, our bounds provide network designers an effective tool to estimate the minimum and maximum blocking probabilities of VSOB networks in which different routing strategies may be applied. An interesting conclusion drawn from our work that has practical applications is that the hardware cost of a VSOB network can be reduced dramatically if a predictable and almost negligible nonzero blocking probability is allowed.

Ant routing is a method for network routing in agent technology. Although its effectiveness and efficiency have been demonstrated and reported in the literature, its properties have not yet been well studied. This paper presents some preliminary analysis on an ant algorithm in regard to its population growing property and jumping behavior. Results conclude that as long as the value max, {i/spl Omega//sub j/|} is known, the practitioner is able to design the algorithm parameters, such as the number of agents being created for each request, k, and the maximum allowable number of jumps of an agent, in order to meet the network constraint.

Crosstalk in optical switching elements (SEs) is one of the major shortcomings in optical switching networks, and avoiding crosstalk is an important issue for proper optical network operation. We propose a new class of optical multistage interconnection networks (MINs)-vertically stacked Benes networks VSB(N, K) that have N inputs (outputs) and consist of K vertically stacked Benes networks. The VSB(N, K) network can support any permutation of an N-element set {0, 1, ..., N-1}. Complete algorithms to realize crosstalk-free permutation in a VSB(N, K) network are the main contributions of this paper.

We study the problem of computing classification rule sets from relational databases so that accurate predictions can be made on test data with missing attribute values. Traditional classifiers perform badly when test data are not as complete as the training data because they tailor a training database too much. We introduce the concept of one rule set being more robust than another, that is, able to make more accurate predictions on test data with missing attribute values. We show that the optimal class association rule set is as robust as the complete class association rule set. We then introduce the k-optimal rule set, which provides predictions exactly the same as the optimal class association rule set on test data with up to k missing attribute values. This leads to a hierarchy of k-optimal rule sets in which decreasing size corresponds to decreasing robustness, and they all more robust than a traditional classification rule set. We introduce two methods to find k-optimal rule sets, i.e. an optimal association rule mining approach and a heuristic approximate approach. We show experimentally that a k-optimal rule set generated by the optimal association rule mining approach performs better than that by the heuristic approximate approach and both rule sets perform significantly better than a typical classification rule set (C4.5Rules) on incomplete test data.

The linear array with a reconfigurable pipelined bus system (LARPBS) is a newly introduced parallel computational model, where processors are connected by a reconfigurable optical bus. In this paper, we show that the selection problem can be solved on the LARPBS model deterministically in O((loglogN)/sup 2// log log log N) time. To our best knowledge, this is the best deterministic selection algorithm on any model with a reconfigurable optical bus.

We present four efficient parallel algorithms for computing a nonequijoin, called range-join, of two relations on N-dimensional mesh-connected computers. Range-joins of relations R and S are an important generalization of conventional equijoins and band-joins and are solved by permutation-based approaches in all proposed algorithms. In general, after sorting all subsets of both relations, the proposed algorithms permute every sorted subset of relation S to each processor in turn, where it is joined with the local subset of relation R. To permute the subsets of S efficiently, we propose two data permutation approaches, namely, the shifting approach which permutes the data recursively from lower dimensions to higher dimensions and the Hamiltonian-cycle approach which first constructs a Hamiltonian cycle on the mesh and then permutes the data along this cycle by repeatedly transferring data from each processor to its successor. We apply the shifting approach to meshes with different storage capacities which results in two different join algorithms. The basic shifting join (BASHJ) algorithm can minimize the number of subsets stored temporarily at a processor, but requires a large number of data transmissions, while the buffering shifting join (BUSHJ) algorithm can achieve a high parallelism and minimize the number of data transmissions, but requires a large number of subsets stored at each processor.

Mining transaction databases for association rules usually generates a large number of rules, most of which are unnecessary when used for subsequent prediction. In this paper we define a rule set for a given transaction database that is much smaller than the association rule set but makes the same predictions as the association rule set by the confidence priority. We call this subset the informative rule set. The informative rule set is not constrained to particular target items; and it is smaller than the non-redundant association rule set. We present an algorithm to directly generate the informative rule set, i.e., without generating all frequent itemsets first, and that accesses the database less often than other unconstrained direct methods. We show experimentally that the informative rule set is much smaller than both the association rule set and the non-redundant association rule set, and that it can be generated more efficiently.

In this paper, we present two efficient parallel algorithms for computing a non-equijoin, range-join, of two relations an N-dimensional mesh-connected computers. The proposed algorithms uses the data-shifting approach to effectively permute every sorted subset of relation S to each processor in turn recursively in dimensions from low to high, where it is joined with the local subset of relation R.

We address the problem of generating ATM labels which facilitates IP packet flow through the network. We define the virtual flow topology and provide a stochastic algorithm GFLOW, that generates labels for virtual connections using periodic broadcasts providing simple and efficient robustness and oblivious execution. For a random network with N nodes of average degree d~~~ and dimeter /spl Theta/(k), we demonstrate how our algorithm can be used to generate a mean l=1+(k-1)d~~ labels at each node to provide a probability /spl Theta/(1/N) that any pair of nodes will have a virtual connection between them. We show that with probability roughly 1/2 +1/2N any node may route a message along a virtual connection which terminates within an /spl epsiv/-neighborhood of the destination, where /spl epsiv/=/spl Theta/ (log/sub d/~ (N/k)), with l as stipulated. Of course the number of labels generated at each node is variable and directly relates to the cost in such a way that a network administrator can trade label space for increased performance. We provide simulation results using Matlab mathematical language interpreter that supports our analysis.

Mesh-connected computers (MCCs) are a class of important parallel architectures due to their simple and regular interconnections. However, their performances are restricted by their large diameters. Various augmenting mechanisms have been proposed to enhance the communication efficiency of MCCs. One major approach is to add nonconfigurable buses for improved broadcasting. A typical example is the mesh-connected computer with multiple buses (MMB). We propose a new class of generalized MMBs, the improved generalized MMBs (IMMBs). We compare IMMBs with MMBs and a class of previously proposed generalized MMBs (GMMBs). We show the power of IMMBs by considering semigroup and prefix computations. Specifically, as our main result we show that for any constant 0½×N½square IMMB using which semigroup and prefix computations on N operands can be carried out in O(Nε) time, while maintaining O(1) broadcasting time. Compared with the previous best complexities O(N⅛) and O(N1/16) achieved on a rectangular MMB and GMMB, respectively, for the same computations, our results show that IMMBs are more powerful than MMBs and GMMBs.

Various augmenting mechanisms have been proposed to enhance the communication efficiency of mesh-connected computers (MCCs). One major approach is to add nonconfigurable buses for improved broadcasting. A typical example is the mesh-connected computer with multiple buses (MMB). In this paper, we propose a new class of generalized MMBs, the improved generalized MMBs (IMMBs). Each processor in an IMMB is connected to exactly two buses. We show the power of IMMBs by considering semigroup and prefix computations. Specifically, we show that semigroup and prefix computations on N operands, and data broadcasting all take O(log N) time on IMMBs. This is the first O(log N) time algorithm for these problems on arrays with fixed broadcasting buses.

This paper addresses the problem of efficient routing in unreliable multihop optical networks supported by Wavelength Division Multiplexing (WDM). We first define a new cost model for routing in (optical) WDM networks that is more general than the existing models. Our model takes into consideration not only the cost of wavelength access and conversion but also the delay for queuing signals arriving at different input channels that share the same output channel at the same node. We then propose a set of efficient algorithms in a reliable WDM network on the new cost model for each of the three most important communication patterns-multiple point-to-point routing, multicast, and multiple multicast. Finally, we show how to obtain a set of efficient algorithms in an unreliable WDM network with up to f faulty optical channels and wavelength conversion gates. Our strategy is to first enhance the physical paths constructed by the algorithms for reliable networks to ensure success of fault-tolerant routing, and then to route among the enhanced paths to establish a set of fault-free physical routes to complete the corresponding routing request for each of the communication patterns.

The chain range-join of k sets, S1, S2, …, Sk, is the set containing all tuples (s1, s2, …, sk) that satisfy ei(1)≤|si−si+1|≤ei(2)⁠, where sk∈ Sk,si∈Si,ei(1)≤ei(2)are fixed constants, 1 ≤ i ≤ k − 1. This paper presents an efficient parallel algorithm for computing the k-set chain range-join in hypercube computers. The proposed algorithm applies the technique of permutation-based range-join and works by joining data sets one by one along the chain. To compute the range-join of k sets S1, S2, …, Sk in a hypercube of p processors, p ≤ |Si| = ni and 1 ≤ i ≤ k, our algorithm requires only yO(∑i=1knip)local memory at each processor, and has a time complexity at most O(((nk/p) + nk−1) log(nk/p)) in the best case when no element in St + 1 matches any element in St, for 1≤t≤k−1,O(kTsort+(k2/pΠi=1kni))in the worst case when all elements in St + 1 match each element in St, where Tsort=O((K/P)Πi=2knilog⁡Πi−2kni)when all elements in St + 1 are distinct, and Tsort=O((K/P)Πi=2kni)when all elements in St + 1 are equal. The general-case time complexity of the algorithm is also shown. The algorithm is implemented on a UNIX-based network using a simulator designed in C and its performance is fully evaluated through extensive testing.

Abstract This paper proposes a new method, recursive expansion (RE), for systematically constructing interconnection networks of arbitrary large size with high performance. On the basis of two small‐size networks, a frame and a unit, the RE method works in a manner of recursively replacing each node in the frame with an expanded network containing a set of copies of the unit and each edge in the frame with a set of interunit connections connecting a pair of the networks until a network of the desired size has been obtained. By RE, we can construct various kinds of large‐size and low‐cost interconnection networks. Two applications of the method, the ℋ︁Σr network based on the torus and the ℋ︁Σr network based on the hypercube, show that our method can produce networks with cost O((log3/2 n)/(log3/2 log n)) (degree O(1)) and O(log n log log n) (degree O(log log n)). In addition to low cost, networks constructed by RE also possess other properties such as high constructability, good extendability, symmetric topology, and efficient message routing. This paper describes an algorithm, for automatically constructing arbitrary large size networks with high performance. For constructing a network of size nr through r phases RE on the basis of a frame of degree df and a unit of size nu and degree du, the algorithm has a time complexity O((max{(df/nu), (du/r)})rn2r). Finally, a routing algorithm for networks constructed by RE is presented. The routing algorithm can realize point‐to‐point message routing without using a global routing table at each node and has a time complexity O((ku + kf)dfr), where ku and kf are diameters of the frame and of the unit, df is the degree of the frame, and r is the number of phases of RE to construct the network. © 1993 by John Wiley & Sons, Inc.