Federated learning (FL) is a machine learning paradigm where multiple clients train their local machine learning models collaboratively (without sharing private data). One of the main challenges in FL is statistical heterogeneity of the data distributions across clients. Personalized FL (PFL) mitigates statistical heterogeneity by collaborative model training across homogeneous clients. In this paper, we propose a novel personalized federated learning by domain-aware network pruning and re-growth, called FedDNPR, that is more accurate as compared to existing PFL methods while maintaining high efficiency. This is achieved by 1) introducing a regularization term capturing heterogeneity of weights in iterative network pruning in order to reduce network sharing among unrelated clients, and 2) iterative network re-growing only from weights of related clients to increase network sharing among related clients. With FedDNPR, model clustering is performed considering the similarity between gradient updates in the last layers of the networks, with cosine as the similarity measure to achieve both accuracy and efficiency in model personalization. With extensive experimental evaluation, we show that FedDNPR significantly outperforms the state-of-the-art PFL approaches, while maintaining comparable efficiency.

Sea ice type classification is essential for climate change research and maritime safety. Traditionally, this process relies on manual ice charting, which is time-consuming, expensive, and requires expert knowledge, making it difficult to scale up for current demands. Automating sea ice type classification is essential to keep pace with rapidly changing sea ice conditions. However, two main challenges limit the development of effective automated classifiers. First, while ice charts provide valuable labeled data, they only offer large-area (polygon) annotations rather than pixel-level labels, leading to a lack of precise training data. Second, although there are additional datasets with useful sea ice information, effectively combining these different data sources remains difficult. To tackle the first challenge, we employed co-training and label propagation, two semi-supervised learning methods, to learn from a small amount of labeled data and a large pool of unlabeled data, thereby improving the accuracy of sea ice classifiers despite limited labeled data. To address the second challenge, we leveraged co-training’s built-in ability to integrate multiple data sources during the training process for the small labeled data. Additionally, we further enhanced data integration by using an ensemble of these co-trained models after training. Our approach demonstrates significant improvements over traditional supervised methods, showcasing the potential of semi-supervised learning methods in addressing two major challenges in developing automated sea ice classification solutions. Our study shows that semi-supervised learning improved F1 scores by 17% for SAR data and 33% for AMSR2 with limited labels, compared to supervised methods, while ensembling further boosted accuracy by 33%.

While time series data are abundant in numerous real world applications, large labeled time series datasets are scarce. Semi-supervised models, which leverage small amounts of labeled data along with a large set of unlabeled data, have been shown to significantly outperform unsupervised learning models that only rely on unlabeled data for time series clustering. However, existing semi-supervised time series clustering algorithms suffer from lack of scalability as they are limited to perform learning operations within the original data space. We propose a scalable and accurate autoencoder-based semi-supervised learning model for time series clustering in the embedded space. With this model, we also introduce multiple semi-supervised objective functions that leverage only a small number of labeled examples but significantly improve the quality of the autoencoder’s learned latent space for clustering. Our experiments on a variety of datasets show that our methods can often improve performance of a typical clustering method (namely, k-means). We demonstrate that our methods achieve a maximum average Adjusted Rand Index (ARI) of 0.897, a 140% increase over an unsupervised Convolutional Autoencoder (CAE) model. Finally, our proposed methods also achieve a maximum improvement of 44% over an existing semi-supervised model.

We present an efficient and accurate long-form question-answering platform, dubbed iLFQA (i.e., short for intelligent Long-Form Question Answering). The purpose of iLFQA is to function as a platform which accepts unscripted questions and efficiently produces semantically meaningful, explanatory, and accurate long-form responses. iLFQA consists of a number of modules for zero-shot classification, text retrieval, and text generation to generate answers to questions based on an open-domain knowledge base. iLFQA is unique in the question answering space because it is an example of a deployable and efficient long-form question answering system. Question answering systems exist in many forms, but long-form question answering remains relatively unexplored, and to the best of our knowledge none of the existing long-form question answering systems are shown to be sufficiently efficient to be deployable. We have made the source code and implementation details of iLFQA available for the benefit of researchers and practitioners in this field. With this demonstration, we present iLFQA as an open-domain, deployable, and accurate open-source long-form question answering platform.

