MapReduce includes three phases of map, shuffle, and reduce. Since the map phase is CPU-intensive and the shuffle phase is I/O-intensive, these phases can be conducted in parallel. This paper studies a joint scheduling optimization of overlapping map and shuffle phases to minimize the average job makespan. New concepts of the strong pair and the weak pair are introduced. Two jobs are defined as a strong pair if the shuffle and map workloads of one job equal the map and shuffle workloads of the other job, respectively. Two jobs are defined as a weak pair if their total map workloads equal their total shuffle workloads. We prove that if the entire set of jobs can be decomposed to strong pairs of jobs, then the optimal schedule can pairwisely execute jobs that can form a strong pair. Following the above intuition, several offline and online scheduling policies are proposed. Extensions are made based on weak pairs. Real data-driven experiments validate the efficiency and effectiveness of the proposed policies.

Motivated by many Online Social Network (OSN)applications such as viral marketing, the Social Influence Maximization Problem (SIMP)has received tremendous attention. SIMP aims to select k initially-influenced seed users to maximize the number of eventually-influenced users. Under the independent cascade model, the SIMP has been proved to be NP-hard, monotone, and submodular. Therefore, a naive greedy algorithm that maximizes the marginal gain obtains an approximation ratio of 1-e-1. This paper extends the SIMP by considering the crowd influence which is combined group influence in additional to individual influence among a given crowd. Our problem is proved to be NP-hard and monotone, but not submodular. It is proved to be inapproximable within a ratio of |V|ε-1for any ε > 0. However, since user connections in OSNs are not random, approximations can be obtained by leveraging the structural properties of OSNs. We prove that the supmodular degree, denoted as Δ. of most OSNs has the following property lim|V|→∞[Δ/O(|V|)] = 0, i.e., Δ ∈ o(|V|) for most OSNs. The supermodularity, denoted by \triangle, is used to measure to what degree our problem violates the submodularity. Two approximation algorithms have been applied with ratios of 1/(Δ+2) and 1-e-1/(Δ+1), respectively. Experiments demonstrate the efficiency and effectiveness of our algorithms.

With the bloom of the sharing economy, bike sharing systems have earned increasing attention, and a great amount of bike sharing systems have been established in major cities. Users of these systems mainly conduct one-way trips, which leads to an unbalanced distribution of the bikes over time and space. The system operators could hire a fleet of vehicles to move bikes among bike stations for rebalancing. We focus on a routing schedule problem for each vehicle used in the rebalancing process and aims to minimize its moving distance. For the problem, we propose a greedy algorithm which can be easily extended to a parallel version. The scheduled route for a vehicle is adapted from the Hamiltonian path covering all unbalanced bike stations. The algorithm greedily adjusts the route if the vehicle cannot moving along the Hamiltonian path due to capacity limitation violation. Different from previous approaches, our algorithm has a more flexible tradeoff between running time consumption and optimality of the output. Finally, we conduct experiments on both real-world and synthetic datasets and compare the performance of our algorithm with a classic approach.

Software-defined networks (SDNs) can support finegrained forwarding policies in the underlying switches. The new content addressable memory, Ternary Content Addressable Memory (TCAM), enables fast lookups for matching rules in message forwarding, represented as binary strings with wildcards. However, the cost and power limit the number of matching rules a TCAM can support. Therefore, rule caching is needed to place high-weight (high-hit) rules in the TCAM hardware, while large, but slow, software switches handle cache-miss traffic. We assume that matching these rules form a forest of trees. A rule R' is a descendant of another rule R if R' is a special case of R. Dependent rules are evaluated in a particular matching order: when a rule is included in the cache, all its descendants in the rule set have to be included as well. Our objective is to maximize the number of rule hits, while limiting the number of cached rules. Three greedy rule-caching algorithms are proposed, including two with approximation ratios of 2 and24/5 , respectively. In addition, we propose a dynamic programming solution that is optimal but slow. The efficiency of the proposed approaches are evaluated through real data-driven simulations.

