As people increasingly rely on road maps in the digital age, manually maintained maps cannot keep up with the demand for accuracy and freshness, evidenced by the recent iOS map incident and the bidding war for Waze. There are many research works on automatic map inference using GPS data, and some have suggested that Google and Waze automate their map update processes to some degree with user data. However, existing published work focuses on refining road geometry. In reality, connectivity issues at intersections, including missing connections and unmarked turn restrictions, are much more prevalent and also more difficult to infer. In this paper, we report our study on the connectivity issues in the OSM Shanghai map using 21 months of GPS data from over |$10\,000$| taxis. We first adapt a robust map matching algorithm. Then, we propose simple algorithms for detecting missing intersections, turn restrictions and road closures. Empirical results show that our algorithms of connectivity refinement for road maps are effective.

This paper describes a map generalization program we submitted to the ACM SIGSPATIAL Cup 2014. In this competition, the goal is to remove as many points in a set of polygonal lines as quickly as possible with respect to two constraints. The topological relationships among the lines must not change, and the relationships between a set of control points and the lines must not change. Inspired by Visvalingam-Whyatt Algorithm, we iteratively examine successive triplets along each line, and remove the middle point if no control point or point of other lines is in the associated triangle. Based on the features of the training datasets, we further introduce many optimization techniques to speed up the computation.

In the multicore era, developers face increasing pressure to parallelize their programs. However, building correct and efficient concurrent programs is substantially more difficult than building sequential ones. To address the multicore challenge, numerous tools have been developed to assist multithreaded programmers, including static and dynamic bug detectors, automated bug fixers, and optimization tools. Many of these tools rely on or benefit from the precise identification of critical sections, i.e., sections where the thread of execution holds at least one lock. For languages where critical sections are not lexically scoped, e.g., C/C++, static analysis often fails to pair up lock and unlock calls correctly. In this paper, we propose a practical lock/unlock pairing mechanism that combines static analysis with dynamic instrumentation to identify critical sections in POSIX multithreaded C/C++ programs. Our method first applies a con-servative inter-procedural path-sensitive dataflow analysis to pair up all lock and unlock calls. When the static analysis fails, our method makes assumptions about the pairing using common heuristics. These assumptions are checked at runtime using lightweight instrumentation. Our experiments show that only one out of 891 lock/unlock pairs violates our assumptions at runtime and the instrumentation imposes negligible overhead of 3.34% at most, for large open-source server programs. Overall, our mechanism can pair up 98.2% of all locks including 7.1 % of them paired speculatively.

As people increasingly rely on road maps in the digital age, manually maintained maps cannot keep up with the demand for accuracy and freshness, evidenced by the recent iOS map incident and the bidding war for Waze. There are many research works on automatic map inference using GPS data, and some have suggested that Google and Waze automate their map update processes to some degree with user data. However, existing published work focuses on refining road geometry. In reality, connectivity issues at intersections, including missing connections and unmarked turn restrictions, are much more prevalent and also more difficult to infer. In this paper, we report on our study on the connectivity issues in the OSM Shanghai map using 21 months of GPS data from over 10, 000 taxis. We first adapt a robust map matching algorithm to detect missing intersections, and then train a time-series detection model for every turn possibility of every intersection using supervised learning.

The process of map matching takes a sequence of possibly noisy GPS coordinates from a vehicle trace and estimates the actual road positions---a crucial first step needed by many GPS applications. There has been a plethora of methods for map matching published, but most of them are evaluated on low-noise datasets obtained from a planned route. And comparisons with other methods are very limited. Based on our previous unifying framework used to catalog different mathematical formulas in many published methods, we evaluate representative algorithms using the low-noise dataset from the GIS Cup 2012 and a high-noise dataset collected from Shanghai downtown. Our experiments reveal that global max-weight and global geometrical map matching methods are the most accurate, but each has its weaknesses. We therefore propose a new map matching algorithm that integrates Fréchet distance with global weight optimization, which is more accurate across all sampling intervals.

