Public transportation plays a vital role in supporting sustainable, accessible, environment-friendly, and equitable urban mobility. However, challenges such as poor first- and last-mile connectivity, limited service coverage, and inefficient use of space continue to limit its effectiveness and uptake. Autonomous vehicles (AVs) offer new opportunities to address these limitations by enhancing flexibility, improving access, and complementing existing transit systems. This vision paper explores how a diverse fleet of AVs, including cars, shuttles, pods, scooters, and buses, can be integrated into public transport to form an adaptive, multimodal, and data-driven mobility ecosystem. We outline key research directions spanning fleet coordination, spatial deployment, infrastructure planning, and intelligent transportation platforms. We highlight the need for interdisciplinary research at the intersection of spatial computing, transportation systems, artificial intelligence, and urban data infrastructure. Our aim is to inform and inspire future efforts toward building autonomous mobility systems that are efficient, inclusive, and future-ready.

The advancement of indoor location-aware technologies enables a wide range of location based services in indoor spaces. In this paper, we formulate a novel Indoor Facility Location Selection (IFLS) query that finds the optimal location for placing a new facility (e.g., a coffee station) in an indoor venue (e.g., a university building) such that the maximum distance of all clients (e.g., staffs/students) to their nearest facility is minimized. To the best of our knowledge we are the first to address this problem in an indoor setting. We first adapt the state-of-the-art solution in road networks for indoor settings, which exposes the limitations of existing approaches to solve our problem in an indoor space. Therefore, we propose an efficient approach which prunes the search space in terms of the number of clients considered, and the total number of facilities retrieved from the database, thus reducing the total number of indoor distance calculations required. The key idea of our approach is to use a single pass on a state-of-the-art index for an indoor space, and reuse the nearest neighbor computation of clients to prune irrelevant facilities and clients. We evaluate the performance of both approaches on four indoor datasets. Our approach achieves a speedup from 2.84× to 71.29× for synthetic data and 97.74× for real data over the baseline.

With the advent of location-based social networks, users can tag their daily activities in different locations through check-ins. These check-in locations signify user preferences for various socio-spatial activities and can be used to improve the quality of services in some applications such as recommendation systems, advertising, and group formation. To support such applications, in this paper, we formulate a new problem of identifying top-k Socio-Spatial co-engaged Location Selection (SSLS) for users in a social graph, that selects the best set of k locations from a large number of location candidates relating to the user and her friends. The selected locations should be (i) spatially and socially relevant to the user and her friends, and (ii) diversified both spatially and socially to maximize the coverage of friends in the socio-spatial space. To address the NP-hard and challenging problem, we first develop an exact solution by designing some pruning strategies, and also develop an approximate solution by deriving relaxed bounds and advanced termination rules. To accelerate the efficiency, we further develop a fast exact approach and a meta-heuristic approximate approach. Finally, extensive experiments are conducted to evaluate the performance of our proposed algorithms against three adapted existing methods using four real-world datasets.

Trip itinerary recommendation finds an ordered sequence of Points-of-Interest (POIs) from a large number of candidate POIs in a city. In this paper, we propose a deep learning-based framework, called DeepAltTrip, that learns to recommend top-$k$alternative itineraries for given source and destination POIs. These alternative itineraries would be not only popular given the historical routes adopted by past users but also dissimilar (or diverse) to each other. The DeepAltTrip consists of two major components: (i)Itinerary Net(ITRNet) which estimates the likelihood of POIs on an itinerary by using graph autoencoders and two (forward and backward) LSTMs; and (ii) a route generation procedure to generate$k$diverse itineraries passing through relevant POIs obtained using ITRNet. For the route generation step, we propose a novel sampling algorithm that can seamlessly handle a wide variety of user-defined constraints. To the best of our knowledge, this is the first work thatlearnsfrom historical trips to provide a set of alternative itineraries to the users. Extensive experiments conducted on eight popular real-world datasets show the effectiveness and efficacy of our approach over state-of-the-art methods.

Computing multiple alternative routes from a source$s$to a target$t$has received significant research attention. However, it is unclear which of the existing approaches generates alternative routes of better quality because the quality of these alternatives is mostly subjective. Motivated by this, in this paper, we present a user study conducted on the road networks of Melbourne, Dhaka and Copenhagen comparing four of the most popular existing approaches including Google Maps. We report the average ratings received by the four approaches, and our statistical analysis shows that there is no credible evidence that the four approaches receive different ratings on average. We also discuss the limitations of this user study and recommend the readers interpret these results with caution.

