Finding routes in road networks is a fundamental task for routing services, but most existing methods only consider the network topology and properties and cannot handle semantic queries that express user preferences or constraints. We present a novel method that leverages historical route recommendations to prune irrelevant paths and speed up the search process. Moreover, we introduce a probabilistic modeling for path finding that can incorporate query semantics, such as "route from Seattle to Redmond with less traffic lights", and find optimal routes that satisfy them. We conduct experiments and evaluations on real-world datasets and show that our method outperforms the state-of-the-art methods in terms of runtime efficiency and route quality and can effectively answer semantic queries.

Searching for directions is one of the most used features of map applications. This paper shares our vision on how Direction Services will change, with LLM-based chat assistants rapidly becoming an integral part of the underlying path search mechanism. We anticipate an influx of more complex, conversational route planning sessions, where users colloquially describe route-related preferences as if they were talking to their personal chauffeur. We envision future systems able to support asks like "avoid the East River tunnel", "take the bridge", or "find me a scenic route around the lake, oh and by the way, I'm driving the EV today". At present, popular map search engines fail in even simple, yet very natural preferences, such as 'take me from A to B via road C'. The reason is mainly twofold, inadequate query understanding and lack of mechanisms in routing to satisfy this type of preferences. The here proposed solution is a novel treatment of routing, one which casts it into an end-to-end 2-layer relevance framework. The framework is capable of performing query understanding for route queries with complex preferences and intents. It treats routes as richly annotated documents and the routing engine, in addition to performing optimization, acts (1) as a retriever of route documents that match the user intent and (2) as a ranker that ranks route candidates not just by a simple time-distance cost model, but by inferring the importance of many variables, some derived from explicitly stated preferences and others identified as relevant through data-driven methodology.

In the realm of map search engines, most are designed as semi-structured information retrieval systems, processing input queries that include text, user location, and viewport. These engines are adept at handling standalone queries, but they struggle with contextual queries, which are increasingly important in the era of conversational searches and require the model to utilize context beyond a single query. This study introduces a novel context-aware map search system, designed to extract, understand, and leverage context in map searches. We also propose an automatic evaluation system, underpinned by multiple Large Language Model (LLM) agents for investigating the trade-off of asking clarifying questions in conversational map search. Our demonstrations and experiments show that the proposed context-aware map search system can support a wide range of conversational searches. Additionally, our automatic evaluation system delivers quality judgments comparable to human evaluations, but at a significantly reduced cost.

Understanding map queries and retrieving correct entity results are the two main relevance tasks in Map search. They are usually performed by a set of task specific machine learning models. Collecting large amount of high quality labelled data for training such models is a time-consuming and labor-intensive process. Although various methods have been studied for producing pseudo data labels, they are limited in their effectiveness when applied across different languages or tasks. The recently released Large Language models (LLMs), including ChatGPT and GPT-4 (GPT for short), have demonstrated state-of-the-art performance in text understanding by using simple prompt instructions with only a handful of examples for in-context learning. In this paper, we explore GPT as a cost-effective alternative for both data labeling and synthetic data generation, where we subsequently use data obtained from this approach to train various task specific models such as maps intent detection, address detection, address parsing, geo-entity ranking, and rank scores calibration. GPT demonstrates strong potential in generating otherwise hard-to-synthesize data. We observe significant accuracy and relevance improvement across all task specific models when trained or fine-tuned on data generated by GPT. Lastly, we propose a general framework combining labeled data from GPT with other sources and a prompt fine-tune structure to guide GPT model in completing a given task.

People often ask questions for which the answer contains multiple locations or locations with additional context. The questions can be very natural and easy to understand by other people, yet if formulated as map queries, today's map search engines struggle to understand them. Here we look into three categories of such map queries: 1) queries with multiple explicitly stated locations, e.g. 'Show me directions from A to B through C, D, and E'; 2) queries where the locations need to be inferred, e.g. 'Show me on the map all locations which James Bond visited in Casino Royale'; 3) queries of locations where we request additional geographical, historical or other context, e.g. 'Show me a map of wildlife in Australia'. We build a prototype system, called Map GPT Playground, and demonstrate with it how such queries can be seamlessly answered by combining the power of Large Language Models (LLM) with foundational maps services, such as geocoding, routing, etc. We describe the architecture of the system and reason over the abstractions needed for the system to be able to generalize across complex query intents and invoke suitable chains of services to fulfil them. Lastly, we demonstrate that in resolving complex location search queries, novel considerations emerge without prior analog, namely the set of returned locations needs to be spatially consistent and often to satisfy some inferred from the query temporal order.

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.

Correct understanding of direction queries is essential in map search for providing accurate direction related results, including routing, travel distance, travel time estimation, etc. Slot tagging is the process of recognizing and annotating query terms as entities such as source, destination, travel mode, travel distance, or travel time, so that downstream map search components can surface the expected result. Transformer-based models have achieved state-of-the-art performance on various language understanding tasks, including slot tagging. However, such models require either good quality labeled data for fine-tuning or large amount of labeled data for full training. Active learning provides a solution for improving training efficiency by selecting only a small amount of very informative queries for labelling. It is not yet clear, though, how to properly apply active learning for transformer-based language models. In this paper, we propose a novel active learning method designed specifically for transformer models and demonstrate its effectiveness for slot tagging of direction queries.

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.

The paper describes Streetside Building Search-Retrieve System (SBSRS) - a system for recognizing buildings from steetside images. SBSRS powers several distinct applications: 1) it improves map-search by enriching its streetview service with semantic information, such as location, business name, open hours, etc.; 2) it enables search by image and location - a novel form of visual image search where both visual and location signals are used to identify the most relevant result to a query image of a building.