This paper describes a point-polygon query program we submitted to the ACM SIGSPATIAL Cup 2013. Point-polygon topological relationship query is one of the core functions for commercial spatial databases, and also an active research topic in academia. Spatial indices are the key to achieve top performance. However, different datasets or query patterns require different indices for optimal performance. Based on the patterns of the training dataset, we build a hierarchy of indices, including polygon index, edge index, and interval index, which help find polygons near a point, calculate the distance from a point to a polygon, and determine whether a point is inside a polygon, respectively. Using the provided training dataset, these three indices reduce the computation time of "WITHIN n" query by 90%, 10%, and 50%, respectively. We build a large dataset with more than 1 million samples and 520 polygons by cloning and offsetting the training dataset 15 and 13 times, respectively. Our program finishes the "WITHIN 1000" query in only one second on a 4-core 3.3GHz Xeon Processor.

Nowadays concurrent programs are becoming more and more important with the development of hardware and network technologies. However, it is not easy for programmers to write reliable concurrent programs. Concurrency characteristics such as thread-interleaving make it difficult to debug or maintain concurrent programs. Although there are lots of research work on concurrency such as multi-thread testing tools, concurrent program verification and data race detection, all of them leave open problems. For instance, some are not scalable enough for large real world applications and some may report false warnings. Since locks are widely used to protect shared memory, it is beneficial for both programmers and tool designers in all fields to have a good understanding of common lock usage patterns in real world concurrent programs. This paper reports an empirical study on lock usage in concurrent programs. It is based on our automatic lock analysis tool called LUPA. The study analyzes how lock is used in concurrent programs and how lock usage changes throughout the product environment. In this study, four representative concurrent programs (Apache httpd, Mysql, Aget, Pbzip2) are selected, of which both lock manifestation and lock usage pattern in different versions are studied. This study reveals some interesting findings including but not limited to: (1) about 80.5% of the lock related functions acquire only one lock, (2) simple lock patterns account for 54.5% of all lock usage in real world applications, (3) only 12 out of 527 detected patterns belong to condition lock pattern which may lead to vulnerabilities easily, (4) only 0.65% of the functions are lock related. Additionally, a potential bug caused by problematic locking pattern is found.

The inaccuracy of manually created digital road maps is a persistent problem, despite their high economic value. We present CrowdAtlas, which automates map update based on people's travels, either individually or crowdsourced. Its mobile navigation app detects significant portions of GPS traces that do not conform to the existing map, as determined by state-of-the-art Viterbi map matching. When there is sufficient evidence collected, map inference algorithms can automatically update the map. The CrowdAtlas server aggregates exceptional traces from users with the navigation app as well as from other, large-scale data sources. From these it automatically generates high quality map updates, which can be propagated to its navigation app and other interested applications. Using CrowdAtlas app, we mapped out a 4.5 km^2 street block in Shanghai in less than half an hour and built a walking/cycling map of the SJTU campus. Using taxi traces collected from Beijing, we contributed completely computer-generated roads for this large, 61 km of missing roads to OpenStreetMap, the first set of open-source map community.

Digital road maps have become essential to many aspects of our lives. Unfortunately, they have persistent quality issues, both in developing countries as well as in developed countries, evidenced by the recent Apple-Google map war. A survey of British drivers showed 26% have been directed by their GPS to go into no-entry areas, and the news periodically reports car accidents caused by or related to digital maps. In addition to correcting existing errors, maps need to be frequently updated to reflect the latest constructions, closures, and reconfigurations. TomTom estimates that roads change by as much as 15% each year. There are also growing demands for other types of maps, including off-road driving, cycling, hiking, and skiing maps. There are services for people to share GPS traces, but none creates navigable maps.

