Mobile devices collect a large amount of visual data that are useful for many applications. Searching for an object of interest over a network of mobile devices can aid human analysts in a variety of situations. However, processing the information on these devices is a challenge owing to the high computational complexity of the state-of-the-art computer vision algorithms that primarily rely on Convolutional Neural Networks (CNNs). Thus, this paper builds PicSys, a system that enables answering visual search queries on a mobile network. The objective of the system is to minimize the maximum completion time over all devices while taking into account the energy consumption of mobile devices as well. First, PicSys carefully divides the computation into multiple filtering stages, such that only a small percentage of images need to run the entire CNN pipeline. Splitting such CNN computation into multiple stages requires understanding the intermediate CNN features and systematically trading off accuracy for the computation speed. Second, PicSys determines where to run each of the stages of the multi-stage pipeline to fully utilize the available resources. Finally, through extensive experimentation, system implementation, and simulation, we show that PicSys performance is close to optimal and significantly outperforms other standard algorithms.

Convolutional Neural Networks (ConvNets/CNNs) have revolutionized the research in computer vision, due to their ability to capture complex patterns, resulting in high inference accuracies. However, the increasingly complex nature of these neural networks means that they are particularly suited for server computers with powerful GPUs. We envision that deep learning applications will be eventually widely deployed on mobile devices, e.g., smartphones, self-driving cars, and drones. Therefore, in this paper, we aim to understand the resource requirements of CNNs on mobile devices in terms of compute time, memory, and power. First, by deploying several popular CNNs on different mobile CPUs and GPUs, we measure and analyze the performance and resource usage for the CNNs on a layerwise granularity. Our findings point out the potential ways of optimizing the CNN pipelines on mobile devices. Second, we model resource requirements of core computations of CNNs. Finally, based on the measurement and modeling, we build and evaluate our modeling tool, Augur, which takes a CNN configuration (descriptor) as the input and estimates the compute time, memory, and power requirements of the CNN, to give insights about whether and how efficiently a CNN can be run on a given mobile platform.

While observing complex events with multiple actors, humans do not assess each actor separately, but infer from the context. The surrounding context provides essential information for understanding actions. To this end, we propose to replace region of interest(RoI) pooling with an attention module, which ranks each spatio-temporal region's relevance to a detected actor instead of cropping. We refer to these as Actor-Conditioned Attention Maps (ACAM), which amplify/dampen the features extracted from the entire scene. The resulting actor-conditioned features focus the model on regions that are relevant to the conditioned actor. For actor localization, we leverage pre-trained object detectors, which transfer better. The proposed model is efficient and our action detection pipeline achieves near real-time performance. Experimental results on AVA 2.1 and JHMDB demonstrate the effectiveness of attention maps, with improvements of 7 mAP on AVA and 4 mAP on JHMDB.

Effectively representing graph node sequences in the form of vector embeddings is critical to many applications. We achieve this by (i) first learning vector embeddings of single graph nodes and (ii) then composing them to compactly represent node sequences. Specifically, we propose SENSE-S (Semantically Enhanced Node Sequence Embedding - for Single nodes), a skip-gram based novel embedding mechanism, for single graph nodes that co-learns graph structure as well as their textual descriptions. We demonstrate that SENSE-S vectors increase the accuracy of multi-label classification tasks by up to 50% and link-prediction tasks by up to 78% under a variety of scenarios using real datasets. Based on SENSE-S, we next propose generic SENSE to compute composite vectors that represent a sequence of nodes, where preserving the node order is important. We prove that this approach is efficient in embedding node sequences, and our experiments on real data confirm its high accuracy.

Deep neural networks (DNNs) are emerging as important drivers for GPU (Graphical Processing Unit) usage. Routinely, now, cloud offerings include GPU-capable VMs, and GPUs are used for training and testing DNNs. A popular way to run inference (or testing) tasks with DNNs is to use middleware called a serving system. Tensorflow-Serving (TF-Serving) is an example of a DNN serving system. In this paper, we consider the problem of carefully scheduling multiple concurrent DNNs in a serving system on a single GPU to achieve fairness or service differentiation objectives, a capability crucial to cloud-based TF-Serving offerings. In scheduling DNNs, we face two challenges: how to schedule, and switch between, different DNN jobs at low overhead; and, how to account for their usage. Our system, Olympian, extends TF-Serving to enable fair sharing of a GPU across multiple concurrent large DNNs at low overhead, a capability TF-Serving by itself is not able to achieve. Specifically, Olympian can run concurrent instances of several large DNN models such as Inception, ResNet, GoogLeNet, AlexNet and VGG, provide each with an equal share of the GPU, while interleaving them at timescales of 1-2 ms, and incurring an overhead of less than 2%. It achieves this by leveraging the predictability of GPU computations to profile GPU resource usage models offline, then using these to achieve low overhead switching between DNNs.

