Tag Archives: 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.

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.

Source: Google AI Blog


Seamless Google Street View Panoramas



In 2007, we introduced Google Street View, enabling you to explore the world through panoramas of neighborhoods, landmarks, museums and more, right from your browser or mobile device. The creation of these panoramas is a complicated process, involving capturing images from a multi-camera rig called a rosette, and then using image blending techniques to carefully stitch them all together. However, many things can thwart the creation of a "successful" panorama, such as mis-calibration of the rosette camera geometry, timing differences between adjacent cameras, and parallax. And while we attempt to address these issues by using approximate scene geometry to account for parallax and frequent camera re-calibration, visible seams in image overlap regions can still occur.
Left: A Street View car carrying a multi-camera rosette. Center: A close-up of the rosette, which is made up of 15 cameras. Right: A visualization of the spatial coverage of each camera. Overlap between adjacent cameras is shown in darker gray.
Left: The Sydney Opera House with stitching seams along its iconic shells. Right: The same Street View panorama after optical flow seam repair.
In order to provide more seamless Street View images, we’ve developed a new algorithm based on optical flow to help solve these challenges. The idea is to subtly warp each input image such that the image content lines up within regions of overlap. This needs to be done carefully to avoid introducing new types of visual artifacts. The approach must also be robust to varying scene geometry, lighting conditions, calibration quality, and many other conditions. To simplify the task of aligning the images and to satisfy computational requirements, we’ve broken it into two steps.

Optical Flow
The first step is to find corresponding pixel locations for each pair of images that overlap. Using techniques described in our PhotoScan blog post, we compute optical flow from one image to the other. This provides a smooth and dense correspondence field. We then downsample the correspondences for computational efficiency. We also discard correspondences where there isn’t enough visual structure to be confident in the results of optical flow.

The boundaries of a pair of constituent images from the rosette camera rig that need to be stitched together.
An illustration of optical flow within the pair’s overlap region.
Extracted correspondences in the pair of images. For each colored dot in the overlap region of the left image, there is an equivalently-colored dot in the overlap region of the right image, indicating how the optical flow algorithm has aligned the point. These pairs of corresponding points are used as input to the global optimization stage. Notice that the overlap covers only a small portion of each image.
Global Optimization
The second step is to warp the rosette’s images to simultaneously align all of the corresponding points from overlap regions (as seen in the figure above). When stitched into a panorama, the set of warped images will then properly align. This is challenging because the overlap regions cover only a small fraction of each image, resulting in an under-constrained problem. To generate visually pleasing results across the whole image, we formulate the warping as a spline-based flow field with spatial regularization. The spline parameters are solved for in a non-linear optimization using Google’s open source Ceres Solver.
A visualization of the final warping process. Left: A section of the panorama covering 180 degrees horizontally. Notice that the overall effect of warping is intentionally quite subtle. Right: A close-up, highlighting how warping repairs the seams.
Our approach has many similarities to previously published work by Shum & Szeliski on “deghosting” panoramas. Key differences include that our approach estimates dense, smooth correspondences (rather than patch-wise, independent correspondences), and we solve a nonlinear optimization for the final warping. The result is a more well-behaved warping that is less likely to introduce new visual artifacts than the kernel-based approach.
Left: A close-up of the un-repaired panorama. Middle: Result of kernel-based interpolation. This fixes discontinuities but at the expense of strong wobbling artifacts due to the small image overlap and limited footprint of kernels. Right: Result of our global optimization.
This is important because our algorithm needs to be robust to the enormous diversity in content in Street View’s billions of panoramas. You can see how effective the algorithm is in the following examples:
Tower Bridge, London
Christ the Redeemer, Rio de Janeiro
An SUV on the streets of Seattle
This new algorithm was recently added to the Street View stitching pipeline. It is now being used to restitch existing panoramas on an ongoing basis. Keep an eye out for improved Street View near you!

Acknowledgements
Special thanks to Bryan Klingner for helping to integrate this feature with the Street View infrastructure.