Search

Due to the emergence of mobile 3D devices, multi-view 3D videos are expected to play increasingly important roles in providing immersively interactive experiences to users. Compared with traditional single-view videos, it is envisaged that a multi-view 3D video requires larger storage space and bandwidth consumption. Nevertheless, efficient caching for multi-view 3D videos in a mobile proxy has not been explored in the literature. In this paper, therefore, we first observe that the storage space can be effectively reduced by leveraging Depth Image Based Rendering (DIBR) in multi-view 3D videos. We then formulate a new cache management problem, named Adaptive View Selection and Cache Operation (AVSCO), and find the optimal policy based on Markov Decision Process (MDP). Afterward, we propose an approximate MDP to effectively aggregate similar states to reduce the MDP state space and devise an efficient and effective algorithm to support human visual continuity in AVSCO. Simulation results manifest that the proposed algorithms can significantly improve the cache hit rate and reduce the bandwidth consumption for the remote access compared with the existing cache replacement algorithms.

Flow consolidation has been proposed for merging multiple flows from different services into an aggregate flow to remedy the state explosion problem in SDN. However, we observe that the QoS requirements are no longer sustained in aggregate flows since the bandwidth decided by TCP is usually different from the desired rate of each service. Therefore, this paper explores an idea to control the rates of only a few service flows so that the rates of all uncontrolled flows allocated by TCP will meet their QoS requirements. We design a new architecture, called Scalable Per-Flow Rate Allocation (SPFRA), and formulate a new optimization problem, termed Scalable Rate Allocation for Aggregate Flows (SRAF), to find a minimum number of controlled flows to increase the scalability of SDN with diverse service requirements. We prove the NP-hardness and inapproximability of SRAF. To solve the problem, we design an algorithm, named Aggregate Flow Selection and Flow Release (AFSFR), to achieve the tightest bound and extend it to support distributed computation and dynamic traffic for instant services. Simulations and implementation on an SDN testbed manifest that AFSFR performs nearly optimally in real networks, and the number of controlled flows can be effectively reduced by 50%.

The social presence theory in social psychology suggests that computer-mediated online interactions are inferior to face-to-face, in-person interactions. In this paper, we consider the scenarios of organizing in person friend-making social activities via online social networks (OSNs) and formulate a new research problem, namely, Hop-bounded Maximum Group Friending (HMGF), that takes into consideration both existing friendships and the likelihood of new friend making in organization of the targeted in person friend-making social activities. To find a set of attendees for such social activities, HMGF is unique and challenging due to the interplay of the group size, the constraint on existing friendships, and the objective of maximizing the likelihood of friend making. We propose an error-bounded approximation algorithm, MaxGF, to efficiently obtain the solutions very close to the optimal solutions. To boost the performance, we devise two graph-theoretical pruning strategies, namely Neighbor Pruning and Core Pruning, which can effectively avoid redundant graph explorations to improve the performance of HMGF. We conduct a user study to validate our problem formulation and perform extensive experiments on real datasets to demonstrate the efficiency and effectiveness of our proposed algorithm. The experimental results manifest that our proposed algorithms outperform the baselines, including the ILP formulation.

Artificial intelligence (AI) on chips has recently driven the expansion of the Social Internet of Things (SIoT), where a group of SIoT devices with social relations can collaboratively identify and handle local events without the help of remote servers. On the other hand, mobile-edge computing (MEC) is a favorable way to locally process SIoT data for reducing data transmission and computation among SIoT devices and backhaul networks. Nevertheless, the load sharing among SIoT devices, MEC, and remote servers brings about new challenges for the communication and computation tradeoff, cross-layer design in SIoT, and forwarding and aggregation tradeoff. To tackle these issues, we formulate a new optimization problem, namely, SIoT collaborative group and device selection problem (SCGDSP), and prove the NP-hardness. We first explore the intrinsic properties of a fundamental SCGDSP case by finding the optimal collaborative group for each user request. Then, we design an approximation algorithm for the general SCGDSP that first evaluates candidate collaborative groups under different social relations, and then selects the collaborative groups and SIoT devices properly. For scalability, the proposed algorithm also supports dynamic user requests and can be distributionally deployed in massive networks enabling collaborative MEC. Moreover, it also sustains local SIoT services, where the computation only involves SIoT devices and MEC servers. Simulation results demonstrate that effective SIoT and collaborative group selection (ESCGS) can reduce by more than 50% of the total communication and computation costs compared with baseline schemes in the real networks from topology zoo. Moreover, the distributed ESCGS reduces by 87% of the running time with total 16.5-MB message overhead, requiring no more than 0.05-ms transmission delay in a 100-Gb/s backbone network with eight MEC servers, 1000 SIoTs, and 800 monitored locations.

Shopping in VR malls has been regarded as a paradigm shift for E-commerce, but most of the conventional VR shopping platforms are designed for a single user. In this paper, we envisage a scenario of VR group shopping, which brings major advantages over conventional group shopping in brick-and-mortar stores and Web shopping: 1) configure flexible display of items and partitioning of subgroups to address individual interests in the group, and 2) support social interactions in the subgroups to boost sales. Accordingly, we formulate the Social-aware VR Group-Item Configuration (SVGIC) problem to configure a set of displayed items for flexibly partitioned subgroups of users in VR group shopping. We prove SVGIC is NP-hard to approximate within $\frac{32}{31} - \epsilon$. We design an approximation algorithm based on the idea of Co-display Subgroup Formation (CSF) to configure proper items for display to different subgroups of friends. Experimental results on real VR datasets and a user study with hTC VIVE manifest that our algorithms outperform baseline approaches by at least 30.1% of solution quality., Comment: 32 pages, 16 figures (41 subfigures). A shorter version of this paper has been submitted to the 46th International Conference on Very Large Databases (VLDB 2020); this is an expanded version containing supplementary details

