SUMMARY: Multi-omics data offer unprecedented insights into complex biological systems, yet their high dimensionality, sparsity, and intricate interactions pose significant analytical challenges. Network-based approaches have advanced multi-omics research by effectively capturing biologically relevant relationships among molecular features (e.g., genes, proteins, metabolites). While these methods are powerful for representing molecular interactions, there remains a need for tools specifically designed to effectively utilize these network representations across diverse downstream analyses. To fulfill this need, we introduce BioNeuralNet, a flexible and modular Python framework tailored for end-to-end network-based multi-omics data analysis. BioNeuralNet leverages Graph Neural Networks (GNNs) to learn biologically meaningful low-dimensional representations from multi-omics networks, converting these complex molecular networks into versatile embeddings. BioNeuralNet supports all major stages of multi-omics network analysis, including several network construction techniques, generation of low-dimensional representations, and a broad range of downstream analytical tasks. Its extensive utilities, including diverse GNN architectures, and compatibility with established Python packages (e.g., scikit-learn, PyTorch, NetworkX), enhance usability and facilitate quick adoption. BioNeuralNet is an open-source, user-friendly, and extensively documented framework designed to support flexible and reproducible multi-omics network analysis in precision medicine. AVAILABILITY AND IMPLEMENTATION: The BioNeuralNet library is available via The Python Package Index (PyPI). Source code, documentation, tutorials, and workflows are hosted at https://bioneuralnet.readthedocs.io. Code archived at https://doi.org/10.5281/zenodo.17503083.

Multiple -omics (genomics, proteomics, etc.) profiles are commonly generated to gain insight into a disease or physiological system. Constructing multi-omics networks with respect to the trait(s) of interest provides an opportunity to understand relationships between molecular features but integration is challenging due to multiple data sets with high dimensionality. One approach is to use canonical correlation to integrate one or two omics types and a single trait of interest. However, these types of methods may be limited due to (1) not accounting for higher-order correlations existing among features, (2) computational inefficiency when extending to more than two omics data when using a penalty term-based sparsity method, and (3) lack of flexibility for focusing on specific correlations (e.g., omics-to-phenotype correlation versus omics-to-omics correlations). In this work, we have developed a novel multi-omics network analysis pipeline called Sparse Generalized Tensor Canonical Correlation Analysis Network Inference (SGTCCA-Net) that can effectively overcome these limitations. We also introduce an implementation to improve the summarization of networks for downstream analyses. Simulation and real-data experiments demonstrate the effectiveness of our novel method for inferring omics networks and features of interest.

Understanding complex diseases hinges on a profound understanding of intricate biomolecular interactions unfolding within a complex, multidimensional landscape, challenging traditional methods to extract meaningful insights. While multi-omics networks capture the richness of biological data, providing a basis for predicting relationships between biomolecules and various phenotypic traits of complex diseases, their inherent complexity limits their predictive power. To address this challenge, we introduce a novel pipeline that leverages the power of Graph Neural Networks (GNNs) to extract and integrate meaningful information from multi-omics networks. By generating informative node embeddings and seamlessly incorporating them into the original subject-level data, our approach captures both local and global network dependencies, leading to substantial improvements in disease prediction accuracy. The proposed pipeline optimizes the embedding generation process for the specific prediction task, enabling the model to learn task-relevant representations. Through rigorous experimentation, we demonstrate the superior performance of our approach, surpassing existing methods by a substantial margin on nine real-world multi-omics datasets. With remarkable increases in accuracy ranging approximately from 8% to 10% over the best-performing baseline, particularly when the multi-omics networks are moderately dense, striking a balance between capturing complex relationships and avoiding excessive noise. Our findings underscore the potential of GNNs to significantly improve disease prediction by effectively extracting and representing knowledge embedded within multi-omics networks.

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%.