Convolutional Neural Networks (CNNs) have revolutionized the research in computer vision, due to their ability to capture complex patterns, resulting in high inference accuracies. However, the increasingly complex nature of these neural networks means that they are particularly suited for server computers with powerful GPUs. We envision that deep learning applications will be eventually and widely deployed on mobile devices, e.g., smartphones, self-driving cars, and drones. Therefore, in this paper, we aim to understand the resource requirements (time, memory) of CNNs on mobile devices. First, by deploying several popular CNNs on mobile CPUs and GPUs, we measure and analyze the performance and resource usage for every layer of the CNNs. Our findings point out the potential ways of optimizing the performance on mobile devices. Second, we model the resource requirements of the different CNN computations. Finally, based on the measurement, profiling, and modeling, we build and evaluate our modeling tool, Augur, which takes a CNN configuration (descriptor) as the input and estimates the compute time and resource usage of the CNN, to give insights about whether and how efficiently a CNN can be run on a given mobile platform. In doing so Augur tackles several challenges: (i) how to overcome profiling and measurement overhead; (ii) how to capture the variance in different mobile platforms with different processors, memory, and cache sizes; and (iii) how to account for the variance in the number, type and size of layers of the different CNN configurations.

When modeling geo-spatial data, it is critical to capture spatial correlations for achieving high accuracy. Spatial Auto-Regression (SAR) is a common tool used to model such data, where the spatial contiguity matrix (W) encodes thespatial correlations. However, the efficacy of SAR is limited by two factors. First, it depends on the choice of contiguity matrix, which is typically not learnt from data, but instead, is assumed to be known apriori. Second, it assumes that the observations can be explained by linear models. In this paper, we propose a Convolutional Neural Network (CNN) framework to model geo-spatial data (specifically housing prices), to learn the spatial correlations automatically. We show that neighborhood information embedded in satellite imagery can be leveraged to achieve the desired spatial smoothing. An additional upside of our framework is the relaxation of linear assumption on the data. Specific challenges we tackle while implementing our framework include, (i) how much of the neighborhood is relevant while estimating housing prices? (ii) what is the right approach to capture multiple resolutions of satellite imagery? and (iii) what other data-sources can help improve the estimation of spatial correlations? We demonstrate a marked improvement of 57% on top of the SAR baseline through the use of features from deep neural networks for the cities of London, Birmingham and Liverpool.

Always-on localization is an important problem for a lot of context sensitive mobile computing applications. This paper proposes WaveLoc, which effectively uses measurements from a trajectory as its fingerprint for localization. Different from traditional approaches, which use signatures from single-points for localization, we leverage signatures from a trajectory, since it offers a lot more information. However, it is much more challenging to match measurements across trajectories than from single points. To tackle this challenge, WaveLoc divides the problem into the following two steps: (i) identify a user's current trajectory by matching its measurements with those in the training traces (trajectory matching) and (ii) localize the user on the trajectory (localization). The core requirement of both steps is an accurate and robust algorithm to match two time-series that may contain significant noise and perturbation due to differences in speed, mobility, devices, and environment. WaveLoc addresses these by performing multi-level wavelet analysis of the measurements and applying an enhanced Dynamic Time Warping (DTW) alignment to the wavelet coefficients. Using both indoor and outdoor experiments, we demonstrate that WaveLoc is accurate and power efficient.

Wireless spectrum is a precious resource and must be allocated and used efficiently. Conventional spectrum allocations let a government agency (e.g., FCC) sell a portion of spectrum to one provider. This is not only restrictive, but also limits spectrum reuse and may lead to significant under-utilization of spectrum. In this paper, we develop a novel truthful double-auction scheme to let any resource owner (e.g., a cellular provider), who has spare spectrum at a given time period, sell to one or more providers that need additional spectrum at that time. Spectrum auctions are fundamentally different from conventional auction problems since spectrum can be reused and competition among buyers is complex due to wireless interference. Our proposal is the first double-auction design for spectrum allocation that explicitly decouples the buyer-side and seller-side auction design while achieving: 1) truthfulness; 2) individual rationality; and 3) budget-balance. To accurately capture wireless interference and support spectrum reuse, we partition the conflict graph so that buyers with strong direct and indirect interference are put into the same subgraph, and buyers with no interference or weak interference are put into separate subgraphs. Then, we compute pricing independently within each subgraph. We then develop a scheme to combine spectrum allocation results from different subgraphs and resolve potential conflicts. We further extend our approach to support local sellers whose spectrum can only be sold to buyers within certain regions, instead of all buyers. Using conflict graphs generated from real cell tower locations, we extensively evaluate our approach and demonstrate that it achieves high efficiency, revenue, and utilization.