Three essential criteria are important for social activity planning: (1) finding attendees familiar with the initiator, (2) ensuring most attendees have tight social relations with each other, and (3) selecting an activity period available to all. In this paper, we propose the Social-Temporal Group Query (STGQ) to find suitable time and attendees with minimum total social distance. We first prove that the problem is NP-hard and inapproximable within any ratio. Next, we design two algorithms, SGSelect and STGSelect , which include effective pruning techniques to substantially reduce running time. Moreover, as users may iteratively adjust query parameters to fine tune the results, we study the problem of Subsequent Social Group Query (SSGQ) . We propose the Accumulative Search Tree and Social Boundary , to cache and index intermediate results of previous queries in order to accelerate subsequent query processing. Experimental results indicate that SGSelect and STGSelect are significantly more efficient than baseline approaches. With the caching mechanisms, processing time of subsequent queries can be further reduced by 50-75 percent. We conduct a user study to compare the proposed approach with manual activity coordination. The results show that our approach obtains higher quality solutions with lower coordination effort, thereby increasing the users’ willingness to organize activities.

Online social networks have become a crucial medium to disseminate the latest political, commercial, and social information. Users with high visibility are often selected as seeds to spread information and affect their adoption in target groups. We study how gender differences and similarities can impact the information spreading process. Using a large-scale Instagram dataset and a small-scale Facebook dataset, we first conduct a multi-faceted analysis taking the interaction type, directionality and frequency into account. To this end, we explore a variety of existing and new single and multihop centrality measures. Our analysis unveils that males and females interact differently depending on the interaction types, e.g., likes or comments, and they feature different support and promotion patterns. We complement prior work showing that females do not reach top visibility (often referred to as the glass ceiling effect) jointly factoring in the connectivity and interaction intensity, both of which were previously mainly discussed independently. Inspired by these observations, we propose a novel seeding framework, called Disparity Seeding, which aims at maximizing spread while reaching a target user group, e.g., a certain percentage of females - promoting the influence of under-represented groups. Disparity Seeding ranks influential users with two gender-aware measures, the Target HI-index and the Embedding index. Extensive simulations comparing Disparity Seeding with target-agnostic algorithms show that Disparity Seeding meets the target percentage while effectively maximizing the spread. Disparity Seeding can be generalized to counter different types of inequality, e.g., race, and proactively promote minorities in the society.

Social Internet of Things (SIoT) has become an emerging network paradigm, where IoT devices with Artificial Intelligence (AI) and social relations can automatically establish a collaborative group to identify events locally. On the other hand, mobile users can act as ubiquitous and versatile sensors to improve the accuracy of SIoT event detection. In this paper, we explore the SIoT Collaboration with Crowdsourcing (SCC) problem to jointly select SIoT devices and hire users to monitor events and locations with accuracy requirements, while minimizing the total SIoT communication and computation costs and the user hiring cost. We prove that SCC is NP-hard and cannot be approximated by any factor unless P = NP. Then, we propose a new algorithm, Accuracy- and Social-aware SIoT and User Selection (ASSUS), with the idea of Collaborative Tree (CT) and Accuracy Profit (AP), where CT exploits users’ social relations to properly choose intermediate SIoTs. Simulation results manifest that ASSUS can effectively reduce more than 50% of the total cost compared with state-of-the-art algorithms.

Viral marketing on social networks, also known as Influence Maximization (IM), aims to select k users for the promotion of a target item by maximizing the total spread of their influence. However, most previous works on IM do not explore the dynamic user perception of promoted items in the process. In this paper, by exploiting the knowledge graph (KG) to capture dynamic user perception, we formulate the problem of Influence Maximization based on Dynamic Personal Perception (IMDPP) that considers user preferences and social influence reflecting the impact of relevant item adoptions. We prove the hardness of IMDPP and design an approximation algorithm, named Dynamic perception for seeding in target markets (Dysim), by exploring the concepts of dynamic reachability, target markets, and substantial influence to select and promote a sequence of relevant items. We evaluate the performance of Dysim in comparison with the state-of-the-art approaches using real social networks with real KGs. The experimental results show that Dysim effectively achieves at least 6 times of influence spread in large datasets over the state-of-the-art approaches.

Owing to a wide range of important applications, such as team formation, dense subgraph discovery, and activity attendee suggestions on online social networks, Group Query attracts a lot of attention from the research community. However, most existing works are constrained by a unified social tightness k (e.g., for k-core, or k-plex), without considering the diverse preferences of social cohesiveness in individuals. In this paper, we introduce a new group query, namely Parameter-free Group Query (PGQ), and propose a learning-based model, called PGQN, to find a group that accommodates personalized requirements on social contexts and activity topics. First, PGQN extracts node features by a GNN-based method on Heterogeneous Activity Information Network (HAIN). Then, we transform the PGQ into a graph-to-set (Graph2Set) problem to learn the diverse user preference on topics and members, and find new attendees to the group. Experimental results manifest that our proposed model outperforms nine state-of-the-art methods by at least 51% in terms of F1-score on three public datasets.

In late 2019, a new virus was discovered, namely SARS-CoV-2. This strain causes severe acute respiratory syndrome coronavirus 2, defined as COVID-19. The disease soon spread all over the world, thus becoming a pandemic. It has been almost two years since worldwide restrictions on our lives started, and the traditional way people live and work has completely changed.

Most scheduling algorithms in the literature for cellular networks are concerned with throughput, fairness, or cost optimization. Recently, however, wireless surveillance in cellular networks has become increasingly important, and more and more institutions and companies have adopted commercial cellular surveillance cameras due to their low installation cost and the wide network coverage. In this paper, therefore, we first explore the resource allocation problem for a multi-camera surveillance system in cellular networks. We minimize the number of allocated resource blocks (RBs) while simultaneously ensuring the coverage requirement for the surveillance system in cellular networks. Specifically, we first describe our system model and then formulate the Camera Set Resource Allocation Problem (CSRAP). Next, we prove that the problem is NP-hard and inapproximable within ln n, where n is the number of surveillance targets. To solve the problem, we propose an approximation algorithm for the general case of CSRAP and then we find the optimal solutions of three deployments of cameras in the Manhattan Street Network to find the intrinsic characteristics of camera selections. The simulation results, based on two real surveillance maps and synthetic datasets, show that the number of allocated RBs can be effectively reduced compared to the existing approach for cellular networks.

