Wireless sensor networks face significant challenges in large-scale multitask scenarios (LSM-WSNs), where traditional data collection methods lead to high energy consumption and packet collisions. Mobile data collection, employing mobile collectors, mitigates these issues but introduces electricity shortages due to limited battery capacity. This paper addresses the core research problem of minimizing charger deployment costs while ensuring uninterrupted power for mobile collectors in long-running LSM-WSNs. We formulate the Minimum-Cost Charger Deployment (MCCD) problem, prove its NP-hardness, and establish its equivalence to the Overflow-Free MCCD (OF-MCCD) problem. By refining constraints and transforming OF-MCCD into a Minimum-Cost Submodular Cover (MCSC) problem, we propose a greedy algorithm with an approximation ratio of$ln\gamma +1$, where$\gamma$is a system parameter. Further, we extend MCCD problem to adjustable power allocation case, showing that continuous power allocation reduces to linear programming, while discrete power allocation remains NP-hard, for which we devise an efficient$ln\gamma +1$-approximation solution. Additionally, we tackle the Charger Deployment Extension (CDE) problem for evolving network requirements. The unique contributions include the first systematic study of cost-optimal charger deployment for LSM-WSNs, novel problem formulations, and theoretically grounded algorithms with provable guarantees. Simulations validate that our solutions outperform baselines across diverse scenarios.

Streaming (machine) learning (SML) can capture dynamic changes in real-time data and perform continuous updates. It has been widely applied in real-world scenarios such as network security, financial regulation, and energy supply. How-ever, due to the sensitivity and lightweight nature of SML models, existing work suffers from low robustness, sudden decline, and catastrophic forgetting when facing unexpected data distribution drifts. Previous studies have attempted to enhance the stability of SML through methods such as data selection, replay, and constraints. However, these methods are typically designed for specific feature spaces and specific ML algorithms. In this paper, we introduce a shift graph based on the distances between data distributions and define three distinct data shift patterns. For these three patterns, we design three adaptive mechanisms, (a) multi-time granularity models, (b) coherent experience clustering, and (c) historical knowledge reuse, that are triggered by a strategy selector, with the goal of enhancing the accuracy and stability of SML. We implement an adaptive and stable SML framework, FreewayML, on top of PyTorch, which is suitable for most SML models. Experimental results show that FreewayML significantly outperforms existing SML systems in both stability and accuracy, with a comparable throughput and latency.

Graph database systems store graph data as nodes and relationships, and utilize graph query languages (e.g., Cypher) for efficiently querying graph data. Proving the equivalence of graph queries is an important foundation for optimizing graph query performance, ensuring graph query reliability, etc. Although researchers have proposed many SQL query equivalence provers for relational database systems, these provers cannot be directly applied to prove the equivalence of graph queries. The difficulty lies in the fact that graph query languages (e.g., Cypher) adopt significantly different data models (property graph model vs. relational model) and query patterns (graph pattern matching vs. tabular tuple calculus) from SQL. In this paper, we propose GraphQE, an automated prover to determine whether two Cypher queries are semantically equivalent. We design a U-semiring based Cypher algebraic representation to model the semantics of Cypher queries. Our Cypher algebraic representation is built on the algebraic structure of unbounded semirings, and can sufficiently express nodes and relationships in property graphs and complex Cypher queries. Then, determining the equivalence of two Cypher queries is transformed into determining the equivalence of the corresponding Cypher algebraic representations, which can be verified by SMT solvers. To evaluate the effectiveness of GraphQE, we construct a dataset consisting of 148 pairs of equivalent Cypher queries. Among them, we have successfully proven 138 pairs of equivalent Cypher queries, demonstrating the effectiveness of GraphQE.

Enhancing the reasoning capabilities of large language models effectively using reinforcement learning (RL) remains a crucial challenge. Existing approaches primarily adopt two contrasting advantage estimation granularities: token-level methods (e.g., PPO) aim to provide fine-grained advantage signals but suffer from inaccurate estimation due to difficulties in training an accurate critic model. On the other extreme, trajectory-level methods (e.g., GRPO) solely rely on a coarse-grained advantage signal from the final reward, leading to imprecise credit assignment. To address these limitations, we propose Segment Policy Optimization (SPO), a novel RL framework that leverages segment-level advantage estimation at an intermediate granularity, achieving a better balance by offering more precise credit assignment than trajectory-level methods and requiring fewer estimation points than token-level methods, enabling accurate advantage estimation based on Monte Carlo (MC) without a critic model. SPO features three components with novel strategies: (1) flexible segment partition; (2) accurate segment advantage estimation; and (3) policy optimization using segment advantages, including a novel probability-mask strategy. We further instantiate SPO for two specific scenarios: (1) SPO-chain for short chain-of-thought (CoT), featuring novel cutpoint-based partition and chain-based advantage estimation, achieving $6$-$12$ percentage point improvements in accuracy over PPO and GRPO on GSM8K. (2) SPO-tree for long CoT, featuring novel tree-based advantage estimation, which significantly reduces the cost of MC estimation, achieving $7$-$11$ percentage point improvements over GRPO on MATH500 under 2K and 4K context evaluation. We make our code publicly available at https://github.com/AIFrameResearch/SPO.

Popular big data frameworks commonly run atop Java Virtual Machine (JVM) and rely on garbage collection (GC) mechanism to automatically allocate/reclaim in-memory objects. Existing garbage collectors are designed based on the hypothesis that most objects are short lived. However, big data frameworks usually generate many long-lived data objects, which can cause heavy GC overhead. Recent approaches have reduced GC overhead in big data frameworks but still suffer from heavy human efforts, additional runtime overhead, or suboptimal GC efficiency. This article describes the design of BridgeGC , a big-data-friendly garbage collector that significantly reduces GC overhead introduced by long-lived data objects. BridgeGC follows a cross-level co-design. At the big data framework level, BridgeGC provides two annotations for framework developers to denote the creation and release of data objects. Based on the annotations, BridgeGC tracks the lifecycles of annotated data objects and optimizes their allocation/reclamation at the GC level. At the GC level, we design a label-based allocator that stores data objects separately from other objects and balances their memory usage in the same JVM, leading to fewer GC cycles. We further design an efficient collector to eliminate unnecessary marking and copying of data objects during GC cycles, lowering the GC time. We have integrated BridgeGC into OpenJDK ZGC. The extensive evaluation, using two popular big data frameworks (Flink and Spark) and a key–value database (Cassandra), shows that BridgeGC achieves 31–82% GC time reduction compared to the baseline ZGC. BridgeGC also outperforms other traditional and academic garbage collectors in end-to-end performance.