Wireless spectrum is a precious resource and must be allocated and used efficiently. The conventional spectrum allocation lets a government (e.g., FCC) sell a given portion of spectrum to one provider. This is not only restrictive, but also limits spectrum reuse and may lead to significant under-utilization of spectrum. In this paper, we develop a novel truthful double auction scheme to let any resource owner (e.g., a cellular provider), who has spare spectrum at a given time, sell to one or more providers that need additional spectrum at that time. Spectrum auction is fundamentally different from conventional auction problems since spectrum can be re-used and competition pattern is complex due to wireless interference. We propose the first double auction design for spectrum allocation that explicitly decouples the buyer side and seller side auction design while achieving (i) truthfulness, (ii) individual rationality, and (iii) budget balance. To accurately capture wireless interference and support spectrum reuse, we partition the conflict graph so that buyers with strong direct and indirect interference are put into the same subgraph and buyers with no or weak interference are put into separate subgraphs and then compute pricing independently within each subgraph. We develop a merge scheme to combine spectrum allocation results from different subgraphs and resolve potential conflicts. Using conflict graphs generated from real cell tower locations, we extensively evaluate our approach and demonstrate that it achieves high efficiency, revenue, and utilization.

No abstract available.

We consider the problem of tracking physical browsing by users in indoor spaces such as retail stores. Analogous to online browsing, where users choose to go to certain webpages, dwell on a subset of pages of interest to them, and click on links of interest while ignoring others, we can draw parallels in the physical setting, where a user might walk purposefully to a section of interest, dwell there for a while, gaze at specific items, and reach out for the ones that they wish to examine more closely.

We develop a novel trajectory-based localization scheme which (i) identifies a user's current trajectory based on the measurements collected while the user is moving, by finding the best match among the training traces (trajectory matching) and then (ii) localizes the user on the trajectory (localization). The core requirement of both the steps is an accurate and robust algorithm to match two time-series that may contain significant noise and perturbation due to differences in mobility, devices, and environments. To achieve this, we develop an enhanced Dynamic Time Warping (DTW) alignment, and apply it to RSS, channel state information, or magnetic field measurements collected from a trajectory. We use indoor and outdoor experiments to demonstrate its effectiveness.

The explosive growth of cellular traffic and its highly dynamic nature often make it increasingly expensive for a cellular service provider to provision enough cellular resources to support the peak traffic demands. In this paper, we propose iDEAL, a novel auction-based incentive framework that allows a cellular service provider to leverage resources from third-party resource owners on demand by buying capacity whenever needed through reverse auctions. iDEAL has several distinctive features: 1) iDEAL explicitly accounts for the diverse spatial coverage of different resources and can effectively foster competition among third-party resource owners in different regions, resulting in significant savings to the cellular service provider. 2) iDEAL provides revenue incentives for third-party resource owners to participate in the reverse auction and be truthful in the bidding process. 3) iDEAL is provably efficient. 4) iDEAL effectively guards against collusion. 5) iDEAL effectively copes with the dynamic nature of traffic demands. In addition, iDEAL has useful extensions that address important practical issues. Extensive evaluation based on real traces from a large US cellular service provider clearly demonstrates the effectiveness of our approach. We further demonstrate the feasibility of iDEAL using a prototype implementation.

The explosive growth of cellular traffic and its highly dynamic nature often make it increasingly expensive for a cellular service provider to provision enough cellular resources to support the peak traffic demands. In this paper, we propose iDEAL, a novel auction-based incentive framework that allows a cellular service provider to leverage resources from third-party resource owners on demand by buying capacity whenever needed through reverse auctions. iDEAL has several distinctive features: (i) iDEAL explicitly accounts for the diverse spatial coverage of different resources and can effectively foster competition among third-party resource owners in different regions, resulting in significant savings to the cellular service provider. (ii) iDEAL provides revenue incentives for third-party resource owners to participate in the reverse auction and be truthful in the bidding process. (iii) iDEAL is provably efficient. (iv) iDEAL effectively guards against collusion. (v) iDEAL effectively copes with the dynamic nature of traffic demands. In addition, iDEAL has useful extensions that address important practical issues. Extensive evaluation based on real traces from a large US cellular service provider clearly demonstrates the effectiveness of our approach. We further demonstrate the feasibility of iDEAL using a prototype implementation.

