The computation of alternative paths for point-to-point shortest paths on time-dependent road networks has numerous practical applications. Despite its importance, there has been a lack of research in the literature addressing alternative paths in time-dependent road networks. In this paper, we present an innovative algorithm designed to generate high-quality alternative paths in a time-dependent context. Our approach leverages an existing time-dependent bidirectional A* algorithm. We first introduce an efficient method for gathering candidate alternative paths by identifying intersections between forward and backward searches. We then present a filtering approach for these candidate paths to ensure that only the highest quality alternatives are returned to the user. Simulation results confirm that our approach achieves good latency performance, returns optimal time-dependent paths, and provides high-quality alternative paths.

Modern direction services must evolve to meet the growing complexity of user queries, which increasingly resemble natural language and include nuanced constraints and preferences. This paper introduces a dynamic, query-aware route enrichment framework designed to enhance routing services by integrating real-time contextual data—such as weather, events, and POIs. The system comprises five key components: query intent understanding, hint point selection along the route, data sourcing, language model-based response generation, and caching for performance optimization. A hybrid approach combining lightweight language models and a rule-based system is used to interpret user intent, while adaptive hint logic minimizes redundant API calls. The enriched route responses can be consumed directly by user interfaces or serve as grounding data for LLM-based assistants. A demo application illustrates the system's effectiveness, showing reduced latency and high response quality. This work demonstrates the feasibility of real-time, intelligent route enrichment and lays the groundwork for future enhancements using AI agents and parallelized architectures.

Map search engines compute the estimated time of arrival (ETA) from location A to location B by first performing local routing-engine optimization over a network of road segments. Once the optimal route candidates are identified their ETA is reevaluated with global post-routing ETA (PostETA) models capable of correcting multiple accumulated local biases. Sequence models have emerged as the state of the art post-routing ETA predictors, however, they are usually applied as regressors fitting a single ETA value. Here we demonstrate that a route can have very different travel times for different drivers even when measured at approximately the same starting time. Fitting a distribution then, instead of a single value, and returning to users both an expectation over ETA together with a confidence range is more accurate and informative. We propose a novel PostETA system including a set of sequence-to-sequence attention models capable of fitting the route ETA distribution. On a data set of over a hundred thousand user trips we demonstrate that the system achieves accuracy comparable to that of regression models, providing in addition an accurate estimate for the variance of the ETA prediction.

Recent works show that Transformer-based learning-to-rank (LTR) approaches can outperform previous well-established ranking methods, such as gradient-boosted decision trees (GBDT), on document and passage re-ranking problems. A common assumption in these works is that the query and the result documents are comprised of purely textual information without explicit structure. In map search, the relevance of results is determined based on rich heterogeneous features - textual features derived from the query and the results, geospatial features such as proximity of a result to the user, structured features reflecting the address format of the result, and the perceived structure of the query. In this work, we propose a novel deep neural network LTR architecture, capable of seamlessly handling heterogeneous inputs, similar to GBDT-based methods. At the same time, unlike GBDT, the architecture does not require human input via (numerous) carefully-crafted features. Instead, features are inferred through a self-attention mechanism. Our model implements two lightweight attention layers optimized for ranking: the first layer computes query-result similarities, the second implements listwise ranking inference. We perform evaluation on several single language and one multilingual dataset. Our model outperforms by a wide margin other Transformer-based ranking architectures and has equal or better performance than GBDT models. Equally important, runtime inference is orders of magnitude faster than other Transformer architectures, significantly reducing hardware serving costs. The model is a low-cost alternative suitable to power ranking in industrial map search engines across a variety of languages and markets.

Inferring user behavior patterns in their daily location visits, i.e., where people go and how long they stay there, enables a variety of useful applications such as time management systems, new location recommendations, and the opportunity for analytics. For example, digital assistants can use inferred daily patterns to automate calendar events for users, or notify users about anticipated traffic conditions to their predicted next location. Retailers, on the other hand, can use the patterns to do location-based recommendations of venues similar or in proximity of the ones anticipated to be visited.

Predicting users daily location visits - when and where they will go, and how long they will stay - is key for making effective location-based recommendations. Knowledge of an upcoming day allows the suggestion of relevant alternatives (e.g., a new coffee shop on the way to work) in advance, prior to a visit. This helps users make informed decisions and plan accordingly.

Image search is a popular application on web search engines. Issuing a location-related query on an image search engine often returns multiple images of maps among the top ranked results. Traditionally, clicking on such images either opens the image in a new browser tab or takes users to a web page containing the image. However, finding the area of intent on an interactive web map (e.g., Bing Maps) is a manual process. In this paper, we describe a novel system, LiveMaps, for analyzing and retrieving an appropriate map viewport for a given image of a map. This provides annotation of images of maps returned by image search engines, allowing users to directly open a link to an interactive map centered on the location of interest.