The rapidly increasing number of vehicles in roads leads to numerous problems in metropolitan areas. Several researchers show that carpooling can be an efficient solution to relieve the pressures caused by large numbers of cars. Previous research on carpools introduces several additional constraints to simplify the problem, but some of them are unreasonable in reality. In this paper, we focus on removing the static capacity constraint. Doing so allows a vehicle to carry more passengers than vehicle's capacity, which is possible if some people are dropped off and new passengers take their places during the journey. A greedy approach based on multi-round matching is proposed, and it is further improved by taking advantage of geometry properties. We apply our algorithms to both simulated and real world datasets, and experiment results show that our algorithms have better performances than existing approaches.

Task resource allocation has always been an important issue in cloud-based data center networks (DCNs). This paper considers provisioning the maximum admissible load (MAL) of virtual machines (VMs) in physical machines (PMs) with underlying tree-structured DCNs using the hose model for communication. The limitation of static load distribution is that it assigns tasks to nodes in a once-and-for-all manner, and thus, requires a priori knowledge of program behavior. To avoid load redistribution during a run time where the load grows, we introduce maximum elasticity scheduling, which has the maximum growth potential subject to the node and link capacities. Given a tree-based topology, this paper aims to find the schedule with the maximum elasticity across both nodes and links. We have found a distributed linear solution based on message passing, and we discuss several extensions of the model. We conclude the paper by presenting various simulation results.

In online social networks, people may want to make new friends to maximize their social influences. For example, business page owners on Facebook want to influence as many people as possible for commercial advantages. Hence, we study a friend recommendation strategy with the perspective of social influence maximization. For the system provider (e.g., Facebook), the objective is to recommend a fixed number of new friends to a given user, such that the given user can maximize his/her social influence through making new friends. Our problem is proved to be NP-hard. A greedy friend recommendation algorithm with an approximation ratio of 1 - 1/∈ is proposed, according to the submodular property. It involves a sub-problem of computing the influence spread. A novel method, which considers the multipath effect, is proposed to compute the influence spread. Experiments demonstrate the efficiency and effectiveness of our algorithms.

In the Online to Offline (O2O) taxi business (e.g., Uber), the interests of passengers, taxi drivers, and the company may not align with one another, since taxis do not belong to the company. To balance these interests, this paper studies the taxi dispatch problem for the O2O taxi business. The interests of passengers and taxi drivers are modeled. For non-sharing taxi dispatches (multiple passenger requests cannot share a taxi), a stable marriage approach is proposed. It can deal with unequal numbers of passenger requests and taxis through matching them to dummy partners. Given dummy partners, stable matchings are proved to exist. Three rules are presented to find out all possible stable matchings. For sharing taxi dispatches (multiple passenger requests can share a taxi), passenger requests are packed through solving a maximum set packing problem. Packed passenger requests are regarded as a single request for matching taxis. Extensive real data-driven experiments demonstrate how well our approach performs. The proposed algorithms have a limited performance gap to the literature in terms of the dispatch delay and the passenger satisfaction, but they significantly improve upon existing algorithms in terms of the taxi satisfaction.

In the smart cities of the future, people expect to gather data from moving vehicles. Due to the existence of malicious users who claim to be in a traffic flow but actually are in others, a location proof for vehicular trajectory-based data needs to be developed. RoadSide Units (RSUs) are commonly used in smart cities, and a vehicular trajectory's location proof can be generated based on messages collected from RSUs along the trajectory. This paper studies the optimal RSU placement problem: Given a set of traffic flows, the objective is to place a minimum number of RSUs to securely distinguish all flows. A traffic flow is securely distinguishable if the set of its passing RSUs is unique among all traffic flows and unforgeable. To solve this problem, an RSU placement algorithm with an approximation ratio O(ln n) is proposed. In order to further reduce the number of deployed RSUs, this paper explores the credential propagation mechanism via Car-to-Car (C2C) communications, which essentially extend the coverage of an RSU. Approximation algorithms are proposed to solve the problem, and extensive real data-driven experiments demonstrate the efficiency and effectiveness of the proposed algorithms.