Many modern navigation systems and map-based services do not only provide the fastest route from a source location$s$to a target location$t$but also provide a few alternative routes to the users as more options to choose from. Consequently, computing alternative paths has received significant research attention. However, it is unclear which of the existing approaches generates alternative routes of better quality because the quality of these alternatives is mostly subjective. Motivated by this, in this paper, we present a user study conducted on the road networks of Melbourne, Dhaka and Copenhagen that compares the quality (as perceived by the users) of the alternative routes generated by four of the most popular existing approaches including the routes provided by Google Maps. We also present a web-based demo system that can be accessed using any internet-enabled device and allows users to see the alternative routes generated by the four approaches for any pair of selected source and target. We report the average ratings received by the four approaches and our statistical analysis shows that there is no credible evidence that the four approaches receive different ratings on average. We also discuss the limitations of this user study and recommend the readers to interpret these results with caution because certain factors may have affected the participants’ ratings.

In this paper, we propose an iterative approach to estimate the frequent itemsets with high accuracy while satisfying the local differential privacy (LDP). The key component behind the improved accuracy of the estimated frequent itemsets by our approach is our novel two-level randomization technique for guaranteeing the LDP. Our randomization technique exploits the correlation of the presence of items in a user’s itemset, which has not been considered before. We present a mathematical proof that shows that our approach satisfies the LDP constraint. Extensive experiments are performed to validate the effectiveness and efficiency of our proposed algorithms using real datasets.

In this demonstration, we present a web based system for the novel contact tracing query (CTQ) that finds users who have come into direct contact with the query user or indirect contact via the already contacted users from a large spatio-temporal database. The CTQ is of paramount importance in the era of new COVID-19 pandemic world for identifying people who came into close spatial and temporal proximity with persons carrying an infectious disease. We demonstrate a multi-level index named QzR-tree, that considers the space coverage and the co-visiting patterns of the trajectories to group users who are likely to meet. More specifically, we use a quadtree to partition user movement traces along with a linear ordering and use the space-time mapping to group users with an R-tree. We develop a web-based demo system to show the effectiveness of the QzR-tree for the CTQ. The web-based system essentially uses a PostgreSQL database to store user trajectories, and indexes these trajectories using the QzR-tree, and finally uses a web interface to take user query and display the results in a map.

Given a set of obstacles in 2D or 3D space, a set of n candidate locations where facilities can be established, the Maximum Visibility Facility Selection (MVFS) query finds k out of the n locations, that yield the maximum visibility coverage of the data space. Though the MVFS problem has been extensively studied in visual sensor networks, computational geometry, and computer vision in the form of optimal camera placement problem, existing solutions are designed for discretized space and only work for MVFS instances having a few hundred facilities. In this paper, we revisit the MVFS problem to support new spatial database applications like "where to place security cameras to ensure better surveillance of a building complex?" or "where to place billboards in the city to maximize visibility from the surrounding space?". We introduce the concept of equivisibility triangulation to devise the first approach to accurately determine the visibility coverage of continuous data space from a subset of the facility locations, which avoids the limitations of discretizing the data space. Then, we propose an efficient graph-theoretic approach that exploits the idea of vertex separators for efficient exact in-memory solution of the MVFS problem. Finally, we propose the first external-memory based approximation algorithm (with a guaranteed approximation ratio of 1 - 1/e) that is scalable for a large number of obstacles and facility locations. We conduct extensive experimental study to show the effectiveness and efficiency of our proposed algorithms.

Basic human values represent what we think are important to our lives that include security, independence, success, kindness, and pleasure. Each of us holds different values with different degrees of importance. Existing studies show that values of a person can be identified from their social network usage. However, the value priority of a person may change over time due to different factors such as time, event, influence, social structure, and technology. In this research, we are the first to investigate whether the change of value priorities can be identified from social network usage. We propose a weighted hybrid time‐series‐based model to capture the change of values of a social network user. We conducted an experimental study with 726 Facebook users and showed that our model accurately captures the value priority changes from the social network usage and achieves significantly higher accuracy than our baseline hidden Markov model‐based technique. We also validated the change of a user's value priorities in real life using a questionnaire‐based technique.

