Search

Road latent cost, which quantifies how desirable each road is for traveling, is important information to enable many smartcity applications such as route recommendation. Arguably, vehicle trajectories are a good source to learn these costs as drivers intelligently incorporate them into their routing decisions. However, major past approaches misinterpret drivers' behaviors and suffer from trajectory sparsity problem, mainly because they adopt an edge-centric perspective which fails to exploit the sequential information in the entire trajectories. To address these shortcomings, we model drivers' routing decision process which targets at global path optimality, and present a framework to reliably discover those costs by exploiting entire trajectories while isolating the influence of heterogeneous destinations. Extensions are also made to address several issues in practice. Extensive experiments on real world data show that the road costs learned in this way significantly outperform past approaches in several urban computing tasks and require less data for learning.

Understanding a user's social interactions in the physical world proves important in building context-aware ubiquitous applications. A good way towards that objective is to categorize people to whom a user is socially related into what we call as social circles. In this note, we propose a novel unsupervised approach that learns from the Bluetooth (BT) sensed data recording one's dynamic proximity relations with others to identify her social circles, each of which is formed along a semantically coherent aspect. For each circle we learn its members as well as the temporal dimensions along which it is formed. Our method is innovative in that it well over- comes data sparsity by information sharing, and allows for circle overlaps which is common in reality. Experiments on real data demonstrate the effectiveness of our method, and also show the potentials of relational mobile data in sensing personal behaviors beyond personal data. Copyright © 2013 ACM

During the past decade, various GPS-equipped devices have generated a tremendous amount of data with time and location information, which we refer to as big spatio-temporal data. In this paper, we present the design and implementation of CloST, a scalable big spatio-temporal data storage system to support data analytics using Hadoop. The main objective of CloST is to avoid scan the whole dataset when a spatio-temporal range is given. To this end, we propose a novel data model which has special treatments on three core attributes including an object id, a location and a time. Based on this data model, CloST hierarchically partitions data using all core attributes which enables efficient parallel processing of spatio-temporal range scans. According to the data characteristics, we devise a compact storage structure which reduces the storage size by an order of magnitude. In addition, we proposes scalable bulk loading algorithms capable of incrementally adding new data into the system. We conduct our experiments using a very large GPS log dataset and the results show that CloST has fast data loading speed, desirable scalability in query processing, as well as high data compression ratio. © 2012 ACM.

Human behavior understanding is a fundamental problem in many ubiquitous applications. It aims to automatically uncover and quantify characteristic behavior patterns in users' daily lives as well as disclose behavior clustering structure among multiple users. The key challenge is how to define a naturally interpreted representation for users' daily behavior patterns, which can be easily exploited to not only uncover the behavior similarity among multiple users but also predict users' future activities. In this paper, we define such a representation, and propose a probabilistic framework which can automatically learn it from mass amount of mobile data in unsupervised setting and exploit it to predict user activities. By an appropriate information sharing among multiple users, this framework overcomes single-user data sparsity problem and effectively identifies behavior clustering structures in a set of users. Experiments conducted on a public reality mining data set demonstrate the effectiveness and accuracy of our methods. Copyright 2012 ACM.

With the increasing availability of metropolitan transportation data, such as those from vehicle GPSs (Global Positioning Systems) and road-side sensors, it becomes viable for authorities, operators, as well as individuals to analyze the data for a better understanding of the transportation system and possibly improved utilization and planning of the system. We report our experience in building the VAST (Visual Analytics for Smart Transportation) system. Our key observation is that metropolitan transportation data are inherently visual as they are spatio-temporal around road networks. Therefore, we visualize traffic data together with digital maps and support analytical queries through this interactive visual interface. As a case study, we demonstrate VAST on real-world taxi GPS and meter data sets from 15, 000 taxis running two months in a Chinese city of over 10 million population. We discuss the technical challenges in data cleaning, storage, visualization, and query processing, and offer our first-hand lessons learned from developing the system. © 2011 Authors.

The large amount of phone call records from mobile operators in a city can inform us how many people are present in any given area and how many are entering or leaving. Each phone call record usually contains the caller and callee IDs, date and time, and the base station where the phone calls are made. As mobile phones are widely used in our daily life, many human behaviors can be revealed by analyzing mobile phone data. In this paper, we propose a comprehensive visual analysis system which can be used to analyze the population's mobility patterns from millions of phone call records. Our system consists of three major components: 1) visual analysis of user groups in a base station; 2) visual analysis of the mobility patterns on different user groups making phone calls in certain base stations; 3) visual analysis of handoff phone call records. Some well-established visualization techniques such as parallel coordinates and pixel-based representations have been integrated into our system. We also develop a novel visualization schemes, Voronoi-diagram-based visual encoding to reveal the unique features of mobile phone data. We have applied our system to real mobile phone data collected in a large city and obtained some interesting findings regarding people's mobility pattern. © 2011 ACM.

