Trip recommendation has drawn considerable attention over the past decade. In trip recommendation, a sequence of point-of-interests (POIs) are recommended for a given query which includes an origin and a destination. Recently the emergence of the attention mechanism and many attention-incorporated models have achieved great success in various fields. Trip recommendation problems demonstrate similar characteristics that can potentially benefit from the attention mechanism. However, applying the attention mechanism for trip recommendation is non-trivial. We are motivated to answer the following two research questions. (1) How can we learn trip representation effectively without labels? Unlike most of the natural language processing tasks, there are no ground-truth labels available for trip recommendation. (2) How can we learn trip representation effectively without handcrafting negative samples? In this paper, we cast the trip representation learning into a natural language processing (NLP) task. We propose BERT-Trip, a self-supervised contrast learning framework, to learn effective and scalable trip representation in support of time-sensitive and user-personalized trip recommendation. BERT-Trip builds on a Siamese network to maximize the similarity between the augmentations of trips with BERT as the backbone encoder. We utilize the masking strategy for generating augmented views (positive sample pairs) of trips in the Siamese network and employ the stop-gradient on one side of the Siamese network to eliminate the need to use any negative sample pairs or momentum encoders. Extensive experiments on real-world datasets demonstrate that BERT-Trip consistently outperformed the state-of-the-art methods in terms of all effectiveness metrics. Compared with the state-of-the-art methods, BERT-Trip is able to yield up to 24 percent and 40 percent increases in F1score on the Flickr and the Weeplaces datasets, respectively. A rigorous performance evaluation of BERT-Trip on scalability up to 12800 POIs is also provided.

Skyline queries have drawn great interest and been widely used in various application domains including multi-criteria decision making, search pruning, and personalized recommendation systems. Given multiple criteria, skyline queries return objects that are not dominated by any other objects. As an extension of traditional skyline queries, probabilistic skyline queries aim to cope with uncertain datasets. This paper presents a novel MapReduce-based framework, ProbSky, in support of fast parallel evaluation of probabilistic skyline queries on large high-dimensional data. ProbSky efficiently evaluates exact p-skyline queries on large uncertain data without compromising the quality of query results. From the theoretical point of view, we formally prove two pruning lemmas integrated with ProbSky to strengthen the early pruning capacity. ProbSky builds on top of three optimization techniques, namely, dominant instance pruning, grid-based partitioning, and pivot point-based acceleration. Extensive experiments on both real and synthetic datasets unveil that compared to the state-of-the-art, ProbSky speeds up the evaluation of exact p-skyline queries on large high-dimensional data by at least one order of magnitude in most cases. Our experimental results also validate that by balancing the memory consumption and execution time among machines, ProbSky is adroit at curbing the bottleneck effect that causes severe system performance deterioration.

Query optimizers in Relational Database Management Systems (RDBMS) rely on the approximations of data distributions of attributes, which are used for cardinality-based decisions like selectivity of a predicate or finding the right join order of a multiway join in a SQL query. The commercial databases try to reach best possible approximations of data distribution using compressed histograms. The state of the art in measurement of quality of a histogram is the q-error. However, one of the shortcomings of the measurement of quality of the histograms using q-error is that it pivots the entire quality on the worst case or the infinity norm of the multiplicative errors of the estimations. This may not be symbolic of the workload or the overall range of errors that would be representative of the system. In this paper, we propose a dynamic programming algorithm to achieve an optimal histogram structure by keeping the overall multiplicative errors low. We propose a one pass linear regression on the step function and apply dynamic programming methods to achieve an optimal histogram structure that optimizes the pair (slope β and intercept α). The algorithm achieves lower slope and intercept of the resultant regression on the sorted order of multiplicative errors, thus reducing the overall estimation errors for the system. We refer to this pair as the Q-Regression of a histogram. We then introduce the metric, QRegrArea as a new means to better quantify the cumulative distribution of errors for a given histogram. We provide the experimental validation of the proposed methods against the state-of the-art models in the literature and industry.