Wireless power transmission has been widely used to replenish energy for wireless sensor networks, where the energy consumption rate of sensor nodes is usually time varying and indefinite. However, few works have investigated the problem of long-term charging scheduling with random variable. This article designs an optimization model for the long-term scheduling of chargers to maximize the time-averaged charging utility while ensuring its time-averaged constraints of budget and response rate. The Lyapunov optimization technique is adopted to transform the stochastic optimization problem into a deterministic optimization problem, which remains NP-hard. Thus, an approximation algorithm following greedy approach is proposed to solve the deterministic optimization problem. We further provide the theoretical analysis of feasibility and performance guarantee of the proposed scheduling algorithm. The simulation results show that our algorithm outperforms three comparison algorithms by 6.53%, 20.04%, and 19.97% in terms of time-averaged charging utility, as well as by 11.25%, 4.42%, and 3.73% in terms of time-averaged response rate on average.

In-database machine learning (In-DB ML) is appealing to database users with security and privacy concerns, as it avoids copying data out of the database to a separate machine learning system. The common way to implement in-DB ML is the ML-as-UDF approach, which utilizes the User-Defined Functions (UDFs) within SQL to implement the ML training and prediction. However, UDFs may introduce security risks with vulnerable code, and suffer from performance problems, as constrained by data access and execution patterns of SQL query operators. To address these limitations, we propose a new in-database machine learning system, namely GaussML, which provides an end-to-end machine-learning ability with native SQL interface. To support ML training/inference within SQL query, GaussML directly integrates typical ML operators into the query engine without UDFs. GaussML also introduces an ML-aware cardinality and cost estimator to optimize the SQL+ML query plan. Moreover, GaussML leverages Single Instruction Multiple Data (SIMD) and data prefetching techniques to accelerate the ML operators for training. We have implemented a series of algorithms inside GaussML in openGauss database. Compared to the state-of-the-art in-DB ML systems like Apache MADlib, our GaussML achieves 2-6× speed-up in extensive experiments.

Streaming graph computation has been widely applied in many fields, e.g., social network analysis and online product recommendation. However, existing streaming graph computation approaches still present limitations on accuracy and efficiency. To improve the accuracy, some distributed systems use the sequential graph update method based on an incremental computation model. However, these systems cannot handle the dynamic graph update concurrently. The speculation-based parallel updating model can parallelize the graph computation, however, it is restricted due to ignoring the original messages when updating a graph. Streaming graph computation usually requires high accuracy and low latency. As such, it is challenging to utilize incremental computation while simultaneously supplying concurrent processing guarantees.To overcome these challenges, in this paper, we first analyze a number of classical graph algorithms and summarize three principles that graph algorithms should satisfy in streaming scenarios. Based on these principles, we propose GraphFlow, a streaming graph computation model. GraphFlow achieves fast and accurate computation by utilizing incremental state update and propagation. To reduce the impact of concurrent update conflicts, GraphFlow provides a fine-grained lock based parallel update strategy. We implement GraphFlow framework and evaluate its performance and concurrent update conflict probability on real-world datasets. Meanwhile, we compare GraphFlow with two existing representative graph processing systems. Experimental results show GraphFlow achieves low latency and outperforms other graph processing systems given large datasets.

Abstract Public transportation system is one of the most effective ways to conserve energy and reduce carbon emissions. However, the traditional public transportation system does not provide customized service and cannot guarantee the arrival time to destination. To address these issues, we formulate the minimum shared bus scheduling problem to minimize the number of shared buses such that all orders can be completed under constraints of deadlines and capacity of shared bus. We propose the approximation algorithms, S‐MBSA for the shared bus with strong endurance and E‐MBSA for the large‐scale order scenario, to solve the minimum shared bus scheduling problem. We further formulate the constrained maximum revenue shared bus scheduling problem to maximize the revenue under the limited number of shared buses, and propose an approximation algorithm, CMRBSA, to find the shared bus route schedules. Through the extensive simulations, we demonstrate the significant superiority of S‐MBSA and E‐MBSA in terms of number of shared buses. Furthermore, CMRBSA outperforms the benchmark algorithms significantly in terms of revenue.

Charger placement is an important problem in improving the quality of service in wireless rechargeable sensor networks. This paper studies the problem ofWireless ChArger PlacemeNt with Multiple (Directional) Antennas (WANDA). The problem is described as follows: given a set of wireless chargers equipped with multiple directional antennas and a set of wireless rechargeable sensors, determine the chargers' positions and orientations to maximize the overall charging utility. According to the relative positional relationship between the antennas, the problem is classified into Relative Orientation Fixed (WANDA-ROF) and Relative Orientation Unfixed (WANDA-ROU) situations. To address WANDA, we present a piecewise constant function to approximate the nonlinearity of charging power and propose an area discretization technique to reduce the infinite solution space to a limited one without performance loss. Then, we prove the monotonic submodularity of WANDA, and present a$\frac{1}{2}-\epsilon$approximation algorithm for the ROF situation and a$\frac{1}{2}-\epsilon$approximation algorithm for the ROU situation, all run in polynomial time. Finally, we conduct extensive simulation and experiments to show that our algorithms outperform comparison algorithms by at least 16% for ROF situation and 12% for ROU situation.

Wireless Power Transfer (WPT) technology has been developed rapidly in recent years. The cooperative charging model and corresponding scheduling methods have been proposed to save the charging cost in paid charging service. However, the state-of-the-art methods ignore the spatial occupation issue of rechargeable devices. Moreover, the cooperative charging scheduling in directional wireless charging has not been studied yet. This paper studies the cooperative scheduling for directional wireless charging with spatial occupation. We formulate the Cooperative Charging Scheduling with Spatial occupation (CCSS) problem of Mobile Rechargeable Sensor Devices (MRSDs) for optimizing the total cost of whole charging system. We first investigate the properties of optimal arrangement of MRSDs in charging group and calculate the tight intervals of charging angles of MRSDs. We show that it is sufficient to bound the error by conducting angle discretization for only two MRSDs in each charging group. Then, a$(\ln n+1)(1+\varepsilon)$-approximation algorithm of the CCSS problem is proposed based on greedy approach, where$n$is the number of MRSDs, and$\varepsilon$is the discretization error. The results of extensive simulations and field experiments demonstrate that our algorithm can reduce at most 42.5% total cost comparing with the benchmark algorithms.

