Road intersections represent one of the most complex configurations encountered when traversing road networks. It is therefore of vital importance to improve their operational performance, as that can significantly contribute towards the efficiency of the whole transport network. Traditional approaches to improve the efficiency of intersections are based on analysis of static data or expert opinions. However, due to the advancements on Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communication technologies, it is possible to enhance safety and improve road intersection efficiency by continuously monitoring traffic conditions and enabling situational awareness of vehicle drivers. Towards this end, we design, develop and evaluate a system for evaluating and forecasting the operational performance of road intersections by mining streams of V2I data. Our system makes use of graph mining and trajectory data mining methods to continuously evaluate a set of well-defined measures of effectiveness (MOEs) for traffic operations at different levels of road network abstraction. In addition, the system enables interactive analysis and exploration of the various MOEs. The system architecture and methods are general and can be used in various settings requiring continuous monitoring and/or forecasting of the road network state.

The relationship between human mobility and the spread of an infectious disease has been well documented. At the same time, availability of mobility data is growing due to advancements in digital contact tracing mobile applications and GPS-enabled devices. Motivated by these observations, we have designed and developed STRIPE (Safe Trips during Epidemics), a mobility-based recommendation system that can provide safer trip recommendations to individuals. The recommendation model considers the risk of infection of alternative trips between an origin and destination. It also considers the risk of infection of specific points of interests (POIs) that occur at the microscale. In this paper, we present a high-level architecture of the system, its main features and system use cases. The broader impact of our research is that by helping individuals making informed decisions, we promote more responsible behaviors in the community as a whole that could effectively alleviate the impact of the epidemic.

Several data mining and machine learning problems can be reduced to the computational geometry problem of finding intersections of a set of geometric objects, such as intersections of line segments or rectangles/boxes. Currently, the state-of-the-art approach for addressing such intersection problems in Euclidean space is collectively known as the sweep-line or plane sweep algorithm, and has been utilized in a variety of application domains, including databases, gaming and transportation, to name a few. The idea behind sweep line is to employ a conceptual line that is swept or moved across the plane, stopping at intersection points. However, to report all K intersections among any N objects, the standard sweep line algorithm (based on the Bentley-Ottmann algorithm) has a time complexity of O((N + K)logN), therefore cannot scale to very large number of objects and cases where there are many intersections. In this paper, we propose MRSWEEP and MRSWEEP-D, two sophisticated and highly scalable algorithms for the parallelization of sweep-line and its variants. We provide algorithmic details of fully distributed in-memory versions of the proposed algorithms using the MapReduce programming paradigm in the Apache Spark cluster environment. A theoretical analysis of the proposed algorithms is presented, as well as a thorough experimental evaluation that provides evidence of the algorithms' scalability in varying levels of problem complexity. We make source code and datasets available to support the reproducibility of the results.

Identifying and quantifying the size of multiple intersections among a large number of axis-aligned geometric objects is an essential computational geometry problem. The ability to solve this problem can effectively inform a number of spatial data mining methods and can provide support in decision making for a variety of applications. Currently, the state-of-the-art approach for addressing such intersection problems resorts to an algorithmic paradigm, collectively known as the sweep-line algorithm. However, its application on specific instances of the problem inherits a number of limitations. With that mind, we design and implement a novel, exact, fast and scalable yet versatile, sweep-line based algorithm, named SLIG. Our algorithm can be employed in a number of problems and applications involving the efficient computation of numerous axis-aligned object intersection problems in multiple dimensions. The key idea of our algorithm lies in constructing an auxiliary data structure when the sweep line algorithm is applied, an intersection graph. This graph can effectively be used to provide connectivity properties among overlapping objects, as well as to inform the much harder problem of finding the location and size of the common area defined by multiple overlapping objects. A thorough experimental evaluation on synthetic data of various characteristics and sizes, demonstrates that SLIG performs significantly faster than classic sweep-line based algorithms. SLIG is not only faster and more versatile, but also provides a suite of powerful querying capabilities. To support the reproducibility of our methods, we make source code and datasets available.

Mining large-scale trajectory data streams (of moving objects) has attracted significant attention due to an abundance of modern tracking devices and a number of real-world applications. In this paper, we are interested in evaluating the relative importance of such objects through monitoring their interactions with other objects, over time. Which object has encountered more other objects? When did these encounters happen and how long did they last? To address this type of questions, we consider a trajectory network that is defined based on the proximity of moving objects over time. Given this network, we are able to evaluate the importance of an object (node) by monitoring its complex network connections to other nodes over time. Traditional approaches to address the problem rely on either evaluating network metrics over a number of static network snapshots or expensive trajectory similarity and clustering methods that require further post-processing. Streaming algorithms also exist, but they focus on simple network metrics. In contrast to these approaches, we devise a method that is able to simultaneously evaluate node importance metrics for all moving objects in the trajectory network. Our proposed method is based on, first, efficiently computing and representing the interactions of moving objects as time intervals. Then, a fast and accurate one-pass sweep-line algorithm over the trajectories (SLOT) is devised that can effectively compute the metrics of interest, all at once. Through experiments on various types of data, we demonstrate that our algorithm is a multitude of times faster than sensible baselines, for a varying range of conditions.