This paper describes a map matching program submitted to the ACM SIGSPATIAL Cup 2012. We first summarize existing map matching algorithms into three categories, and compare their performance thoroughly. In general, global max-weight methods using the Viterbi dynamic programming algorithm are the most accurate but the accuracy varies at different sampling intervals using different weight functions. Our submission selects a hybrid that improves upon the best two weight functions such that its accuracy is better than both and the performance is robust against varying sampling rates. In addition, we employ many optimization techniques to reduce the overall latency, as the scoring heavily emphasizes on speed. Using the training dataset with manually corrected ground truth, our Java-based program matched all 14,436 samples in 5 seconds on a dual-core 3.3 GHz iCore 3 processor, and achieved 98.9% accuracy.

We address the problem of inferring road maps from large-scale GPS traces that have relatively low resolution and sampling frequency. Unlike past published work that requires high-resolution traces with dense sampling, we focus on situations with coarse granularity data, such as that obtained from thousands of taxis in Shanghai, which transmit their location as seldom as once per minute. Such data sources can be made available inexpensively as byproducts of existing processes, rather than having to drive every road with high-quality GPS instrumentation just for map building - and having to re-drive roads for periodic updates. Although the challenges in using opportunistic probe data are significant, successful mining algorithms could potentially enable the creation of continuously updated maps at very low cost.

Service composition has received significant attention in the research community, and the focus has been on service semantics and composition algorithms. Surprisingly, the problem of representation of the composition outcome has been largely ignored. Ad-hoc workflows are often employed, which typically sacrifice alternative paths and parallelism for the sake of simple representation. In this paper, we show how theory of regions, which was originally developed to derive Petri nets from finite state automata, can be applied to find the optimal representation of composition. To apply the theory, we first propose an automaton-based composition framework that incorporates most existing composition techniques without changing the service semantics or its description language. Then based on the special requirements of the composition representation, we develop our own Petri net synthesis algorithm that combines the benefits of two well known algorithms from the theory of regions. We demonstrate that AND/OR workflow nets can limit the concurrency even for simple input/output based service composition, while our Petri net representation is optimal in terms of flexibility and parallelism. Our experimental evaluations include a case study on composing Google Checkout Service, and the study on Oracle BPEL samples, for which our algorithm obtains better concurrent representations for almost all non-trivial cases.

Deadlock in multithreaded programs is an increasingly important problem as ubiquitous multicore architectures force parallelization upon an ever wider range of software. This paper presents a theoretical foundation for dynamic deadlock avoidance in concurrent programs that employ conventional mutual exclusion and synchronization primitives (e.g., multithreaded C/Pthreads programs). Beginning with control flow graphs extracted from program source code, we construct a formal model of the program and then apply Discrete Control Theory to automatically synthesize deadlock-avoidance control logic that is implemented by program instrumentation. At run time, the control logic avoids deadlocks by postponing lock acquisitions. Discrete Control Theory guarantees that the program instrumented with our synthesized control logic cannot deadlock. Our method furthermore guarantees that the control logic is maximally permissive: it postpones lock acquisitions only when necessary to prevent deadlocks, and therefore permits maximal runtime concurrency. Our prototype for C/Pthreads scales to real software including Apache, OpenLDAP, and two kinds of benchmarks, automatically avoiding both injected and naturally occurring deadlocks while imposing modest runtime overheads.

As information technology (IT) administration becomes increasingly complex, workflow technologies are gaining popularity for IT automation. Writing correct workflow programs is notoriously difficult. Although static analysis tools are available, fixing defects remains manual and error-prone. This paper applies discrete control theory to IT automation workflows. Discrete control detects flaws in workflows just as static analysis does, and more importantly it also allows safe execution of flawed workflows by dynamically avoiding run-time failures. Our approach can guarantee compliance with certain requirements and can partially decouple requirements from software, reducing the need to modify the latter if the former change. We have implemented a discrete control module for a real IT automation system. Experiments with workflows from a real production system and with randomly generated workflows show that our approach scales to workflows of practical size.