The need for real-time, tailored, and autonomous decision-making applications driven by machine learning and deep learning models has propelled the development and use of edge computing devices. Edge computing devices are characterized by the generation of large volumes of data and minimal computational resources (memory, processing capacity, etc.). In this work, we present a novel and integrated framework, called Incremental Semi-Supervised Tri-Training, for incremental update as well as personalization of models residing on edge computing devices in the absence of domain specific labelled data. The proposed framework encompasses three heavy weight neural networks working collaboratively to generate high quality pseudo-labels in a self-supervised manner to train a teacher model. The knowledge from the teacher model is then distilled into the student model residing on the edge device. The developed models are incrementally updated resulting in personalization of the edge model over time without requiring labels/annotations. We demonstrate the efficacy of the proposed framework in the context of a sleep staging application using the Physionet Sleep EDF-Expanded data repository.

MOTIVATION: Biological networks can provide a system-level understanding of underlying processes. In many contexts, networks have a high degree of modularity, i.e. they consist of subsets of nodes, often known as subnetworks or modules, which are highly interconnected and may perform separate functions. In order to perform subsequent analyses to investigate the association between the identified module and a variable of interest, a module summarization, that best explains the module's information and reduces dimensionality is often needed. Conventional approaches for obtaining network representation typically rely only on the profiles of the nodes within the network while disregarding the inherent network topological information. RESULTS: In this article, we propose NetSHy, a hybrid approach which is capable of reducing the dimension of a network while incorporating topological properties to aid the interpretation of the downstream analyses. In particular, NetSHy applies principal component analysis (PCA) on a combination of the node profiles and the well-known Laplacian matrix derived directly from the network similarity matrix to extract a summarization at a subject level. Simulation scenarios based on random and empirical networks at varying network sizes and sparsity levels show that NetSHy outperforms the conventional PCA approach applied directly on node profiles, in terms of recovering the true correlation with a phenotype of interest and maintaining a higher amount of explained variation in the data when networks are relatively sparse. The robustness of NetSHy is also demonstrated by a more consistent correlation with the observed phenotype as the sample size decreases. Lastly, a genome-wide association study is performed as an application of a downstream analysis, where NetSHy summarization scores on the biological networks identify more significant single nucleotide polymorphisms than the conventional network representation. AVAILABILITY AND IMPLEMENTATION: R code implementation of NetSHy is available at https://github.com/thaovu1/NetSHy. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Every year, the U.S. economy loses more than${\$}$411 billion because of work performance reduction, injuries, and traffic accidents caused by microsleep. To mitigate microsleep's consequences, an unobtrusive, reliable, and socially acceptable microsleep detection solution throughout the day, every day is required. Unfortunately, existing solutions do not meet these requirements. In this paper, we propose WAKE, a novel behind-the-ear wearable device for microsleep detection. By monitoring biosignals from the brain, eye movements, facial muscle contractions, and sweat gland activities from behind the user's ears, WAKE can detect microsleep with a high temporal resolution. We introduce a Three-fold Cascaded Amplifying (3CA) technique to tame the motion artifacts and environmental noises for capturing high fidelity signals. Through our prototyping, we show that WAKE can suppress motion and environmental noise in real-time by 9.74-19.47 dB while walking, driving, or staying in different environments, ensuring that the biosignals are captured reliably. We evaluated WAKE using gold-standard devices on 19 sleep-deprived and narcoleptic subjects. The Leave-One-Subject-Out Cross-Validation results show the feasibility of WAKE in microsleep detection on an unseen subject with average precision and recall of 76 and 85 percent, respectively.

The study of complex behavior of biological systems has become increasingly dependent on evolutionary network modeling. In particular, multi-omics networks capture interactions between biomolecules such as proteins and metabolites, providing a basis for predicting relationships between such biomolecules and various phenotypic traits of complex diseases. In this paper, we introduce an integrative framework that given a multi-omics network representing a cohort of subjects, learns expressive representations for network nodes, and combines the learned nodes representations with the biological profiles of individual subjects for enriched representation of the subjects. With extensive empirical evaluation using real-world multi-omics networks, we show that our proposed framework significantly outperforms existing and baseline methods in terms of subject representation accuracy, particularly when the multi-omics network representing the cohort is sparse and structured and therefore, more informative.

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.