Context has been recognized as an important factor to consider in personalized recommender systems. Particularly in location-based services (LBSs), a fundamental task is to recommend to a mobile user where he/she could be interested to visit next at the right time. Additionally, location-based social networks (LBSNs) allow users to share location-embedded information with friends who often co-occur in the same or nearby points-of-interest (POIs) or share similar POI visiting histories, due to the social homophily theory and Tobler's first law of geography. So, both the time information and LBSN friendship relations should be utilized for POI recommendation. Tensor completion has recently gained some attention in time-aware recommender systems. The problem decomposes a user-item-time tensor into low-rank embedding matrices of users, items and times using its observed entries, so that the underlying low-rank subspace structure can be tracked to fill the missing entries for time-aware recommendation. However, these tensor completion methods ignore the social-spatial context information available in LBSNs, which is important for POI recommendation since people tend to share their preferences with their friends, and near things are more related than distant things. In this paper, we utilize the side information of social networks and POI locations to enhance the tensor completion model paradigm for more effective time-aware POI recommendation. Specifically, we propose a regularization loss head based on a novel social Hausdorff distance function to optimize the reconstructed tensor. We also quantify the popularity of different POIs with location entropy to prevent very popular POIs from being over-represented hence suppressing the appearance of other more diverse POIs. To address the sensitivity of negative sampling, we train the model on the whole data by treating all unlabeled entries in the observed tensor as negative, and rewriting the loss function in a smart way to reduce the computational cost. Through extensive experiments on real datasets, we demonstrate the superiority of our model over state-of-the-art tensor completion methods.

Depression is one of the leading factors in global disability and a top driver for suicides. Studies have shown that depression has an effect on language usage. In recent years, especially during the COVID pandemic, social media platforms have become the de facto platform for many individuals to self-disclose or discuss mental health issues like depression. This trend presents a unique opportunity for researchers and healthcare professionals to detect potential mental illnesses for early intervention or treatment by taking advantage of the recent advances in machine learning approaches. Existing depression detection methods on social media, however, suffer from two major limitations. First, these solutions heavily rely on the amount, quality, and type of user-posted content. Second, the overlooked social circle impact should be leveraged to enhance the prediction capabilities. In this paper, we propose a depression detection framework, MentalNet, based on heterogeneous graph convolution by capturing users’ interactions (replies, mentions, and quotetiveets) with their friends on social media and differentiating the intimacy of users’ social circles (e.g., family, friends, or acquaintances). Specifically, we formulate the problem of depression detection on social media as a graph classification problem by representing users’ social circles in the format of heterogeneous graphs. MentalNet embraces three modules, (1) extraction of ego-network node features, (2) construction of user interaction graphs, and (3) depression detection based on heterogeneous graph classification. The extensive experiments on Twitter data demonstrate that MentalNet consistently and significantly outperforms the state-of-the-art methods in terms of all the effectiveness metrics. Compared to the baseline methods, MentalNet is able to effectively predict early depression in Twitter users with up to 24% improvement on F1 score.

Fast diagnostic prediction of brain dysfunctions such as autism spectrum disorder (ASD), attention deficit hyperactivity disorder (ADHD) and Alzheimer’s disease is important due to their prevalence in the population. A typical workflow for brain dysfunction prediction is to preprocess a brain image into a network of connected brain regions, where indicative features are extracted using simple linear or convolutional models to be used for prediction. However, due to restrictions on patient data sharing such as HIPAA rules, the number of training samples is often very limited. Even with efforts like the ABIDE initiative that aggregated brain imaging data from laboratories around the world, the subject number merely reaches around 1,000, limiting the effectiveness of data-driven models such as deep learning models.To overcome this data scarcity problem, we propose a GAN-based data augmentation technique to generate realistic brain region networks, which are used to increase the size of an existing training set so that a brain dysfunction classifier can be better trained to achieve a higher prediction accuracy. In the brain region network setting, we propose a generator that considers each brain region as an embedding, so that the connectivity between two regions can be computed using the inner product of their embeddings. This generator is trained along with a phenotype-enhanced BrainNetCNN, a domain-specific discriminator (i.e., classifier), to improve its prediction accuracy. Our embedding-based generator generates samples following the original data feature distribution (i.e., age, gender, and health condition), which improves generator quality and avoids mode collapse.Our design is generally applicable to various neuroimaging data, and experimental results obtained on two real datasets ABIDE-I and ADHD200 confirmed the effectiveness of the proposed method. Our model has been open-sourced on GitHub at https://github.com/binwsh/GAN-for-Neural-Graph.