With the widespread use of GPS-enabled mobile devices, an unprecedented amount of trajectory data has become available from various sources such as Bikely, GPS-wayPoints, and Uber. The rise of smart transportation services and recent break-throughs in autonomous vehicles increase our reliance on trajectory data in a wide variety of applications. Supporting these services in emerging platforms requires more efficient query processing in trajectory databases. In this paper, we propose two new coverage queries for trajectory databases: (i) k Best Facility Trajectory Search ( k BFT); and (ii) k Best Coverage Facility Trajectory Search ( k BCovFT). We propose a novel index structure, the Trajectory Quadtree (TQ-tree) that utilizes a quadtree to hierarchically organize trajectories into different nodes, and then applies a z-ordering to further organize the trajectories by spatial locality inside each node. This structure is highly effective in pruning the trajectory search space, which is of independent interest. By exploiting the TQ-tree, we develop a divide-and-conquer approach to efficiently process a k BFT query. To solve the k BCovFT, which is a non-submodular NP-hard problem, we propose a greedy approximation. We evaluate our algorithms through an extensive experimental study on several real datasets, and demonstrate that our algorithms outperform baselines by two to three orders of magnitude.

A socio spatial group query finds a group of users who possess strong social connections with each other and have the minimum aggregate spatial distance to a meeting point. Existing studies limit to either finding the best group of a fixed size for a single meeting location, or a single group of a fixed size w.r.t. multiple locations. However, it is highly desirable to consider multiple locations in a real-life scenario in order to organize impromptu activities of groups of various sizes. In this paper, we propose Top k Flexible Socio Spatial Group Query (Top k-FSSGQ) to find the top k groups w.r.t. multiple POIs where each group follows the minimum social connectivity constraints. We devise a ranking function to measure the group score by combining social closeness, spatial distance, and group size, which provides the flexibility of choosing groups of different sizes under different constraints. To effectively process the Top k-FSSGQ, we first develop an Exact approach that ensures early termination of the search based on the derived upper bounds. We prove that the problem is NP-hard, hence we first present a heuristic based approximation algorithm to effectively select members in intermediate solution groups based on the social connectivity of the users. Later we design a Fast Approximate approach based on the relaxed social and spatial bounds, and connectivity constraint heuristic. Experimental studies have verified the effectiveness and efficiency of our proposed approaches on real datasets.

Basic Human Values represent a set of values such as security, independence, success, kindness, and pleasure what we think are important to our lives. Each of us holds different values with different degrees of importance. Existing studies show that values of a person can be identified from her social network usage. However, the value priority of a person may change over time due to different factors such as time, event, influence, social structure, and technology. In this research, we are the first to investigate whether the change of value priorities can be identified from social network usage. We have proposed a HMM based technique to capture the change of values of a person.

In this demonstration, we present VizQ, an efficient, scalable, and interactive system to process and visualize a comprehensive collection of novel visibility queries in the presence of obstacles in 3D space. Specifically, we demonstrate four types of query processing: (i) k Maximum Visibility Query (kMVQ), that finds k locations with the maximum visibility of a target object (ii) Visibility Color Map (VCM), where each point in the space is assigned a color value denoting the visibility measure of the target (iii) Continuous Maximum Visibility (CMV) that continuously finds the location that provides the best view of a moving target, and (iv) Text Visibility Color Map (TVCM), where VCM is generated considering readability of text data displayed on a target. We are the first to propose efficient algorithms to run all of the above four types of visibility queries in the context of a large number of 3D obstacle database. We exploit human visibility metrics to design our data structures and algorithms to efficiently process queries, and our approaches outperform baseline approaches in several order of magnitude both in terms of I/Os and processing time. The link of our demonstration video is https://youtu.be/rcizJtFvQfU.

We address the problem of efficient maintenance of the answer to a new type of query: Continuous Maximizing Range- Sum (Co-MaxRS) for moving objects trajectories. The traditional static/spatial MaxRS problem finds a location for placing the centroid of a given (axes-parallel) rectangle R so that the sum of the weights of the point-objects from a given set O inside the interior of R is maximized. However, moving objects continuously change their locations over time, so the MaxRS solution for a particular time instant need not be a solution at another time instant. In this paper, we devise the conditions under which a particular MaxRS solution may cease to be valid and a new optimal location for the query-rectangle R is needed. More specifically, we solve the problem of maintaining the trajectory of the centroid of R. In addition, we propose efficient pruning strategies (and corresponding data structures) to speed-up the process of maintaining the accuracy of the Co-MaxRS solution. We prove the correctness of our approach and present experimental evaluations over both real and synthetic datasets, demonstrating the benefits of the proposed methods.

