Tag Archives: Google Maps

Charting the next 15 years of Google Maps



It’s easy to take for granted how much information about the world is now available at our fingertips. But it wasn’t long ago that traveling to a new place meant fumbling through sheets of turn-by-turn instructions while trying to keep one hand on the steering wheel, with no way to anticipate how bad traffic would be or find a restaurant along the way. It was around that time, 15 years ago, that Google Maps set out on an audacious goal to map the world. 


I remember seeing early versions of Google Maps and being amazed at how easily you could scroll, zoom and search the world. One of my earliest memories of working on Google Maps was as a member of our user experience team, which designs and improves the usability of our products. In a world before smartphones, one of the biggest questions that we agonized over was where to put the Print button on the page so that people could easily take their directions on the go. 


Needless to say, a lot has changed. Google Maps has mapped more than 220 countries, surfaced information for about 200 million places and businesses, and helped billions of people get from point A to point B with confidence. In the beginning, we focused on answering the question: “How do I get from here to there?” Over time, our mission has expanded from helping you navigate to also helping you discover the best places to go and things to do once you’re there. As we celebrate our birthday this week, we’re reflecting on how the definition of what a map can do has broadened, and how machine learning will propel us forward from here. 


Navigating the world: From simple directions to Live View 


Fifteen years ago, printing out directions was considered state-of-the-art. So the idea of getting turn-by-turn driving navigation from your phone while on the road seemed revolutionary. In 2009, Google Maps pioneered turn-by-turn mobile navigation, and we’ve since added directions and navigation for walking, transit, bicycles, two-wheelers, and more--all with the goal of helping you with every trip across every mode of transportation. Since people increasingly use a mix of transportation options in a single trip--like walking to the train station and then taking a rideshare to their final stop--one of our next challenges involves stitching together these navigation options and ETAs for a more seamless experience.


Directions alone aren’t enough. We’re also helping you get there faster and more comfortably by arming you with relevant real-time information like live traffic alerts, predictions for how crowded your bus will be and which bike-sharing locations have available bikes. And we’ve used technology like augmented reality (AR) to help bring the map to life in helpful ways. Last year we introduced Live View, which uses AR, AI and your smartphone camera to show you your surroundings with the directions overlaid. It solves the real pain point of walking halfway down the block toward a place only to realize you’re going the wrong way (I’ve definitely been there!).


Exploring the world once you get there


We’ve always fundamentally believed that a map is much more than masses of land and sea, that a city is more than a web of streets. After all, the things that make my hometown shine are the brunch spot with my favorite veggie scramble, the pet salon that keeps my dog happy while he gets a trim, and the pizza spot with the foosball table that keeps my kids entertained while we wait. A truly helpful map reflects all of those local insights and helps you find places and experiences that are right for you—so that’s been a big focus for us over the last few years. 


Until recently, if you were looking to grab a slice of pizza, you’d get a list of 20 nearby pizza joints. (And way before that, you’d have to search in advance on a desktop to get the list, or if you were already out of the house you had to roam streets seeking the smell of melted cheese!) Now, we can help you find all of the pizza spots nearby, when they're open, how crowded they’ll be, and which one has the best toppings. Once you’ve decided where to go, you can easily make a reservation or call the restaurant. 


Doing this well at scale requires a deep understanding of businesses and places—which is where our active community of users comes in. Every day, people contribute more than 20 million pieces of content to Google, like photos, reviews and ratings. These contributions continually make our map richer and more helpful for everyone. They also power features like popular dishes at restaurants, up-to-date road closures and wheelchair accessible routes. We’re also making it easy for you to get things done at these places within Google Maps—so you can go from finding a yoga studio to booking a class. 


The technology propelling the future of Maps


The world is always changing—new roads are added, bus routes are changed and natural disasters alter accessible routes. That’s why a map needs to be updated, comprehensive and accurate. Major breakthroughs in AI have transformed our approach to mapmaking, helping us bring high-quality maps and local information to more parts of the world faster. 