Image search is a popular application on web search engines. Issuing a location-related query in image search engines often returns multiple images of maps among the top ranked results. Traditionally, clicking on such images either opens the image in a new browser tab or takes users to a web page containing the image. However, finding the area of intent on an interactive web map is a manual process. In this paper, we describe a novel system, LiveMaps, for analyzing and retrieving an appropriate map viewport for a given image of a map. This allows annotation of images of maps returned by image search engines, allowing users to directly open a link to an interactive map centered on the location of interest.

Real-time geocoders help users find precise locations in online mapping systems. Geocoding unstructured queries can be difficult, as users may describe map locations by referencing several spatially co-located entities (e.g., a business near a street intersection). Serving these queries is important as it provides new capabilities and allows for expanding in markets with less structured postal systems. Traditionally, this problem poses significant difficulties for online systems where latency constraints prevent exhaustive join-based algorithms. Previous work in this area involved natural language processing to segment queries based on known rules, or purely spatial approaches that are difficult to maintain and may have high latency. In this paper, we present a new approach to geocoding - BingGC - that makes fulfillment of extremely diverse geocoding queries possible via a combination of traditional web search technologies and a novel algorithm that uses textual search and spatial joins to quickly find results. It allows resolution of up to s spatially co-located entities in a single query with no pre-computation or rule-based matching. We provide experimental analysis of our system compared against leading online geocoders.

Given a collection of geo-located activities (e.g., Crime reports), ring-shaped hotspot detection (RHD) finds rings, where concentration of activities inside the ring is much higher than outside. RHD is important for the applications such as crime analysis, where it may focus the search for crime source's location, e.g. The home of a serial criminal. RHD is challenging because of the large number of candidate rings and the high computational cost of the statistical significance test. Previous statistically significant hotspot detection techniques (e.g., Sat Scan) identify circular/rectangular areas, but can not discover rings. This paper proposes a dual grid based pruning (DGP) approach to detect ring-shaped hotspots. A case study on real crime data confirms that DGP detects novel ring-shaped regions, regions that go undetected by Sat Scan. Experiments show that DGP improves the computational cost of a naive approach substantially.

Given a spatio-temporal network (STN) and a set of STN operations, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient method of storing STN data that minimizes disk I/O costs for given STN operations. The SSTN problem is important for many societal applications, such as surface and air transportation management systems. The problem is NP hard, and is challenging due to an inherently large data volume and novel semantics (e.g., Lagrangian reference frame). Related works rely on orthogonal partitioning approaches (e.g., snapshot and longitudinal) and incur excessive I/O costs when performing common STN queries. Our preliminary work proposed a non-orthogonal partitioning approach in which we optimized the LGetOneSuccessor() operation that retrieves a single successor for a given node on STN. In this paper, we provide a method to optimize the LGetAllSuccessors() operation, which retrieves all successors for a given node on a STN. This new approach uses the concept of a Lagrangian Family Set (LFS) to model data access patterns for STN queries. Experimental results using real-world road and flight traffic datasets demonstrate that the proposed approach outperforms prior work for LGetAllSuccessors() computation workloads.

Given a set of GPS trajectories on a road network, the goal of the k-Primary Corridors (k-PC) problem is to summarize trajectories into k groups, each represented by its most central trajectory. This problem is important to a variety of domains, such as transportation services interested in finding primary corridors for public transportation or greener travel (e.g., bicycling) by leveraging emerging GPS trajectory datasets. Related trajectory mining approaches, e.g., density or frequency based hot-routes, focus on anomaly detection rather than summarization and may not be effective for the k-PC problem. The k-PC problem is challenging due to the computational cost of creating the track similarity matrix. A naïve graph-based approach to compute a single element of this track similarity matrix requires multiple invocations of common shortest-path algorithms (e.g., Dijkstra). To reduce the computational cost of creating this track similarity matrix, we propose a novel algorithm that switches from a graph-based view to a matrix-based view, computing each element in the matrix with a single invocation of a shortest-path algorithm. Experimental results show that these ideas substantially reduce computational cost without altering the results.

Given a set of operators and a spatio-temporal network, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient data storage method that minimizes disk I/O access costs. Storing and accessing spatio-temporal networks is increasingly important in many societal applications such as transportation management and emergency planning. This problem is challenging due to strains on traditional adjacency list representations when storing temporal attribute values from the sizable increase in length of the time-series. Current approaches for the SSTN problem focus on orthogonal partitioning (e.g., snapshot, longitudinal, etc.), which may produce excessive I/O costs when performing traversal-based spatio-temporal network queries (e.g., route evaluation, arrival time prediction, etc) due to the desired nodes not being allocated to a common page. We propose a Lagrangian-Connectivity Partitioning (LCP) technique to efficiently store and access spatio-temporal networks that utilizes the interaction between nodes and edges in a network. Experimental evaluation using the Minneapolis, MN road network showed that LCP outperforms traditional orthogonal approaches.