Wireless Power Transmission (WPT) has been widely used to replenish energy for wireless rechargeable sensor networks. This paper concerns the fundamental issue of robust fault-tolerant placement of wireless chargers for directional charging. Following the general directional charging model, we formulate theCharger Placement for Robust Coverage (CPRC)problem, which has continuous and infinite constraints, for resisting the wireless charger failure. We transform the problem to the equivalent integer program problem without performance loss by area partition and dominating strategy extraction. We show that the greedy algorithm achieves the logarithmic approximation ratio. We further formulate theCharger Placement for Robust Utility (CPRU)problem for resisting the sensor node failure. This problem also has continuous and infinite constraints. We transform the problem to the combinational optimization problem with finite strategy space through the techniques of charging power approximation, area discretization and dominating strategy extraction. We present the algorithm, which utilizes the combination of binary search and greedy algorithm, to solve theCPRUproblem. We conduct both simulations and field experiments to validate our theoretical results. The simulation results show that the proposed algorithms forCPRCandCPRUcan outperform comparison algorithms by at least 17.48% and 21.15%, respectively.

Abstract Modern machine learning (ML) systems commonly use stochastic gradient descent (SGD) to train ML models. However, SGD relies on random data order to converge, which usually requires a full data shuffle. For in-DB ML systems and deep learning systems with large datasets stored onblock-addressable secondary storagesuch as HDD and SSD, this full data shuffle leads to low I/O performance—the data shuffling time can be even longer than the training itself, due to massive random data accesses. To balance the convergence rate of SGD (which favors data randomness) and its I/O performance (which favors sequential access), previous work has proposed several data shuffling strategies. In this paper, we first perform an empirical study on existing data shuffling strategies, showing that these strategies suffer from either low performance or low convergence rate. To solve this problem, we propose a simple but noveltwo-leveldata shuffling strategy named , which canavoida full data shuffle while maintainingcomparableconvergence rate of SGD as if a full shuffle were performed. We further theoretically analyze the convergence behavior of and empirically evaluate its efficacy in both in-DB ML and deep learning systems. For in-DB ML systems, we integrate into PostgreSQL by introducing three newphysicaloperators with optimizations. For deep learning systems, we extend single-process to multi-process for the parallel/distributed environment and integrate it into PyTorch. Our evaluation shows that can achieve comparable convergence rate with the full-shuffle-based SGD for both linear models and deep learning models. For in-DB ML with linear models, is 1.6 $$\times $$ × $$-$$ - 12.8 $$\times $$ × faster than two state-of-the-art systems, Apache MADlib and Bismarck, on both HDD and SSD. For deep learning models on ImageNet, is 1.5 $$\times $$ × faster than PyTorch with full data shuffle.

To port the Linux distributions to a new Instruction Set Architecture (ISA), developers have to rebuild the software packages of the distributions.The complex dependencies of the software packages bring a great challenge.It is important to understand and properly handle the dependencies.We selected Fedora, a typical Linux distribution, and studied the dependencies within the software repositories of aarch64 and x86_64 architecture.We proposed a package dependency network framework to study the roles played by different packages.We obtained three network dependency patterns and proposed the corresponding division strategies which help developer build the source packages in parallel.Our study reveals that the key packages located at the root of multiple dependency chains significantly impact the division of the network, and their builds should be prioritized.Meanwhile, some packages with external dependencies can be temporarily masked to make a sub-network independent.Furthermore, the network dependency patterns are also observed in Fedora 33 riscv64 and OpenEuler riscv64.Our findings can help researchers have a better knowledge of Linux distribution dependency network and help practitioners conduct efficient package builds.

The multi-hop wireless charging technology can largely extend the charging service range of chargers, thus has promising prospect in sustainable energy replenishment for wireless rechargeable sensor network. This paper proposes a new cost criterion, termed comprehensive cost consisting of energy cost and deployment cost, to measure the actual expenditure of wireless charging. We present a multi-hop wireless charging model and formulate the problem of minimizing the comprehensive cost such that the energy demand of all sensor nodes can be fulfilled by the energy capacitated chargers. We propose a (ln n+1)-approximation algorithm for the optimization problem, where n is the number of sensor nodes. Then, we propose a straightforward cost sharing mechanism, which ensures that no subset of sensor nodes can benefit by breaking away from the current charging tree for any fixed charger position, to realize the paid charging service of multi-hop wireless charging. Furthermore, to keep the magnetic fields of transmitters from the interfering, the conflict avoidance schemes are proposed in both central and distributed situations. Finally, we discuss the distributed scheme for minimizing the comprehensive cost without support of central server. Through extensive simulations, we demonstrate the significant superiority of the proposed algorithms in terms of comprehensive cost.

The multi-hop wireless charging technology has attracted a lot of attention, as it largely extends the charging range of chargers. Different from the existing work with single cost optimization, the objective of this article is to optimize the comprehensive cost, which is the combination of energy cost and deployment cost. We decompose the target problem into two sub-problems. The first sub-problem aims to minimize the deployment cost with energy capacity constraints. The proposed algorithm follows the greedy strategy, where the subset of sensor nodes for any charger is determined by finding the capacitated minimum spanning tree. The second sub-problem, which aims to maximize the reduction of comprehensive cost by adding chargers to the solution of the first sub-problem, is proved to be an unconstrained submodular set function maximization problem and can be solved by a 1/2-approximation randomized linear time algorithm for its equivalent problem. Through extensive simulations, we demonstrate that the proposed solution can reduce the comprehensive cost by 57.55% comparing with the benchmark algorithms.

To control the rapid spread of COVID-19, we consider deploying a set of Unmanned Aerial Vehicles (UAVs) to form a quarantine barrier such that anyone crossing the barrier can be detected. We use a charging pile to recharge UAVs. The problem is scheduling UAVs to cover the barrier, and, for any scheduling strategy, estimating the minimum number of UAVs needed to cover the barrier forever. We propose breaking the barrier into subsegments so that each subsegment can be monitored by a single UAV. We then analyze two scheduling strategies, where the first one is simple to implement and the second one requires fewer UAVs. The first strategy divides UAVs into groups with each group covering a subsegment. For this strategy, we derive a closed-form formula for the minimum number of UAVs. In the case of insufficient UAVs, we give a recursive function to compute the exact coverage time and give a dynamic-programming algorithm to allocate UAVs to subsegments to maximize the overall coverage time. The second strategy schedules all UAVs dynamically. We prove a lower and an upper bound on the minimum number of UAVs. We implement a prototype system to verify the proposed coverage model and perform simulations to investigate the performance.