Over the last decade, transportation has been evolving along a technology pathway towards automation and electrification, with the promise of broad positive economic impact. In the short term, increased use of algorithmic routing has instead led to increased road network congestion, which is itself a strong indicator of a negative impact in terms of economics, emissions, and safety. These outcomes are strongly tied to the effects of "user-optimal" route plans competing over the finite road network supply. As demonstrated in our prior work, these concerns can be addressed by computing a system-optimal (SO) batch route plan, which minimizes the system-level average travel time for a given set of traveling agents. However, this leads to two problems of scale. First, as network sizes increase, SO-assigned routes will decay in optimality more readily as network congestion effects vary. Second, as population sizes increase, the problem space quickly becomes intractable for SO route planning.In this paper we extend the original SO route planning problem to include within-route replanning, which addresses the decaying optimality of one-time route plans in large transportation networks. While this allows for a more adaptive SO solution, it greatly increases the number of agents seeking guidance in each batch. To address this, we introduce a sub-batching heuristic based on trajectory clustering to decompose the batch route planning problem into independent sub-batches. Once identified, a fi ltering te chnique is ap plied to re duce th e total number of sub-batches. These remaining sub-batches are then each assigned route plans using our original SO technique. This approach can tailor-fit the problem to a set of compute resources, yielding a complete replanning batch pipeline suitable for online execution. An experimental study demonstrates the impact of the proposed technique in three city road networks, improving on the performance of our past work and delivering on the promise of improved scalability. In particular, where travel times were reduced by up to 48.49% with user-optimal replanning, they are further reduced by up to 60.96% using the SO technique.

Route planning in transportation networks is typically performed as a single optimization at trip departure. In this paper, we consider the impact of within-trip replanning on the performance of the overall network in a fully-algorithmic route selection scenario. An experimental study of three real road networks using synthetic demand demonstrates in over 200 trials the effects of replanning with respect to the replanning rate and the adoption rate of replanning. Overall network travel times are reduced by up to 48.49% from a baseline where all drivers are assigned a single route, demonstrating the profound effect of dynamic within-trip replanning. These observations are part of our work exploring a system-optimal route planning strategy that is robust to network size and conditions.

Thanks to recent prevalence of location tracking technologies, collecting massive spatiotemporal datasets containing moving object trajectories has become possible, providing an exceptional opportunity to derive interesting insights about the behavior of moving objects such as people, animals, and vehicles. In particular, mining patterns from "co-movements" of objects (such as movements by players of a sports team, joints of the human body while walking, and vehicles in a transportation network) can lead to the discovery of interesting patterns (e.g., offense tactics of a sports team, gait signature of a person, and driving behaviors causing heavy traffic). Various trajectory mining and frequent pattern mining techniques have been proposed to discover patterns in trajectory datasets and more generally, event sequences. However, existing approaches are inapplicable for co-movement pattern mining from multi-trajectory datasets. In this paper, we propose a novel and efficient framework for co-movement pattern mining. We also extend this framework for efficient mining of such patterns at multiple spatial scales. The performance of the proposed solutions is evaluated by conducting extensive experiments using two real datasets, a soccer game dataset and a human gait dataset. Our experimental results show that our proposed algorithms are promising.

The existing online mapping systems process many user route queries simultaneously, yet solve each independently, using typical route guidance solutions. These route recommendations are presented as optimal, but often this is not truly the case, due to the effects of competition users experience over the resulting experienced routes, a phenomenon referred to in Game Theory as a Nash Equilibrium. Additionally, route plans of this nature can result in poor utilization of the road network from a system-optimizing perspective as well. In this paper, we introduce an enhanced approach for route guidance, motivated by the relevance of a system optimal equilibrium strategy, while also maintaining some fairness to the individual. With this approach the objective is to optimize the global road network utilization (as measured by, e.g., mobility, or global emissions) by selecting from a set of generally fair user route alternatives in a batch setting. For the first time, we present an approximate, anytime algorithm based on Monte Carlo Tree Search and Eppstein's Top-K Shortest Paths algorithm to solve this complex dual optimization problem in real-time. This approach attempts to identify and avoid the potentially harmful network effects of sub-optimal route combinations. Experiments show that mobility optimization over real road networks of Rye and Golden, Colorado in a microscopic traffic simulation with a network congestion-minimizing objective can achieve considerable mobility improvement for users, as observed by their effective travel time improvement up to 12% with some consideration of route fairness.

