Database and method of generating same

Abstract

A database comprises a plurality of keys representing respective data items stored in the database and respective data tags associated with at least some of the data items. Data tags represent different identifiers or categories among which the associated data items are grouped. The database is arranged in the form of a tree-structured directed graph in which each of the plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, respective arcs for a given one of the plurality of keys representing a respective character or characters of the given key. The arcs and the nodes depending from the root node of data items which represent a sequence of characters shared by different keys are combined, and the data tags are associated with the arcs.

1 . A database comprising a plurality of keys representing respective data items stored in the database and respective data tags associated with at least some of the data items, respective data tags representing different identifiers or categories among which the associated data items are grouped, wherein the database is arranged in the form of a tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key, and wherein the arcs and the nodes depending from said root node of data items which represent a sequence of characters shared by different keys are combined, and the data tags are associated with the arcs.  
     
     
         2 . A database comprising a plurality of keys representing respective data items stored in the database, wherein the database is arranged in the form of a tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key, and wherein the arcs and the nodes depending from said root node of data items representing a sequence of characters shared by different keys are combined, and the arcs and the nodes extending from a given terminal node of data items representing a sequence of characters shared by different keys are also combined, said given terminal node being a sink.  
     
     
         3 . A database according to  claim 1 , wherein the arcs and the nodes extending from a given terminal node of data items representing a sequence of characters shared by different keys are also combined, said given terminal node being a sink.  
     
     
         4 . A database according to  claim 1  wherein a data tag is associated with each one of the arcs so that a data tag is read from the database as said respective character(s) of the key are read from the database.  
     
     
         5 . A database according to  claim 3  wherein a data tag is associated with each one of the arcs so that a data tag is read from the database as said respective character(s) of the key are read from the database.  
     
     
         6 . A database according to  claim 4  wherein the last data tag which is read before reaching a terminal node defines the category or identifier of the key.  
     
     
         7 . A database according to  claim 5  wherein the last data tag which is read before reaching a terminal node defines the category or identifier of the key.  
     
     
         8 . A database according to  claim 1  wherein in cases where successive arcs within a path have the same data tags associated with them, only one occurrence of the data tag when reading from the root node is stored in the database.  
     
     
         9 . A database according to  claim 3  wherein in cases where successive arcs within a path have the same data tags associated with them, only one occurrence of the data tag when reading from the root node is stored in the database.  
     
     
         10 . A database according to  claim 8  wherein said only one is the first occurrence of the data tag.  
     
     
         11 . A database according to  claim 9  wherein said only one is the first occurrence of the data tag.  
     
     
         12 . A method of generating a database having a plurality of keys representing respective data items stored in the database and respective data tags associated with at least some of the data items, respective data tags representing different identifiers or categories among which the data items are grouped, wherein the method comprises: 
 generating a data set represented by tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, and respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key wherein arcs and nodes depending from said root node of data items which represent a sequence of characters shared by different keys and category or identifier are combined; and    associating at least some of the arcs with data tags which correspond to the category or identifier of the key represented by the character or characters of the arc.    
     
     
         13 . A method of generating a database having a plurality of keys representing respective data items stored in the database, wherein the method comprises: 
 generating a data set represented by tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, and respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key, wherein arcs and nodes depending from said root node of data items which represent a sequence of characters shared by different keys are combined; and    compacting the data set so that arcs and nodes extending from a given terminal node towards said root node of data items which represent a sequence of characters shared by different keys are also combined, said given terminal node being a sink.    
     
     
         14 . A method according to  claim 11 , the method further including compacting the data set by removing from a sequence of repeating identical data tags all but one of said identical data tags.  
     
     
         15 . A method according to  claim 14 , the method further including further compacting the data set so that arcs and nodes extending from a given terminal node towards said root node of data items which represent a sequence of characters and category or identifier shared by different keys are also combined, wherein said given terminal node is a sink node.  
     
     
         16 . A method according to  claim 14 , wherein said one of said identical data tags is the first occurrence thereof in the sequence.  
     
     
         17 . A method according to  claim 16 , wherein either one or both of the steps of compacting the data set include a recursive routine.  
     
     
         18 . A method according to  claim 15 , wherein said one of said identical data tags is the first occurrence thereof in the sequence.  
     
     
         19 . A method according to  claim 18 , wherein either one or both of the steps of compacting the data set include a recursive routine.  
     
     
         20 . A method according to  claim 13 , wherein either one or both of the steps of compacting the data set include a recursive routine.  
     
     
         21 . A method according to said compacting step of  claim 13  including assigning a weight value to nodes of the data set, the weight value of a given node being dependent on the characters between said given node and an associated sink(s), said given node and associated sink(s) defining a sub-tree of said data set, and identifying two or more nodes having identical weight values as potentially having identical sub-trees.  
     
     
         22 . A method according to said further compacting step of  claim 15  including assigning a weight value to nodes of the data set, the weight value of a given node being dependent on the characters between said given node and an associated sink(s), said given node and associated sink(s) defining a sub-tree of said data set, and identifying two or more nodes having identical weight values as potentially having identical sub-trees.  
     
     
         23 . A method according to  claim 21  wherein the weight value is based on a checksum value incorporating the category or identifier of an arc extending from the node to which the weight value is being applied, in addition to the characters in the sub-tree.  
     
     
         24 . A method according to  claim 22  wherein the weight value is based on a checksum value incorporating the category or identifier of an arc extending from the node to which the weight value is being applied, in addition to the characters in the sub-tree.  
     
     
         25 . A method according to  claim 23  wherein the checksum value further incorporates an indication of the size of the associated sub-tree of the given node.  
     
     
         26 . A method according to  claim 24  wherein the checksum value further incorporates an indication of the size of the associated sub-tree of the given node.  
     
     
         27 . A method according to  claim 21 , wherein the step of compacting to reduce identical sub-trees includes comparing with one another the nodes and sub-trees depending from, and including, nodes having identical weight values.  
     
     
         28 . A method according to  claim 22  wherein the step of compacting to reduce identical sub-trees includes comparing with one another the nodes and sub-trees depending from, and including, nodes having identical weight values.  
     
     
         29 . A method according to  claim 27  wherein nodes having weight values representative of longer sub-trees are preferably compared and compacted prior to those representative of shorter ones.  
     
     
         30 . A method according to  claim 28  wherein nodes having weight values representative of longer sub-trees are preferably compared and compacted prior to those representative of shorter ones.  
     
     
         31 . A method according to  claim 29  wherein nodes and their respective sub-trees identified as identical are rationalised by directing the arc(s) leading to one of the nodes to the other node and removing said one node and its associated sub-tree from the database.  
     
     
         32 . A method according to  claim 30  wherein nodes and their respective sub-trees identified as identical are rationalised by directing the arc(s) leading to one of the nodes to the other node and removing said one node and its associated sub-tree from the database.  
     
     
         33 . A method according to  claim 31  wherein the identification of the sub-trees includes use of a recursive routine.  
     
     
         34 . A method according to  claim 32  wherein the identification of the sub-trees includes use of a recursive routine.  
     
     
         35 . A database according  claim 1  wherein the tree data structure is in the form of a tree-structured directed graph.  
     
     
         36 . A database according  claim 2  wherein the tree data structure is in the form of a tree-structured directed graph.  
     
     
         37 . A method according to  claim 12  wherein the tree data structure is in the form of a tree-structured directed graph.  
     
     
         38 . A method according to  claim 13  wherein the tree data structure is in the form of a tree-structured directed graph.  
     
     
         39 . A database according to  claim 1 , wherein the data items represent Universal Resource Locators (URL'S) for identifying Internet web pages.  
     
     
         40 . A database according to  claim 2 , wherein the data items represent Universal Resource Locators (URL'S) for identifying Internet web pages.  
     
     
         41 . A method according to  claim 12 , wherein the data items represent Universal Resource Locators (URL'S) for identifying Internet web pages.  
     
     
         42 . A method according to  claim 13 , wherein the data items represent Universal Resource Locators (URL'S) for identifying Internet web pages.  
     
     
         43 . A database according to  claim 1 , wherein the data items represent Universal Resource Locators (URL'S) for identifying Internet web pages, the categories corresponding to subject matter types, respective data tags representing different subject matter types.  
     
     
         44 . A method according to  claim 12 , wherein the data items represent Universal Resource Locators (URL'S) for identifying Internet web pages, the categories corresponding to subject matter types, respective data tags representing different subject matter types.  
     
     
         45 . A data carrier comprising a database comprising a plurality of keys representing respective data items stored in the database and respective data tags associated with at least some of the data items, respective data tags representing different identifiers or categories among which the associated data items are grouped, wherein the database is arranged in the form of a tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key, and wherein the arcs and the nodes depending from said root node of data items which represent a sequence of characters shared by different keys are combined, and the data tags are associated with the arcs.  
     
     
         46 . A data carrier according to  claim 45 , wherein the data items of the database are URL's and the data tags are subject matter types for them.  
     
     
         47 . A data carrier according to  claim 45 , wherein the arcs and the nodes extending from a given terminal node of data items representing a sequence of characters shared by different keys are also combined, said given terminal node being a sink.  
     
     
         48 . A data carrier according to  claim 47 , wherein the data items of the database are URL's and the data tags are subject matter types for them.  
     
     
         49 . A data carrier comprising a database comprising a plurality of keys representing respective data items stored in the database, wherein the database is arranged in the form of a tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key, and wherein the arcs and the nodes depending from said root node of data items representing a sequence of characters shared by different keys are combined, and the arcs and the nodes extending from a given terminal node of data items representing a sequence of characters shared by different keys are also combined, said given terminal node being a sink.  
     
     
         50 . A data carrier according to  claim 49 , wherein the data items of the database are URL's and the data tags are subject matter types for them.  
     
     
         51 . A computer program containing code, which when run on a computer, can configure the computer to generate a database comprising a plurality of keys representing respective data items stored in the database and respective data tags associated with at least some of the data items, respective data tags representing different identifiers or categories among which the associated data items are grouped, wherein the database is arranged in the form of a tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key, and wherein the arcs and the nodes depending from said root node of data items which represent a sequence of characters shared by different keys are combined, and the data tags are associated with the arcs.  
     
     
         52 . A computer program according to  claim 51 , wherein the arcs and the nodes extending from a given terminal node of data items representing a sequence of characters shared by different keys are also combined, said given terminal node being a sink.  
     
     
         53 . A computer program containing code, which when run on a computer, can configure the computer to generate a database comprising a plurality of keys representing respective data items stored in the database, wherein the database is arranged in the form of a tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key, and wherein the arcs and the nodes depending from said root node of data items representing a sequence of characters shared by different keys are combined, and the arcs and the nodes extending from a given terminal node of data items representing a sequence of characters shared by different keys are also combined, said given terminal node being a sink.  
     
     
         54 . A computer program containing code for configuring a computer to perform a method of generating a database having a plurality of keys representing respective data items stored in the database and respective data tags associated with at least some of the data items, respective data tags representing different identifiers or categories among which the data items are grouped, wherein the method comprises: 
 generating a data set represented by tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, and respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key wherein arcs and nodes depending from said root node of data items which represent a sequence of characters shared by different keys and category or identifier are combined; and    associating at least some of the arcs with data tags which correspond to the category or identifier of the key represented by the character or characters of the arc.    
     
     
         55 . A computer program according to  claim 54 , wherein the method further includes: 
 compacting the data set by removing from a sequence of repeating identical data tags all but one of said identical data tags; and    further compacting the data set so that arcs and nodes extending from a given terminal node towards said root node of data items which represent a sequence of characters and category or identifier shared by different keys are also combined, wherein said given terminal node is a sink node.    
     
     
         56 . A computer program containing code for configuring a computer to perform a method of generating a database having a plurality of keys representing respective data items stored in the database, wherein the method comprises: 
 generating a data set represented by tree data structure in which each of said plurality of keys is represented by a series of nodes and arcs defining a path between a root node and a terminal node, each node being linked to at least one other node by a respective arc, and respective arcs for a given one of said plurality of keys representing a respective character or characters of said given key, wherein arcs and nodes depending from said root node of data items which represent a sequence of characters shared by different keys are combined; and    compacting the data set so that arcs and nodes extending from a given terminal node towards said root node of data items which represent a sequence of characters shared by different keys are also combined, said given terminal node being a sink.