In contrast to traditional online videos, live multi-streaming supports real-time social interactions between multiple streamers and viewers, such as donations. However, donation and multi-streaming channel recommendations are challenging due to complicated streamer and viewer relations, asymmetric communications, and the tradeoff between personal interests and group interactions. In this paper, we introduce Multi-Stream Party (MSP) and formulate a new multi-streaming recommendation problem, called Donation and MSP Recommendation (DAMRec). We propose Multi-stream Party Recommender System (MARS) to extract latent features via socio-temporal coupled donation-response tensor factorization for donation and MSP recommendations. Experimental results on Twitch and Douyu manifest that MARS significantly outperforms existing recommenders by at least 38.8% in terms of hit ratio and mean average precision.

New radio (NR) and non-orthogonal multiple access (NOMA) have emerged for more scalable and efficient resource utilization in 5G. NR implements mixed numerology with a flexible radio frame structure to ensure forward compatibility for future services, whereas NOMA allows multiple users with different channel states to share identical radio resources. However, the resource allocation in the NOMA-based mixed numerology system is challenging due to the naturally different shapes of Physical Resource Block (PRB) for NR and the reused locations of PRBs in a radio frame for NOMA. In this paper, we formulate a new optimization problem Multi-Dimensional Resource Allocation Problem (MDRAP) and prove that MDRAP is NP-hard. To solve the problem, we propose an approximation algorithm to maximize the weighted sum rate under the heterogeneity of users. The algorithm includes Zone Displacement to displace the locations of allocated PRBs in different layers of the radio frame, and Zone Allocation to change the location of the bounded rectangles (i.e., zones) for the allocation in each layer. We design Layer Dissimilarity to examine the location and shape of PRBs for avoiding inter-numerology interference between different layers. Simulation results show that the proposed algorithm outperforms state-of-the-art algorithms regarding throughput and fairness.

Previous research on Segment Routing (SR) mostly focused on unicast, whereas online SDN multicast with segment trees supporting IETF dynamic group membership has not been explored. Compared with unicast SR, online SDN multicast with segment trees is more challenging since finding an appropriate size, shape, and location for each segment tree is crucial to deploy it in more multicast trees. In this paper, we explore Multi-tree Multicast Segment Routing (MMSR) to jointly minimize the bandwidth consumption and forwarding rule updates over time by leveraging segment trees. We prove MMSR is NP-hard and design an online competitive algorithm, named Segment Tree Routing and Update Scheduling (STRUS) to achieve the tightest bound. STRUS includes Segment Tree Merging and Segment Tree Pruning to merge smaller overlapping subtrees into segment trees, and then tailor them to serve more multicast trees. We design Stability Indicator and Reusage Indicator to carefully construct segment trees at the backbone of multicast trees and reroute multicast trees to span more segment trees. Simulation and implementation on real SDNs with YouTube traffic manifest that STRUS outperforms state-of-the-art algorithms regarding the total cost and TCAM usage. Moreover, STRUS is practical for SDN since its running time is about 1 second, even for massive networks with thousands of nodes.

Due to the growing need for Multi-View Videos (MVV) in advertisement, TV, and education, effectively allocating the resources of next-generation wireless technologies to provide MVV streams is challenging. To achieve the high utility for MVV users, this paper proposes a cross-layer resource allocation mechanism to leverage video synthesizing schemes (such as Depth-Image-Based Rendering (DIBR)) for efficient MVV streaming with massive MIMO. We formulate a new problem Antenna Allocation with Video Synthesizing (AAVS) and prove its NP-hardness. Then, we design an algorithm, named Marginal Utility-Based Iteration (MUBI). The performance is evaluated by the data-driven simulations, and the results manifest that MUBI outperforms the baselines regarding the total utility of users.

With the emergence of innovative applications for Virtual Reality (VR) in touring, E-commerce, and social activities, high-quality VR video streaming becomes essential. To support numerous wireless VR users, this paper aims to leverage video synthesis techniques to effectively reduce the multicast bandwidth consumption. It synthesizes the view in the video for a user from the one of a nearby user with similar Field of View (FoV), under the virtual distance and view angle constraints. We first formulate a new optimization problem, named VR Content Sharing and Multicasting (VCSM), and prove the NP-hardness. Then, we propose View Sharing Relation Graph (VSRG) to model the synthesis relation between each pair of views. We then design a new algorithm, named Bandwidth-Efficient Multicast with Synthesis (BEMS) to select multicast views and the corresponding MCS in wireless networks. Simulation results show that BEMS can effectively reduce bandwidth consumption by more than 50% compared with state-of-the-art wireless transmission schemes.

Research suggests that social relationships have substantial impacts on individuals' health outcomes. Network intervention, through careful planning, can assist a network of users to build healthy relationships. However, most previous work is not designed to assist such planning by carefully examining and improving multiple network characteristics. In this paper, we propose and evaluate algorithms that facilitate network intervention planning through simultaneous optimization of network degree, closeness, betweenness, and local clustering coefficient, under scenarios involving Network Intervention with Limited Degradation - for Single target (NILD-S) and Network Intervention with Limited Degradation - for Multiple targets (NILD-M). We prove that NILD-S and NILD-M are NP-hard and cannot be approximated within any ratio in polynomial time unless P=NP. We propose the Candidate Re-selection with Preserved Dependency (CRPD) algorithm for NILD-S, and the Objective-aware Intervention edge Selection and Adjustment (OISA) algorithm for NILD-M. Various pruning strategies are designed to boost the efficiency of the proposed algorithms. Extensive experiments on various real social networks collected from public schools and Web and an empirical study are conducted to show that CRPD and OISA outperform the baselines in both efficiency and effectiveness.

Static network embedding has been widely studied to convert sparse structure information into a dense latent space. However, the majority of real networks are continuously evolving, and deriving the whole embedding for every snapshot is computationally intensive. To avoid recomputing the embedding over time, we explore streaming network embedding for two reasons: 1) to efficiently identify the nodes required to update the embeddings under multi-type network changes, and 2) to carefully revise the embeddings to maintain transduction over different parts of the network. Specifically, we propose a new representation learning framework, named Graph Memory Refreshing (GMR), to preserve both global types of structural information efficiently. We prove that GMR maintains the consistency of embeddings (crucial for network analysis) for isomorphic structures better than existing approaches. Experimental results demonstrate that GMR outperforms the baselines with much smaller time.