While depression is rated as the most important leading factor to global disability, early detection of depression is a non-trivial task. Existing depression detection mechanisms harvesting social media data suffer from two major limitations. First, existing solutions rely heavily on the amount, quality, and variety of content types (textual, visual, etc.) posted by users to make accurate inferences, therefore suffering from the cold-start problem when coping with users with limited training data (e.g., most existing works exclude users with fewer than 25 tweets). Second, existing approaches ignore the social impact or indication from users' social circles that can be leveraged to enhance the inference results. In this paper, we present MentalSpot, a social-contagion based depression early-screening framework using meta-learning. Specifically, we first construct a social-contagion driven data repository PsycheNet, filling the void of social-circle based depression datasets. We design a triplet network to extract users' embeddings based on the similarities of the linguistic features extracted from written texts. Afterwards, for each target user, we employ dynamic mean shift pruning to select her top-k homogeneous friends in the metric space, the texts written by whom will then be leveraged to train a friend based depression detection model. Extensive experiments show that MentalSpot outperforms the state of the art in terms of all effectiveness metrics, especially for users with very few tweets. Specifically, by using only five tweets per user, MentalSpot successfully yields an F1 score that would otherwise be achieved by the state-of-the-art methods requiring at least twenty tweets. Our approach represents a step forward to address the cold-start problem that deep learning techniques struggle with for their applications in psychiatric diagnosis. The principal beneficiaries of this study are healthcare professionals in medical institutions to determine timely and targeted interventions in a clinical setting. This study also supports non-profit groups in reaching out to people with mental health issues, helping in a global health task that cannot be fully covered by clinicians.

Knowing the locations of tweets can benefit a wide variety of applications such as venue recommendation, event detection, and monitoring disaster outbreaks. However, the problem of fine-grained tweet geolocation prediction is challenging since tweets are short and therefore may not contain any geo-indicative words or may contain ambiguous, noisy information. Existing solutions either yield an unsatisfactory accuracy in practical applications or make predictions that even experts struggle to interpret, failing to engender sufficient trust and actionability for real-world deployment. Our paper presents a tweet geolocation prediction framework, EDGE (Entity-Diffusion Gaussian Ensemble), which delivers predictions that are both accurate and highly interpretable without requiring any additional contextual information such as user profile and location history. In EDGE, we cast the geolocation problem as a neutral network optimization problem by learning probabilistic generative models. Compared with existing works, EDGE has two distinctive features: (1) the inference builds on mining the correlation between non geo-indicative entities and geo-indicative entities by diffusing their semantic embeddings over the constructed graph neural network (Entity Diffusion) and (2) each prediction result is represented as a Gaussian mixture instead of specific geographical coordinates (Gaussian Ensemble). Extensive experiments using real-world tweet datasets validate the superiority of EDGE over the state of the art in terms of all distance-based and POI-based metrics.

Real-time traffic prediction is essential for mitigating traffic congestion and reducing travel time. Recent advancement in graph convolutional network (GCN) has motivated a series of GCN-based models for traffic forecasting on an urban road network. However, these graph-based methods cannot capture the intricate dependencies of consecutive road segments such as no left turn, and dynamic spatial dependency. In this paper, we propose Trajectory WaveNet, or T-wave in short, a traffic forecasting model that utilizes the actual vehicle trajectories to capture the above intricate dependencies to improve prediction performance. Both trajectories and traffic data are obtained from the floating car data collected by ridesharing companies such as DiDi. T-wave treats vehicle trajectories as first-class citizens, and applies dilated causal convolutions along both the temporal dimension (i.e., recent, daily-periodic and weekly-periodic historical traffic data) and the spatial dimension (i.e., trajectories). For effective training, a trajectory mini-batch sampling technique is devised considering both spatial and temporal proximity. Extensive experiments on real datasets show that T-wave consistently bests the state-of-the-art models.

Ridesharing companies such as Ube and DiDi provide ride-hailing services where passengers and drivers are matched via mobile apps. As a result, large amounts of vehicle trajectories and vehicle speed data are collected that can be used for traffic prediction. The recent popularity of graph convolutional networks (GCNs) has opened up new possibilities for real-time traffic prediction and many GCN-based models have been proposed to capture the spatial correlation on the urban road network. However, the graph-based approaches fail to capture the intricate dependencies of consecutive road segments that are well captured by trajectories.

