Search

Mobility data captures the locations of moving objects such as humans, animals, and cars. With the availability of GPS-equipped mobile devices and other inexpensive location-tracking technologies, mobility data is collected ubiquitously. In recent years, the use of mobility data has demonstrated significant impact in various domains including traffic management, urban planning, and health sciences. In this paper, we present the emerging domain of mobility data science. Towards a unified approach to mobility data science, we envision a pipeline having the following components: mobility data collection, cleaning, analysis, management, and privacy. For each of these components, we explain how mobility data science differs from general data science, we survey the current state of the art and describe open challenges for the research community in the coming years., Comment: Updated to reflect the major revision for ACM Transactions on Spatial Algorithms and Systems (TSAS). This version reflects the final version accepted by ACM TSAS

Consider a customer who needs to fulfill a shopping list, and also a personal shopper who is willing to buy and resell to customers the goods in their shopping lists. It is in the personal shopper's best interest to find (shopping) routes that (i) minimize the time serving a customer, in order to be able to serve more customers, and (ii) minimize the price paid for the goods, in order to maximize his/her potential profit when reselling them. Those are typically competing criteria leading to what we refer to as the Personal Shopper's Dilemma query, i.e., to determine where to buy each of the required goods while attempting to optimize both criteria at the same time. Given the query's NP-hardness we propose a heuristic approach to determine a subset of the sub-optimal routes under any linear combination of the aforementioned criteria, i.e., the query's approximate linear skyline set. In order to measure the effectiveness of our approach we also introduce two new metrics, optimality and coverage gaps w.r.t. an optimal, but computationally expensive, baseline solution. Our experiments, using realistic city-scale datasets, show that our proposed approach is two orders of magnitude faster than the baseline and yields low values for the optimality and coverage gaps., Comment: An abridged version of this paper will appear at The 28th ACM SIGSPATIAL Intl Conf. on Advances in Geographic Information Systems 2020 (ACM SIGSPATIAL 2020), Seattle, Washington, USA, November 3-6, 2020

Augmenting training datasets has been shown to improve the learning effectiveness for several computer vision tasks. A good augmentation produces an augmented dataset that adds variability while retaining the statistical properties of the original dataset. Some techniques, such as AutoAugment and Fast AutoAugment, have introduced a search phase to find a set of suitable augmentation policies for a given model and dataset. This comes at the cost of great computational overhead, adding up to several thousand GPU hours. More recently RandAugment was proposed to substantially speedup the search phase by approximating the search space by a couple of hyperparameters, but still incurring non-negligible cost for tuning those. In this paper we show that, under the assumption that the augmentation space is approximately distribution invariant, a uniform sampling over the continuous space of augmentation transformations is sufficient to train highly effective models. Based on that result we propose UniformAugment, an automated data augmentation approach that completely avoids a search phase. In addition to discussing the theoretical underpinning supporting our approach, we also use the standard datasets, as well as established models for image classification, to show that UniformAugment's effectiveness is comparable to the aforementioned methods, while still being highly efficient by virtue of not requiring any search.

One important problem in crowdsourcing is that of assigning tasks to workers. We consider a scenario where a worker is traveling on a preferred/typical path (e.g., from school to home) and there is a set of tasks available to be performed. Furthermore, we assume that: each task yields a positive reward, the worker has the skills necessary to perform all available tasks and he/she is willing to possibly deviate from his/her preferred path as long as he/she travels at most a total given distance/time. We call this problem the In-Route Task Selection (IRTS) problem and investigate it using the skyline paradigm in order to obtain the exact set of non-dominated solutions, i.e., good and diverse solutions yielding different combinations of smaller or larger rewards while traveling more or less. This is a practically relevant problem as it empowers the worker as he/she can decide, in real time, which tasks suit his/her needs and/or availability better. After showing that the IRTS problem is NP-hard, we propose an exact (but expensive) solution and a few others practical heuristic solutions. While the exact solution is suitable only for reasonably small IRTS instances, the heuristic solutions can produce solutions with good values of precision and recall for problems of realistic sizes within practical, in fact most often sub-second, query processing time., Comment: An abridged version of this manuscript has been accepted for publication as a short paper at ACM SIGSPATIAL 2018

Rankings are a fact of life. Whether or not one likes them, they exist and are influential. Within academia, and in computer science in particular, rankings not only capture our attention but also widely influence people who have a limited understanding of computing science research, including prospective students, university administrators, and policy-makers. In short, rankings matter. This position paper advocates for the adoption of "GOTO rankings": rankings that use Good data, are Open, Transparent, and Objective, and the rejection of rankings that do not meet these criteria., Comment: Accepted, to appear in Communications of the ACM

HDBSCAN*, a state-of-the-art density-based hierarchical clustering method, produces a hierarchical organization of clusters in a dataset w.r.t. a parameter mpts. While the performance of HDBSCAN* is robust w.r.t. mpts in the sense that a small change in mpts typically leads to only a small or no change in the clustering structure, choosing a "good" mpts value can be challenging: depending on the data distribution, a high or low value for mpts may be more appropriate, and certain data clusters may reveal themselves at different values of mpts. To explore results for a range of mpts values, however, one has to run HDBSCAN* for each value in the range independently, which is computationally inefficient. In this paper, we propose an efficient approach to compute all HDBSCAN* hierarchies for a range of mpts values by replacing the graph used by HDBSCAN* with a much smaller graph that is guaranteed to contain the required information. An extensive experimental evaluation shows that with our approach one can obtain over one hundred hierarchies for the computational cost equivalent to running HDBSCAN* about 2 times., Comment: A short version of this paper appears at IEEE ICDM 2017. Corrected typos. Revised abstract

