System and method for generating hierarchical forward knowledge

Abstract

A method for generating an index to be provided by data sources or lower level index servers to higher order index servers is suited for use in connection with a distributed directory service comprising a hierarchical arrangement of data sources, data servers and index servers. The method involves determining the amount of data to be indexed, and comparing the amount of data to be indexed to a predefined maximum index size. An index of reduced size is generated if the amount of data to be indexed is greater than the maximum index size, and then this index is provided to higher order index servers. The index is formed by parsing the data in accordance with a prescribed data hierarchy (e.g., left or right) and using portions of the data while omitting other portions of the data. The index is formed such that it will meet the criteria of (a) producing no false negatives when queried and (b) comprising less data than the data to be indexed.

We claim:  
     
         1 . A method for generating an index of data, comprising the steps of: 
 determining the amount of data to be indexed; and    generating an index by (a) parsing the data in accordance with a prescribed data hierarchy and (b) forming the index using portions of the data while omitting other portions of the data, wherein the index is generated by a first computer and forwarded to a second computer and is used by the second computer to route queries to the first computer.    
     
     
         2 . A method as recited in  claim 1 , wherein the data to be indexed is served by a data server or index server in a distributed directory service.  
     
     
         3 . A method as recited in  claim 1 , wherein the index is formed so as to substantially meet the criteria of (i) producing no false negatives when queried and (ii) comprising less data than the data to be indexed.  
     
     
         4 . A method as recited in  claim 1 , wherein the parsing is carried out in accordance with prescribed delimiters or separators contained in the data to be indexed.  
     
     
         5 . A method as recited in  claim 1 , further comprising the step of providing the index to an index server of a distributed directory service, whereby the index is usable by the index server for query routing.  
     
     
         6 . A method as recited in  claim 1 , wherein the data to be indexed is served by a data server or index server in a distributed directory service; wherein the index is formed so as to substantially meet the criteria of (i) producing no false negatives when queried and (ii) comprising less data than the data to be indexed of producing a minimal number of false positives when queried; wherein the parsing is carried out in accordance with prescribed delimiters or separators contained in the data to be indexed; and further comprising the step of providing the index to a higher order index server of the distributed directory service, whereby the index is usable by the higher order index server for query routing.  
     
     
         7 . A computer readable storage medium containing an index formed in accordance with the method recited in  claim 1 .  
     
     
         8 . A method for operating a distributed directory service, comprising the steps of: 
 providing a plurality of index servers arranged in a hierarchy comprising multiple levels including at least a top level and a base level;    providing a plurality of data sources, wherein each such data source is coupled to at least one base level index server;    generating an index for the data provided by the data sources;    providing the index corresponding to each data source to a base level index server; and    using the index so provided in routing queries to the data sources;    wherein the index is formed so as to substantially meet the criteria of (i) producing no false negatives when queried and (ii) comprising less data than the data to be indexed.    
     
     
         9 . A method as recited in  claim 8 , wherein each index is generated by: 
 determining the amount of data to be indexed; and    determining if the amount of data to be indexed is greater than a predefined maximum index size and, if so, generating an index by (a) parsing the data in accordance with a prescribed data hierarchy, and (b) forming the index using portions of the data while omitting other portions of the data.    
     
     
         10 . A method as recited in  claim 8 , wherein the index meets the further criterion of producing a minimal number of false positives when queried.  
     
     
         11 . A method as recited in  claim 8 , wherein the parsing is carried out in accordance with prescribed delimiters or separators contained in the data to be indexed.  
     
     
         12 . A method as recited in  claim 8 , wherein: 
 each index is generated by determining the amount of data to be indexed, and determining if the amount of data to be indexed is greater than a predefined maximum index size and, if so, generating an index by (a) parsing the data in accordance with a prescribed data hierarchy, and (b) forming the index using portions of the data while omitting other portions of the data;    each index meets the further criterion of producing a minimal number of false positives when queried; and    the parsing is carried out in accordance with prescribed delimiters or separators contained in the data to be indexed.    
     
     
         13 . A distributed directory service, comprising: 
 a plurality of index servers arranged in a hierarchy comprising multiple levels including at least a top level and a base level; and    a plurality of data servers, wherein each such data server is coupled to at least one base level index server;    wherein each index server includes a computer readable storage medium in which is stored an index for the data provided by the data servers, the index being used in routing queries to the data servers; and    wherein the index is formed so as to substantially meet the criteria of (i) producing no false negatives when queried and (ii) comprising less data than the data to be indexed.    
     
     
         14 . A distributed directory service as recited in  claim 13 , further comprising means for generating each index by: 
 determining the amount of data to be indexed; and    determining if the amount of data to be indexed is greater than a predefined maximum index size and, if so, generating an index by (a) parsing the data in accordance with a prescribed data hierarchy, and (b) forming the index using portions of the data while omitting other portions of the data.    
     
     
         15 . A distributed directory service as recited in  claim 13 , wherein the index meets the further criterion of producing a minimal number of false positives when queried.  
     
     
         16 . A distributed directory service as recited in  claim 13 , wherein the parsing is carried out in accordance with prescribed delimiters or separators contained in the data to be indexed.  
     
     
         17 . A distributed directory service as recited in  claim 13 , wherein each index meets the further criterion of producing a minimal number of false positives when queried; and the parsing is carried out in accordance with prescribed delimiters or separators contained in the data to be indexed.  
     
     
         18 . A system for use in a directory service, comprising an index server and a plurality of data sources coupled to the index server, wherein the index server includes a computer readable storage medium in which is stored an index for a data source, wherein the index is formed so as to substantially meet the criteria of (i) producing no false negatives when queried and (ii) comprising less data than the underlying data for which it is an index.  
     
     
         19 . A system as recited in  claim 18 , wherein the index server further includes means for, upon receiving a query from a client, using the index to provide to the client a referral to the corresponding data source, whereby the client may use the referral to submit the rewritten query to the data source.  
     
     
         20 . A system as recited in  claim 19 , wherein the system comprises a plurality of index servers and a plurality of data sources, wherein the index servers are arranged in a hierarchy comprising multiple levels including at least a base level and each data source is coupled to at least one base level index server.