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.

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.

Address parsing is a critical step for map search engines. This component annotates the terms of an address query, e.g. house numbers, road names, administrative units etc., so that the address search engine can resolve the expected result. Deep recurrent models achieve state of the art performance for address parsing; however, scaling such models is problematic. They require a significant amount of term-annotated data which is expensive to acquire. In this paper, active learning significantly reduces the amount of labeled data required to train accurate address parsing models. We demonstrate the efficiency of our approach when cold-starting with human-labeled as well as synthetically-generated data.

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.

At present, most major app marketplaces perform ranking and recommendation based on search relevance features or marketplace ``popularity'' statistics. For instance, they check similarity between app descriptions and user search queries, or rank-order the apps according to statistics such as number of downloads, user ratings etc. Rankings derived from such signals, important as they are, are insufficient to capture the dynamics of the apps ecosystem. Consider for example the questions: In a particular user context, is app A more likely to be launched than app B? Or does app C provide complementary functionality to app D-- Answering these questions requires identifying and analyzing the dependencies between apps in the apps ecosystem. Ranking mechanisms that reflect such interdependences are thus necessary.

Many web applications such as ad matching systems, vertical search engines, and page categorization systems require the identification of a particular type or class of pages on the Web. The sheer number and diversity of the pages on the Web, however, makes the problem of obtaining a good sample of the class of interest hard. In this paper, we describe a successfully deployed end-to-end system that starts from a biased training sample and makes use of several state-of-the-art machine learning algorithms working in tandem, including a powerful active learning component, in order to achieve a good classification system. The system is evaluated on traffic from a real-world ad-matching platform and is shown to achieve high categorization effectiveness with a significant reduction in editorial effort and labeling time.

It has long been noted that many data mining algorithms can be built on top of join algorithms. This has lead to a wealth of recent work on efficiently supporting such joins with various indexing techniques. However, there are many applications which are characterized by two special conditions, firstly the two datasets to be joined are of radically different sizes, a situation we call an asymmetric join. Secondly, the two datasets are not, and possibly can not be indexed for some reason. In such circumstances the time complexity is proportional to the product of the number of objects in each of the two datasets, an untenable proposition in most cases. In this work we make two contributions to mitigate this situation. We argue that for many applications, an exact solution to the problem is not required, and we show that by framing the problem as an anytime algorithm we can extract most of the benefit of a join in a small fraction of the time taken by the full algorithm. In situations where the exact answer is required, we show that we can quickly index just the smaller dataset on the fly, and greatly speed up the exact computation. We motivate and empirically confirm the utility of our ideas with case studies on problems as diverse as batch classification, anomaly detection and annotation of historical manuscripts.

Support vector clustering transforms the data into a high dimensional feature space, where a decision function is computed. In the original space, the function outlines the boundaries of higher density regions, naturally splitting the data into individual clusters. The method, however, though theoretically sound, has certain drawbacks which make it not so appealing to the practitioner. Namely, it is unstable in the presence of outliers and it is hard to control the number of clusters that it identifies. Parametrizing the algorithm incorrectly in noisy settings, can either disguise some objectively present clusters in the data, or can identify a large number of small and nonintuitive clusters. Here, we explore the properties of the data in small regions building a mixture of factor analyzers. The obtained information is used to regularize the complexity of the outlined cluster boundaries, by assigning suitable weighting to each example. The approach is demonstrated to be less susceptible to noise and to outline better interpretable clusters than support vector clustering alone.

The problem of finding unusual time series has recently attracted much attention, and several promising methods are now in the literature. However, virtually all proposed methods assume that the data reside in main memory. For many real-world problems this is not be the case. For example, in astronomy, multi-terabyte time series datasets are the norm. Most current algorithms faced with data which cannot fit in main memory resort to multiple scans of the disk/tape and are thus intractable. In this work we show how one particular definition of unusual time series, the time series discord, can be discovered with a disk aware algorithm. The proposed algorithm is exact and requires only two linear scans of the disk with a tiny buffer of main memory. Furthermore, it is very simple to implement. We use the algorithm to provide further evidence of the effectiveness of the discord definition in areas as diverse as astronomy, Web query mining, video surveillance, etc., and show the efficiency of our method on datasets which are many orders of magnitude larger than anything else attempted in the literature.

Time series motifs are approximately repeated patterns foundwithin the data. Such motifs have utility for many data mining algorithms, including rule-discovery,novelty-detection, summarization and clustering. Since the formalization of the problem and the introduction of efficient linear time algorithms, motif discovery has been successfully applied tomany domains, including medicine, motion capture, robotics and meteorology.In this work we show that most previous applications of time series motifs have been severely limited by the definition's brittleness to even slight changes of uniform scaling, the speed at which the patterns develop. We introduce a new algorithm that allows discovery of time series motifs with invariance to uniform scaling, and show that it produces objectively superior results in several important domains. Apart from being more general than all other motifdiscovery algorithms, a further contribution of our work isthat it is simpler than previous approaches, in particular we have drastically reduced the number of parameters that need to be specified.

Object recognition and content-based image retrieval systems rely heavily on the accurate and efficient identification of shapes. A fundamental requirement in the shape analysis process is that shape similarities should be computed invariantly to basic geometric transformations, e.g. scaling, shifting, and most importantly, rotations. And while scale and shift invariance are easily achievable through a suitable shape representation, rotation invariance is much harder to deal with. In this work we explore the metric properties of the rotation invariant distance measures and propose an algorithm for fast similarity search in the shape space. The algorithm can be utilized in a number of important data mining tasks such as shape clustering and classification, or for discovering of motifs and discords in image collections. The technique is demonstrated to introduce a dramatic speed-up over the current approaches, and is guaranteed to introduce no false dismissals.

Shape clustering can significantly facilitate the automatic labeling of objects present in image collections. For example, it could outline the existing groups of pathological cells in a bank of cyto-images; the groups of species on photographs collected from certain aerials; or the groups of objects observed on surveillance scenes from an office building. Here we demonstrate that a nonlinear projection algorithm such as Isomap can attract together shapes of similar objects, suggesting the existence of isometry between the shape space and a low dimensional nonlinear embedding. Whenever there is a relatively small amount of noise in the data, the projection forms compact, convex clusters that can easily be learned by a subsequent partitioning scheme. We further propose a modification of the Isomap projection based on the concept of degree-bounded minimum spanning trees. The proposed approach is demonstrated to move apart bridged clusters and to alleviate the effect of noise in the data.