Computing the shortest path distances between two vertices on road networks is a core operation in many real-world applications, e.g., finding the closest taxi/hotel. However existing techniques have several limitations. First, traditional Dijkstra-based methods have long latency and cannot meet the high-performance requirement. Second, existing indexing-based methods either involve huge index sizes or have poor performance. To address these limitations, in this paper we propose a learning-based method which can efficiently compute an approximate shortest-path distance such that (1) the performance is super fast, e.g., taking 60-150 nanoseconds; (2) the error ratio of the approximate results is super small, e.g., below 0.7%; (3) scales well to large road networks, e.g., millions of nodes. The key idea is to first embed the road networks into a low dimensional space for capturing the distance relations between vertices, get an embedded vector for each vertex, and then perform a distance metric (L1metric) on the embedded vectors to approximate shortest-path distances. We propose a hierarchical model to represent the embedding, and design an effective method to train the model. We also design a fine-tuning method to judiciously select high-quality training data. Extensive experiments on real-world datasets show that our embedding based approach significantly outperforms the state-of-the-art methods.

Database exploration - the problem of finding and ranking desired tuples - is important for data discovery and analysis. Precisely specifying SQL queries is not always feasible in practice, such as "finding and ranking off-road cars based on a combination of Price, Make, Model, Age, and Mileage." - not only due to the query complexity (e.g., which may have many if-then-else, and, or and not logic), but also because the user typically does not have the knowledge of all data instances. We propose DExPlorer, a system for interactive database exploration. DExPlorer offers a simple and user-friendly interface which allows to: (1) confirm whether a tuple is desired or not, and (2) decide whether a tuple is more preferred than another. Behind the scenes, we jointly use multiple ML models to learn from the above two types of user feedback. Moreover, in order to effectively involve users, we carefully select the set of tuples for which we need to solicit feedback. Therefore, we devise question selection algorithms that consider not only the estimated benefit of each tuple, but also the possible partial orders between any two suggested tuples. Experiments on real-world datasets show that DExPlorer is more effective than existing approaches.

Spatio-temporal data analysis is very important in many time-critical applications. We take Coronavirus disease (COVID-19) as an example, and the key questions that everyone will ask every day are: how does Coronavirus spread? where are the high-risk areas? where have confirmed cases around me? Interactive data analytics, which allows general users to easily monitor and explore such events, plays a key role. However, some emerging cases, such as COVID-19, bring many new challenges: (C1) New information may come with different formats: basic structured data such as confirmed/suspected/serious/death/recovered cases, unstructured data from newspapers for travel history of confirmed cases, and so on. (C2) Discovering new insights: data visualization is widely used for storytelling; however, the challenge here is how to automatically find "interesting stories", which might be different from day to day. We propose DeepTrack, a system that monitors spatio-temporal data, using the case of COVID-19. For (C1), we describe (a) how we integrate and clean data from different sources by existing modules. For (C2), we discuss (b) how to build new modules for ad-hoc data sources and requirements, (c) what are the basic (or static) charts used; and (d) how to generate recommended (or dynamic) charts that are based on new incoming data. The attendees can use DeepTrack to interactively explore various COVID-19 cases.

Knowledge graphs are widely applied in many applications. Automatically solving mathematical exercises is also an interesting task which can be enhanced by knowledge reasoning. In this paper, we design MathGraph, a knowledge graph aiming to solve high school mathematical exercises. Since it requires fine-grained mathematical derivation and calculation of different mathematical objects, we design a crowdsourcing-based method to help build MathGraph. MathGraph supports massive kinds of mathematical objects, operations and constraints which may be involved in exercises. Furthermore, we propose an algorithm to align a semantically parsed exercise to MathGraph and figure out the answer automatically. Extensive experiments on real-world datasets verify the effectiveness of MathGraph.

Ride-sharing (RS) has great values in saving energy and alleviating traffic pressure. In this paper, we propose a new ride-sharing model, where each driver requires that the shared route percentage (SRP, the ratio of the shared route's distance to the driver's total traveled distance) exceeds her expected rate (e.g., 0.8) when sharing with a rider. We consider two variants of this problem. The first considers multiple drivers and multiple riders, and aims to compute a set of driver-rider pairs to maximize the overall SRP. We model this problem as the maximum weighted bigraph matching problem. We propose an effective exact algorithm, and an efficient approximate solution with error-bound guarantee. The second considers multiple drivers and a single rider and aims to find the top-k drivers for the rider with the largest SRP. We devise pruning techniques and propose a best-first algorithm to progressively selects drivers with high probability to be in the top-k results.

Ride-sharing (RS) has great values in saving energy and alleviating traffic pressure. Existing studies can be improved for better efficiency. Therefore, we propose a new ride-sharing model, where each driver has a requirement that if the driver shares a ride with a rider, the shared route percentage (i.e., the ratio of the shared route's distance to the driver's total travel distance) exceeds an expectation rate of the driver, e.g., 0.8. We consider two variants of this problem. The first considers multiple drivers and multiple riders and aims to compute driver-rider pairs to maximize the overall shared route percentage (SRP). We model this problem as the maximum weighted bigraph matching problem, where the vertices are drivers and riders, edges are driver-rider pairs, and edge weights are driver-rider's SRP. However, it is rather expensive to compute the SRP values for large numbers of driver-rider pairs on road networks. To address this problem, we propose an efficient method to prune many unnecessary driver-rider pairs and avoid computing the SRP values for every pair. To improve the efficiency, we propose an approximate method with error bound guarantee. The basic idea is that we compute an upper bound and a lower bound for each driver-rider pair in constant time. Then, we estimate an upper bound and a lower bound of the graph matching. Next, we select some driver-rider pairs, compute their real shortest-route distance, and update the lower and upper bounds of the maximum graph matching. We repeat above steps until the ratio of the upper bound to the lower bound is not larger than a given approximate rate. The second considers multiple drivers and a single rider and aims to find the top-$k$drivers for the rider with the largest SRP. We first prune a large number of drivers that cannot meet the SRP requirements. Then, we propose a best-first algorithm that progressively selects the drivers with high probability to be in the top-$k$results and prunes the drivers that cannot be in the top-$k$results. Extensive experiments on real-world datasets demonstrate the superiority of our method.