With the rapid development of location sensors, it is now possible to accurately study how various items (such as viruses or messages) spread across populations of moving objects. In such applications, an item can propagate through the object population where two objects are close. Such a dynamic network of objects called a "contact network". In this paper, we define and study a family of probabilistic reachability queries in uncertain contact networks, where contacts between objects are probabilistic. A probabilistic reachability query verifies whether two objects are "reachable" with a probability no less than a threshold η. To enable efficient processing of probabilistic reachability queries on large uncertain contact networks, first, we present a series-parallel reduction technique that significantly reduces the size of the input uncertain contact network in order to shrink the search space while maintaining accuracy and second, we introduce Optimized Spatiotemporal Tree Cover, an index structure that leverages the spatiotemporal properties of the contact network. With an extensive analytical and empirical study, we demonstrate superiority of our proposed solution versus a baseline solution (i.e., Monte Carlo sampling) and the only other existing solution with 400% and 200% improvement in query processing time on average, respectively.

With the rapid development of location sensors, it is now possible to study how various items (such as viruses and messages) spread across populations of moving objects at scale. In such applications, two objects are considered in-contact while they are sufficiently close to each other. Such a dynamic network of objects, so-called a "contact network". In this paper, we define and study probabilistic reachability queries in uncertain contact networks, where contacts between objects are probabilistic. A probabilistic reachability query verifies whether two objects are "reachable" with a probability no less than a threshold η. We introduce Optimized Spatiotemporal Tree Cover, an index structure that leverages the spatiotemporal properties of the contact network to enable efficient processing of the reachability queries on large uncertain contact networks. With an extensive study using both real and synthetic datasets, we demonstrate superiority of our proposed solution versus a baseline solution (i.e., Monte Carlo Sampling) and the only other existing solution for reachability queries on uncertain contact networks, with 350% and 150% improvement in query processing time on average, respectively.

Thanks to recent prevalence of location sensors, collecting massive spatiotemporal datasets containing moving object trajectories has become possible, providing an exceptional opportunity to derive interesting insights about behavior of the moving objects such as people, animals, and vehicles. In particular, mining patterns from co-movements of objects (such as players of a sports team, joints of a person while walking, and cars in a transportation network) can lead to the discovery of interesting patterns (e.g., offense tactics of the sports team, gait signature of the person, and driving behaviors causing heavy traffic). With our prior work, we proposed efficient algorithms to mine frequent co-movement patterns from trajectory datasets. In this paper, we focus on the problem of efficient query processing on massive co-movement pattern datasets generated by such pattern mining algorithms. Given a dataset of frequent co-movement patterns, various spatiotemporal queries can be posed to retrieve relevant patterns among all generated patterns from the pattern dataset. We term such queries “pattern queries”. Co-movement patterns are often numerous due to combinatorial complexity of such patterns, and therefore, co-movement pattern datasets grow very large, rendering naive execution of the pattern queries ineffective. In this paper, we propose novel index structures and query processing algorithms for efficient answering of two families of range pattern queries on massive co-movement pattern datasets, namely, spatial range pattern queries and temporal range pattern queries. Our extensive empirical studies with three real datasets have demonstrated the efficiency of the proposed methods.

Given a set S of sites and a set O of objects in a metric space, the Optimal Location (OL) problem is about computing a location in the space where introducing a new site (e.g., a retail store) maximizes the number of the objects (e.g., customers) that would choose the new site as their "preferred" site among all sites. However, the existing solutions for the optimal location problem assume that there is only one criterion to determine the preferred site for each object (i.e., the metric distance between objects and sites), whereas with numerous real-world applications multiple criteria are used as preference measures. In this paper, for the first time we develop an efficient and exact solution for the so-called Multi-Criteria Optimal Location (MCOL) problem that can scale with large datasets. Toward that end, first we formalize the MCOL problem as maximal reverse skyline query (MaxRSKY). Given a set of sites and a set of objects in a d-dimensional space, MaxRSKY query returns a location in the space where if a new site s is introduced, the size of the (bichromatic) reverse skyline set of s is maximal. To the best of our knowledge, this paper is the first to define and study MaxRSKY query. Accordingly, we propose a baseline solution for identification of the optimal location.

Many location-based applications are enabled by handling numerous moving queries over mobile objects. Efficient processing of such queries mainly relies on effective probing, i.e., polling the objects to obtain their current locations (required for processing the queries). With effective probing, one can monitor the current location of the objects with sufficient accuracy for the existing queries, by striking a balance between communication cost of probing and accuracy of the knowledge about current location of the objects. In this paper, we focus on location-based applications that reduce to processing a large set of proximity monitoring queries simultaneously, where each query continuously monitors if a pair of objects are within a certain predefined distance. Accordingly, we propose an effective object probing solution for efficient processing of proximity monitoring queries. In particular, with our proposed solution for the first time we formulate optimal probing as a batch processing problem and propose a method to prioritize probing the objects such that the total number of probes required to answer all queries is minimized. Our extensive experiments demonstrate the efficiency of our proposed solution for a wide range of applications involving up to hundreds of millions of queries.