Users around the world have embraced new generation of mobile devices such as the smartphones at a remarkable rate. These devices are equipped with powerful communication and computation capabilities and they enable a wide range of exciting location-based services, e.g., location based ads, content prefetching etc. Many of these services can benefit from a better understanding of the smartphone user mobility, which may differ significantly from the general user mobility. Hence, previous works on understanding user mobility models and predicting user mobility may not directly apply to smartphone users. To overcome this, in this paper we analyze data from two popular location based social networks, where the users are real smartphone users and the places they check-in represent the typical locations where they use their smartphone applications. Specifically, we analyze how individual users move across different locations. We identify several factors that affect user mobility and their relative significance. We then leverage these factors to perform individual mobility prediction. We further show that our mobility prediction yields significant benefit to two important location based applications: content prefetching and shared ride recommendation.

Rate adaptation in WiFi networks has received significant attention recently. However, most existing work focuses on selecting the rate to maximize throughput. How to select a data rate to minimize energy consumption is an important yet under-explored topic. This problem is becoming increasingly important with the rapidly increasing popularity of MIMO deployment, because MIMO offers diverse rate choices (e.g., the number of antennas, the number of streams, modulation, and FEC coding) and selecting the appropriate rate has significant impact on power consumption.

This paper proposes VideoFountain, a novel service that deploys kiosks at popular venues to store and transmit digital media to users' personal devices using Wi-Fi access points, which may not have Internet connectivity. We leverage mobile users to deliver content to these kiosks. A key component in this design is an in-depth understanding of user mobility. We gather real mobility traces from two largest location-based social networks (Foursquare and Gowalla) and analyze both macroscopic and microscopic human mobility in different cities. Based on the insights we gain, we study several algorithms to determine the initial placement of content and design routing algorithms to optimize the content delivery. We further consider several practical issues, such as how to incentivize users to forward content, how to manage copyrights, how to ensure security, and how to achieve service discovery. We demonstrate the feasibility of VideoFountain using trace-driven simulations.

Wireless multicarrier communication systems transmit data by spreading it over multiple subcarriers and are widely used today owing to their robustness to multipath fading, high spectrum efficiency, and ease of implementation. In this paper, we use real measurements to show there is significant frequency diversity in Wi-Fi channels, and propose a series of techniques to explicitly harness such frequency diversity. In particular, we leverage the Channel State Information (CSI), which captures the SNR on each subcarrier to (i) map symbols to subcarriers according to their importance, (ii) effectively recover partially corrupted FEC groups and facilitate FEC decoding, and (iii) develop MAC-layer FEC to offer different degrees of protection to the symbols according to their error rates at the PHY layer. We further develop a rate adaptation approach that works together with these optimization schemes. Our trace-driven simulation and testbed experiments based on USRP clearly demonstrate the effectiveness of our approaches.

Localization is a fundamental operation for many wireless networks. While GPS is widely used for location determination, it is unavailable in many environments either due to its high cost or the lack of line of sight to the satellites (e.g., indoors, under the ground, or in a downtown canyon). The limitations of GPS have motivated researchers to develop many localization schemes to infer locations based on measured wireless signals. However, most of these existing schemes focus on localization in static wireless networks. As many wireless networks are mobile (e.g., mobile sensor networks, disaster recovery networks, and vehicular networks), we focus on localization in mobile networks in this paper. We analyze real mobility traces and find that they exhibit temporal stability and low-rank structure. Motivated by this observation, we develop three novel localization schemes to accurately determine locations in mobile networks: (i) Low Rank based Localization (LRL), which exploits the low-rank structure in mobility, (ii) Temporal Stability based Localization (TSL), which leverages the temporal stability, and (iii) Temporal Stability and Low Rank based Localization (TSLRL), which incorporates both the temporal stability and the low-rank structure. These localization schemes are general and can leverage either mere connectivity (i.e., range-free localization) or distance estimation between neighbors (i.e., range-based localization). Using extensive simulations and testbed experiments, we show that our new schemes significantly outperform state-of-the-art localization schemes under a wide range of scenarios and are robust to measurement errors.