Abstract: In object retrieval area, the current mainstream solution is Bag of Visual Words (BoVW) method, but there are several problems existing in the conventional BoVW methods, such as low time efficiency and large memory consumption, the synonymy and ambiguity of visual words. In this paper, a method based on randomized visual dictionaries and query expansion is proposed considering the above problems. Firstly, Exact Euclidean Locality Sensitive Hashing (E2LSH) is used to cluster local features of the training dataset, and a group of scalable randomized visual vocabularies is constructed. Then, the visual words distribution histograms and index files are created according to these randomized vocabularies. Finally, a query expansion strategy is introduced to accomplish object retrieval. Experimental results indicate that the distinguishability of objects is effectively improved and the object retrieval accuracy of the novel method is boosted dramatically compared with the classical methods, besides, it adapts large scale datasets well.