Activity recognition using ubiquitous wearable devices (e.g., smartphones, smartwatches and sport bracelets) can be applied to many application domains such as healthcare, smart environments, assisted living, human-computer interaction, surveillance etc. Most existing activity recognition approaches require users to provide each activity a sufficient amount of annotations (labels) in order to achieve acceptable performance and therefore often fail to scale to a large number of activities by recognizing new (emerging) activities. To tackle this limitation, the systems requiring limited training data are much desired. However, existing activity recognition solutions on limited training data rely heavily on low-level activity or attribute extraction and therefore suffer from two major limitations: (1) failing to work well when activities are highly similar to each other, such as jogging, running, and jumping front and back, and (2) leading to overall system performance degradation on recognizing existing activities with sufficient training data. In this paper, we introduce SMART, a unified semi-supervised framework for recognizing highly similar emerging activities without sacrificing the performance on recognizing existing activities. Extensive experiments on real-world data showed that compared to the state of the art, SMART yielded superior performance on recognizing emerging activities, especially highly similar emerging activities, while providing comparable performance on recognizing existing activities.

In mobile crowdsourcing, workers are financially motivated to perform self-selected tasks to maximize their revenue. Unfortunately, the existing task scheduling approaches in mobile crowdsourcing fail to scale for massive tasks and large geographic areas. We present Turbo-GTS, a system that assigns tasks to each worker to maximize the total number of the tasks that can be completed for an entire worker group while taking into account various spatial and temporal constraints, such as task execution duration, task expiration time, and worker/task geographic locations. The core of Turbo-GTS is WBT-NNH and WBT-NUD, our two newly developed scheduling algorithms, which build on the algorithms, QT-NNH and QT-NUD, proposed in our prior work [5]. The key idea is that Turbo-GTS performs dynamic workload balancing among all workers using the proposed Workload-balancing Bisection Tree (WBT) in support of large-scale Geo-Task Scheduling (GTS). Turbo-GTS includes an interactive interface for users to load the current task/worker distributions and compare the task assignment of each worker returned by different algorithms in a real-time fashion. Using the Foursquare mobile user check-in data in New York City and Tokyo, we show the superiority of Turbo-GTS over the state of the art in terms of the total number of the tasks that can be accomplished by the entire worker group and the corresponding running time. We also demonstrate the front-end interface of Turbo-GTS with two exploratory use cases in New York City.

In this paper, we study the problem of recommending time-sensitive location sequence for mobile users using their check-in data on location-based social networks. Most of the existing studies on Point of Interest (POI) recommendation and prediction fail to address the following two key challenges: (1) how to handle the scenario where the user-location matrix is very sparse (i.e., each user has a very limited number of check-ins, or to say, cold-start users), and (2) how to recommend an optimal time-sensitive visit sequence where each venue matches a time slot specified by users, based on their check-in histories. Motivated by the two challenges above, we propose a predictive framework that enables time-sensitive location sequence recommendation leveraging both the users' semantic and spatial similarities, especially for cold-start users. Our novel framework consists of three modules: semantic similarity modeling, spatial similarity modeling, and on-line sequence recommendation. In semantic modeling, we calculate users' similarity scores by comparing users' temporal hierarchical semantic trees. In spatial modeling, we use Gaussian Mixture Model (GMM) to compute users' similarity scores with respect to their geographical movement paterns. Aferwards, we combine the check-in data of the target user with those of her top-k most similar users in terms of both semantic and spatial similarities to train a personalized Hidden Markov Model (HMM) to predict the most probable venue category for each specified time slot. At last, we recommend location sequence based on the predicted venue category sequence for the target user using geographical mapping.

In mobile crowdsourcing, workers are financially motivated to perform as many self-selected tasks as possible to maximize their revenue. Unfortunately, the existing task scheduling approaches in mobile crowdsourcing fail to consider task execution duration and do not scale for massive tasks and large geographic areas (e.g., a whole city). In this paper, we study on the geo-task scheduling problem (GTS) under the various spatial and temporal constraints in real-world mobile crowdsourcing applications, including task execution duration and task expiration time. Given the location of a worker, the goal of our study is to find an optimal task execution sequence that maximizes the number of tasks that could be finished. Since the exact solution to the maximum task scheduling is computationally intractable, we propose two sub-optimal approaches (LCPF and NUD-IC) based on the particle filtering and the DBSCAN clustering.