With the emergence of virtual reality (VR) like holographic telepresence, it is envisaged that the current networks may be overwhelmed due to the higher bandwidth demand to support high-resolution videos. On the other hand, Camera Blending Field (CBF) has been proposed to restore the occluded regions of cameras to enhance the user’s Quality of Experience (QoE) in VR. In this paper, we explore the source selection to maximize the user’s QoE under the network capacity and 3D reconstruction constraints. We first formulate a new optimization problem, named Source Selection for Real-time Telepresence with Occlusion (SSRTO), with the objective of QoE maximization. Then, we prove the NP-hardness and propose a new algorithm, Maximum Quality of Complete Model (MQCM), to maximize the user’s QoE by examining the proximity of cameras on the built Angle Directed Graph (ADG) and Neighbor Directed Graph (NDG) for reconstructing the complete 3D model. Simulation results show that MQCM can effectively improve the user’s QoE by more than 100% compared with the baseline schemes.

Existing research on social networks manifests two crucial criteria to improve activity engagement of users: (1) user interests in the activity topics and (2) opportunities of making new friends with some acquaintances. However, current online platforms still involve massive manual selection for activity attendees and contents without proper recommendations. In this paper, therefore, we formulate a new activity organization problem, named Social Knowledge Group Query (SKGQ), to recommend attendees and topic-related contents simultaneously. We prove that SKGQ is NP-hard and design an approximation algorithm, named Social cOntent Knowledge Exploration (SOKE), to jointly choose the activity attendees and topic-related contents according to social-oriented and topic- oriented strategies. Simulation results manifest that the solution acquired by SOKE is close to the optimal solution and outperforms various baselines.

Data science embraces interdisciplinary methodologies and tools, such as those in statistics, artificial intelligence/machine learning, data management, algorithms, and computation. Practicing data science to empower innovative applications, however, remains an art due to many factors beyond technology, such as sophistication of application scenarios, business demands, and the central role of human being in the loop. The purpose of this keynote speech is to share with the audience two most important rules of thumb that I learned from my practice of data science research, development and applications, as well as my thoughts on the future enterprise and organization data strategies. First, I will demonstrate the importance and challenges in developing domain-oriented, end-to-end solutions. Specifically, I will discuss our experience in transforming algorithms to domain-oriented tools, and review some of our latest techniques in transforming black-box deep learning networks into interpretable white-box models. Second, I will advocate the core value of data science as the connector and transformer between vertical application challenges and general scientific principles and engineering tools. Using network embedding as an example, I will illustrate the innovative value of building connectors and transformers for new types of data and applications so that they can take great advantage of well established scientific methods and engineering tools. I envision data science for social, commercial and ecological good has to build on enterprise and organization data strategies and infrastructure. About future work, I will provide some thoughts on this perspective, such as data value assessing and pricing, as well as privacy preservation.

Recent technological advent in virtual reality (VR) has attracted a lot of attention to the VR shopping, which thus far is designed for a single user. In this paper, we envision the scenario of VR group shopping, where VR supports: 1) flexible display of items to address diverse personal preferences, and 2) convenient view switching between personal and group views to foster social interactions. We formulate the Multiview-Enabled Configuration Recommendation (MECR) problem to rank a set of displayed items for a VR shopping user. We design the Multiview-Enabled Configuration Ranking System (MEIRS) that first extracts discriminative features based on Marketing theories and then introduces a new coupled tensor factorization model to learn the representation of users, Multi-View Display (MVD) configurations, and multiple feedback with content features. Experimental results manifest that the proposed approach outperforms personalized recommendations and group recommendations by at least 30.8% in large-scale datasets and 63.3% in the user study in terms of hit ratio and mean average precision.

The explosive growth in popularity of social networking leads to the problematic usage. An increasing number of social network mental disorders (SNMDs), such as Cyber-Relationship Addiction, Information Overload, and Net Compulsion, have been recently noted. Symptoms of these mental disorders are usually observed passively today, resulting in delayed clinical intervention. In this paper, we argue that mining online social behavior provides an opportunity to actively identify SNMDs at an early stage. It is challenging to detect SNMDs because the mental status cannot be directly observed from online social activity logs. Our approach, new and innovative to the practice of SNMD detection, does not rely on self-revealing of those mental factors via questionnaires in Psychology. Instead, we propose a machine learning framework, namely, Social Network Mental Disorder Detection (SNMDD) , that exploits features extracted from social network data to accurately identify potential cases of SNMDs. We also exploit multi-source learning in SNMDD and propose a new SNMD-based Tensor Model (STM) to improve the accuracy. To increase the scalability of STM, we further improve the efficiency with performance guarantee. Our framework is evaluated via a user study with 3,126 online social network users. We conduct a feature analysis, and also apply SNMDD on large-scale datasets and analyze the characteristics of the three SNMD types. The results manifest that SNMDD is promising for identifying online social network users with potential SNMDs.

With the advance of the photovoltaic panel technology, the infrastructure equipment of cellular networks with solar energy sources has attracted extensive interests. It is expected that base stations (BSs) and relay stations (RSs) with renewable energy will play important roles in reducing the power consumption from electrical grids in future green cellular networks. Inspired by this technology trend, this paper considers a heterogeneous green cellular network, in which a part of RSs is powered by solar energy sources to represent the incremental deployment for the infrastructure with renewable energy in the near future. We formulate a new relay selection and power allocation problem with Mixed Integer Linear Programming to select solar-powered RSs and grid-powered RSs, such that the total grid power consumption is effectively minimized in decode-and-forward cooperative communication networks. We design an algorithm to derive the optimal solution, and also devise an efficient distributed algorithm to reduce the computational cost. The simulation results demonstrate that the algorithms can effectively reduce the total grid power consumption with different channel conditions, different deployments of RSs in a network, and different available power levels in solar-powered RSs. In addition, the problem model and the proposed algorithms can be extended to support hybrid energy sources.