Influence maximization is an interesting and well-motivated problem in social networks study. The traditional influence maximization problem is defined as finding the most "influential" vertices without considering the vertex attribute. Though it is useful, in practice, there exist different attributes for vertices, e.g., mobile phone social networks. So, it is more important and useful to capture the vertices having the maximum influence in different search categories, which is exactly the problem that we study in this work. Thus, we name this new problem as Categorical Influence Maximization (CIM). Compare with identifying maximum influence vertices in a single category social network, CIM is much harder because we have to deal with large scale complex data. In this work, based on the observations from real mobile phone social network data, we propose a Probability Distribution based Search method (PDS) to tackle the CIM problem. Specifically, the PDS method consists of three steps. First, we propose a probability distribution based parameter free method (PD-max) to identify the maximum influential vertex set for the specified category by studying the categorical influential distribution within a time interval. Second, among these detected influential vertices, we design a probability distribution based minimizing method (PD-minmax) to find the minimum number of vertices in each category having the maximum influences. We test our solutions with real data sets, which were collected for one year in a city in China. The extensive experiment results show that our methods outperform the existing ones. Copyright 2011 ACM.

Identifying hot spots of moving vehicles in an urban area is essential to many smart city applications. The practical research on hot spots in smart city presents many unique features, such as highly mobile environments, supremely limited size of sample objects, and the non-uniform, biased samples. All these features have raised new challenges that make the traditional density-based clustering algorithms fail to capture the real clustering property of objects, making the results less meaningful. In this paper we propose a novel, non-density-based approach called mobility-based clustering. The key idea is that sample objects are employed as "sensors" to perceive the vehicle crowdedness in nearby areas using their instant mobility, rather than the "object representatives". As such the mobility of samples is naturally incorporated. Several key factors beyond the vehicle crowdedness have been identified and techniques to compensate these effects are proposed. We evaluate the performance of mobility-based clustering based on real traffic situations. Experimental results show that using 0.3 % of vehicles as the samples, mobility-based clustering can accurately identify hot spots which can hardly be obtained by the latest representative algorithm UMicro. © 2010 ACM.

Interference is a critical issue in wireless communications. In a typical multiple-user environment, different users may severely interfere with each other. Coordination among users therefore is an indispensable part for interference management in wireless networks. It is known that, coordination among multiple nodes is a costly operation taking a significant amount of valuable communication resource. In this paper, we have an interesting observation that by generating intended patterns, some simultaneous transmissions, i.e., "interference", can be successfully decoded without degrading the effective throughput in original transmission. As such, an extra and "free" coordination channel can be built. Based on this idea we propose a DC-MAC to leverage this "free" channel for efficient medium access in a multiple-user wireless network. We theoretically analyze the capacity of this channel under different environments with various modulation schemes. USRP2-based implementation experiments show that compared with the widely adopted CSMA, DC-MAC can improve the channel utilization efficiency by up to 250%.

Interference is a critical issue in wireless communications. In a typical multiple-user environment, different users may severely interfere with each other. Coordination among users therefore is an indispensable part for interference management in wireless networks. It is known that, coordination among multiple nodes is a costly operation taking a significant amount of valuable communication resource. In this paper, we have an interesting observation that by generating intended patterns, some simultaneous transmissions, i.e., "interference", can be successfully decoded without degrading the effective throughput in original transmission. As such, an extra and "free" coordination channel can be built. Based on this idea we propose a DC-MAC to leverage this "free" channel for efficient medium access in a multiple-user wireless network. We theoretically analyze the capacity of this channel under different environments with various modulation schemes. USRP2-based implementation experiments show that compared with the widely adopted CSMA, DC-MAC can improve the channel utilization efficiency by up to 250%.

