With the widespread adoption of devices and tools for the creation and capture of various media, there is a need to organize, and allow retrieval of, multimedia objects. While numerous techniques for content analysis and similarity measurement of multimedia objects are being developed, these techniques are not directly suitable for efficient retrieval from large multimedia databases. This thesis addresses four challenges faced for making multimedia retrieval scalable. First, a method is proposed to embed objects into a Euclidean space based on dissimilarities computed using an arbitrary, possibly expensive, similarity measure. The method creates an embedding with low computational cost, and the embedding can be used to efficiently compute approximate distances between objects. Second, a distance measure and indexing method is proposed to allow efficient retrieval based on partial similarities between objects. Unlike other measures that utilize partial similarity, this measure is metric, and allows a much lower retrieval cost. Third, we present a system for scalably finding landmarks in images using a local feature representation. Efficiency is achieved by embedding object representations into a Euclidean space. Fourth, an indexing method is proposed for answering Support Vector Machine (SVM) queries, which represent a concept learnt using a training set, and represented by an SVM classifier. This index is independent of the parameter used to train the SVM. Overall, this thesis makes a strong contribution to bridging the gap between multimedia content analysis and a scalable multimedia retrieval system.