This paper studies the problem of Wireless ChArger PlacemeNt with Multiple (Directional) Antennas (WANDA). Given a set of wireless chargers wherein each charger is equipped with multiple directional antennas and a set of wireless rechargeable sensors, determining the chargers' positions and the antennas' orientations, such that the overall charging utility is maximized. To address WANDA, we first present a piecewise constant function to approximate the nonlinear relationship between charging power and charging distance. Then, we propose an area discretization technique to reduce the infinite solution space to a limited one without performance loss. Next, we present approximation algorithms for both Relative Orientation Fixed (WANDA-ROF) and Relative Orientation Unfixed (WANDA-ROU) situations. For WANDA-ROF, we propose a Maximum Coverage Set extraction method that transforms WANDA-ROF into the problem of maximizing a monotone submodular function subject to a partition matroid constraint and then present a$1/2 -\epsilon$approximation algorithm. For WANDA-ROU, we construct a candidate position set for each charger to limit the searching space. Then, we propose a novel two-level submodular optimization scheme to address it, which achieves an approx-imation ratio of 1/6 - ∊. Simulation and experimental results show that our algorithms outperform comparison algorithms by at least 22%.

Stochastic gradient descent (SGD) is the cornerstone of modern ML systems. Despite its computational efficiency, SGD requires random data access that is inherently inefficient when implemented in systems that rely on block-addressable secondary storage such as HDD and SSD, e.g., in-DB ML systems and TensorFlow/PyTorch over large files. To address this impedance mismatch, various data shuffling strategies have been proposed to balance the convergence rate of SGD (which favors randomness) and its I/O performance (which favors sequential access).

When a UAV broadcasts its location periodically during flight, a target will observe the strongest signal when the UAV is at the closest location; thus, the target can infer its location based on the observed signals and the UAV’s trajectory. We consider how to design trajectories for UAVs such that all targets can locate themselves, and the maximum length of trajectories is minimized. To make the problem tractable, we impose constraints on the set of possible trajectories such that they only contain the edges of small squares. We propose an integer-linear-programming-based solution, which runs in exponential time, and two polynomial-time constant-factor approximation algorithms. We implement a prototype system to verify the feasibility of the localization method. Simulations show that our approach outperforms the existing ones in terms of flight length and localization error.

The success of online shopping accelerates the development of express delivery business with economic and efficient service. Current express delivery systems usually deliver the packages in noncooperation mode and cannot jointly optimize the express fee and moving cost of users. This paper proposes the cooperative package assignment system by lumping packages at the same express station to share the express fee, and proposes a novel pricing structure to stimulate the express stations to join the system without revenue loss by introducing cooperation cost. We formulate thecooperative package assignment (CPA)problem with heterogeneous express stations for joint optimization of users’ express fee and moving cost. Then, an approximate algorithm,CPAA, is proposed for theCPAproblem based on the greedy approach using submodular function minimization. We show that the designed algorithm achieves computational efficiency and guaranteed approximation. Furthermore, we model the large-scaleCPAproblem asCPA-gameand present a game theoretic algorithm,CPAGA. We show thatCPA-gamehas at least oneNash Equilibrium, andCPAGAfinally converges to a pureNash Equilibrium. Through extensive simulations, we demonstrate thatCPAAandCPAGAshow great advantages in terms of comprehensive cost, which is 28.1% and 19.9% lower than that in noncooperation mode on average, respectively. Moreover,CPAGAshows great scalability and is more suitable for large-scale cooperative package assignment systems.

Crowdsourcing has become an effective tool to utilize human intelligence to perform tasks that are challenging for machines. Many truth discovery methods and incentive mechanisms for crowdsourcing have been proposed. However, most of them cannot deal with the crowdsourcing with copiers, who copy a part (or all) of data from other workers. This article aims at designing crowdsourcing incentive mechanism for truth discovery of textual answers with copiers. We formulate the problem of maximizing the social welfare such that all tasks can be completed with the least confidence for truth discovery and design an three-stage incentive mechanism. In contextual embedding and clustering stage, we construct and cluster the content vector representations of textual crowdsourced answers at the semantic level. In truth discovery stage, we estimate the truth for each task based on the dependence and accuracy of workers. In reverse auction stage, we design a greedy algorithm to select the winners and determine the payment. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, truthfulness, and guaranteed approximation. Moreover, our truth discovery methods show prominent advantage in terms of precision when there are copiers in the crowdsourcing systems.

Stochastic Gradient Descent (SGD) has become the de facto way to train deep neural networks in distributed clusters. A critical factor in determining the training throughput and model accuracy is the choice of the parameter synchronization protocol. For example, while Bulk Synchronous Parallel (BSP) often achieves better converged accuracy, the corresponding training throughput can be negatively impacted by stragglers. In contrast, Asynchronous Parallel (ASP) can have higher throughput, but its convergence and accuracy can be impacted by stale gradients. To improve the performance of synchronization protocol, recent work often focuses on designing new protocols with a heavy reliance on hard-to-tune hyper-parameters. In this paper, we design a hybrid synchronization approach that exploits the benefits of both BSP and ASP, i.e., reducing training time while simultaneously maintaining the converged accuracy. Based on extensive empirical profiling, we devise a collection of adaptive policies that determine how and when to switch between synchronization protocols. Our policies include both offline ones that target recurring jobs and online ones for handling transient stragglers. We implement the proposed policies in a prototype system, called Sync-Switch, on top of TensorFlow, and evaluate the training performance with popular deep learning models and datasets. Our experiments show that Sync-Switch can achieve ASP level training speedup while maintaining similar converged accuracy when comparing to BSP. Moreover, Sync-Switch's elastic-based policy can adequately mitigate the impact from transient stragglers.

Wireless Power Transmission (WPT) has been widely used to replenish energy for Wireless Rechargeable Sensor Networks. However, the charging service model, which is of the essence to commercial WPT, has not emerged so far. In this paper, we present a wireless charging service model from the perspective of cooperative charging economics, and formulate the Cooperative Charging Scheduling (CCS) problem for joint optimization of rechargeable devices' charging cost and moving cost. We first propose two intragroup cost sharing schemes to sustain the cooperation among devices. Then, the approximation algorithm CCSA of the CCS problem is proposed based on greedy approach and submodular function minimization. Furthermore, we model the large-scale CCS problem as a coalition formation game and present a game theoretic algorithm CCSGA. We show that CCSGA finally converges to a pure Nash Equilibrium. We conduct simulations, and field experiments on a testbed consisting of 5 chargers and 8 rechargeable sensor nodes. The results show that the average comprehensive cost of CCSA is 27.3% lower than the noncooperation algorithm and is only 7.3% higher than the optimal solution on average. In field experiments, CCSA outperforms the noncooperation algorithm by 42.9% in terms of comprehensive cost on average. Moreover, CCSGA is much faster than the approximation algorithm and is more suitable for large-scale cooperative charging scheduling.