Because Online Social Networks (OSNs) have become increasingly important in the last decade, they have motivated a great deal of research on Social Network Analysis (SNA). Currently, SNA algorithms are evaluated on real datasets obtained from large-scale OSNs, which are usually sampled by Breadth-First-Search (BFS), Random Walk (RW), or some variations of the latter. However, none of the released datasets provides any statistical guarantees on the difference between the sampled datasets and the ground truth. Moreover, all existing sampling algorithms only focus on sampling a single OSN, but each OSN is actually a sampling of a complete social network. Hence, even if the whole dataset from a single OSN is sampled, the results may still be skewed and may not fully reflect the properties of the complete social network. To address the above issues, we have made the first attempt to explore the joint sampling of multiple OSNs and propose an approach called Quality-guaranteed Multi-network Sampler (QMSampler) that can jointly sample multiple OSNs. QMSampler provides a statistical guarantee on the difference between the sampled real dataset and the ground truth (the perfect integration of all OSNs). Our experimental results demonstrate that the proposed approach generates a much smaller bias than any existing method. QMSampler has also been released as a free download.

With the recent emergence of naked-eye 3D mobile devices and various 3D-enabled laptops, service providers now afford the opportunity to provide mobile 3D video streaming in LTE-Advanced networks. Differing from traditional single-view 3D videos, multi-view 3D videos allow users to choose preferred view angles and thus are promising for new applications, such as free-viewpoint television (FTV). Nevertheless, enabling multi-view 3D video services may overwhelm the network resource when transmitting all views of every video. Fortunately, Depth-Image-Based Rendering (DIBR) allows each mobile client to synthesize the desired view from a nearby left view and right view, so that not all views of a video are necessarily transmitted. A new challenge with DIBR, however, is to carefully choose the transmitted views to limit the video distortion and minimize the bandwidth consumption. In this paper, therefore, we first formulate a new optimization problem, called View and MCS Selection (VMS) Problem, to minimize the bandwidth consumption for multi-view 3D video multicast in LTE networks. An algorithm, called View and MCS Aggregation (VMAG) is proposed to find the optimal solution to VMS. For Carrier Aggregation (CA) in LTE-Advanced networks, we formulate a new View, MCS and Carrier Selection (VMCS) Problem and prove that the problem is NP-Hard. We first design a dynamic programming algorithm, called the View Assignment with MCS and Carrier (VAMC) algorithm, to find the optimal solution for small instances. We then propose the View and MCS Aggregation with Carrier (VMAGC) algorithm based on VMAG to effectively find the near-optimal solution to VMCS. The simulation results show that bandwidth consumption can be effectively reduced by over 30 percent in VMS and VMCS.

Due to the emergence of 3D video applications like virtual reality, network storage management for 360° videos is expected to play an important role. In comparison with traditional videos, it is envisaged that a 360° video requires larger space to store multiple views. Nevertheless, efficient storage schemes for 360° videos in a proxy have not been explored in the literature. In this paper, therefore, we first observe that the storage space can be effectively reduced by leveraging real-time image-based generation schemes to synthesize the desired views in 360° videos. We then formulate a new optimization problem, named Dynamic View Synthesis and Selection Problem (DVSSP), to minimize the total network cost over time, which includes the cost of synthesis, local transmission, and fetching views from the remote server. Since the current storage influences the cost spent in the future, we then devise an online algorithm based on the dynamic programming technique to carefully examine the correlation between nearby views that are most likely to be requested in the following time slots. Simulation results manifest that the proposed algorithm can significantly improve the hit rate by more than 50% and reduce more than 45% total cost compared with various baseline algorithms.

Internet of Things (IoT) has been regarded as one of the most significant network paradigms in the future. For IoT, it is crucial to ensure the correctness of detection which includes the factors of accuracy and precision. On the other hand, Mobile Edge Computing (MEC) has emerged as a promising way to process big IoT data at the network edge so as to reduce the computation and transmission energy in the networks. In this paper, we explore the energy minimization problem in MEC networks by considering both the accuracy and precision requirements of IoT. Specifically, given 1) a set of IoT devices, 2) a set of observed targets, 3) an MEC network, 4) the energy consumption model, and 5) the accuracy and precision requirements, we formulate a new optimization problem, named Accuracy and Precision-Aware IoT Device Selection (APAIDS), to minimize the overall energy consumption in MEC networks. We prove the NP-hardness of APAIDS and then propose a new algorithm, named Energy Efficient Device and MEC Server Selection (EDMS), to minimize energy consumption by jointly selecting IoT devices, configuring MEC association, and selecting processing servers for dealing with the data of each target. Finally, we evaluate EDMS on two real networks. In comparison with the baseline schemes, the results manifest that the overall energy consumption can be reduced by more than 60%.

Traffic engineering (TE) and efficient network updating have been considered as separate problems in previous SDN research. Traffic engineering mostly focuses on static traffic and does not consider the rerouting overheads to support dynamic traffic. Efficient network updating assumes the new routing is provided by TE and focuses on minimizing only the rerouting overheads, and therefore, the improved new routing with bandwidth consumption similar to the new routing from TE but much lower rerouting overheads has not been explored. In this paper, we explore Multi-tree Low-overhead Multicast Rerouting (MLMR) to jointly solve both problems for SDN multicast. We prove that MLMR is NP-hard and design a new approximation algorithm, named Multicast Rerouting and Update Scheduling Algorithm (MRUSA). Equipped with the notions of deterioration indicator, motivator, and inhibitor, MRUSA provides incremental tree updating and multi-tree update scheduling to address the trade-off between the bandwidth consumption and rerouting overheads. Frequent rerouting due to tiny changes of multicast users can be effectively avoided, because rerouting time for each group can be correctly identified. Simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 35% compared with SPT and ST, and the computation time is small for massive SDN.

Online social networks have become the medium for efficient viral marketing exploiting social influence in information diffusion. However, the emerging application Social Coupon (SC) incorporating social referral into coupons cannot be efficiently solved by previous researches which do not take into account the effect of SC allocation. The number of allocated SCs restricts the number of influenced friends for each user. In the paper, we investigate not only the seed selection problem but also the effect of SC allocation for optimizing the redemption rate which represents the efficiency of SC allocation. Accordingly, we formulate a problem named Seed Selection and SC allocation for Redemption Maximization (S3CRM) and prove the hardness of S3CRM. We design an effective algorithm with a performance guarantee, called Seed Selection and Social Coupon allocation algorithm. For S3CRM, we introduce the notion of marginal redemption to evaluate the efficiency of investment in seeds and SCs. Moreover, for a balanced investment, we develop a new graph structure called guaranteed path, to explore the opportunity to optimize the redemption rate. Finally, we perform a comprehensive evaluation on our proposed algorithm with various baselines. The results validate our ideas and show the effectiveness of the proposed algorithm over baselines., Full version (accepted by ICDE 2019)