Given a set S of sites and a set O of weighted objects located on a road network, the optimal network location (ONL) query computes a location on the road network where introducing a new site would maximize the total weight of the objects that are closer to the new site than to any other site. The existing solutions for optimal network location query assume that sites and objects rarely change their location over time, whereas there are numerous new applications with which sites and/or objects frequently change location. Unfortunately, the existing solutions for optimal network location query are not applicable to answer such these so-called dynamic optimal network location queries (DONL), since the result generated by such solutions is most probably invalid by the time computation is complete. In this paper for the first time we formalize the problem of DONL queries as Continuous Maximal Reverse Nearest Neighbor (CMaxRNN) queries on spatial networks, and introduce an approach that allows for efficient and incremental update of MaxRNN query results on spatial networks. With an extensive experimental study we verify and evaluate the efficiency of our proposed approach with both synthetic and real-world datasets.

With the advent of reliable positioning technologies and prevalence of location-based services, it is now feasible to accurately study the propagation of items such as infectious viruses, sensitive information pieces, and malwares through a population of moving objects, e.g., individuals, mobile devices, and vehicles. In such application scenarios, an item passes between two objects when the objects are sufficiently close (i.e., when they are, so-called, in contact ), and hence once an item is initiated, it can penetrate the object population through the evolving network of contacts among objects, termed contact network . In this paper, for the first time we define and study reachability queries in large (i.e., disk-resident) contact datasets which record the movement of a (potentially large) set of objects moving in a spatial environment over an extended time period. A reachability query verifies whether two objects are "reachable" through the evolving contact network represented by such contact datasets. We propose two contact-dataset indexes that enable efficient evaluation of such queries despite the potentially humongous size of the contact datasets. With the first index, termed ReachGrid , at the query time only a small necessary portion of the contact network which is required for reachability evaluation is constructed and traversed. With the second approach, termed ReachGraph , we precompute reachability at different scales and leverage these precalculations at the query time for efficient query processing. We optimize the placement of both indexes on disk to enable efficient index traversal during query processing. We study the pros and cons of our proposed approaches by performing extensive experiments with both real and synthetic data. Based on our experimental results, our proposed approaches outperform existing reachability query processing techniques in contact networks by 76% on average.

The problem of point-to-point shortest path computation in spatial networks is extensively studied with many approaches proposed to speed-up the computation. Most of the existing approaches make the simplifying assumption that weights (e.g., travel-time) of the network edges are constant. However, with real-world spatial networks the edge travel-times are time-dependent, where the arrival-time to an edge determines the actual travel-time of the edge. With this paper, we study the applicability of existing shortest path algorithms to real-world large time-dependent spatial networks. In addition, we evaluate the importance of considering time-dependent edge travel-times for route planning in spatial networks. We show that time-dependent shortest path computation can reduce the travel-time by 36% on average as compared to the static shortest path computation that assumes constant edge travel-times.