In recent years, mobile crowdsensing has become an effective method for large-scale data collection. Incentive mechanism is fundamentally important for mobile crowdsensing systems. Many mobile crowdsensing systems expect to optimize multiple objectives simultaneously. Most of the existing works transform the multiobjective problem into a single objective problem through constraints or scalarization method. However, due to the uncertain importance (weights) of objectives and the instable quality of crowdsensed data, such transformation is usually unrealizable. In this article, we aim to optimize the worst performance of two objective functions in mobile crowdsensing in order to improve the system robustness. We model an auction-based biobjective robust mobile crowdsensing system, and design two independent objective functions to maximize the expected profit and coverage, respectively. We formulate the robust user selection (RUS) problem, and design an incentive mechanism, which utilizes the combination of binary search and greedy algorithm, to solve the RUS problem. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the designed incentive mechanisms satisfy desirable properties of computational efficiency, individual rationality, truthfulness, and constant approximation to the tightened RUS problem. Moreover, the proposed incentive mechanism can be easily extended to multiobjective robust mobile crowdsensing systems, and all desirable properties still hold. The simulation results reveal that our incentive mechanism achieves 11% improvement of the platform’s utility, compared with the greedy algorithm for biobjective mobile crowdsensing systems on average.

The development of Electric Vehicle (EV) helps to ease energy crises and deduce vehicle exhaust emissions. However, it also brings a great impact on both transportation networks and power grids. There are some serious impediments in terms of energy charging to the popularization of EV, such as high deployment cost of charging stations, low charging efficiency, and voltage deviation of power grid. To address these issues, we design a new EV charging system, which levers the bus network in urban areas through the integration of OnLine Electric Vehicle (OLEV) system and Microwave Power Transfer (MPT) system. We formulate the EV route scheduling problem based on this new charging system to maximize the total residual energy subject to all EVs can arrive to their destinations before deadlines. Then, we propose an approximation algorithm, RSA, to solve the route scheduling problem. To relieve the traffic congestion, we further formulate the conflict-free EV route scheduling problem, and use the matching based algorithm, FRSA, to find the EV route schedules with the maximal residual energy. Through the extensive simulations, we demonstrate that RSA and FRSA can increase the average residual energy by 67.66% and 50.36% compared with the solution without the designed wireless charging system, respectively. Moreover, RSA reduces 22.22% of travel time and outputs 77.23% of residual energy, and FRSA can obtain 83.51% residual energy with 3.62% of extra travel time of the corresponding optimal solutions on average, respectively.

In this paper, we consider the problem of area charging, that is, assuming that there is a mobile charger (MC) equipped with a directional wireless charger whose charging area is in the shape of a sector, and the MC can only recharge sensors on the boundary of an Area of Interest (AOI), how to design an efficient charging scheme for the MC to recharge any sensor inside the AOI with efficient energy while its overall charging time is minimized. To address this problem, we first partition the AOI into two types of subareas, i.e., rectangle-like subareas and sector-like subareas, based on the Medial Axis of the AOI. Second, we propose rectangle-based moving strategy for the rectangle-like subareas, and sector-based rotating strategy for the sector-like subareas, respectively, for the MC. Finally, we calculate charging time of all subareas based on the above two moving strategies, and prove that our algorithm achieves a constant approximation ratio. We evaluate our algorithm by conducting extensive simulation. The results show that on average, other comparison algorithms require at least 18:70 times of charging time of that of our algorithm.

Stream clustering is an important data mining technique to capture the evolving patterns in real-time data streams. Today’s data streams, e.g., IoT events and Web clicks, are usually high-speed and contain dynamically-changing patterns. Existing stream clustering algorithms usually follow an online-offline paradigm with a one-record-at-a-time update model, which was designed for running in a single machine. These stream clustering algorithms, with this sequential update model, cannot be efficiently parallelized and fail to deliver the required high throughput for stream clustering.In this paper, we present DistStream, a distributed framework that can effectively scale out online-offline stream clustering algorithms. To parallelize these algorithms for high throughput, we develop a mini-batch update model with efficient parallelization approaches. To maintain high clustering quality, DistStream’s mini-batch update model preserves the update order in all the computation steps during parallel execution, which can reflect the recent changes for dynamically-changing streaming data. We implement DistStream atop Spark Streaming, as well as four representative stream clustering algorithms based on DistStream. Our evaluation on three real-world datasets shows that DistStream-based stream clustering algorithms can achieve sublinear throughput gain and comparable (99%) clustering quality with their single-machine counterparts.

We consider barrier coverage applications where a set of UAVs are deployed to monitor whether intruders pass through a line, i.e., the barrier. Due to limited energy supply of UAVs, a charging pile is used to recharge UAVs. The problem is to place UAVs on top of the barrier and schedule them to the charging pile such that the barrier is seamlessly covered and the total number of UAVs is minimized. We decompose the problem into subproblems by dividing the barrier into disjoint subsegments and covering each subsegment independently. We prove a theoretical lower bound on the minimum number of UAVs required to cover the barrier forever. We then propose two scheduling strategies. In the first strategy, only fully recharged backup UAVs will be scheduled to take over UAVs running out of energy. If there are enough UAVs, this strategy can cover the barrier forever. The second strategy is proposed to deal with the situation that the number of UAVs is insufficient. Under the strategy, if no backup UAV is fully recharged, the one with the most battery energy will be selected to take over the monitoring task. When the number of UAVs is insufficient, the barrier can still be covered for a long time. We analytically derive the number of UAVs required by the first strategy, and the monitoring duration of the second strategy in case of insufficient UAVs. Simulations verify the effectiveness of the proposed solutions.

Apache Spark has been widely used to build big data applications. Spark utilizes the abstraction of Resilient Distributed Dataset (RDD) to store and retrieve large-scale data. To reduce duplicate computation of an RDD, Spark can cache the RDD in memory and then reuse it later, thus improving performance. Spark relies on application developers to enforce caching decisions by using persist() and unpersist() APIs, e.g., which RDD is persisted and when the RDD is persisted / unpersisted. Incorrect RDD caching decisions can cause duplicate computations, or waste precious memory resource, thus introducing serious performance degradation in Spark applications. In this paper, we propose CacheCheck, to automatically detect cache-related bugs in Spark applications. We summarize six cache-related bug patterns in Spark applications, and then dynamically detect cache-related bugs by analyzing the execution traces of Spark applications. We evaluate CacheCheck on six real-world Spark applications. The experimental result shows that CacheCheck detects 72 previously unknown cache-related bugs, and 28 of them have been fixed by developers.

Graph algorithms are widely applied in social networks, computational biology, Internet security and a broad range of complexity science. Although there are many state-of-the-art graph frameworks, few frameworks support parallel graph mining in joint cloud computing environment. In this paper, we propose GraphLib, a parallel graph mining library, based on a BSP (Bulk Synchronous Parallel) service over joint cloud computing which was proposed in our prior work. We first summarize the features of commonly-used graph mining algorithms, and present our approaches for parallelizing typical graph mining algorithms. GraphLib includes 17 parallel graph mining algorithms that can be used in 3 scenarios. We evaluate the performance of 4 typical parallel graph algorithms in GraphLib on three real-world datasets. Our parallelized algorithms can achieve sub-linear scalability.