With the rapid advent of Virtual Reality (VR) technology and virtual tour applications, there is a research need on spatial queries tailored for simultaneous movements in both the physical and virtual worlds. Traditional spatial queries, designed mainly for one world, do not consider the entangled dual worlds in VR. In this paper, we first investigate the fundamental shortest-path query in VR as the building block for spatial queries, aiming to avoid hitting boundaries and obstacles in the physical environment by leveraging Redirected Walking (RW) in Computer Graphics. Specifically, we first formulate Dual-world Redirected-walking Obstacle-free Path (DROP) to find the minimum-distance path in the virtual world, which is constrained by the RW cost in the physical world to ensure immersive experience in VR. We prove DROP is NP-hard and design a fully polynomial-time approximation scheme, Dual Entangled World Navigation (DEWN), by finding Minimum Immersion Loss Range (MIL Range). Afterward, we show that the existing spatial query algorithms and index structures can leverage DEWN as a building block to support kNN and range queries in the dual worlds of VR. Experimental results and a user study with implementation in HTC VIVE manifest that DEWN outperforms the baselines with smoother RW operations in various VR scenarios., Comment: 20 pages, 39 figures. A shorter version of this paper has been accepted for publication in the 28th ACM International Conference on Information and Knowledge Management (CIKM 2019); this is an expanded version containing supplementary details

With the emergence of multi-view 3D videos, network operators now face a new challenge to resolve the dramatic increase of the network bandwidth required to support all subscribed views (typically 16 or 32) of a video. Recently, Depth-Image-Based Rendering (DIBR) in Computer Vision has been demonstrated as a promising way for efficient multi-view 3D video multicast, because many views can be synthesized in mobile devices and no longer need to be transmitted. Nevertheless, DIBR is computationally intensive and incurs additional power consumption in mobile devices, and unsubscribed views need to be transmitted to mobile users for DIBR. In this paper, therefore, we aim to leverage Mobile Edge Computing (MEC) for DIBR to foster effective and efficient multi-view video multicast. We formulate a new problem, named Multi-view Multicast Synthesis and Delivery (MMSD) and prove the NP-Hardness. We design an approximation algorithm, named Merge Search Forest Algorithm (MSFA), to choose the view to be synthesized and build a multicast topology including a low-cost forest for supporting each subscribed view. Simulation results manifest that MSFA outperforms the existing approaches by 30% to 50% of the total communication and computation cost.

While the popularity of online social network (OSN) apps continues to grow, little attention has been drawn to the increasing cases of Social Network Addictions (SNAs). In this paper, we argue that by mining OSN data in support of online intervention treatment, data scientists may assist mental healthcare professionals to alleviate the symptoms of users with SNA in early stages. Our idea, based on behavioral therapy, is to incrementally substitute highly addictive newsfeeds with safer, less addictive, and more supportive newsfeeds. To realize this idea, we propose a novel framework, called Newsfeed Substituting and Supporting System (N3S), for newsfeed filtering and dissemination in support of SNA interventions. New research challenges arise in 1) measuring the addictive degree of a newsfeed to an SNA patient, and 2) properly substituting addictive newsfeeds with safe ones based on psychological theories. To address these issues, we first propose the Additive Degree Model (ADM) to measure the addictive degrees of newsfeeds to different users. We then formulate a new optimization problem aiming to maximize the efficacy of behavioral therapy without sacrificing user preferences. Accordingly, we design a randomized algorithm with a theoretical bound. A user study with 716 Facebook users and 11 mental healthcare professionals around the world manifests that the addictive scores can be reduced by more than 30%. Moreover, experiments show that the correlation between the SNA scores and the addictive degrees quantified by the proposed model is much greater than that of state-of-the-art preference based models.

Spatial proximity is one of the most important factors for the quick deployment of the task groups in various time-sensitive missions. This article proposes a new spatial query, Spatio-Social Team Query (SSTQ) , that forms a strong task group by considering (1) the group’s spatial distance (i.e., transportation time), (2) skills of the candidate group members, and (3) social rapport among the candidates. Efficient processing of SSTQ is very challenging, because the aforementioned spatial, skill, and social factors need to be carefully examined. In this article, therefore, we first formulate two subproblems of SSTQ, namely Hop-Constrained Team Problem (HCTP) and Connection-Oriented Team Query (COTQ) . HCTP is a decision problem that considers only social and skill dimensions. We prove that HCTP is NP-Complete. Moreover, based on the hardness of HCTP, we prove that SSTQ is NP-Hard and inapproximable within any factor . On the other hand, COTQ is a special case of SSTQ that relaxes the social constraint. We prove that COTQ is NP-Hard and propose an approximation algorithm for COTQ, namely COTprox . Furthermore, based on the observations on COTprox, we devise an approximation algorithm, SSTprox , with a guaranteed error bound for SSTQ. Finally, to efficiently obtain the optimal solution to SSTQ for small instances, we design two efficient algorithms, SpatialFirst and SkillFirst , with different scenarios in mind. These two algorithms incorporate various effective ordering and pruning techniques to reduce the search space for answering SSTQ. Experimental results on real datasets indicate that the proposed algorithms can efficiently answer SSTQ under various parameter settings.

