近年来,多媒体检索重排序方法因其能有效提高多媒体检索的准确率而得到广泛关注,其中基于图的重排序是目前的主流方法。基于图的重排序方法可大致分为两类:全局上下文敏感的重排序方法和局部上下文敏感的重排序方法。随着多媒体数据的爆发式增长,局部上下文敏感的重排序方法因其高效的计算效率而渐渐开始流行。局部上下文敏感的重排序方法一般分为两步:1)利用局部上下文敏感的相似度度量方法重新度量多媒体数据之间的相似度关系;2)使用结果选择算法在新的相似度关系图中选择检索结果集合。本文针对这两个步骤分别提出了一种方法。在相似度关系再度量阶段,传统的方法一般选择一层近邻作为上下文信息,这种方法对近邻范围的大小极为敏感。过小的近邻范围使得部分多媒体对象之间的相似度无法度量,过大的近邻范围容易引入噪声。为此本文提出了一种利用局部延伸近邻及原始排序列表中的位次信息的相似度度量方法LSNRI。通过该方法不仅能利用更多的上下文信息,同时也能有效减弱噪声的影响。在检索结果选择阶段,本文根据多媒体检索问题的特殊性,提出了一种基于聚类的重排序算法框架,并在该框架下提出了一种基于谱聚类的重排序方法。由于谱聚类的求解复杂度过高,不适合多媒体检索场景,本文提出了一种贪心策略GSC求解多媒体检索问题中的谱聚类问题,可以有效提高计算效率。为了克服GSC方法对噪声敏感的问题,本文将拓展查询QE方法应用到GSC的初始化过程中。结合QE和GSC可以在相似度再度量的基础上进一步提升检索准确率。为验证提出方法的有效性,本文给出了所有方法在图像和音乐的五个标准数据集上的实验,数据集包括:Corel-1K、Corel-10K、Coil-100、UKbench和GTZAN,实验结果表明本文提出的方法能有效提高多媒体检索的准确率。