In this paper, we consider a scenario where an unmanned aerial vehicle (UAV) collects data from a set of nodes placed on a two-dimensional (2-D) plane. The UAV flies along a given line to collect data. To prevent transmission collisions, only one node is allowed to transmit data to the UAV at any time, and the number of nodes that can transmit data to the UAV cannot exceed a specified number to avoid frequent switches. The problem is to select a subset of nodes and schedule their transmission time to maximize the UAV's throughput. After formulating the problem, we find that it is difficult to solve due to mixture of real variables and integer variables. We then propose to decompose the problem into subproblems, and give a polynomial time algorithm to solve each subproblem to optimality. We then get an exact algorithm by solving all subproblems. Unfortunately, due to an exponential number of subproblems, the overall running time is exponential with respect to the input size. We then propose two polynomial-time suboptimal algorithms to solve the problem, both of which explore a polynomial number of subproblems. Simulations show that the suboptimal algorithms perform comparably with the exponential-time exact algorithm, while the running time is much smaller.

We consider using UAVs to provide location service to ground targets. UAVs fly over the target area and broadcast their locations periodically via wireless signals. When a UAV flies along a straight line, a target will observe the strongest signal when the UAV is at the closest location, based on which it can infer its location. The problem is to minimize the flight length subject to the constraint that the transmission range of a UAV is limited and all targets in the area should be located. We formulate the problem and give an optimal flight path to cover a square with side length no greater than a certain value. In the general case when the given area cannot be covered by the square, we propose to divide UAVs into two groups, whose flight paths are either parallel or orthogonal. We conduct simulations to compare our approach with existing approaches. Results verify the superiority of our approach in terms of flight length and localization error.

Mobile crowd sensing emerges as a new paradigm which takes advantage of the pervasive sensor-embedded smartphones to collect data. Many incentive mechanisms for mobile crowd sensing have been proposed. However, none of them takes into consideration the cooperative compatibility of users for multiple cooperative tasks. In this paper, we design truthful incentive mechanisms to minimize the social cost such that each of the cooperative tasks can be completed by a group of compatible users. We study two bid models and formulate the Social Optimization Compatible User Selection (SOCUS) problem for each model. We also define three compatibility models and use real-life relationships from social networks to model the compatibility relationships. We design two incentive mechanisms, MCT - M and MCT - S, for the compatibility cases. Both of MCT - M and MCT - S consist of two steps: compatible user grouping and reverse auction. We further present a user grouping method through neural network model and clustering algorithm. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, and truthfulness. Moreover, MCT - M can output the optimal solution. By using neural network and clustering algorithm for user grouping, the proposed incentive mechanisms can reduce the social cost and overpayment ratio further with less grouping time.

Crowdsourcing has become an efficient paradigm for performing large scale tasks. Truth discovery and incentive mechanism are fundamentally important for the crowdsourcing system. Many truth discovery methods and incentive mechanisms for crowdsourcing have been proposed. However, most of them cannot be applied to dealing with the crowdsourcing with copiers. To address the issue, we formulate the problem of maximizing the social welfare such that all tasks can be completed with the least confidence for truth discovery. We design an incentive mechanism consisting of truth discovery stage and reverse auction stage. In truth discovery stage, we estimate the truth for each task based on both the dependence and accuracy of workers. In reverse auction stage, we design a greedy algorithm to select the winners and determine the payment. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, truthfulness, and guaranteed approximation. Moreover, our truth discovery method shows prominent advantage in terms of precision when there are copiers in the crowdsourcing systems.

Mobile crowdsensing emerges as a new paradigm that takes advantage of pervasive sensor-embedded smartphones to collect sensory data. Many incentive mechanisms for mobile crowdsensing have been proposed. However, none of them takes into consideration the spatio-temporal tasks in mobile crowdsensing systems, where the sensing areas of tasks can have overlaps, and the collective sensing time for each task needs to meet the specified time duration. In this paper, we present two system models for location sensitive users and location insensitive users, respectively, and formulate the social optimization problem for each model. We design two reverse auction based truthful incentive mechanisms to minimize the social cost subject to the constraint that each of the spatio-temporal tasks can be completed with its collective sensing time no less than a minimum sensing time required by the platform. Through both theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, truthfulness, and guaranteed approximation.

Popular big data frameworks, ranging from Hadoop MapReduce to Spark, rely on garbage-collected languages, such as Java and Scala. Big data applications are especially sensitive to the effectiveness of garbage collection (i.e., GC), because they usually process a large volume of data objects that lead to heavy GC overhead. Lacking in-depth understanding of GC performance has impeded performance improvement in big data applications. In this paper, we conduct the first comprehensive evaluation on three popular garbage collectors, i.e., Parallel, CMS, and G1, using four representative Spark applications. By thoroughly investigating the correlation between these big data applications' memory usage patterns and the collectors' GC patterns, we obtain many findings about GC inefficiencies. We further propose empirical guidelines for application developers, and insightful optimization strategies for designing big-data-friendly garbage collectors.

Mobile crowdsourcing has become an efficient paradigm for performing large scale tasks. The incentive mechanism is important for the mobile crowdsourcing system to stimulate participants, and to achieve good service quality. In this paper, we focus on solving the insufficient participation problem in the budget constrained online crowdsourcing system. We present a two-tiered social crowdsourcing architecture, which can enable the selected registered users to recruit their social neighbors by diffusing the tasks to their social circles. In the two-tiered social crowdsourcing system, the tasks are associated with different end times, and both the registered users and their social neighbors have different arrival/departure times. An online incentive mechanism, MTSC, which consists of two steps: Agent Selection and Online Reverse Auction, is proposed for this novel mobile crowdsourcing system. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed incentive mechanism achieves computational efficiency, individual rationality, budget feasibility, cost truthfulness, and time truthfulness.

Stream processing system (SPS) faces the problem of node failure when running over a long period of time. In addition, "exactly once" precise semantic guarantee is more and more important for SPS in some scenarios. In general, the approaches to achieve precise semantic is by using global snapshot, which should store state and records to external reliable storage or rely on transactions. However, these approaches suffer from high recovery latency, because of large I/O disk overhead. In order to reduce excessive latency in failure recovery, we save the intermediate results which are produced during the stream processing, and propose an algorithm DCAS which asynchronously snapshots state to implements precise recovery. In addition, we use in-memory distributed cache to provide the storage of intermediate results and snapshots to reduce recovery latency. We evaluate our failure recovery approach in recovery latency and runtime overhead. The experimental results show that our approach is 2 to 6 times faster than other conventional failure recovery approaches, and induces a 6% runtime overhead.

