This paper reformulates the problem of recommending related queries on a search engine as an extreme multi-label learning task. Extreme multi-label learning aims to annotate each data  point with the most relevant {\it subset} of labels from an extremely large label set. Each of the top 100 million queries on Bing was treated as a separate label in the proposed reformulation and an extreme classifier was learnt which took the user's query as input and predicted the relevant subset of 100 million queries as output. Unfortunately, state-of-the-art extreme classifiers have not been shown to scale beyond 10 million labels and have poor prediction accuracies for queries.  This paper therefore develops the \alg algorithm which can be accurately trained on low-dimensional, dense deep learning features popularly used to represent queries and which efficiently scales to 100 million labels and 240 million training points. \alg achieves this by reducing the training and prediction times from linear to logarithmic in the number of labels based on a novel negative sampling technique. This allows the proposed reformulation to address some of the limitations of traditional related search approaches in terms of coverage, density and quality.

Experiments on publically available extreme classification datasets with low-dimensional dense features as well as related searches datasets mined from the Bing logs revealed that \alg could be more accurate than leading extreme classifiers while also scaling to 100 million labels. Furthermore, \alg was found to improve the accuracy of recommendations by 10\% as compared to state-of-the-art related search techniques. Finally, when added to the ensemble in production in Bing, \alg was found to increase the trigger coverage by 52\%, the suggestion density by 33\%, the overall success rate by 2.6\% and the success rate for tail queries by 12.6\%. \alg's source code can be downloaded from~\citep{SLiCEURL}.