Recent breakthroughs in wireless energy transfer-based rechargeable batteries enable a promising application of Wireless Charging Vehicles (WCVs) in Wireless Rechargeable Sensor Networks (WRSNs). This paper studies cooperative WCV schedules in WRSNs to optimize sensor recharging. The objective is to minimize the number of WCVs under the constraint that all sensors must be periodically recharged before running out of energy (i.e., before lifetime). Our problem is NP-hard and is very challenging due to the complexity of WCV route schedules. WCVs can be used to recharge sensors in turn. Our problem is thoroughly explored in line, cycle, and metric spaces (such as a three-dimensional Euclidean space). In terms of line and cycle spaces, greedy algorithms with ratios of 2 and 4, respectively, are proposed. By exploring two WCV schedule patterns, the optimal algorithm is found for the cycle space when sensor lifetimes are identical. For the metric space with an identical sensor lifetime, an algorithm with a ratio of 2.5 is proposed through constructing the minimum distance forest among sensors. It is also extended to the metric space with non-identical sensor lifetimes by grouping sensors according to their lifetimes. Finally, real data-driven experiments demonstrate the efficiency and effectiveness of the proposed approximation algorithms.

Nowadays, the notion of diseases has been extended from real human diseases to general epidemic information propagations, such as the rumors in distributed systems. Controlling the spread of a disease is usually done through quarantine, where people that have, or are suspected to have, a disease are isolated from having interactions with others. As a tradeoff, normal human interactions are inevitably degraded by the quarantine. This motivates us to explore a robust quarantine strategy that can eliminate epidemic outbreaks with minimal isolation costs. Our problem is shown to be NP-hard. A bounded algorithm with an approximation ratio of two is proposed, through utilizing the feasibility and minimality properties. Finally, real data-driven experiments demonstrate the efficiency and effectiveness of the proposed algorithms in real-world applications.

MapReduce includes three phases of map, shuffle, and reduce. Since the map phase is CPU-intensive and the shuffle phase is I/O-intensive, these phases can be conducted in parallel. This paper studies a joint scheduling optimization of overlapping map and shuffle phases to minimize the average job makespan. Challenges come from the dependency relationship between map and shuffle phases, since the shuffle phase may wait to transfer the data emitted by the map phase. A new concept of the strong pair is introduced. Two jobs are defined as a strong pair, if the shuffle and map workloads of one job equal the map and shuffle workloads of the other job, respectively. We prove that, if the entire set of jobs can be decomposed to strong pairs of jobs, then the optimal schedule is to pairwisely execute jobs that can form a strong pair. Following the above intuition, several offline and online scheduling policies are proposed. They first group jobs according to job workloads, and then, execute jobs within each group through a pairwise manner. Real data-driven experiments validate the efficiency and effectiveness of the proposed policies.

This paper proposes a scalable publish/subscribe system based on unstructured P2P networks, which are shown to have Nested Scale-Free Architectures (NSFAs). The scale-free architecture is a classic concept, which means that the peer degree distribution follows power-law. ‘Nested’ indicates that the scale-free architecture is preserved when low-degree peers and their associated connections are removed. We find that NSFA's hierarchy can be distributedly constructed, and has a better bound than classic hierarchies. By leveraging the NSFA's hierarchy, our publish/subscribe system achieves a competitive tradeoff among the event routing efficiency, system robustness, and overhead. For an unstructured P2P network with |V| peers, the number of routing hops for the event deliveries in our system is expected to be O(ln ln |V|). For the topological information, each peer only needs to maintain an overhead with a constant size, O(1). Peer arrival, departure, and failure can be handled within a message complexity of O(ln ln |V|). Finally, real data-driven experiments demonstrate the efficiency and effectiveness of the NSFA-based publish/subscribe system.