The rise of innovative transportation services and the recent breakthrough in the development of autonomous vehicles have stimulated the research on collective travel planning problems such as ride-sharing, carpooling, and on-demand vehicle routing in recent years. In this paper, we introduce several optimization problems to recommend a suitable route and stops of a vehicle, in a road network, for a group of users intending to travel collectively. The goal of each problem is to minimize the aggregate cost of the individual travelers' paths and the shared route under various constraints. First, we introduce the optimal end-stops (OES) query that finds a pair of pick-up-and-drop-off locations such that the sum of the distance between these locations and the total distance traveled by the travelers from their start locations to the pick-up location and from the drop-off location to their end locations is minimized. We propose a polynomial-time fast algorithm for the OES query by utilizing the path-coherence property of road networks. Second, we formulate the optimal route and intermediate stops (ORIS) query to find a set of intermediate stops for the vehicle such that the sum of the total distance traveled by the vehicle and the total distance traveled by the travelers from their start locations to one of the stops and to their end locations from one of the stops is minimized. We propose a novel near-optimal polynomial-time-and-space heuristic algorithm for the ORIS query that performs reasonably well in practice. We also analyze several variants of this problem. Finally, we perform extensive experiments to demonstrate the efficiency and efficacy of our algorithms.

We address the problem of maintaining the correct answer-sets to the Conditional Maximizing Range-Sum (C-MaxRS) query in spatial data streams. Given a set of (possibly weighted) 2D point objects, the traditional MaxRS problem determines an optimal placement for an axes-parallel rectangle r so that the number -- or, the weighted sum -- of objects in its interior is maximized. In many practical settings, the objects from a particular set -- e.g., restaurants -- can be of distinct types -- e.g., fast-food, Asian, etc. The C-MaxRS problem deals with maximizing the overall sum, given class-based existential constraints, i.e., a lower bound on the count of objects of interests from particular classes. We first propose an efficient algorithm to the static C-MaxRS query, and extend the solution to handle dynamic (data streams) settings. Our experiments over datasets of up to 100,000 objects show that the proposed solutions provide significant efficiency benefits.

Contemporary modern world has witnessed the widespread emergence of online social media and similar technologies. Peoples' behaviour over different social network platform has become an interesting topic of research. In this study, we investigate whether people express analogous identity over different platforms and analysis of different social platform usage contributes to reveal more of a person. We analyse people's usage pattern in two major online platforms, the most widely used social media platform Twitter and a major online commenting platform Disqus. We extract linguistic features and infer personality traits from both of these platforms. Our study reveals differential relationship between personality traits and Disqus and Twitter usage. We also find that social media has an influence on a person's discussion topic. People share opinion on varieties of topics and entities exclusively in Twitter and Disqus. Moreover Disqus provides stronger assessment of a person's sentiment over a topic or entity. Combination of these two profiles gives an extensive view of a user's interest and sensitivity which justify the inference that people use different social network for different purposes and single social network analysis is not enough to build a comprehensive virtual identity of a person.

A group of friends located at their working places may want to plan a trip to visit a shopping center, have dinner at a restaurant, watch a movie at a theater, and then finally return to their homes with the minimum total trip distance. For a group of spatially dispersed users a group trip planning (GTP) query returns points of interests (POIs) of different types such as a shopping center, a restaurant and a movie theater that minimize the aggregate trip distance for the group. The aggregate trip distance could be the sum or maximum of the trip distances of all users in the group, where the users travel from their source locations via the jointly visited POIs to their individual destinations. In this paper, we develop both optimal and approximation algorithms for GTP queries for both Euclidean space and road networks. Processing GTP queries in real time is a computational challenge as trips involve POIs of multiple types and computation of aggregate trip distances. We develop novel techniques to refine the POI search space for a GTP query based on geometric properties of ellipses, which in turn significantly reduces the number of aggregate trip distance computations. An extensive set of experiments on a real and synthetic datasets shows that our approach outperforms the most competitive approach on an average by three orders of magnitude in terms of processing time.