In this paper we present an algorithm for optimal processing of time-dependent sequenced route queries in road networks, i.e., given a road network where the travel time over an edge is time-dependent and a given ordered list of categories of interest, we find the fastest route between an origin and destination that passes through a sequence of points of interest belonging to each of the specified categories of interest. For instance, considering a city road network at a given departure time, one can find the fastest route between one's work and his/her home, passing through a bank, a supermarket and a restaurant, in this order. The main contribution of our work is the consideration of the time dependency of the network, a realistic characteristic of urban road networks, which has not been considered previously when addressing the optimal sequenced route query. Our approach uses the A* search paradigm that is equipped with an admissible heuristic function, thus guaranteed to yield the optimal solution, along with a pruning scheme for further reducing the search space. In order to compare our proposal we extended a previously proposed solution aimed at non-time dependent sequenced route queries, enabling it to deal with the time-dependency. Our experiments using real and synthetic data sets have shown our proposed solution to be up to two orders of magnitude faster than the temporally extended previous solution., Comment: 10 pages, 12 figures To be published as a short paper in the 23rd ACM SIGSPATIAL

Directions and paths, as commonly provided by navigation systems, are usually derived considering absolute metrics, e.g., finding the shortest path within an underlying road network. With the aid of crowdsourced geospatial data we aim at obtaining paths that do not only minimize distance but also lead through more popular areas using knowledge generated by users. We extract spatial relations such as "nearby" or "next to" from travel blogs, that define closeness between pairs of points of interest (PoIs) and quantify each of these relations using a probabilistic model. Subsequently, we create a relationship graph where each node corresponds to a PoI and each edge describes the spatial connection between the respective PoIs. Using Bayesian inference we obtain a probabilistic measure of spatial closeness according to the crowd. Applying this measure to the corresponding road network, we obtain an altered cost function which does not exclusively rely on distance, and enriches an actual road networks taking crowdsourced spatial relations into account. Finally, we propose two routing algorithms on the enriched road networks. To evaluate our approach, we use Flickr photo data as a ground truth for popularity. Our experimental results -- based on real world datasets -- show that the paths computed w.r.t.\ our alternative cost function yield competitive solutions in terms of path length while also providing more "popular" paths, making routing easier and more informative for the user., Comment: Accepted as a short paper at ACM SIGSPATIAL GIS 2014

The open source development community consists of both paid and volunteer developers as well as new and experienced users. Previous work has applied social network analysis (SNA) to open source communities and has demonstrated value in expertise discovery and triaging. One problem with applying SNA directly to the data of the entire project lifetime is that the impact of local activities will be drowned out. In this paper we provide a method for aggregating, analyzing, and visualizing local (small time periods) interactions of bug reporting participants by using the SNA to measure the betweeness centrality of these participants. In particular we mined the Android bug repository by producing social networks from overlapping 30-day windows of bug reports, each sliding over by day. In this paper we define three patterns of participant behaviour based on their local centrality. We propose a method of analyzing the centrality of bug report participants both locally and globally, then we conduct a thorough case study of the bug reporter's activity within the Android bug repository. Furthermore, we validate the conclusions of our method by mining the Android version control system and inspecting the Android release history. We found that windowed SNA analysis elicited local behaviour that were invisible during global analysis.

Ecosystems monitoring is essential to properly understand their development and the effects of events, both climatological and anthropological in nature. The amount of data used in these assessments is increasing at very high rates. This is due to increasing availability of sensing systems and the development of new techniques to analyze sensor data. The Enviro-Net Project encompasses several of such sensor system deployments across five countries in the Americas. These deployments use a few different ground-based sensor systems, installed at different heights monitoring the conditions in tropical dry forests over long periods of time. This paper presents our experience in deploying and maintaining these systems, retrieving and pre-processing the data, and describes the Web portal developed to help with data management, visualization and analysis., Comment: v2: 29 pages, 5 figures, reflects changes addressing reviewers' comments v1: 38 pages, 8 figures

The typical content-based image retrieval problem is to find images within a database that are similar to a given query image. This paper presents a solution to a different problem, namely that of content based sub-image retrieval, i.e., finding images from a database that contains another image. Note that this is different from finding a region in a (segmented) image that is similar to another image region given as a query. We present a technique for CBsIR that explores relevance feedback, i.e., the user's input on intermediary results, in order to improve retrieval efficiency. Upon modeling images as a set of overlapping and recursive tiles, we use a tile re-weighting scheme that assigns penalties to each tile of the database images and updates the tile penalties for all relevant images retrieved at each iteration using both the relevant and irrelevant images identified by the user. Each tile is modeled by means of its color content using a compact but very efficient method which can, indirectly, capture some notion of texture as well, despite the fact that only color information is maintained. Performance evaluation on a largely heterogeneous dataset of over 10,000 images shows that the system can achieve a stable average recall value of 70% within the top 20 retrieved (and presented) images after only 5 iterations, with each such iteration taking about 2 seconds on an off-the-shelf desktop computer., Comment: A preliminary version of this paper appeared in the Proceedings of the 1st ACM International Workshop on Multimedia Databases, p. 63-69. 2003