For instance, we worked with our data operations team to manually trace common building outlines, then trained our machine learning models to recognize building edges and shapes. Thanks to this technique, we’ve mapped as many buildings in the last year as we did in the previous 10. Elsewhere, machine learning helps us recognize handwritten building numbers that would be hard even for a passerby in a car to see. This is especially important when mapping areas where formal street signs and house numbers are uncommon. In Lagos, Nigeria alone, machine learning has helped us add 20,000 street names, 50,000 addresses, and 100,000 new businesses—lighting up the map with local places and businesses where there once was little detailed information. 


The map of the next 15 years 


As we celebrate our birthday and look ahead to the next 15 years, we’re rolling out a few new updates, including a refreshed look for the app and more information about your transit rides. And we’ve updated our Google Maps icon to reflect our journey.


When we set out to map the world, we knew it would be a challenge. But 15 years in, I’m still in awe of what a gargantuan task it is. It requires building and curating an understanding of everything there is to know about the physical world, and then bringing that information to people in a way that helps you navigate, explore and get things done in your world. The real world is infinitely detailed and always changing, so our work of reflecting it back to you is never done. 

Posted by Jen Fitzpatrick, Senior Vice President, Google Maps

Google Maps is turning 15! Celebrate with a new look and features



In 2005, we set out to map the world. Since then we’ve pushed the limits of what a map can do: from helping you easily navigate from point A to B, to helping you explore and get things done in the world. With more than 1 billion people turning to Google Maps to see and explore the world, we're celebrating our 15th birthday with a new look and product updates based on feedback from you.


A fresh look from the inside out
Starting today, you'll see an updated Google Maps app for Android and iOS that gives you everything you need at your fingertips with five easy-to-access tabs: Explore, Commute, Saved, Contribute and Updates.
  • Explore: Looking for a place nearby to grab lunch, enjoy live music or play arcade games? In the Explore tab, you’ll find information, ratings, reviews and more for about 200 million places around the world, including local restaurants, nearby attractions and city landmarks. 
  • Commute: Whether you’re traveling by car or public transit, the Commute tab is there to make sure you’re on the most efficient route. Set up your daily commute to get real-time traffic updates, travel times and suggestions for alternative routes.
  • Saved: People have saved more than 6.5 billion places on Google Maps—from the new bakery across town to the famous restaurant on your upcoming vacation. Now you can view all of these spots in one convenient place, as well as find and organize plans for an upcoming trip and share recommendations based on places you've been.
  • Contribute: Hundreds of millions of people each year contribute information that helps keep Google Maps up to date. With the new Contribute tab, you can easily share local knowledge, such as details about roads and addresses, missing places, business reviews and photos. Each contribution goes a long way in helping others learn about new places and decide what to do.
  • Updates: The new Updates tab provides you with a feed of trending, must-see spots from local experts and publishers, like The Infatuation. In addition to discovering, saving and sharing recommendations with your network, you can also directly chat with businesses to get questions answered.


Our five tabs provide easier access to everything you need in Google Maps.


We’re also updating our look with a new Google Maps icon that reflects the evolution we’ve made mapping the world. It’s based on a key part of Google Maps since the very beginning—the pin— and represents the shift we’ve made from getting you to your destination to also helping you discover new places and experiences.


And because we can’t resist a good birthday celebration, keep an eye out for our celebratory party-themed car icon, available for a limited time when you navigate with Google Maps.

Look out for our new icon on your phone and browser.


Made for you, on the go
We’re constantly evolving to help you get around—no matter how you choose to travel. Our new transit features in the Google Maps app help you stay informed when you’re taking public transportation.