Big data applications that rely on relational databases gradually expose limitations on scalability and performance. In recent years, Hadoop ecosystem has been widely adopted as an evolving solution. This paper presents the migration of a legacy data analytics application in a provincial data center. The target platform follows "no one size fits all" method. Considering different workloads, data storage is hybrid with distributed file system (HDFS) and distributed NoSQL database. Beyond the architecture re-design, we focus on the problem of data model transformation from relational database to NoSQL database. We propose a query-aware approach to free developers from tedious manual work. The approach generates query-specific views (NoView) for NoSQL and re-structures the views to align with NoSQL's data model. Our results show that the migrated application achieves high scalability and high performance. We believe that our practice provides valuable insights (such as NoSQL data modeling methodology), and the techniques can be easily applied to other similar migrations.

Out of memory (OOM) errors occur frequently in data-intensive applications that run atop distributed data-parallel frameworks, such as MapReduce and Spark. In these applications, the memory space is shared by the framework and user code. Since the framework hides the details of distributed execution, it is challenging for users to pinpoint the root causes and fix these OOM errors. This paper presents a comprehensive characteristic study on 123 real-world OOM errors in Hadoop and Spark applications. Our major findings include: (1) 12% errors are caused by the large data buffered/cached in the framework, which indicates that it is hard for users to configure the right memory quota to balance the memory usage of the framework and user code. (2) 37% errors are caused by the unexpected large runtime data, such as large data partition, hotspot key, and large key/value record. (3) Most errors (64%) are caused by memory-consuming user code, which carelessly processes unexpected large data or generates large in-memory computing results. Among them, 13% errors are also caused by the unexpected large runtime data. (4) There are three common fix patterns (used in 34% errors), namely changing the memory/dataflow-related configurations, dividing runtime data, and optimizing user code logic. Our findings inspire us to propose potential solutions to avoid the OOM errors: (1) providing dynamic memory management mechanisms to balance the memory usage of the framework and user code at runtime; (2) providing users with memory+disk data structures, since accumulating large computing results in in-memory data structures is a common cause (15% errors).

Multihop broadcasting in low-duty-cycle Wireless Sensor Networks (WSNs) is a very challenging problem, since every node has its own working schedule. Existing solutions usually use unicast instead of broadcast to forward packets from a node to its neighbors according to their working schedules, which is, however, not energy efficient. In this article, we propose to exploit the broadcast nature of wireless media to further save energy for low-duty-cycle networks, by adopting a novel broadcasting communication model. The key idea is to let some early wake-up nodes postpone their wake-up slots to overhear broadcasting messages from its neighbors. This model utilizes the spatiotemporal locality of broadcast to reduce the total energy consumption, which can be essentially characterized by the total number of broadcasting message transmissions. Based on such model, we aim at minimizing the total number of broadcasting message transmissions of a broadcast for low-duty-cycle WSNs, subject to the constraint that the broadcasting latency is optimal. We prove that it is NP-hard to find the optimal solution, and design an approximation algorithm that can achieve a polylogarithmic approximation ratio. Extensive simulation results show that our algorithm outperforms the traditional solutions in terms of energy efficiency.

In this work, we introduce a real-time driver activity recognition method which takes a sequence of depth images as input and outputs an activity class among a predetermined set of driver activities. A classification algorithm called Random Forests is employed and further enhanced by a unique state based inference system to reduce initial classifier errors. For example, frequent changes in driver activities are penalized so as to stabilize the output. The cost of activity change is decided by a state inference system which takes both temporal and spatial coherence into account. The paper will introduce the training system, explain the state inference system and the cost based penalty calculation. Finally we will discuss the results and future work.

With the capability of fast, wireless communication, combined with cloud and location-based services, modern drivers can potentially access a wide variety of information about their automobile's environment. This paper presents a system for information query by the driver by using a simple pointing mechanism, combined with visual feedback in the form of a 3-D Head-up Display (3D-HUD). Because of its 3-D properties, the HUD can also be used for Augmented Reality (AR) as it allows physical elements in the driver's field of view to be annotated with computer graphics. The combination of simple natural user input tailored for the constraints of the driver with a see-thru 3D-HUD allows drivers to query information while minimizing visual and manual distraction.

Recently, broadcast scheduling for low-duty-cycle WSNs has been extensively studied. However, most of the existing solutions mainly focus on energy efficiency optimization in terms of total energy consumption and very few of them take into account the load balance, which is an important design objective in low-duty-cycle WSNs. In this paper, we propose an energy-efficient broadcasting schedule for low-duty-cycle WSNs, which approximately minimizes the maximum workload of nodes for broadcasting while achieving low total energy consumption. By capturing the spatiotemporal characteristic of broadcasting in low-duty-cycle networks, we first model our scheduling problem as the Directed Minimum Weighted-degree Steiner Tree Problem, which is NP-hard. To solve this problem, we devise the Load-Balanced Broadcasting Schedule (LBcast) algorithm. Further, we introduce how to implement it in a distributed way. Our simulation results reveal that compared with the existing solutions considering the optimization of total energy consumption, LBcast exhibits much better load balance and also achieves low total energy consumption.

Wireless Rechargeable Sensor Networks (WRSNs) can be recharged after deployment for sustainable operations. Recent works propose to use a single mobile charger (MC) traveling through the network fields to recharge every sensor node. These algorithms work well in small scale networks. However, in large scale networks these algorithms do not work efficiently, especially when the amount of energy the MC can provide is limited. To address these challenges, multiple MCs can be used. In this paper, we investigate the minimum MCs problem (MinMCP) for rechargeable sensor networks: how to find the minimum number of energy-constrained MCs and design their recharging routes given a sensor network such that each sensor node in the WRSN maintains continuous work. Our results are three folds. We first prove that for any ϵ > 0, there is no (2-ϵ)-approximation algorithm for Distance Constrained Vehicle Routing Problem (DVRP) on a general metric space, which is the best as far as we know. By reducing from DVRP, we prove that MinMCP is NP-hard, and the inapproximability bound for MinMCP is the same as that of DVRP. Then we propose approximation algorithms for this problem. Finally, we conduct simulations to validate the effectiveness of our algorithms.