The recent advancement of GPS-enabled mobile technologies and the proliferation of map-based applications are attracting an increasing number of people to use location based services (LBSs). Processing a larger number of simultaneous queries efficiently have become an important research topic in recent years. In this paper, we focus on an important class of LBSs, shortest path queries (SP-queries) in road networks. Given a source and a destination in a road network, an SP-query returns the path from the source to the destination that minimizes the travel time. We particularly focus on batch processing of simultaneous SP-queries in road networks. Traditional systems that process one query at a time usually provide slow responses, causing the machine to flood with incoming queries. Existing fast solutions for SP-queries require expensive pre-processing steps and are incapable of adapting with the continuous change in traffic on the roads. We propose an efficient group based approach that provides an approximate solution with reduced cost and high accuracy. An important benefit of our approach is that it does not require expensive pre-processing. The key concept is to exploit the path-coherence property of road networks by grouping queries that share substantial common paths in their shortest paths and processing the group in a single pass. Our approach incurs an average relative error of 0.5% and is on average 6 times faster than the straightforward approach that evaluates each SP-query individually.

The proliferation of location-based social networks allows people to access location-based services as a group. We address Group Optimal Sequenced Route (GOSR) queries that enable a group to plan a trip with a minimum aggregate trip distance. The trip starts from the source locations of the group members, goes via a predefined sequence of different point of interests (POIs) such as a restaurant, shopping center and movie theater, and ends at the destination locations of the group members. The aggregate trip distance can be the total or the maximum trip distance of the group members. We introduce a novel approach to efficiently compute group optimal sequenced routes in road networks. We exploit elliptical properties to refine the POI search space and develop efficient algorithms for GOSR queries. Experiments show that our approach outperforms a naive approach significantly in terms of processing time and I/Os.

Many real-world problems, such as placement of surveillance cameras and pricing of hotel rooms with a view, require the ability to determine the visibility of a given target object from different locations. Advances in large-scale 3D modeling (e.g., 3D virtual cities) provide us with data that can be used to solve these problems with high accuracy. In this paper, we investigate the problem of finding the location which provides the best view of a target object with visual obstacles in 2D or 3D space, for example, finding the location that provides the best view of fireworks in a city with tall buildings. To solve this problem, we first define the quality measure of a view (i.e., visibility measure) as the visible angular size of the target object. Then, we propose a new query type called the k-Maximum Visibility (kMV) query, which finds k locations from a set of locations that maximize the visibility of the target object. Our objective in this paper is to design a query solution which is capable of handling large-scale city models. This objective precludes the use of approaches that rely on constructing a visibility graph of the entire data space. As a result, we propose three approaches that incrementally consider relevant obstacles in order to determine the visibility of a target object from a given set of locations. These approaches differ in the order of obstacle retrieval, namely: query centric distance based, query centric visible region based, and target centric distance based approaches. We have conducted an extensive experimental study on real 2D and 3D datasets to demonstrate the efficiency and effectiveness of our solutions.

Continuous queries in road networks have gained significant research interests due to advances in GIS and mobile computing. Consider the following scenario: "A driver uses a networked GPS navigator to monitor five nearest gas stations in a road network." The main challenge of processing such a moving query is how to efficiently monitor network distances of the k nearest and possible resultant objects. To enable result monitoring in real-time, researchers have devised techniques which utilize precomputed distances and results, e.g., the network Voronoi diagram (NVD). However, the main drawback of preprocessing is that it requires access to all data objects and network nodes, which means that it is not suitable for large datasets in many real life situations. The best existing method to monitor kNN results without precomputation relies on executions of snapshot queries at network nodes encountered by the query point. This method results in repetitive distance evaluation over the same or similar sets of nodes. In this paper, we propose a method called the local network Voronoi diagram (LNVD) to compute query answers for a small area around the query point. As a result, our method requires neither precomputation nor distance evaluation at every intersection. According to our extensive analysis and experimental results, our method significantly outperforms the best existing method in terms of data access and computation costs.

With recent advances in mobile computing technologies, mobile devices can now render 3D objects realistically. Many users of these devices such as tourists, mixed-reality gamers, and rescue officers, need real-time retrieval of 3D objects over a wireless network. Due to bandwidth and latency restrictions in mobile settings, efficient continuous retrieval of 3D objects remains a challenge. In this paper, we describe a motion-aware approach to this problem. We first introduce multi-resolution storage and retrieval methods for 3D data, which restrict access to only the necessary content based on the client's motion pattern. We then propose a motion-aware buffer management technique as well as an efficient index using multi-resolution representations of objects. Our experiments demonstrate the effectiveness of our solution to continuous retrieval of complex spatial data in mobile settings.