Current search mechanisms of DHT-based P2P systems can well handle a single keyword search problem. Other than single keyword search, multi-keyword search is quite popular and useful in many real applications. Simply using the solution for single keyword search will require distributed intersection/union operations in wide area networks, leading to unacceptable traffic cost. As it is well known that Bloom Filter (BF) is effective in reducing traffic, we would like to use BF encoding to handle multi-keyword search. Applying BF is not difficult, but how to get optimal results is not trivial. In this study we show, through mathematical proof, that the optimal setting of BF in terms of traffic cost is determined by the global statistical information of keywords, not the minimized false positive rate as claimed by previous methods. Through extensive experiments, we demonstrate how to obtain optimal settings. We further argue that the intersection order between sets is important for multi-keyword search. Thus, we design optimal order strategies based on BF for both "and" and "or" queries. To better evaluate the performance of this design, we conduct extensive simulations on TREC WT10G test collection and the query log of a commercial search engine. Results show that our design significantly reduces the search traffic of existing approach by 73%.

Topology control has been proposed as a promising technique to achieve energy-efficiency in wireless sensor networks (WSNs). However, existing topology control algorithms assume that wireless links are static, either connected or disconnected. Taking advantage of the time-varying characteristic of wireless links, we define the energy-efficient opportunistic topology control problem, which exploits opportunistic communication to maximize energy-efficiency as well as to satisfy given network performance requirement. After proving this problem to be NP-hard, we propose a greedy solution and show its effectiveness through simulation. To the best of our knowledge, this is the first paper to apply opportunistic communication to topology control in WSNs. We demonstrate that opportunistic topology control can significantly improve energy-efficiency without sacrificing network performance. Copyright 2007 ACM.

The persistent nature of physical events makes it possible to detect events using lowly duty-cycled sensors. However, it raises a serious over-detection problem when every sensor blindly wakes up in each cycle, in particular, if sensor density is high. In this paper, we propose an innovative probabilistic wakeup protocol for energy-efficient event detection in wireless sensor networks. The central idea is to reduce the duty cycle of every sensor via probabilistic wakeup, exploiting the dense deployment of sensor networks. A distinctive feature is that the system ensures that the detection delay of any event occurring anywhere in the sensing field is statistically bounded. In addition, the algorithm exposes a convenient interface for users to define the requirement on detection latency, thereby tuning the intrinsic tradeoff between energy efficiency and event detection performance. The algorithm is a lightweight and completely localized protocol, and introduces minimal communication overhead. Extensive experiments have been conducted and results demonstrate that this algorithm significantly prolongs the system lifetime. Copyright 2007 ACM.

This paper examines some critical issues raised in the design of libraries for MPCs, such as scalability, portability, recompilation, and flexibility. we advocate a layered structure of library design, comprising a high-level language layer, a machine-independent node layer, a machine-dependent node layer, and an object code layer for different demands and requirements. We discuss the impact of various data decomposition strategies on program performance and the computation and communication analysts techniques employed at different layers. We also propose the concept of the range of scalability as a metric for selecting the most appropriate implementation. A linear system solver based on the Gaussian elimination method is used as an example to illustrate various design alternatives.

A new style of efficient parallel algorithms on distributed-memory multiprocessors is introduced, which exploits parallelism through pipelined parallel computation, or large-grain pipelining. By using macro-pipelining between nodes in the system, large-grain pipelining regulates the flows of data in the multiprocessor so that the degree of overlapping can be maximized and the effect of communication overhead can be minimized. To model pipelined parallel computations, an analytic model is presented, which takes into account both underlying architecture and algorithm behavior. The resultant model is accurate enough to not only predict the performance of a given algorithm, but also assist in algorithm designs for determining optimal design parameters such as the granularity. Results from experiments performed on a 64-node NCUBE multiprocessor match closely to the predicted performance. A systematic procedure for designing pipelined data parallel algorithms from nested loop programs is described. The impact of the second generation distributed-memory multiprocessors on the pipelined parallel computations is also discussed. © 1988 ACM.

Three parallel algorithms, namely the parallel partition LU (PPT) algorithm, the parallel partition hybrid (PPH) algorithm, and the parallel diagonal dominant (PDD) algorithm are proposed for solving tridiagonal linear systems on multicomput-ers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and non-pivoting. The PPT algorithm is good when the number of processors is small; otherwise, the PPH algorithm is better. When the system is diagonal dominant, the PDD algorithm is highly parallel and provides an approximate solution which equals to the exact solution within machine accuracy. Both computation and communication complexities of the three algorithms are presented. All three methods proposed in this paper outperform other known parallel algorithms and have been implemented on a 64-node Ncube multicomputer. The analytic results matches closely with the results measured from the Ncube machine. © 1989 ACM.