Map-Reduce is a powerful solution for processing and analyzing large-scale data. Just as Hadoop and Spark are able to deal with terabyte data and even more. Users only need to complete "map" and "reduce" function, the Map-Reduce framework can finish variety jobs. But many machine learning and data mining algorithms cannot leverage the Map-Reduce framework or it would take large efforts to modify the algorithm itself. This issue can be explained by the following ways: 1. Map-Reduce is a batch operation so that most of Map-Reduce frameworks do not built-in to support iteration. 2. Map-Reduce is absolutely parallel, each vertex cannot obtain all records, so none of them could get the global optimal model. In this paper, we proposed a job management tool to enable the Map-Reduce framework to support iteration, called "de-parallel". This make the Map-Reduce framework like Hadoop so that Map-Reduce could run more algorithms and support more various tasks. In addition, our tool does not modify the Map-Reduce framework itself. In face MR-Runner interacts with Map-Reduce framework like a "client", therefore MR-Runner could be deployed in any single PC instead of Map-Reduce cluster. We also abstract the mainly interface related to Map-Reduce frameworks, this makes our tool portable to the representative Map-Reduce frameworks.

For low-duty-cycle wireless sensor networks, multihop broadcasting is a challenging problem, since every node has its own working schedules. In this paper, we design a novel broadcasting algorithm, of which key idea is to let some early wake-up nodes postpone their wake-up slots to overhear broadcasting message from its neighbors. This design utilizes the spatiotemporal locality of broadcasting to reduce the number of transmissions. We show that to find the broadcasting schedule with minimal latency and optimized total energy consumption is NP-hard, and then design an approximation algorithm that can guarantee the optimality of broadcasting latency and achieve a polylogarithmic approximation ratio for total energy consumption. Compared with the traditional solution, extensive experimental results show that our algorithm achieves the minimal broadcasting latency while reducing energy consumption significantly.

Existing scheduling schemes for stochastic event capture with rechargeable sensors either adopt simplified assumptions on event staying time or provide no performance guarantee. Considering the stochasticity of event staying time, we investigate the sensor scheduling problem aiming to maximize the overall Quality of Monitoring (QoM) in events capture application of wireless rechargeable sensor networks. We first provide a paradigm to calculate the QoM of a point of interests (PoI) and formulate the scheduling problem into an optimization problem. Although we find that that this problem is NP-complete, we prove that the objective function of the optimization problem is monotone submodular. Therefore we can express the problem as a maximization of a submodular function subject to a matroid constraint. Accordingly we can design an approximation algorithm which achieves a factor of 1/2 of the optimum. We evaluate the performance of our solution through simulations, and simulation results show that our scheme outperforms former works.

One fundamental question in Wireless Rechargeable Sensor Networks (WRSNs) is the energy provisioning problem, i.e., how to deploy energy sources in a network to ensure that the nodes can harvest sufficient energy for continuous operation. Though the potential mobility of nodes has been exploited to reduce the number of sources necessary in energy provisioning problem in existing literature, the non-negligible impacts of the constraints of node speed and battery capacity on energy provisioning are completely overlooked, in order to simplify the analysis. In this paper, we propose a new metric - Quality of Energy Provisioning (QoEP) - to characterize the expected portion of time that a mobile node can sustain normal operation in WRSNs, which factors in the constraints of node speed and battery capacity. To avoid confining the analysis to a specific mobility model, we study spatial distribution instead. We investigate the upper and lower bounds of QoEP in one-dimensional case with one single source and multiple sources respectively. For single source case, we prove the tight lower bound and upper bound of QoEP. Extending the results to multiple sources, we obtain tight lower bound and relaxed upper bound in normal cases, together with tight upper bound for one special case. Moreover, we give the tight lower bounds in both 2D and 3D cases. Finally, we perform extensive simulations to verify our findings. Simulation results show that our bounds perfectly hold, and outperform the former works.

We present a file layout algorithm for flow fields to improve runtime I/O efficiency for out-of-core streamline computation. Because of the increasing discrepancy between the speed of processors and storage devices, the cost of I/O becomes a major bottleneck for out-of-core computation. To reduce the I/O cost, loading data with better spatial locality has proved to be effective. It is also known that sequential file access is more efficient. To facilitate efficient streamline computation, we propose to reorganize the data blocks in a file following the data access pattern so that more efficient I/O and effective prefetching can be accomplished. To achieve the goal, we divide the domain into small spatial blocks and order the blocks into a linear layout based on the underlying flow directions. The ordering is done using a weighted directed graph model which can be formulated as a linear graph arrangement problem. Our goal is to arrange the file in a way consistent with the data access pattern during streamline computation. This allows us to prefetch a contiguous segment of data at a time from disk and minimize the memory cache miss rate. We use a recursive partitioning method to approximate the optimal layout. Our experimental results show that the resulting file layout reduces I/O cost and hence enables more efficient out-of-core streamline computation.

In many applications of WSNs, the events occur infrequently but once they occur, the corresponding information needs to be sent to the sink node in a short period of time for the necessary reactions. Detection of rare events in a fast and energy-efficient manner is an important issue in WSNs. In this paper, based on the optimal solution for the Best-choice Problem with Bounded Random Observation Number, we propose an Energy-efficient Online Decision Scheme (EODS) to handle this problem. Combining with the design of nodes' duty cycle, the EODS avoids the redundant transmissions and achieves the tradeoff between delay and energy efficiency. Simulation results reveal that the EODS achieves a good balance between delay and energy efficiency.

The process of visualization can be seen as a visual communication channel where the input to the channel is the raw data, and the output is the result of a visualization algorithm. From this point of view, we can evaluate the effectiveness of visualization by measuring how much information in the original data is being communicated through the visual communication channel. In this paper, we present an information-theoretic framework for flow visualization with a special focus on streamline generation. In our framework, a vector field is modeled as a distribution of directions from which Shannon's entropy is used to measure the information content in the field. The effectiveness of the streamlines displayed in visualization can be measured by first constructing a new distribution of vectors derived from the existing streamlines, and then comparing this distribution with that of the original data set using the conditional entropy. The conditional entropy between these two distributions indicates how much information in the original data remains hidden after the selected streamlines are displayed. The quality of the visualization can be improved by progressively introducing new streamlines until the conditional entropy converges to a small value. We describe the key components of our framework with detailed analysis, and show that the framework can effectively visualize 2D and 3D flow data.

The performance of wireless sensor networks (WSNs) is tightly coupled with the geometric environment in which sensors are deployed. In a practical environment, bottleneck regions, for example bridges, may exist due to the existence of physical obstacles or energy depletion. In this paper, we propose a load-balancing based optimal routing protocol (LORP). By finding the boundaries of holes in a sensor network with bottlenecks, LORP first identifies the bridges in the sensor field using our MACB algorithm. A centralized routing algorithm, "balance-first" routing is then employed to prolong the lifetime of a WSN with bottlenecks. Theoretical analysis prove that LORP can improve the load distribution among different bridges, increase the lifetime of a WSN, and enhance the quality of network services. This conclusion is reinforced in our simulation results.