Learning a measure of similarity between pairs of objects is an important generic problem in machine learning. It is particularly useful in large scale applications like searching for an image that is related to a given image or finding videos that are relevant to a given video. In these tasks, users look for objects that are not only visually similar but also semantically related to a given object. Unfortunately, the approaches that exist today for learning such semantic similarity do not scale to large datasets. The current paper presents OASIS, an Online Algorithm for Scalable Image Similarity learning that is based on a bilinear similarity measure over sparse representations. OASIS is an online dual approach using the passive-aggressive family of learning algorithms with a large margin criterion and an efficient hinge loss cost. Our experiments show that OASIS is both fast and accurate at a wide range of scales: for a dataset with thousands of images, it achieves better (but comparable) results than existing state-of-the-art methods, but runs up to 100 times faster. For large, web scale, datasets, OASIS can be trained on two million images within 3 days on a single CPU, On this large scale dataset, human evaluations showed that 35\% of the nearest neighbors of a given test image, as found by OASIS, were semantically relevant to that image. This suggests that query independent similarity learning could be accurately achieved even for large scale datasets that could not be handled before.