Method and system for identifying image relatedness using link and page layout analysis

Abstract

A method and system for determining relatedness of images of pages based on link and page layout analysis. A link analysis system determines relatedness between images by first identifying blocks within web pages, and then analyzing the importance of the blocks to web pages, web pages to blocks, and images to blocks. Based on this analysis, the link analysis system determines the degree to which each image is related to each other image. The link analysis system may also use the relatedness of images to generate a ranking of the images. The link analysis system may also generate a vector representation of the images based on their relatedness and apply a clustering algorithm to the vector representations to identify clusters of related images.

1 . A method in a computer system for determining relatedness between blocks of pages, the method comprising: 
 calculating value indicators of a page to a block;    calculating value indicators of a block to a page; and    calculating block-to-block indicators of relatedness of one block to another block by combining the value indicators of a block to a page and the value indicators of importance of a page to a block.    
   
   
       2 . The method of  claim 1  wherein the value indicators of a page to a block are probabilities that a user will select a link from each block that will lead to each other page.  
   
   
       3 . The method of  claim 1  wherein the value indicators of a block to a page are probabilities that a user will focus on each block of the page.  
   
   
       4 . The method of  claim 1  wherein the value indicators of a page to a block are probabilities that a user will select a link from each block that will lead to each other page and the value indicators of a block to a page are probabilities that a user will focus on each block of the page.  
   
   
       5 . The method of  claim 1  including calculating a rank of the blocks from the block-to-block indicators.  
   
   
       6 . The method of  claim 5  wherein the calculated rank is based on a probability that a user starting at an arbitrary block will transition to another block.  
   
   
       7 . The method of  claim 1  wherein the block-to-block indicators are calculated as follows:  
       W B ZX  
     where X is a matrix of the value indicators of a block to a page and Z is a matrix of the value indicators of a page to a block.  
   
   
       8 . A computer-readable storage medium containing instructions for controlling a computer system to determine relatedness between page elements, the method comprising: 
 calculating value indicators of a first element to a second element;    calculating value indicators of a second element to a first element; and    calculating indicators of relatedness of a first element to another first element by combining the value indicators of a first element to a second element and the value indicators of a second element to a first element.    
   
   
       9 . The computer-readable storage medium of  claim 8  wherein the first element is an image of a block of a page and the second element is a block.  
   
   
       10 . The computer-readable storage medium of  claim 8  wherein the first element is a block of a page and the second element is a page.  
   
   
       11 . The computer-readable storage medium of  claim 8  wherein the value indicators of a first element to a second element are probabilities that a user will select from the first element information relating to each other second element.  
   
   
       12 . The computer-readable storage medium of  claim 8  wherein the value indicators of a second element to a first element are probabilities that a user will focus on each second element within the first element.  
   
   
       13 . The computer-readable storage medium of  claim 8  wherein the value indicators of a first element to a second element are probabilities that a user will select from the first element information relating to each other second element and wherein the value indicators of a second element to a first element are probabilities that a user will focus on each second element within the first element.  
   
   
       14 . The computer-readable storage medium of  claim 8  including calculating a rank of the first elements from the indicators of relatedness of the first element to another first element.  
   
   
       15 . The computer-readable storage medium of  claim 14  wherein the calculated rank is based on a probability that a user starting at a first element will transition to another first element.  
   
   
       16 . The computer-readable storage medium of  claim 8  wherein the first element is a page and the second element is a block of the page.  
   
   
       17 . A computer system for determining relatedness between blocks of pages, comprising: 
 for each combination of a page and a block, 
 a probability of the page to the block indicating that a user will select a link from the block that will lead to the page; and  
 a probability of the block to the page indicating that a user will focus on the block of that page; and  
   a component that combines the probabilities of a block to a page and the probabilities of a page to a block to calculate block-to-block indicators of relatedness of one block to another block.    
   
   
       18 . The computer system of  claim 17  including a component that ranks the block based on the block-to-block indicators of relatedness.  
   
   
       19 . The computer system of  claim 18  wherein the ranking is based on a probability that a user starting at an arbitrary block will transition to another block.  
   
   
       20 . The computer system of  claim 17  wherein in the block-to-block indicators are calculated as follows:  
       W B ZX  
     where W B  is a matrix of block-to-block indicators, Z is a matrix of the probabilities of pages to blocks, and X is a matrix of the probabilities of blocks to pages.