Microsleep, caused by sleep deprivation, sleep apnea, and narcolepsy, costs the U.S.'s economy more than $411 billion/year because of work performance reduction, injuries, and traffic accidents. Mitigating microsleep's consequences require an unobtrusive, reliable, and socially acceptable microsleep detection solution throughout the day, every day. Unfortunately, existing solutions do not meet these requirements.

Over 50 million people undergo surgeries each year in the United States, with over 70% of them filling opioid prescriptions within one week of the surgery. Due to the highly addictive nature of these opiates, a post-surgical window is a crucial time for pain management to ensure accurate prescription of opioids. Drug prescription nowadays relies primarily on self-reported pain levels to determine the frequency and dosage of pain drug. Patient pain self-reports are, however, influenced by subjective pain tolerance, memories of past painful episodes, current context, and the patient's integrity in reporting their pain level. Therefore, objective measures of pain are needed to better inform pain management.

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.

This paper introduces LIBS, a light-weight and inexpensive wearable sensing system, that can capture electrical activities of human brain, eyes, and facial muscles with two pairs of custom-built flexible electrodes each of which is embedded on an off-the-shelf foam earplug. A supervised non-negative matrix factorization algorithm to adaptively analyze and extract these bioelectrical signals from a single mixed in-ear channel collected by the sensor is also proposed. While LIBS can enable a wide class of low-cost self-care, human computer interaction, and health monitoring applications, we demonstrate its medical potential by developing an autonomous whole-night sleep staging system utilizing LIBS's outputs. We constructed a hardware prototype from off-the-shelf electronic components and used it to conduct 38 hours of sleep studies on 8 participants over a period of 30 days. Our evaluation results show that LIBS can monitor biosignals representing brain activities, eye movements, and muscle contractions with excellent fidelity such that it can be used for sleep stage classification with an average of more than 95% accuracy.

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.

Geospatial queries (GQ) have been used in a wide variety of applications such as decision support systems, profile-based marketing, bioinformatics and GIS. Most of the existing query-answering approaches assume centralized processing on a single machine although GQs are intrinsically parallelizable. There are some approaches that have been designed for parallel databases and cluster systems, however, these only apply to the systems with limited parallel processing capability, far from that of the cloud-based platforms. In this paper, we study the problem of parallel geospatial query processing with the MapReduce programming model. Our proposed approach creates a spatial index, Voronoi diagram, for given data points in 2D space and enables efficient processing of a wide range of GQs. We evaluated the performance of our proposed techniques and correspondingly compared them with their closest related work while varying the number of employed nodes.

In this paper, we propose an efficient sample-based approach to answer fixed-precision approximate continuous aggregate queries in peer-to-peer databases. First, we define practical semantics to formulate fixed-precision approximate continuous aggregate queries. Second, we propose "Digest", a two-ti

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.

Due to enormous complexity of the unstructured peer-to-peer networks as large-scale, self-configure, and dynamic systems, the models used to characterize these systems are either inaccurate, because of oversimplification, or analytically inapplicable, due to their high complexity. By recognizing unstructured peer-to-peer networks as "complex systems ", we employ statistical models used before to characterize complex systems for formal analysis and efficient design of peer-to-peer networks. We provide two examples of application of this modeling approach that demonstrate its power. For instance, using this approach we have been able to formalize the main problem with normal flooding search, propose a remedial approach with our probabilistic flooding technique, and find the optimal operating point for probabilistic flooding rigorously, such that it improves scalability of the normal flooding by 99%.

Flooding is an effective mechanism for both broadcast and unicast modes of communication (in unstructured networks), providing broad coverage and guaranteeing minimum delay. However, flooding is not a scalable communication mechanism, mainly because of the communication overhead it imposes to the network. We use the percolation theory to formalize the main problem with flooding in the context of power-law networks, propose a remedial approach with our probabilistic flooding technique, and find the optimal operating point for probabilistic flooding rigorously, such that it improves scalability of the normal flooding by 99%.

