An important trend in web information processing is the support of content- based multimedia retrieval (CBMR). However, the most prevailing paradigm of CBMR, such as content-based image retrieval, content-based audio retrieval, etc, is rather conservative. It can only retrieve media objects of single modality. With the rapid development of Internet, there is a great deal of media objects of different modalities in the multimedia documents such as webpages, which exhibit latent semantic correlation. Cross-media retrieval, as a new multi- media retrieval method, is to retrieve all the related media objects with multi- modalities via submitting a query media object. To the best of our knowledge, this is the first study on how to speed up the cross-media retrieval via indexes. In this paper, based on a Cross-Reference-Graph(CRG)-based similarity retrieval method, we propose a novel unified high-dimensional indexing scheme called CIndex, which is specifically designed to effectively speedup the retrieval performance of the large crossmedia databases. In addition, we have conducted comprehensive experiments to testify the effectiveness and efficiency of our proposed method.