Studies show that a person is willing to join a social group activity if the activity is interesting, and if some close friends also join the activity as companions. The literature has demonstrated that the interests of a person and the social tightness among friends can be effectively derived and mined from social networking websites. However, even with the above two kinds of information widely available, social group activities still need to be coordinated manually, and the process is tedious and time-consuming for users, especially for a large social group activity, due to complications of social connectivity and the diversity of possible interests among friends. To address the above important need, this paper proposes to automatically select and recommend potential attendees of a social group activity, which could be very useful for social networking websites as a value-added service. We first formulate a new problem, named Willingness mAximization for Social grOup (WASO). This paper points out that the solution obtained by a greedy algorithm is likely to be trapped in a local optimal solution. Thus, we design a new randomized algorithm to effectively and efficiently solve the problem. Given the available computational budgets, the proposed algorithm is able to optimally allocate the resources and find a solution with an approximation ratio. We implement the proposed algorithm in Facebook, and the user study demonstrates that social groups obtained by the proposed algorithm significantly outperform the solutions manually configured by users.

Power and on–off control problems are examined for renewable energy enabled base-stations (BSs) and relay nodes (RNs) in cooperative multicast networks. Renewable energy is utilized at BSs and RNs to reduce the overall grid energy cost. By considering a practical energy consumption model and the statistics of the renewable energy arrival, the optimal transmit powers are first determined by minimizing the expected grid energy consumption subject to an average outage probability constraint at MUs. The optimal solution is found via line search in the general case and is obtained in closed-form at high SNR. In addition, an on–off control policy is also proposed to further reduce the basic operational energy costs. The joint on–off and power control problems are solved approximately using two sequential deflation techniques, namely, the subset-search and the convex-relaxation-based approaches. The power control problem is also extended to the multicarrier scenario with unequal transmit powers and is solved using successive convex approximation. Simulations using the photovoltaic energy arrival model are provided to demonstrate the effectiveness of the proposed schemes. The results show that expending more power at RNs allows for more efficient use of renewable energy and, thus, increases energy-savings.

Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group with No-Pair Constraint (MkTG), to find a socially tenuous group from the online social network. We prove that MkTG is NP-hard and inapproximable within any ratio. Two algorithms, namely TERA and TERA-ADV, are designed for solving MkTG effectively and efficiently. Further, we examine the MkTG problem on tree-based social networks, due to their structural resemblance with corporate social networks built upon the supervision relation. Accordingly, we devise an efficient algorithm, namely Tenuity Maximization for Trees (TMT), to obtain the optimal solution in polynomial time. In addition, we study a more general version of MkTG, named Generalized Minimum k-Triangle Disconnected Group without No-Pair Constraint (MkTG-G). We formulate MkTG-G, analyze its inapproximability, and propose a randomized approximation algorithm, named Randomized Ranking with Limited Neighborhood Participation (RLNP). Experimental results on real datasets manifest that the proposed algorithms outperform the baselines in terms of both efficiency and solution quality.

Mobile Edge Computing (MEC) has recently emerged as a primary candidate for big data processing to reduce the latency and jitter. On the other hand, Software-Defined Internet of Things (SD-IoT) has been proposed to effectively and flexibly collect and process big IoT data. Nevertheless, minimizing the energy consumption in SD-IoT with big data processing (e.g., data aggregation and reconstruction) has not been explored before. In this paper, therefore, we explore the sensor data selection and routing problem in SD-IoT with big data processing. Specifically, given 1) a set of sensors, 2) a set of observed locations, 3) the network topology, and 4) the energy consumption model of big data processing and forwarding, we formulate a new optimization problem, named Sensor Data Selection, Processing, and Routing Problem (SDSPRP), to minimize the total energy consumption in SD-IoT. We prove that the emphasized problem is NP-hard and inapproximable within O(log|K|). To solve the problem, we propose an αlog|K|- approximation algorithm, called Energy Efficient Sensor Selection and Routing (ESR), to minimize the energy consumption by jointly considering the sensor selection and the energy consumption in traffic engineering and data processing. The proposed algorithm is evaluated on two real networks, and the results manifest that the energy consumption in SD- IoT can be reduced by more than 56%.

Previous research on SDN traffic engineering mostly focuses on static traffic, whereas dynamic traffic, though more practical, has drawn much less attention. Especially, online SDN multicast that supports IETF dynamic group membership (i.e., any user can join or leave at any time) has not been explored. Different from traditional shortest-path trees (SPT) and graph theoretical Steiner trees (ST), which concentrate on routing one tree at any instant, online SDN multicast traffic engineering is more challenging because it needs to support dynamic group membership and optimize a sequence of correlated trees without the knowledge of future join and leave, whereas the scalability of SDN due to limited TCAM is also crucial. In this paper, therefore, we formulate a new optimization problem, named Online Branch-aware Steiner Tree (OBST), to jointly consider the bandwidth consumption, SDN multicast scalability, and rerouting overhead. We prove that OBST is NP-hard and does not have a $|D_{max}|^{1-\epsilon}$-competitive algorithm for any $\epsilon >0$, where $|D_{max}|$ is the largest group size at any time. We design a $|D_{max}|$-competitive algorithm equipped with the notion of the budget, the deposit, and Reference Tree to achieve the tightest bound. The simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 25% compared with SPT and ST, and the computation time is small for massive SDN., Comment: Full version (accepted by INFOCOM 2018)

The small screen size of a smartwatch limits user experience when watching or interacting with media. We propose a supplementary tactile feedback system to enhance the user experience with a method unique to the smartwatch form factor. Our system has a deformable surface on the back of the watch face, allowing the visual scene on screen to extend into 2.5D physical space. This allows the user to watch and feel virtual objects, such as experiencing a ball bouncing against the wrist. We devised two controlled experiments to analyze the influence of tactile display resolution on the illusion of virtual object presence. Our first study revealed that on average, a taxel can render virtual objects between 70% and 138% of its own size without shattering the illusion. From the second study, we found visual and haptic feedback can be separated by 4.5mm to 16.2mm for the tested taxels. Based on the results, we developed a prototype (called RetroShape) with 4×4 10mm taxels using micro servo motors, and demonstrated its unique capability through a set of tactile-enhanced games and videos. A preliminary user evaluation showed that participants welcome RetroShape as a useful addition to existing smartwatch output.