Traffic flow monitoring systems aim to measure and monitor vehicle trajectories in smart cities. Their critical applications include vehicle theft prevention, vehicle localization, and traffic congestion solution. This paper studies an RoadSide Unit (RSU) placement problem in traffic flow monitoring systems. Given some traffic flows on streets, the objective is to place a minimum number of RSUs to cover and distinguish all traffic flows. A traffic flow is covered and distinguishable, if the set of its passing RSUs is non-empty and unique among all traffic flows. The RSU placement problem is NP-hard, monotonic, and non-submodular. It is a non-trivial extension of the traditional set cover problem that is submodular. We show that, to cover and distinguish an arbitrary pair of traffic flows (ƒ and ƒ′), two RSUs should be placed on streets from two different subsets of ƒ∖ƒ′, ƒ′∖ƒ, and ƒ ⋂ ƒ′. Three bounded RSU placement algorithms are proposed. Their approximation ratios are n ln n(n−1)/2, n+1/2 ln 3n(n−1)/2, and ln n(n+1)/2, respectively. Here, n is the number of given traffic flows. Extensive real data-driven experiments demonstrate the efficiency and effectiveness of the proposed algorithms.

Trust-based recommendation systems study how people form opinions via trusted friends, so as to predict unknown ratings based on the ratings expressed by trusted friends. Most of the existing work only considers the ratings at the current time slot. In real life, a user's opinion evolves over time, since he receives the influence of different opinions sequentially. In addition, existing work usually targets a single user at a time; there is a need to predict multiple ratings for multiple connected users. To reach these ends, we propose a novel multiple-rating prediction scheme, FluidRating, which uses fluid dynamics theory to reveal the time-evolving formulation process of human opinions. In this scheme, each user corresponds to a container, and several containers are connected through single directional pipes, corresponding to influence relations. We identify three features of human personality in the opinion formulation and propagation process: “persistency” represents how much one insists on his opinion, “persuasiveness” represents the ability to impact others, and “forgetting” reflects the common truth that people have limited memory. The recommendation (or influence) is modeled as fluid with two dimensions: its temperature is taken as the “opinion/rating,” and its height is deemed as the persistency. When new opinions emerge, each person refines his opinion through a round of fluid exchange with neighbors. Opinions of multiple rounds are aggregated to gain a final prediction. Experimental evaluation in a real data set validates the feasibility and the effectiveness of the proposed model.

In online social networks (OSNs), to evaluate trust from one user to another indirectly connected user, the trust evidence in the trusted paths (i.e., paths built through intermediate trustful users) should be carefully treated. Some paths may overlap with each other, leading to a unique challenge ofpath dependence, i.e., how to aggregate the trust values of multiple dependent trusted paths. OSNs bear the characteristic of high clustering, which makes the path dependence phenomenon common. Another challenge istrust decaythrough propagation, i.e., how to propagate trust along a trusted path, considering the possible decay in each node. We analyze the similarity between trust propagation and network flow, and convert a trust evaluation task with path dependence and trust decay into a generalized network flow problem. We propose a modified flow-based trust evaluation schemeGFTrust, in which we address path dependence using network flow, and model trust decay with the leakage associated with each node. Experimental results, with the real social network data sets of Epinions and Advogato, demonstrate that GFTrust can predict trust in OSNs with a high accuracy, and verify its preferable properties.

There is a great potential to boost the performance of mobile devices by offloading computation-intensive parts of mobile applications to the cloud. However, this potential is hindered by a gap between how individual mobile devices demand computational resources and how cloud providers offer them: offloading requests from a mobile device usually require a quick response, which may be infrequent, and is subject to variable network connectivity, whereas cloud resources incur relatively long setup times, are leased for long time quanta, and are indifferent to network connectivity. In this paper, we present the design of utility-based uploads sharing strategy in cloud scenarios, which bridges the above gap through providing computation offloading as a service to mobile devices. Our scheme efficiently manages cloud resources for offloading requests to improve offloading performances of mobile devices, as well as to reduce the monetary cost per request of the provider. We also schedule offloading requests to resolve the contention problem for cloud resources. The proposed scheme makes offloading decisions with a controlled risk to overcome the uncertainties caused by variable network connectivity and program execution. Simulation results show that the proposed scheme can reduce the costs of cloud resources and enable mobile computation speedup for mobile devices.

