Microsoft open sources SPTAG algorithm to make Bing smarter!

Yesterday, Microsoft announced that it has open-sourced an algorithm called Space Partition Tree And Graph (SPTAG) to make the Bing search engine quickly return search results.

This algorithm allows users to take advantage of the intelligence from deep learning models for searching through billions of pieces of information, called vectors, in milliseconds. Machine-learning algorithms help search engines to deliver the best answers by building vectors. They are long lists of numbers that represent their input data, whether it be text on a webpage, images, sound, or videos.

With the help of the vector search, it becomes easier to search by concept rather than keyword. For example, if a user types in “How tall is the tower in Paris?” Bing can return a natural language result telling the user the Eiffel Tower is 1,063 feet, even though the word “Eiffel” never appeared in the search query and the word “tall” never appears in the result.

Bing captures billions of vectors for all the different kinds of media that it indexes and Microsoft uses SPTAG for searching these vectors. In this process, firstly, the team took a pre-trained model and then encoded that data into vectors, where each vector represents a word or pixel.

With the help of SPTAG library, which is at the core of the open-sourced Python library, it was possible to generate a vector index. So, when the queries come in, the deep learning model translates that text or image into a vector and the library finds the most related vectors in that index.

To explain this in detail, when an input query is converted into a vector, SPTAG is used to quickly find "approximate nearest neighbors" (ANN), or in other words, it searches the vectors that are similar to the input.

The SPTAG library is now available under the MIT license and provides all of the tools for building and searching distributed vector indexes.

According to the Microsoft team, the vectorizing effort has extended to over 150 billion pieces of data with Bing search which brings improvement over traditional keyword matching.

Jeffrey Zhu, program manager on Microsoft’s Bing team, said, “Bing processes billions of documents every day, and the idea now is that we can represent these entries as vectors and search through this giant index of 100 billion-plus vectors to find the most related results in 5 milliseconds.”

Microsoft’s official blog reads, “Only a few years ago, web search was simple. Users typed a few words and waded through pages of results. Today, those same users may instead snap a picture on a phone and drop it into a search box or use an intelligent assistant to ask a question without physically touching a device at all. They may also type a question and expect an actual reply, not a list of pages with likely answers.”

The Bing team is expecting that the algorithm could be used for enterprise or consumer-facing applications for identifying a language being spoken based on an audio snippet. It could be even used for image-heavy services such as an app that lets people take pictures of flowers and for identifying what type of flower it is.

It seems that there are endless possibilities with this algorithm when fused with the vector concept!

To know more about this news, check out Microsoft’s blog post.