System And Method For Forming Spines Of Document Clusters With The Aid Of A Digital Computer

Abstract

A system and method for forming spines of document clusters with the aid of a digital computer is provided. Concepts are generated for each of a plurality of document clusters. Candidate spines are selected for placement of at least a portion of the document clusters based on the concepts. The concepts generated for each document cluster are determined and for each concept, a number of other document clusters for which the concept is generated is determined. Those concepts that are generated for more than a single document cluster and that are generated for less than a threshold number of the document clusters are identified. The identified concepts are designated as candidate spine concepts and the candidate spines are formed based on the candidate spine concepts. Other clusters are assigned to the candidate spines based on the candidate spine concepts.

What is claimed is: 
     
         1 . A system for forming spines of document clusters with the aid of a digital computer, comprising:
 concepts for each of a plurality of document clusters;   a server comprising a central processing unit, memory, an input port to receive the concepts, and an output port, wherein the central processing unit is configured to:
 select candidate spines for placement of at least a portion of the document clusters based on the concepts, comprising:
 determine the concepts generated for each document cluster; 
 for each concept, determine a number of other document clusters for which the concept is generated; 
 identify those concepts that are generated for more than a single document cluster and that are generated for less than a threshold number of the document clusters; and 
 designate the identified concepts as candidate spine concepts and form the candidate spines based on the candidate spine concepts; and 
 
 assign other clusters to the candidate spines based on the candidate spine concepts. 
   
     
     
         2 . A system according to  claim 1 , wherein the central processing unit discards those concepts that are generated for a single document cluster and those concepts that are generated for more than the threshold number of document clusters. 
     
     
         3 . A system according to  claim 1 , wherein the central processing unit compares each of the document clusters to each of the candidate spines, determines a spine fit of each document cluster to each candidate spine based on the comparison, and assigns each document cluster to one of the candidate spines having a best spine fit. 
     
     
         4 . A system according to  claim 3 , wherein the central processing unit calculates the spine fit F according to the following equation: 
       
         
           
             
               F 
               = 
               
                 
                   log 
                    
                   
                     ( 
                     
                       popularity 
                       
                         rank 
                         2 
                       
                     
                     ) 
                   
                 
                 × 
                 scale 
               
             
           
         
       
       where popularity is defined as a number of the document clusters associated with the candidate spine concept of one such candidate spine, rank is defined as a rank of the candidate spine concept for the document cluster compared, and scale is defined as a bias factor for favoring a user specified concept or predefined specified characteristic. 
     
     
         5 . A system according to  claim 3 , wherein the central processing unit identifies a candidate spine with a single cluster assigned, assigns the single cluster to a candidate spine with a next best spine fit, and discards the identified candidate spine. 
     
     
         6 . A system according to  claim 1 , wherein the central processing unit analyzes the candidate spines and generates a concept score vector based on the document clusters assigned to that candidate spine. 
     
     
         7 . A system according to  claim 1 , wherein the central processing unit determines the concepts for the document clusters by generating document concepts for the documents within each document cluster, ranking the document concepts for each cluster, and designating top-ranked document concepts as the concepts for each document cluster. 
     
     
         8 . A system according to  claim 7 , wherein each top-ranked document concepts satisfies one of the document concept appears in a center of that cluster, the document concept is included in a minimum of two documents, and the document concept is included in at least 30% of the documents in the document cluster. 
     
     
         9 . A system according to  claim 1 , wherein the central processing unit places one or more of the candidate spines into a display by identifying those candidate spines that are unique based on a sufficient dissimilarity from the other candidate spines and positioning the unique candidate spines in the display. 
     
     
         10 . A system according to  claim 9 , wherein the central processing unit places one or more of the non-unique candidate spines in the display adjacent to one or more of the unique candidate spines. 
     
     
         11 . A method for forming spines of document clusters with the aid of a digital computer, comprising:
 generating concepts for each of a plurality of document clusters;   selecting candidate spines for placement of at least a portion of the document clusters based on the concepts, comprising:
 determining the concepts generated for each document cluster; 
 for each concept, determining a number of other document clusters for which the concept is generated; 
 identifying those concepts that are generated for more than a single document cluster and that are generated for less than a threshold number of the document clusters; and 
 designating the identified concepts as candidate spine concepts and forming the candidate spines based on the candidate spine concepts; and 
   assigning other clusters to the candidate spines based on the candidate spine concepts.   
     
     
         12 . A method according to  claim 11 , further comprising:
 discarding those concepts that are generated for a single document cluster and those concepts that are generated for more than the threshold number of document clusters.   
     
     
         13 . A method according to  claim 11 , further comprising:
 comparing each of the document clusters to each of the candidate spines;   based on the comparison, determining a spine fit of each document cluster to each candidate spine; and   assigning each document cluster to one of the candidate spines having a best spine fit.   
     
     
         14 . A method according to  claim 13 , further comprising:
 calculating the spine fit F according to the following equation:   
       
         
           
             
               F 
               = 
               
                 
                   log 
                    
                   
                     ( 
                     
                       popularity 
                       
                         rank 
                         2 
                       
                     
                     ) 
                   
                 
                 × 
                 scale 
               
             
           
         
       
       where popularity is defined as a number of document clusters associated with the candidate spine concept of one such candidate spine, rank is defined as a rank of the candidate spine concept for the document cluster compared, and scale is defined as a bias factor for favoring a user specified concept or predefined specified characteristic. 
     
     
         15 . A method according to  claim 13 , further comprising:
 identifying a candidate spine with a single cluster assigned;   assigning the single cluster to a candidate spine with a next best spine fit; and   discarding the identified candidate spine.   
     
     
         16 . A method according to  claim 11 , further comprising:
 analyzing the candidate spines; and   generating a concept score vector based on the document clusters assigned to that candidate spine.   
     
     
         17 . A method according to  claim 11 , further comprising:
 determining the concepts for the document clusters, comprising:   generating document concepts for the documents within each document cluster;   ranking the document concepts for each document cluster; and   designating top-ranked document concepts as the concepts for each document cluster.   
     
     
         18 . A method according to  claim 17 , wherein each top-ranked document concept satisfies one of the document concept appears in a center of that cluster, the document concept is included in a minimum of two documents, and the document concept is included in at least 30% of the documents in the document cluster. 
     
     
         19 . A method according to  claim 11 , further comprising:
 placing one or more of the candidate spines into a display, comprising:
 identifying those candidate spines that are unique based on a sufficient dissimilarity from the other candidate spines; and 
 positioning the unique candidate spines in the display. 
   
     
     
         20 . A method according to  claim 19 , further comprising:
 placing one or more of the non-unique candidate spines in the display adjacent to one or more of the unique candidate spines.