Microsoft has opened the source code of the vector search library used in Bing

Microsoft released source texts of the machine learning library SPTAG (Space Partition Tree And Graph) with the implementation of the approximate nearest neighbor search algorithm. The library was developed in Microsoft's research division and the search technology development center (Microsoft Search Technology Center). In practice, SPTAG is used in the Bing search engine to determine the most relevant results considering the context of search queries. The code is written in C++ and is distributed is under the MIT license. There are builds available for Linux and Windows. A Python wrapper is included.

Although the ideas for using vector stores in search engines have been around for some time, their practical implementation is hindered by the high resource intensity of vector operations and scalability limitations. Combining deep machine learning methods with approximate nearest neighbor search algorithms has allowed performance and scalability of vector systems to reach levels acceptable for major search engines. For example, in Bing, for a vector index of over 150 billion vectors, the time to retrieve the most relevant results is within 8 milliseconds.

The library includes tools for building indexes and organizing vector searches, as well as a set of tools for maintaining a distributed online search system that covers very large collections of vectors. The following modules are offered: index builder for indexing, searcher for querying using the index distributed across a cluster of multiple nodes, server for running handlers on nodes, Aggregator for combining multiple servers into a single unit, and a client for sending requests. The system supports the inclusion of new vectors into the index and the removal of vectors on the fly. The library assumes that the processed and presented data in the collection is structured as interconnected vectors, which can be compared based on

Euclidean (L2) or cosine distances. When performing a search query, vectors are returned that have the minimum distance to the original vector. SPTAG provides two methods for organizing vector space: SPTAG-KDT (K-dimensional tree ( kd-tree)) and graph of relative neighborhoods) and SPTAG-BKT (k-means treek-means tree and the graph of relative neighborhoods. The first method requires fewer resources when working with the index, while the second demonstrates higher search result accuracy in extremely large collections of vectors.

Moreover, vector search is not limited to text and can be applied to multimedia information and images, as well as in recommendation systems. For instance, one prototype built on the PyTorch framework implemented a vector system for similarity-based image searching, developed using data from several benchmark collections of animal images, including cats and dogs, which were converted into sets of vectors. When an incoming image is submitted for search, it is transformed into a vector using a machine learning model, based on which the most similar vectors are selected from the index using the SPTAG algorithm, resulting in the return of associated images.

Source: opennet.ru