Link prediction is a fundamental problem in social network analysis. Although the link prediction problem is not new, the challenge of how to exploit various existing network information, such as network structure data and node attribute data, to enable AI-style knowledge inference for large social networks still remains unsolved. In this paper, we design and implement a scalable framework that treats link prediction as knowledge reasoning using Markov Logic Networks (MLNs). Differing from other probabilistic graphical models, MLNs allow undirected relationships with cycles and long-range (non-adjacent) dependency, which are essential and abound in social networks. In our framework, the prior knowledge is captured as the structure dependency (such as friendship) and the attribute dependency (such as social communities) in terms of inference rules, associated with uncertainty represented as probabilities. Next, we employ the random walk to discover the inference subgraph, on which probabilistic inference is performed, so that the required computation and storage cost can be significantly reduced without much sacrifice of the inference accuracy. Our extensive experiments with real-world datasets verify the superiority of our proposed approaches over two baseline methods and show that our approaches are able to provide a tunable tradeoff between inference accuracy and efficiency.

In this paper, we propose two parameterized frameworks, namely the Uniform Watchtower (UW) framework and the Hot zone-based Watchtower (HW) framework, for the evaluation of spatial queries on large road networks. The motivation of this research is twofold: (1) how to answer spatial queries efficiently on large road networks with massive POI data and (2) how to take advantage of social data in spatial query processing. In UW, the network traversal terminates once it acquires the Point of Interest (POI) distance information stored in watchtowers. In HW, by observing that users' movements often exhibit strong spatial patterns, we employ probabilistic clustering to model mobile user check-in data as a mixture of 2-dimensional Gaussian distributions to identify hot zones so that watchtowers can be deployed discriminatorily. Our analyses verify the superiority of HW over UW in terms of query response time.

As one of the most important Semantic Web applications, social network analysis has attracted more and more interest from researchers due to the rapidly increasing availability of massive social network data. A desired solution for social network analysis should address the following issues. First, in many real world applications, inference rules are partially correct. An ideal solution should be able to handle partially correct rules. Second, applications in practice often involve large amounts of data. The inference mechanism should scale up towards large-scale data. Third, inference methods should take into account probabilistic evidence data because these are domains abounding with uncertainty. Various solutions for social network analysis have existed for quite a few years; however, none of them support all the aforementioned features. In this paper, we design and implement LinkProbe, a prototype to quantitatively predict the existence of links among nodes in large-scale social networks, which are empowered by Markov Logic Networks (MLNs). MLN has been proved to be an effective inference model which can handle complex dependencies and partially correct rules. More importantly, although MLN has shown acceptable performance in prior works, it is also reported as impractical in handling large-scale data due to its highly demanding nature in terms of inference time and memory consumption. In order to overcome these limitations, LinkProbe retrieves the k-backbone graphs and conducts the MLN inference on both the most globally influencing nodes and most locally related nodes. Our extensive experiments show that LinkProbe manages to provide a tunable balance between MLN inference accuracy and inference efficiency.

The past few years have witnessed the emergence of an increasing number of applications for tracking and tracing based on radio frequency identification (RFID) technologies. However, raw RFID readings are usually of low quality and may contain numerous anomalies. An ideal solution for RFID data cleansing should address the following issues. First, in many applications, duplicate readings of the same object are very common. The solution should take advantage of the resulting data redundancy for data cleaning. Second, prior knowledge about the environment may help improve data quality, and a desired solution must be able to take into account such knowledge. Third, the solution should take advantage of physical constraints in target applications to elevate the accuracy of data cleansing. There are several existing RFID data cleansing techniques. However, none of them support all the aforementioned features. In this paper, we propose a Bayesian inference-based framework for cleaning RFID raw data. We first design an n-state detection model and formally prove that the three-state model can maximize the system performance. Then, we extend the n-state model to support two-dimensional RFID reader arrays and compute the likelihood efficiently. In addition, we devise a Metropolis-Hastings sampler with constraints, which incorporates constraint management to clean RFID data with high efficiency and accuracy. Moreover, to support real-time object monitoring, we present the streaming Bayesian inference method to cope with realtime RFID data streams. Finally, we evaluate the performance of our solutions through extensive experiments.