Last year, we introduced crowdedness predictions to help you see how crowded your bus, train or subway is likely to be based on past rides. To help you plan your travels, we’re adding new insights about your route from past riders, so you’ll be able to see important details, such as: 
  • Temperature: For a more comfortable ride, check in advance if the temperature is considered by past riders as on the colder or warmer side.
  • Accessibility: If you have special needs or require additional support, you can identify public transit lines with staffed assistance, accessible entrance and seating, accessible stop-button or hi-visible LED.
  • Women’s Section: In regions where transit systems have designated women's sections or carriages, we'll help surface this information along with whether other passengers abide by it.
  • Security Onboard: Feel safer knowing if security monitoring is on board—whether that’s with a security guard present, installed security cameras or an available helpline.
  • Number of carriages available: In Japan only, you can pick a route based on the number of carriages so that it increases your chances of getting a seat.


    These useful bits of information come from past riders who've shared their experiences and will appear alongside public transit routes when available. To help future riders, you can answer a short survey within Google Maps about your experience on recent trips. We’ll start rolling this out globally in March, with availability varying by region and municipal transportation agency.

    New trip attributes help you make informed decisions about your travel plans.


    A sense of direction
    Last year, we introduced Live View to help you quickly decide which way to go when you start a walking route with Google Maps. By combining Street View’s real-world imagery, machine learning and smartphone sensors, Live View in Google Maps shows you your surroundings with the directions overlaid in augmented reality. 


    Over the coming months, we’ll be expanding Live View and testing new capabilities, starting with better assistance whenever you’re searching for a place. You’ll be able to quickly see how far away and in which direction a place is.


    Live View will soon help you get oriented in the right direction in new ways.


    A big thank you to everyone for placing your trust in us and for being with us on this wild ride over the last 15 years. See you out there on the journey!

    Posted by Dane Glasgow, Vice President of Product, Google Maps

    Announcing the Google Maps Platform YouTube Channel!

    Posted by Samirah Javed, Social Partnership Manager and Alex Muramoto, Developer Advocate

    The time has come!

    We’re excited to announce the official launch of the Google Maps Platform YouTube channel, a place for developers to learn and immerse themselves in the possibilities with maps.





    We already have some great content on the channel about how to get started, incredible user stories, and the return of our Geocasts series coming soon - a series dedicated to providing walkthroughs and tips to help you learn how to implement Google Maps Platform features in your web and mobile apps.

    Subscribe here → @GoogleMapsPlatformGoogle Maps Platform bannerSee you there!

    Adding 57,000 public toilets to Google Maps across India

    https://lh6.googleusercontent.com/G06WQYQ_kzWfqKM0miZ0t6D9c8SMEg0Xdxg9LdSLYN-5sGumg6NLxHoQJNVq3ZUWrBHOvRNyI_E0ot1vhC2aBQULF1XVpJXDCbEitG7mLOs9GGYa4eJWoDWR_O6Z4tx4vyFfOWHa
    In 2016, in collaboration with the Swachh Bharat Mission, Ministry of Housing & Urban Affairs, we embarked on a campaign to help users across India to locate public toilets within Google Maps. We launched this as a pilot in three cities: New Delhi, Bhopal, and Indore. After almost three years, this effort now encompasses over 57,000 public toilets in 2,300+ cities across the nation.




    With Google Maps, our aim has always been to help people as they navigate and explore the world, wherever they are. And we believe that making information about public sanitation facilities easily accessible to people is a key element for social good -- one that also constitutes the cornerstone of the government's Swachh Bharat campaign to promote clean habits and hygiene.


    We have a long history of making Google Maps more relevant, accurate, and reliable for Indian users with India-first solutions such as two-wheeler mode and offline Maps. For this campaign, our product and engineering teams together built a new process seamlessly integrate toilet listings into Google Maps. We have worked closely with the Ministry to update Maps with key information about public toilets from across India, while refining our systems to accurately surface these toilets through a variety of user queries -- over 2.5 lakh users now search for public toilets every month across Search and Maps.


    Today, all you need is to search for ‘public toilets near me’ on Google Search, the Google Assistant or Google Maps and receive results at your fingertips. 


    In addition, through Google My Business, we helped the Ministry take ownership of these listings on Google Maps so they could monitor visits, ratings, reviews and more, thereby gaining valuable insights that could help them take necessary action to maintain and upgrade toilets. 


    Google Maps Local Guides are also continuing to feedback on toilets in their locality, late last year we ran a campaign to spur awareness and adoption that resulted in 32,000 reviews, photos and edits being added to public toilets across India.


    We have been humbled to be a part of this campaign, and remain committed to finding ways to make Google Maps even more useful and relevant to users across India. 


    Posted by Anal Ghosh, Sr. Program Manager, Google Maps

    Explore your world with these new Google Maps features

    https://lh5.googleusercontent.com/RZK2IimfzK2Pl_ApOPsfwa2ROyDLcm1gl_DU2oY9Psr2SA3a-k6k5BKo2-KHgInO_15EH8WyuGKcSAJzHLJPgEiRqgVBLtis05RrWWiYg23yMIwqvXriIgzB96bSOOwALCp8MuGZ
    From showing you the quickest morning commutes, to helping you stay safe on your ride home at the end of the day, Google Maps has a long history of building India-first features to keep Indians on the move, safely.


    But we want to help with more than just getting from A to B. Starting today, we are happy to announce three new features in Google Maps available to Indian users on their phones: a redesigned, India-inspired Explore tab, a new For You experience, and dining Offers that help you find places you’re likely to enjoy with deals to make the experience even sweeter. Whether it's finding things to do in an area or getting offers on dining out, or recommending places and experiences, we hope Google Maps can now help you discover a new side to your city. 




    Explore tab: Ever since we launched the Explore tab, it has been a one-tap means of getting suggestions on dining, events, and things to do based on the area being viewed. But we wanted to make this experience even more helpful; to reflect the rich diversity of local neighborhoods and communities. Which is why we have redesigned the Explore tab for India.


    We’ve heard that Indian Maps users prefer a more assistive and visual browsing experience that is easy to access. Based on top queries and the way people interact with Google Maps in India, we’ve added seven shortcuts that you can access from the Explore tab: Restaurants, Petrol Pumps, ATMs, Offers, Shopping, Hotels, and Medical Shops. Using machine learning, we automatically identify the top suggestions across these categories in every city.


    In addition to exploring near your location, you can now also explore other popular neighborhoods in your city -- simply tap the arrow option next to “Explore Nearby”. Using machine learning, we’re  able to automatically identify the top areas in every city. Besides your own city, you can also look up other Indian cities by just searching the city name -- an easy way to get up to speed before you travel.




    For You: Didn’t know about that hip new cafe that opened up in a neighboring suburb? Now it’s easier than ever to stay in-the-know: tap the For You tab to get inspiration on new restaurants, trending places, and personalized recommendations tailored to your interests. This feature also uses the ‘Your Match’ score, which uses machine learning to combine what we know about millions of places with the information you’ve added -- restaurants you’ve rated, cuisines you’ve liked, and places you have visited. The first time you use this feature you can select the areas/localities you are interested in, and get more personalized and relevant recommendations over time.


    Not only that, users can now ‘follow’ a business and get business updates, news on events and stay on top of any offers posted by them in the ‘For You’ tab. We’ll also recommend other businesses based on merchants you follow -- these interests are user-defined and also inferred by Google.


    The For You tab offers a simple, assistive experience to help you discover your city with a single tap -- and it will continue to improve over time.




    Offers: Everyone loves a good deal, but keeping track of offers from newspaper clippings or email announcements or through multiple apps can be hard — and lead to a bulging wallet. That's why we've added a way to discover local offers, starting with restaurants. We are launching an Offers section where you can find deals and claim them at restaurants across the top 11 Indian metros. Simply tap the ‘Offers’ shortcut in the Explore tab or filter for restaurants with offers. We’re launching this feature in partnership with EazyDiner, where you can now find offers for over 4,000 restaurants and hope to add many more categories and partners soon.


    We can’t wait for you to try out these new features, and to discover those hidden gems in your city. Happy exploring!

    Posted by Krish Vitaldevara, Director, Google Maps, and Chandu Thota, Director, Google Maps

    Stay informed about local bus and long-distance train schedules, now on Google Maps

    https://lh6.googleusercontent.com/zvHioNrFyqyMvE_Nso9DDiPkRsvSC4K_uLdUsoEiigp6MAIGaVGrqhYv5iCs1-nT_mfWHq6jxd7sKAJFwbr0N0mawPVVkf0fEhe5W_EZpEzhIeGqpoy7IhPiK_YOlHdut8922tDV
    From a college student hopping onto a bus, to a family on vacation boarding a train journey to the serene beaches of Goa, public transport is the lifeblood of millions of Indians. And Google Maps is being used by over a billion travelers to navigate and explore their world, wherever they are. Beyond providing the ability to simply navigate between places, we have focused on building India-first features for Google Maps, to deliver a more relevant, accurate, and reliable experience.
    Today we are happy to announce three more features to Google Maps in India, to make public transport  journeys more efficient and seamless: Bus travel times from live traffic in 10 of the largest cities in India, live train status for Indian Railways trains, and mixed-mode commute suggestions that now combine auto-rickshaw and public transport.


    Simplifying travel on public transport buses
    Google Maps can now tell you about your bus travel times based on live traffic. This uses the power of Google’s live traffic data and public bus schedules to calculate delays and provide accurate travel times. This is the first product of its kind -- launching first in India -- enabling you to know how long your bus trip will take when factoring in live traffic conditions. This feature is launching in Delhi, Bangalore, Mumbai, Hyderabad, Pune, Lucknow, Chennai, Mysore, Coimbatore, and Surat.




    To use this feature, enter your starting location and destination, then tap the transit tab. The results for bus travel times from live traffic will include the time in green (when running on time) or red (when delayed.)


    Real-time train information for long-distance trains
    Google Maps can now help you know when your train will arrive by indicating the real-time status. Search for your starting location and destination, or your starting station and destination to see a list of trains that you can take between the routes. From there, you can easily see the real-time status, and whether any of them are delayed, right inside Google Maps. This feature was developed in partnership with the Where is My Train app that Google acquired last year.


    Mixed-mode directions results that include auto-rickshaws
    We’re excited to announce directions support in Maps for journeys that combine auto-rickshaw and public transport. The public transport tab on Google Maps for Android will now tell you when taking such a journey is a good option, how long it will take, which station you should take an auto-rickshaw to/from. You can also see the rickshaw meter estimate, and departure times for your transit connection. This feature will be available for Delhi and Bangalore initially and will soon be extended to more cities.



    Posted by Taylah Hasaballah, Product Manager, Google Maps

    Using Global Localization to Improve Navigation



    One of the consistent challenges when navigating with Google Maps is figuring out the right direction to go: sure, the app tells you to go north - but many times you're left wondering, "Where exactly am I, and which way is north?" Over the years, we've attempted to improve the accuracy of the blue dot with tools like GPS and compass, but found that both have physical limitations that make solving this challenge difficult, especially in urban environments.

    We're experimenting with a way to solve this problem using a technique we call global localization, which combines Visual Positioning Service (VPS), Street View, and machine learning to more accurately identify position and orientation. Using the smartphone camera as a sensor, this technology enables a more powerful and intuitive way to help people quickly determine which way to go.
    Due to limitations with accuracy and orientation, guidance via GPS alone is limited in urban environments. Using VPS, Street View and machine learning, Global Localization can provide better context on where you are relative to where you're going.
    In this post, we'll discuss some of the limitations of navigation in urban environments and how global localization can help overcome them.

    Where GPS Falls Short
    The process of identifying the position and orientation of a device relative to some reference point is referred to as localization. Various techniques approach localization in different ways. GPS relies on measuring the delay of radio signals from multiple dedicated satellites to determine a precise location. However, in dense urban environments like New York or San Francisco, it can be incredibly hard to pinpoint a geographic location due to low visibility to the sky and signals reflecting off of buildings. This can result in highly inaccurate placements on the map, meaning that your location could appear on the wrong side of the street, or even a few blocks away.
    GPS signals bouncing off facades in an urban environment.
    GPS has another technical shortcoming: it can only determine the location of the device, not the orientation. Sometimes, sensors in your mobile device can remedy the situation by measuring the magnetic and gravity field of the earth and the relative motion of the device in order to give rough estimates of your orientation. But these sensors are easily skewed by magnetic objects such as cars, pipes, buildings, and even electrical wires inside the phone, resulting in errors that can be inaccurate by up to 180 degrees.

    A New Approach to Localization
    To improve the precision position and orientation of the blue dot on the map, a new complementary technology is necessary. When walking down the street, you orient yourself by comparing what you see with what you expect to see. Global localization uses a combination of techniques that enable the camera on your mobile device to orient itself much as you would.

    VPS determines the location of a device based on imagery rather than GPS signals. VPS first creates a map by taking a series of images which have a known location and analyzing them for key visual features, such as the outline of buildings or bridges, to create a large scale and fast searchable index of those visual features. To localize the device, VPS compares the features in imagery from the phone to those in the VPS index. However, the accuracy of localization through VPS is greatly affected by the quality of the both the imagery and the location associated with it. And that poses another question—where does one find an extensive source of high-quality global imagery?

    Enter Street View
    Over 10 years ago we launched Street View in Google Maps in order to help people explore the world more deeply. In that time, Street View has continued to expand its coverage of the world, empowering people to not only preview their route, but also step inside famous landmarks and museums, no matter where they are. To deliver global localization with VPS, we connected it with Street View data, making use of information gathered and tested from over 93 countries across the globe. This rich dataset provides trillions of strong reference points to apply triangulation, helping more accurately determine the position of a device and guide people towards their destination.
    Features matched from multiple images.
    Although this approach works well in theory, making it work well in practice is a challenge. The problem is that the imagery from the phone at the time of localization may differ from what the scene looked like when the Street View imagery was collected, perhaps months earlier. For example, trees have lots of rich detail, but change as the seasons change and even as the wind blows. To get a good match, we need to filter out temporary parts of the scene and focus on permanent structure that doesn't change over time. That's why a core ingredient in this new approach is applying machine learning to automatically decide which features to pay attention to, prioritizing features that are likely to be permanent parts of the scene and ignoring things like trees, dynamic light movement, and construction that are likely transient. This is just one of the many ways in which we use machine learning to improve accuracy.

    Combining Global Localization with Augmented Reality
    Global localization is an additional option that users can enable when they most need accuracy. And, this increased precision has enabled the possibility of a number of new experiences. One of the newest features we're testing is the ability to use ARCore, Google's platform for building augmented reality experiences, to overlay directions right on top of Google Maps when someone is in walking navigation mode. With this feature, a quick glance at your phone shows you exactly which direction you need to go.
    Although early results are promising, there's significant work to be done. One outstanding challenge is making this technology work everywhere, in all types of conditions—think late at night, in a snowstorm, or in torrential downpour. To make sure we're building something that's truly useful, we're starting to test this feature with select Local Guides, a small group of Google Maps enthusiasts around the world who we know will offer us the feedback about how this approach can be most helpful.

    Like other AI-driven camera experiences such as Google Lens (which uses the camera to let you search what you see), we believe the ability to overlay directions over the real world environment offers an exciting and useful way to use the technology that already exists in your pocket. We look forward to continuing to develop this technology, and the potential for smartphone cameras to add new types of valuable experiences.

    Source: Google AI Blog


    Book a ride with the Google Assistant

    https://lh5.googleusercontent.com/xSY8wGoxTfoLSAfMjBj_VVRyMs6NxmC0QS1VfyKJQN40-74jlZZSV-7--tQvBApr7SQNsop9KgK117QI_yVgkbrdlztffu6c9YxUD5VVDQL1lbc5rAMf5GyUm61B3UIxDLNsFVUA
    When my friends and I are getting ready to head out to dinner, there's always a moment when we stop to ask who is going to order our ride. Now, Google can take care of it. This week, we’re rolling out a new way to easily book ride services with your Google Assistant.


    With your Android phone, iPhone, Google Home, or any smart speaker with the Assistant, start by saying, “Hey Google, book a ride to the Bluebird Cafe” or “Hey Google, get me a taxi to Indira Gandhi International Airport.” You will then be given a list of popular ride services to select from, including Uber, Ola, and many more, along with more information on estimated pricing and wait times from each service. If you only want ride options from a single provider, just include their name in your request, for example, “Hey Google, get me an Ola ride to Gateway of India.”


    Then grab your phone and tap on your preferred ride service, and the app will open to let you confirm the booking. The feature will be available first in English and any country where one of our supported ride service partners operate. We plan to expand to more languages in the coming months.


    If you’re in a hurry and your hands are all tied up, you’ll now be able to use the Assistant to see all your favorite ride services in one place and pick the one that works best for you.

    Posted by Vishal Dutta, Product Manager

    Introducing Google Maps Platform

    Posted by Google Maps Platform Team

    It's been thirteen years since we opened up Google Maps to your creativity and passion. Since then, it's been exciting to see how you've transformed your industries and improved people's lives. You've changed the way we ride to work, discover the best schools for our children, and search for a new place to live. We can't wait to see what you do next. That's why today we're introducing a series of updates designed to make it easier for you to start taking advantage of new location-based features and products.

    We're excited to announce Google Maps Platform—the next generation of our Google Maps business—encompassing streamlined API products and new industry solutions to help drive innovation.

    In March, we announced our first industry solution for game studios to create real-world games using Google Maps data. Today, we also offer solutions tailored for ridesharing and asset tracking companies. Ridesharing companies can embed the Google Maps navigation experience directly into their apps to optimize the driver and customer experience. Our asset tracking offering helps businesses improve efficiencies by locating vehicles and assets in real-time, visualizing where assets have traveled, and routing vehicles with complex trips. We expect to bring new solutions to market in the future, in areas where we're positioned to offer insights and expertise.

    Our core APIs work together to provide the building blocks you need to create location-based apps and experiences. One of our goals is to evolve our core APIs to make them simpler, easier to use and scalable as you grow. That's why we've introduced a number of updates to help you do so.

    Streamlined products to create new location-based experiences

    We're simplifying our 18 individual APIs into three core products—Maps, Routes and Places, to make it easier for you to find, explore and add new features to your apps and sites. And, these new updates will work with your existing code—no changes required.

    One pricing plan, free support, and a single console

    We've heard that you want simple, easy to understand pricing that gives you access to all our core APIs. That's one of the reasons we merged our Standard and Premium plans to form one pay-as-you go pricing plan for our core products. With this new plan, developers will receive the first $200 of monthly usage for free. We estimate that most of you will have monthly usage that will keep you within this free tier. With this new pricing plan you'll pay only for the services you use each month with no annual, up-front commitments, termination fees or usage limits. And we're rolling out free customer support for all. In addition, our products are now integrated with Google Cloud Platform Console to make it easier for you to track your usage, manage your projects, and discover new innovative Cloud products.

    Scale easily as you grow

    Beginning June 11, you'll need a valid API key and a Google Cloud Platform billing account to access our core products. Once you enable billing, you will gain access to your $200 of free monthly usage to use for our Maps, Routes, and Places products. As your business grows or usage spikes, our plan will scale with you. And, with Google Maps' global infrastructure, you can scale without thinking about capacity, reliability, or performance. We'll continue to partner with Google programs that bring our products to nonprofits, startups, crisis response, and news media organizations. We've put new processes in place to help us scale these programs to hundreds of thousands of organizations and more countries around the world.

    We're excited about all the new location-based experiences you'll build, and we want to be there to support you along the way. If you're currently using our core APIs, please take a look at our Guide for Existing Users to further understand these changes and help you easily transition to the new plan. And if you're just getting started, you can start your first project here. We're here to help.

    Balanced Partitioning and Hierarchical Clustering at Scale



    Solving large-scale optimization problems often starts with graph partitioning, which means partitioning the vertices of the graph into clusters to be processed on different machines. The need to make sure that clusters are of near equal size gives rise to the balanced graph partitioning problem. In simple terms, we need to partition the vertices of a given graph into k almost equal clusters, while we minimize the number of edges that are cut by the partition. This NP-hard problem is notoriously difficult in practice because the best approximation algorithms for small instances rely on semidefinite programming which is impractical for larger instances.

    This post presents the distributed algorithm we developed which is more applicable to large instances. We introduced this balanced graph-partitioning algorithm in our WSDM 2016 paper, and have applied this approach to several applications within Google. Our more recent NIPS 2017 paper provides more details of the algorithm via a theoretical and empirical study.

    Balanced Partitioning via Linear Embedding
    Our algorithm first embeds vertices of the graph onto a line, and then processes vertices in a distributed manner guided by the linear embedding order. We examine various ways to find the initial embedding, and apply four different techniques (such as local swaps and dynamic programming) to obtain the final partition. The best initial embedding is based on “affinity clustering”.

    Affinity Hierarchical Clustering
    Affinity clustering is an agglomerative hierarchical graph clustering based on Borůvka’s classic Maximum-cost Spanning Tree algorithm. As discussed above, this algorithm is a critical part of our balanced partitioning tool. The algorithm starts by placing each vertex in a cluster of its own: v0, v1, and so on. Then, in each iteration, the highest-cost edge out of each cluster is selected in order to induce larger merged clusters: A0, A1, A2, etc. in the first round and B0, B1, etc. in the second round and so on. The set of merges naturally produces a hierarchical clustering, and gives rise to a linear ordering of the leaf vertices (vertices with degree one). The image below demonstrates this, with the numbers at the bottom corresponding to the ordering of the vertices.
    Our NIPS’17 paper explains how we run affinity clustering efficiently in the massively parallel computation (MPC) model, in particular using distributed hash tables (DHTs) to significantly reduce running time. This paper also presents a theoretical study of the algorithm. We report clustering results for graphs with tens of trillions of edges, and also observe that affinity clustering empirically beats other clustering algorithms such as k-means in terms of “quality of the clusters”. This video contains a summary of the result and explains how this parallel algorithm may produce higher-quality clusters even compared to a sequential single-linkage agglomerative algorithm.

    Comparison to Previous Work
    In comparing our algorithm to previous work in (distributed) balanced graph partitioning, we focus on FENNEL, Spinner, METIS, and a recent label propagation-based algorithm. We report results on several public social networks as well as a large private map graph. For a Twitter followership graph, we see a consistent improvement of 15–25% over previous results (Ugander and Backstrom, 2013), and for LiveJournal graph, our algorithm outperforms all the others for all cases except k = 2, where ours is slightly worse than FENNEL's.

    The following table presents the fraction of cut edges in the Twitter graph obtained via different algorithms for various values of k, the number of clusters. The numbers given in parentheses denote the size imbalance factor: i.e., the relative difference of the sizes of largest and smallest clusters. Here “Vanilla Affinity Clustering” denotes the first stage of our algorithm where only the hierarchical clustering is built and no further processing is performed on the cuts. Notice that this is already as good as the best previous work (shown in the first two columns below), cutting a smaller fraction of edges while achieving a perfect (and thus better) balance (i.e., 0% imbalance). The last column in the table includes the final result of our algorithm with the post-processing.

    k
    UB13
    (5%)
    Vanilla Affinity
    Clustering
    (0%)
    Final Algorithm
    (0%)
    20
    37.0%
    38.0%
    35.71%
    27.50%
    40
    43.0%
    40.0%
    40.83%
    33.71%
    60
    46.0%
    43.0%
    43.03%
    36.65%
    80
    47.5%
    44.0%
    43.27%
    38.65%
    100
    49.0%
    46.0%
    45.05%
    41.53%

    Applications
    We apply balanced graph partitioning to multiple applications including Google Maps driving directions, the serving backend for web search, and finding treatment groups for experimental design. For example, in Google Maps the World map graph is stored in several shards. The navigational queries spanning multiple shards are substantially more expensive than those handled within a shard. Using the methods described in our paper, we can reduce 21% of cross-shard queries by increasing the shard imbalance factor from 0% to 10%. As discussed in our paper, live experiments on real traffic show that the number of multi-shard queries from our cut-optimization techniques is 40% less compared to a baseline Hilbert embedding technique. This, in turn, results in less CPU usage in response to queries. In a future blog post, we will talk about application of this work in the web search serving backend, where balanced partitioning helped us design a cache-aware load balancing system that dramatically reduced our cache miss rate.

    Acknowledgements
    We especially thank Vahab Mirrokni whose guidance and technical contribution were instrumental in developing these algorithms and writing this post. We also thank our other co-authors and colleagues for their contributions: Raimondas Kiveris, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Silvio Lattanzi, Aaron Archer and other members of NYC Algorithms and Optimization research team.