This paper studies the node degree snowballing effects (i.e., degree growth effects) in the age-sensitive preferential attachment model, where nodes are iteratively added one by one to a growing network. Upon entering the network, each new node connects to a suitably chosen set of existing nodes, while the attachment probability for an existing node to get connected depends on both its node degree and age difference. We are interested in accelerating the node degree snowballing effects through the impact of the initial links. If a new node enters the growing network with more initial links (a larger degree), it could attract many more links from the later nodes, and thus, its degree snowballs faster. We find that the initial links are only impactful when neither the node degree nor the age difference dominates the attachment probability. In that case, the relationship between the ratio of the additional initial link and the gain ratio of the eventual node degree is shown to include two stages (linear stage and diminishing return stage). Applications of our work involve citation networks and online social networks. For example, in citation networks, we answer the question that whether an author can attract additional citations through self-citations. Finally, real data-driven experiments verify the accuracies of our results, which cast some new light in real-world growing networks.

In this paper, we address a promising application in the Vehicular Cyber-Physical Systems (VCPS) called roadside advertisement dissemination. Its application involves three elements: the drivers in the vehicles, Roadside Access Points (RAPs), and shopkeepers. The shopkeeper wants to attract as many customers as possible, through using RAPs to disseminate advertisements to the passing vehicles. Upon receiving an advertisement, the driver may detour towards the shop, depending on the detour distance. Given a fixed number of RAPs and the traffic distribution, our goal is to optimize the RAP placement for the shopkeeper to maximally attract potential customers. This application is a non-trivial extension of traditional coverage problems, the difference being that we use RAPs to cover the traffic flows. RAP placement algorithms may pose complex trade-offs. If we place RAPs at locations that can provide small detour distances to attract more customers, these locations may not necessarily be located in heavy traffic regions. While heavy traffic regions cover more flows, they can cause large detour distances, making shopping less attractive to customers. To balance this trade off, novel RAP placement algorithms are proposed. Since real-world traffic distributions exhibit unique patterns, here we further consider the Manhattan grid scenario and then propose corresponding near-optimal solutions. Real trace-driven experiments validate the competitive performance of the proposed algorithms.

As special applications of delay tolerant networks (DTNs), efficient data collection and event detection in the deep sea pose some unique challenges, due to the need of timely data reporting and the delay of acoustic transmission in the ocean. Since underwater communications suffer from a significant signal attenuation, autonomous underwater vehicles (AUVs) deployed in the deep sea are used to surface frequently to transmit collected data and events to the surface stations. However, extra delay is introduced at each resurfacing, since AUVs are usually operated in the deep sea. In this paper, we want to minimize the average data and event reporting delay, through optimizing the number and locations of AUV resurfacing events. We also study the AUV trajectory planning using an extended Euler circuit, where the search space is a set of segments (e.g., oil pipes) in the deep sea. Finally, experiments in both the synthetic and real traces validate the efficiency and effectiveness of the proposed algorithms.

The goal of a trust-based recommendation system is to predict unknown ratings based on the ratings expressed by trusted friends. However, most of the existing work only considers the ratings at the current time slot. In real life, a user receives the influence of different opinions sequentially; accordingly, his opinion evolves over time. We propose a novel rating prediction scheme, FluidRating, which uses fluid dynamics theory to reveal the time-evolving formulation process of human opinions. The recommendation is modeled as fluid with two dimensions: the temperature is taken as the “opinion/rating,” and its volume is deemed as the “persistency,” representing how much one insists on his opinion. When new opinions come, each user refines his opinion through a round of fluid exchange with his neighbors. Opinions from multiple rounds are aggregated to gain a final prediction; both uniform and non-uniform aggregation are tested. Moreover, Three sampling approaches are proposed and examined. The experimental evaluation of a real data set validates the feasibility of the proposed model, and also demonstrates its effectiveness.

In this paper, an up-and-down routing protocol is proposed for mobile opportunistic social networks, which exhibit a nested core-periphery structure. In such a network, a few active nodes with large weighted degrees form the network core, while the network peripheries are composed of many inactive nodes with small weighted degrees. By nested, it means that the core-periphery structure is preserved, when periphery nodes are removed. Based on this structure, a message can be uploaded from the source to the network core, through iteratively forwarding the message to a relay that has a higher position in the nested network hierarchy. Then, space-efficient Bloom-filter-based hints are introduced to provide guidance for downloading messages from the network core to the destination. Through utilizing the network structure and space-efficient routing hints, subtle balances between the data delivery delay, ratio, and cost are achieved by our proposed approach. Finally, through extensive simulations, we show that the up-and-down routing scheme achieves a competitive performance on the data delivery delay and ratio, with a relatively small cost on the prior information maintenance and a relatively low forwarding cost.