Depth-Image-Based Rendering (DIBR) is a popular technology and enables the viewers to watch multi-view 3D videos via TV or smart phone. In this paper, we propose a game-theoretical framework over a multi-view and multi-video network where one server delivers multiple multi-view 3D videos to multiple viewers. In a mobile network, any individual viewers can subscribe to a video with any viewing angle within a specified viewing range in 3D-enabled mobile handsets. To facilitate efficient resource allocation for multi-view 3D videos, we formulate a new resource allocation problem, named Price-based 3D Viewing Range Control problem (PVRC), as a Stackelberg game in Game Theory, in which the server and the viewers are modeled as the leader and the followers, respectively, to jointly consider the revenue of the server and the utilities of the viewers. We analyze the price setting problem by investigating the Stackelberg equilibrium between the server and viewers. Simulation results demonstrate that compared to popular uniform-price setting, non-uniform pricing is an effective approach for reducing the difference of utilities among the viewers, effectively controlling the viewing ranges and avoiding starvation of the network resources to only few viewers. Moreover, we also derive the social optimum in the problem, and the simulation results show that the derived Stackelberg equilibrium is close to the social optimum.

Management of uncertain data in spatial queries has drawn extensive research interests to consider the granularity of devices and noises in the collection and the delivery of data. Most previous works usually model and handle uncertain data to find the required results directly. However, it is more difficult for users to obtain useful insights when data uncertainty dramatically increases. In this case, users are usually willing to invest more resources to improve the result by reducing the data uncertainty in order to obtain more interesting observations with the existing schemes. In light of this important need, this paper formulates a new problem of selecting a given number of uncertain data objects for acquiring their attribute values to improve the result of the Probabilistic k-Nearest-Neighbor (k-PNN) query. We prove that better query results are guaranteed to be returned with data acquisition, and we devise several algorithms to maximize the expected improvement. We first explore the optimal single-object acquisition for 1-PNN to examine the fundamental problem structure and then propose an efficient algorithm that discovers crucial properties to simplify the probability derivation in varied situations. We extend the proposed algorithm to achieve the optimal multi-object acquisition for 1-PNN by deriving an upper bound to facilitate efficient pruning of unnecessary sets of objects. Moreover, for data acquisition of k-PNN, we extract the k-PNN answers with sufficiently large probabilities to trim the search space and properly exploit the result of single-object acquisition for estimating the gain from multi-object acquisition. The experimental results demonstrate that the probability of k-PNN can be significantly improved even with only a small number of objects for data acquisition.

Network Function Virtualization (NFV) on Software-Defined Networks (SDN) can effectively optimize the allocation of Virtual Network Functions (VNFs) and the routing of network flows simultaneously. Nevertheless, most previous studies on NFV focus on unicast service chains and thereby are not scalable to support a large number of destinations in multicast. On the other hand, the allocation of VNFs has not been supported in the current SDN multicast routing algorithms. In this paper, therefore, we make the first attempt to tackle a new challenging problem for finding a service forest with multiple service trees, where each tree contains multiple VNFs required by each destination. Specifically, we formulate a new optimization, named Service Overlay Forest (SOF), to minimize the total cost of all allocated VNFs and all multicast trees in the forest. We design a new $3\rho_{ST}$-approximation algorithm to solve the problem, where $\rho_{ST}$ denotes the best approximation ratio of the Steiner Tree problem, and the distributed implementation of the algorithm is also presented. Simulation results on real networks for data centers manifest that the proposed algorithm outperforms the existing ones by over 25%. Moreover, the implementation of an experimental SDN with HP OpenFlow switches indicates that SOF can significantly improve the QoE of the Youtube service., Comment: Technical Report

Software-Defined Networking and Network Function Virtualisation (SDN/NFV) can provide flexible resource allocation to support innovative security solutions in a central manner. To mitigate HTTP DDoS attacks, shuffling-based moving target defense has been regarded as one of the most effective ways by redirecting user traffic among a group of virtualized service functions. However, previous work did not notice that frequent changes of user traffic will significantly intensify the control overhead of SDN. In this paper, therefore, we first model the effectiveness and cost for shuffling in SDN/NFV networking with Multi-Objective Markov Decision Processes to find the optimal tradeoff between the effectiveness and cost. We then propose a cost-effective approximation algorithm with a guarantee performance bound to solve the problem. Simulation and implementation on an experimental SDN/NFV network manifest that, given 100 attackers among 1000 users and 50 virtualized functions of a web service, our algorithm achieves the approximation ratio of 0.68 and imposes only 2.4s rule modification latency for each shuffle.

With software-defined network (SDN) and network function virtualization (NFV) techniques, we can embed the service chain consisting of a sequence of virtualized network functions (VNFs), i.e., we can determine the flow path and deploy the VNFs contained in the service chain at any place on the path. In the literature, the methods of service chain embedding bound the number of VNFs at a node, whereas the link capacities are disregarded and the amount of flows is not considered, which could cause serious congestion. In addition, according to our experiment, the process overhead on a computation node is linear to the total amount of flows processed. In this paper, we propose a method of service chain embedding to maximize the total amount of flows while bounding the process overhead of the flows on a node by its computation capability and the total amount of flows on an link by its bandwidth capacity. To our knowledge, our method is the first approximation algorithm of service chain embedding with considering flow in the literature. Simulations show our algorithm has good performance in terms of the total amount of flows.

An increasing number of social network mental disorders (SNMDs), such as Cyber-Relationship Addiction, Information Overload, and Net Compulsion, have been recently noted. Symptoms of these mental disorders are usually observed passively today, resulting in delayed clinical intervention. In this paper, we argue that mining online social behavior provides an opportunity to actively identify SNMDs at an early stage. It is challenging to detect SNMDs because the mental factors considered in standard diagnostic criteria (questionnaire) cannot be observed from online social activity logs. Our approach, new and innovative to the practice of SNMD detection, does not rely on self-revealing of those mental factors via questionnaires. Instead, we propose a machine learning framework, namely, Social Network Mental Disorder Detection (SNMDD), that exploits features extracted from social network data to accurately identify potential cases of SNMDs. We also exploit multi-source learning in SNMDD and propose a new SNMD-based Tensor Model (STM) to improve the performance. Our framework is evaluated via a user study with 3126 online social network users. We conduct a feature analysis, and also apply SNMDD on large-scale datasets and analyze the characteristics of the three SNMD types. The results show that SNMDD is promising for identifying online social network users with potential SNMDs., Comment: 11 pages