PageRank算法在非网页检索问题中的应用

【作者】 赵波；

【导师】 陶晓鹏；

【作者基本信息】 复旦大学 ， 计算机软件与理论， 2010， 硕士

【摘要】 在1998年,网络信息检索领域有两种重要的网页排序模型被提出,它们分别是HITS(Hypertext Induced Topic Search)[5]和PageRank[11]。PageRank由于其固有的对恶意网页的抗干扰性和检索无关的特点逐渐成为主流的网络信息排名方法。PageRank的这两个优点正是HITS的弱点。由于商业利益的原因,有很多的公司采用各种恶意网页技术来欺骗搜索引擎的排序系统从而提高自己网页的排名。如果搜索引擎检索相关的话,候选页面和排序需要为每个检索词来单独计算,这样造成严重的系统负担的同时也降低了检索返回速度。检索无关的搜索引擎通过事先计算出各个网页的重要性从而在有查询请求时快速的返回排序好的相关网页。随着计算机性能的逐步提高和计算机硬件成本的降低,越来越多的多媒体信息如图片,视频等被出现在互联网上。不同于文本检索,多媒体信息的检索长久以来一直没有有效可行的办法,大多数是沿用基于文本的检索技术来利用多媒体信息周围的文字信息对多媒体信息本身进行排序。这样不可避免的会导致对不同检索词检索质量的参差不齐,甚至出现很多跟检索无关的检索结果。近年来,很多研究人员通过利用多媒体信息本身的内容来提高这类信息的检索质量。对网络图像检索来说,Fergus[1]等人首先采用提取搜索引擎所返回的部分结果的图像内容,在利用这些图像信息来对部分返回图像重新排序,实验证明这样的方法明显的改善了图像检索的质量。Jing [2,3,4]等人在此基础上,针对网络图像种类繁多的特点提出了VisualRank来改善网络图像的检索质量。VisualRank首先提取出图像本身的局部信息,然后利用locality-sensitive hashing[15]来对这些信息配对。这样会产生一个图像详细关系图,最后在这个图上利用PageRank对每个图像计算PageRank得分。VisualRank的适用返回比Fergus等人提出的方法更广,但其提出的使用locality-sensitive hashing的图像局部特征匹配方法将会导致内存需求线性的增长。关于不同主题的网络图像集的质量又是千差万别的,VisualRank并没有这种区分能力,对所有的图像特征都进行了匹配。为了克服这两个问题,本文提出了基于网络图片显著特征的网络图片检索方法,首先筛选出那些出现频率较高的特征点,以这些特征点作为图像特征匹配的目标。因为PageRank本身是通过一些节点本身的相似性来对这些节点进行重要性排序,所以它应该有很广的应用范围。针对于目前GPU技术的发展,GPU变得越来越复杂,并且各个模块的相互关联越来越紧密,本文提出了基于PageRank的GPU性能评估办法。更多还原

【Abstract】 In 1998, many important theories are proposed on web information retrieval. Two of them are HITS (Hypertext Induced Topic Search) [5] and PageRank [11]. Because its inherent impervious to spam web pages and its query independent, PageRank become the dominant web information retrieval method. PageRank’s strength is also HITS’s shortage.With the great success of the computer hardware industry, more and more multimedia documents are available on the web. This proposes new requirements for search engines. Different from the well researched web page retrieval technique, multimedia web information retrieval did not have effective method for a long time. The traditional way is to use the text-based method to retrieve the text information around the images, etc. Recently, researchers tried to exploit the multimedia information itself to improve the retrieval result. Fergus et al[1] used a learning-based method. They collect top images returned by Google Image Search engine and used its visual information to re-rank all the collected images. Jing et al[2,3,4] expand this work to fit the web image retrieval work. They also collected the top returned results of Google Image Search engine and extract the local image features. The different is they used locality-sensitive hashing [15] to match the features for all the images. This result a similarity graph of the image set. Then have this graph they used PageRank to re-rank all the images. Their experiments show big improvement to the current image search systems. VisualRank also have its problems, one is it will do the match for all the features regardless the image set quality and the other is locality-sensitive hashing may require too many memory. To handle these two problems, we proposed image retrieval method based on silent local features.PageRank is a method to use the inherent similarity information of a data set to compute its important factors. So it may be used in many more fields. The GPU architecture becomes more and more complex and different models have tight connections with each other. We also proposed PageRank-based method to evaluate GPU performance.更多还原