The techniques of utilizing spatial data on the Semantic Web have attracted more and more interest from researchers due to the rapidly increasing applications based on geographic information. However, there are currently limited solutions providing efficient spatial query evaluation based on Semantic Web data. In this demonstration, we present Geo-Store, a novel spatially-augmented SPARQL evaluation system. By extending the standard SPARQL query language with spatial query filters, Geo-Store is able to process complex spatial queries with common spatial constraints. These spatial filters are designed based on our Spatially Aware Mapping (SAM) scheme. With SAM, spatial data are pre-processed and encoded with their Hilbert values by employing the Hilbert curve, resulting in more efficient spatial query processing than the existing approaches. The Geo-Store demonstration includes both a server and a web browser-based client.

Data uncertainty arises in many situations. A common approach to query processing uncertain data is to sample many "possible worlds" from the uncertain data and to run queries against the possible worlds. However, sampling is not a trivial task, as a randomly sampled possible world may not satisfy known constraints imposed on the data. In this paper, we focus on an important category of constraints, the aggregate constraints. An aggregate constraint is placed on a set of records instead of on a single record, and a real-life system usually has a large number of aggregate constraints. It is a challenging task to find qualified possible worlds in this scenario, since tuple by tuple sampling is extremely inefficient because it rarely leads to a qualified possible world. In this paper, we introduce two approaches for querying uncertain data with aggregate constraints: constraint aware sampling and MCMC sampling. Our experiments show that the new approaches lead to high quality query results with reasonable cost.

Radio Frequency Identification (RFID) technologies are used in many applications for data collection. However, raw RFID readings are usually of low quality and may contain many anomalies. An ideal solution for RFID data cleansing should address the following issues. First, in many applications, duplicate readings (by multiple readers simultaneously or by a single reader over a period of time) of the same object are very common. The solution should take advantage of the resulting data redundancy for data cleaning. Second, prior knowledge about the readers and the environment (e.g., prior data distribution, false negative rates of readers) may help improve data quality and remove data anomalies, and a desired solution must be able to quantify the degree of uncertainty based on such knowledge. Third, the solution should take advantage of given constraints in target applications (e.g., the number of objects in a same location cannot exceed a given value) to elevate the accuracy of data cleansing. There are a number of existing RFID data cleansing techniques. However, none of them support all the aforementioned features. In this paper we propose a Bayesian inference based approach for cleaning RFID raw data. Our approach takes full advantage of data redundancy. To capture the likelihood, we design an n-state detection model and formally prove that the 3-state model can maximize the system performance. Moreover, in order to sample from the posterior, we devise a Metropolis-Hastings sampler with Constraints (MH-C), which incorporates constraint management to clean RFID raw data with high efficiency and accuracy. We validate our solution with a common RFID application and demonstrate the advantages of our approach through extensive simulations.

The k-anonymity technique is widely used to provide location privacy protection for accessing location-based services (LBS), i.e., the exact location of a query initiator is cloaked into a spatial region that contains at least k indistinguishable users. However, a centralized location anonymizer may pose serious privacy threats and could be the system bottleneck. Moreover, many cloaking methods are developed for the Euclidean space and fail to consider the features of road networks. In this demonstration, we present the technologies and implementations which protect location privacy by peer-to-peer based cloaking on road networks. We name the prototype system as PROS. With PROS, a mobile user forms a cloaked road segment set by collaborating with her peers when she needs to retrieve information from location-based service providers. Afterward, the cloaked road segment set is sent to the service provider for query processing and an inclusive query result set is returned to the query initiator after the query evaluation.

Trip planning search (TPS) represents an important class of queries in Geographic Information Systems (GIS). In many real-world applications, TPS requests are issued with a number of constraints. Unfortunately, most of these constrained TPS cannot be directly answered by any of the existing algorithms. By formulating each restriction into rules, we propose a novel form of route query, namely the multi-rule partial sequenced route (MRPSR) query. Our work provides a unified framework that also subsumes the well-known trip planning query (TPQ) and the optimal sequenced route (OSR) query. In this paper, we first prove that MRPSR is NP-hard and then present three heuristic algorithms to search for near-optimal solutions for the MRPSR query. Our extensive simulations show that all of the proposed algorithms can answer the MRPSR query effectively and efficiently. Using both real and synthetic datasets, we investigate the performance of our algorithms with the metrics of the route distance and the response time in terms of the percentage of the constrained points of interest (POI) categories. Compared to the LORD-based brute-force solution, the response times of our algorithms are remarkably reduced while the resulting route length is only slightly longer than the shortest route.