Given a set S of sites and a set O of weighted objects, an optimal location query finds the location(s) where introducing a new site maximizes the total weight of the objects that are closer to the new site than to any other site. With such a query, for instance, a franchise corporation (e.g., McDonald's) can find a location to open a new store such that the number of potential store customers (i.e., people living close to the store) is maximized. Optimal location queries are computationally complex to compute and require efficient solutions that scale with large datasets. Previously, two specific approaches have been proposed for efficient computation of optimal location queries. However, they both assume p-norm distance (namely, L1 and L2/Euclidean); hence, they are not applicable where sites and objects are located on spatial networks. In this paper, we focus on optimal network location (ONL) queries, i.e., optimal location queries with which objects and sites reside on a spatial network. We introduce an approach, namely EONL (short for Expansion-based ONL), which enables efficient computation of ONL queries. Moreover, with an extensive experimental study we verify and compare the efficiency of our proposed approach with real datasets, and we demonstrate the importance of considering network distance (rather than p-norm distance) with ONL queries.

In this paper, we present TransDec, an end-to-end-data-driven system which enables spatiotemporal queries in transportation systems with dynamic, real-time and historical data. TransDec fuses a variety of real-world spatiotemporal datasets including massive traffic sensor data, trajectory data, transportation network data, and point-of-interest data to create an immersive and realistic virtual model of a transportation system. With TransDec, we address the challenges in visualization, monitoring, querying and analysis of dynamic and large-scale transportation data in both time and space.

Harnessing the potential of today's ever growing and dynamic geospatial data requires the development of novel visual analysis interfaces, tools and technologies. In this paper, we present GeoDec, a generic framework capable of supporting queries and visualizations of real-world spatio-temporal data sets. We show, for various locations and applications, how our innovative Query Driven Design enhances the visual analysis of geospatial data through the interactive manipulation of queries and the temporal navigation of these query results.

We envision participatory texture documentation (PTD) as a process in which a group of users (dedicated individuals and/or general public) with camera-equipped mobile phones participate in collaborative collection of urban texture information. PTD enables inexpensive, scalable and high resolution urban texture documentation. We have proposed to implement PTD in two steps [10]. At the first step, termed viewpoint selection, a minimum number of points in the urban environment are selected from which the texture of the entire urban environment (the part visible to cameras) can be collected/captured. At the second step, called viewpoint assignment, the selected viewpoints are assigned to the participating users such that given a limited number of users with various constraints (e.g., restricted available time) users can collectively capture the maximum amount of texture information within a limited time interval. In this paper, we focus on the viewpoint assignment problem. We first prove that this problem is an NP-hard problem, and therefore, the optimal solution for viewpoint assignment fails to scale as the extent of the urban environment and the number of participating users grow. Subsequently, we propose a family of heuristics for efficient viewpoint assignment to reduce the assignment running time while ensuring an almost complete texture collection. We study, profile and verify our proposed solutions comparatively by both rigorous analysis and extensive experiments.

In this paper, we outline our efficient sample-based approach to answer fixed-precision approximate continuous aggregate queries in peer-to-peer databases. We describe our approach in the context of Digest, a two-tier system we have developed for correct and efficient query answering by sampling. With Digest, at the top tier we develop a query evaluation engine that uses the samples collected from the peer-to-peer database to continually estimate the running result of the approximate continuous aggregate query with guaranteed precision. For efficient query evaluation, we propose an extrapolation algorithm that predicts the evolution of the running result and adapts the frequency of the continual sampling occasions accordingly to avoid redundant samples. We also introduce a repeated sampling algorithm that draws on the correlation between the samples at successive sampling occasions and exploits linear regression to minimize the number of the samples derived at each occasion. At the bottom tier, we introduce a distributed sampling algorithm for random sampling (uniform and nonuniform) from peer-to-peer databases with arbitrary network topology and tuple distribution. Our sampling algorithm is based on the Metropolis Markov Chain Monte Carlo method that guarantees randomness of the sample with arbitrary small variation difference with the desired distribution, while it is comparable to optimal sampling in sampling cost/time. We evaluate the efficiency of Digest via simulation using real data.

In this paper, we propose DBSampler, a query execution mechanism to answer "partial selection" queries in peerto- peer databases. A partial selection query is an arbitrary selection query that is satisfied with a fraction \in of the results; a universal operation with applications in database tuning, query optimization and approximate query processing in peer-to-peer databases. DBSampler is based on an epidemic dissemination algorithm. We model the epidemic dissemination as a percolation problem and by rigorous percolation analysis tune DBSampler per-query and on-thefly to answer partial queries correctly and efficiently. We verify the efficiency of DBSampler in terms of query cost and query time via extensive simulation.

Peer-to-peer Data Networks (PDNs) are large-scale, self-organizing, distributed query processing systems. Familiar examples of PDN are peer-to-peer file-sharing networks, which support exact-match search queries to locate user-requested files. In this paper, we formalize the more general problem of similarity-search in PDNs, and propose a family of distributed access methods, termed Small-World Access Methods (SWAM), for efficient execution of various similarity-search queries, namely exact-match, range, and k-nearest-neighbor queries. Unlike its predecessors, i.e., LH* and DHTs, SWAM does not control the assignment of data objects to PDN nodes; each node autonomously stores its own data. Besides, SWAM supports all similarity-search queries on multiple attributes. SWAM guarantees that the query object will be found (if it exists in the network) in average time logarithmically proportional to the network size. Moreover, once the query object is found, all the similar objects would be in its proximate network neighborhood and hence enabling efficient range and k-nearest-neighbor queries.