In online social networks, information cascades occur when people observe the actions of others (followees) and then make the same choices that the others have made (followers). Cascade predictions are important, since they can detect and help resist bad cascades. We focus on photo cascade predictions in Flickr: given the current cascade and social topology, we want to predict the number of propagated users at a future-time-slot. Information cascades include a large amount of data that crosses both space and time. To reduce prediction time complexities, our idea is to decompose the spatiotemporal cascade information (a larger size of data) to user characteristics (a smaller size of data) for subsequent predictions. Space and time matrices are introduced to record the cascade information. We introduce a set of new notions, persuasiveness and receptiveness (represented as two vectors for complexity reduction), to capture characteristics of followees and followers. Persuasiveness includes followees' abilities to propagate information, while receptiveness includes followers' willingness to accept information. Then, we propose a three-stage parallel prediction scheme as follows. (1) We map the spatiotemporal cascade information to a weighted matrix, in which the weights of space and time information are tuned. (2) Singular value decomposition is used to extract nodes' persuasiveness and receptiveness from the weighted matrix. (3) Predictions are conducted based on nodes' persuasiveness and receptiveness. Finally, evaluations are conducted to verify the competitive performance of the proposed scheme.

In this paper, an opportunistic multi-copy two-hop routing algorithm is proposed for mobile social networks (MSNs) to minimize the expected data delivery delay, using local information. For each source-destination pair, the source dynamically maintains a forwarding set consisting of relay nodes. The forwarding set selection is based on the number of remaining message copies, as well as the number and quality of relays that have not received a message copy. The source only forwards its message to the relay nodes in its forwarding set, which will in turn forward the message to the destination directly. We propose a greedy approach to select the forwarding set with n message copies at the source, in an MSN with m (m>n) relays. All forwarding sets can be determined with a time complexity of O(m log m+nm). Then, the proposed multi-copy two-hop routing algorithm is applied to a feature space routing scheme, where the contact frequencies are estimated by social feature distances. Finally, the competitive performance of the proposed schemes are shown in real trace-driven simulations.

In this paper, a user-based CPU verification scheme is proposed for cloud cheating detection. In this scheme, a predefined computational task is constructed for the cloud to execute in our cheating detection process. Then we compare the difference of the actual execution time (recorded by the user) and the theoretical execution time, as to determine whether the cloud is cheating or not. A time-lock puzzle is introduced to construct the predefined computational task, so that the predefined computational task is guaranteed to be executed by the cloud. Our cheating detection process has a higher probability of detecting cloud cheating if using a larger predefined computational task, which in turn costs more time. Further analysis shows that, if the total detection time is limited, it is better to detect cloud cheating using small-scale and short-length cheating detecting processes multiple times, as opposed to large-scale and long-length processes a few times. Finally, the feasibility and validity of the proposed scheme is shown in the evaluations.

In Opportunistic Mobile Networks (OppNets), data is opportunistically exchanged between nodes who encounter each other. In order to enable such data exchanges, nodes in the network have to probe their environment continually, so as to discover neighbor nodes. This can be an extremely energy-consuming process. If nodes probe very frequently, they will consume a lot of energy, and might be energy inefficient. On the other hand, infrequent contact probing might cause nodes to miss many of their contacts, and thus opportunities to exchange data are lost. Therefore, there exists a trade-off between energy efficiency and the contact opportunities in OppNets. In this paper, in order to investigate this trade-off, we first propose a model to quantify the detecting probability in OppNets, using the Random WayPoint (RWP) model. Then, extensive simulations are conducted to validate the correctness of our proposed model. Finally, based on the proposed model, we analyze the trade-off between energy efficiency and the total number of effective contacts under different situations. Our results show that the good trade-off points are obviously different when the speed of nodes is different. Moreover, the detecting probability increases as the speed of nodes decreases, while the total number of effective contacts increases as the speed of nodes increases.