The World Wide Web (WWW) is the largest distributed information space and has grown to encompass diverse information resources. Although the web is growing exponentially, the individual's capacity to read and digest content is essentially fixed. The full economic potential of the web will not be realized unless enabling technologies are provided to facilitate access to web resources. Currently web personalization is the most promising approach to remedy this problem, and web mining, particularly web-usage mining, is considered a crucial component of any efficacious web-personalization system. In this paper, we describe a complete framework for web-usage mining to satisfy the challenging requirements of web-personalization applications. For online and anonymous web personalization to be effective, web usage mining must be accomplished in real time as accurately as possible. On the other hand, web-usage mining should allow a compromise between scalability and accuracy to be applicable to real-life websites with numerous visitors. Within our web-usage-mining framework, we introduce a distributed user-tracking approach for accurate, scalable, and implicit collection of the usage data. We also propose a new model, the feature-matrices (FM) model, to discover and interpret users' access patterns. With FM, various spatial and temporal features of usage data can be captured with flexible precision so that we can trade off accuracy for scalability based on the specific application requirements. Moreover, tunable complexity of the FM model allows real-time and adaptive access pattern discovery from usage data. We define a novel similarity measure based on FM that is specifically designed for accurate classification of partial navigation patterns in real time. Our extensive experiments with both synthetic and real data verify correctness and efficacy of our web-usage-mining framework for anonymous and efficient web personalization.

Distributed continuous media server (DCMS) architectures are proposed to minimize the communication-storage cost for those continuous media applications that serve a large number of geographically distributed clients. Typically, a DCMS is designed as a pure hierarchy of centralized continuous media servers. RedHi, a Redundant Hierarchical topology for DCMS networks, can result in higher utilization and better reliability over pure hierarchy. We focus on the design of a resource management system (RMS) for RedHi that can exploit the resources of its DCMS network to achieve these performance objectives. Our RMS is based on a fully decentralized approach to achieve optimal scalability and robustness. The major drawback of a fully decentralized design is the increase in latency time and communication overhead to locate the requested object. However, as compared to the typically long duration and high resource/bandwidth requirements of continuous media objects, the extra latency and overhead of a decentralized resource management approach become negligible. Moreover, our RMS collapses three management tasks (object location, path selection and resource reservation) into one fully decentralized object delivery mechanism, reducing the latency even further. Decentralization of the resource management satisfies our scalability and robustness objectives, whereas collapsing the management tasks helps alleviate the latency and overhead constraints. To achieve a high resource utilization, the object delivery scheme uses our proposed cost function, as well as various object location and resource reservation policies to select and allocate the best streaming path to serve each request. The object delivery scheme is designed as an application-layer resource management middleware for the DCMS architecture to be independent of the underlying telecommunication infrastructure. Experiments show that our RMS is successful in realization of the higher resource utilization for the DCMS networks with the RedHi topology.

Distributed continuous media server (DCMS) architectures are proposed to minimize the communication-storage cost for those continuous media applications that serve a large number of geographically distributed clients. Typically, a DCMS is designed as a pure hierarchy (tree) of centralized continuous media servers. In an earlier work, we proposed a redundant hierarchical topology for DCMS networks, termed RedHi, which can potentially result in higher utilization and better reliability over pure hierarchy. We focus on the design of a resource management system for RedHi that can exploit the resources of its DCMS network to achieve these performance objectives. Our proposed resource management system is based on a fully decentralized approach to achieve optimal scalability and robustness. In general, the major drawback of a fully decentralized design is the increase in latency time and communication overhead to locate the requested object. However, as compared to the typically long duration and high resource/bandwidth requirements of continuous media objects, the extra latency and overhead of a decentralized resource management approach become negligible. Moreover, our resource management system collapses three management tasks: (1) object location, (2) path selection, and (3) resource reservation, into one fully decentralized object delivery mechanism, reducing the latency even further. In sum, decentralization of the resource management satisfies our scalability and robustness objectives, whereas collapsing the management tasks helps alleviate the latency and overhead constraints.