Web page connectivity server construction

Claim 2

A process for constructing a Host Database comprising: creating a preliminary Host Table in a connectivity server that collects, arranges and stores data to define the connectivity of pages on the Web, sorting URLs in a URL database concurrently with the creating of the preliminary Host Table occurring; and creating a Host Table and a Host Index, the Host Table containing information about the URLs from the preliminary Host Table.

Claim 3

A process as defined in claim 1 , wherein the preliminary Host Table is provided a plurality of entries, each entry comprising the starting CS_id of a series, the number of CS_ids in series, and a HostFP.

Claim 4

A process as defined in claim 2 , wherein a the HostFP consists essentially of the fingerprint of a host and a port number portion of a URL.

Claim 5

A process as defined in claim 2 , wherein the Host Table is created from the preliminary Host Table by: (i) sorting the preliminary Host Table by CS_id; (ii) copying entries from the preliminary Host Table to the Host Table; (iii) creating an index on the preliminary Host Table; (iv) sorting the index; and (v) for each entry, storing the related HostFP from the preliminary Host Table, the HostFP for identifying the entry.

Claim 6

A process for constructing a URL Database for a connectivity server that collects, arranges and stores data to define the connectivity of pages on the Web, the process comprising: (a) reading a set of links files, each of which contains a series of source URLs; (b) calculating a fingerprint for each URL; (c) creating a temporary URL_info Table in the form of a hash table having as keys the most significant N bits of a URL fingerprint; (d) creating an ID Index from the URLs_info Table; (e) assigning CS_ids to URLs; (f) routing the CS_ids to URLs; (g) creating a URL Index; and (h) converting URL fingerprints to CS_ids.

Claim 7

A process for constructing a URL Database for a connectivity server that collects, arranges and stores data to define the connectivity of pages on the Web, the process comprising: (a) reading a set of links files, each of which contains a series of source URLs; (b) calculating a fingerprint for each URL; (c) creating a temporary URL_info Table in the form of a hash table having as keys the most significant N bits of a URL fingerprint; (d) creating an ID Index from the URLs_info Table; (e) assigning CS_ids to URLs; (f) routing the CS_ids to URLs; (g) creating a URL Index; and (h) converting URL fingerprints to CS_ids.

Claim 8

A process as defined in claim 5 , comprising the further step of providing a URL Database API that operates to translate a URL to a fingerprint, a URL to a CS_id, a fingerprint to a URL, a fingerprint to a CS_id, a CS_id to a URL, or a CS_id to a fingerprint.

Claim 9

A process as defined in claim 5 , comprising the further steps of dividing the URL Database into partitions and allocating each of the URLs to a partition in accordance with a predetermined characteristic of the respective URL.

Claim 10

A process as defined in claim 7 , wherein each of the URLs is allocated to a partition in accordance with the importance of the URL.

Claim 11

A process as defined in claim 8 , wherein the importance of a URL is determined by the indegree or outdegree of the URL.

Claim 12

A process as defined in claim 9 , wherein the URL Database comprises at least three partitions and wherein Partition 0 is occupied by URLs with a respective indegree or outdegree greater than or equal to a first number, Partition 1 is occupied by URLs with, a respective indegree or outdegree greater than or equal to a second number but less than the first number, and Partition 2 is occupied by URLs with a respective indegree or outdegree less than the second number.

Claim 13

A process as defined in claim 10 , wherein the first number is 255 and the second number is 16.

Claim 14

A process as defined in claim 11 , wherein, within each partition, URLs are sorted lexicographically and CS_ids are assigned to URLs sequentially.

Claim 15

A process as defined in claim 12 , wherein URLs are compressed by, for each URL: (i) discarding the URL scheme; (ii) performing a prefix compression; and (iii) performing a second compression.

Claim 16

A process as defined in claim 13 , wherein performing the prefix compression comprises the steps: (ii.a) writing a number followed by a first URL, and (ii.b) for each URL i subsequent to the first URL, writing a one-byte integer followed by a remainder, where the one-byte integer represents the length of a common prefix shared by a URL i and a URL (i−1) and where the remainder is the portion of URL i following the common prefix.

Claim 17

A process as defined in claim 5 , wherein URLs are compressed by, for each URL: (i) discarding the URL scheme; (ii) performing a prefix compression; and (iii) performing a second compression.

Claim 18

A process as defined in claim 15 , wherein performing the prefix compression comprises the steps: (ii.a) writing a number followed by a first URL; and (ii.b) for each URL i subsequent to the first URL, writing a one-byte integer followed by a remainder, where the one-byte integer represents the length of a common prefix shared by a URL i and a URL (i−1) and where the remainder is the portion of URL i following the common prefix.

Claim 19

A process as defined in claim 5 , wherein a fingerprint is calculated for each URL in accordance with a deterministic mathematical function.

Claim 20

A process as defined in claim 17 , wherein a fingerprint is calculated for each URL according to a hash function that returns a unique integer value corresponding to each unique URL string.

Claim 21

A process as defined in claim 17 , wherein each record in the URLs_info Table contains remaining M least significant bits of the URL fingerprint.

Claim 22

A process as defined in claim 19 , wherein each record additionally contains metadata comprising: (1) the indegree of each URL; (2) the outdegree of each URL; and (3) a set of Boolean values.

Claim 23

A process as defined in claim 20 , wherein the set of Boolean values contains a Boolean value that indicates whether a respective URL has been a source URL.

Claim 24

A process as defined in claim 20 , wherein the set of Boolean values contains a Boolean value that indicates whether the respective URL has appeared in an input file.

Claim 25

A process as defined in claim 20 , wherein the set of Boolean values contains a value that indicates whether the URL has appeared as a source URL in an input file.

Claim 26

An information storage device for storing, arranging and presenting data defining the connectivity of pages on the Web, the device comprising: a URL Database that stores URLs and that associates a fingerprint and a CS_id with, each stored URL, the URL Database comprising: a URL Database API, a URL Index Array, and a plurality of partitions that store URLs according to a predetermined criteria; a Host Database that associates a Host_id with each distinct hostname in the URL Database, the host comprising: a Host Database API that operates to accept a CS_id and return a corresponding Host_id and to accept a Host_id and return the CS_ids on the corresponding host; and a Link Database that stores links between source URLs and destination URLs, the link Database comprising: a Link Database API that operates to retrieve, for a given CS_id, the number of outlinks from the URL corresponding to the CS_id and the number of inlinks to that URL, wherein the device is constructed in accordance with a method comprising: (a) reading a set of links files; (b) creating a temporary URLs_info Table; (c) creating an B) Index from the URLs_info Table; (d) assigning CS_ids to URLs; (e) writing the CS_ids to the ID Index; (f) compressing URLs; (g) creating a URL Index; (h) creating a Host Table; (i) converting URL fingerprints to CS_ids; (j) creating outstarts and outlinks tables; and (k) writing instarts and inlink tables to a partitioned URL Database.

Claim 27

An information storage device for storing, arranging and presenting data defining the connectivity of pages on the Web, the device comprising: a URL Database that stores URLs and that associates a fingerprint and a CS_id with, each stored URL, the URL Database comprising: a URL Database API, a URL Index Array, and a plurality of partitions that store URLs according to a predetermined criteria; a Host Database that associates a Host_id with each distinct hostname in the URL Database, the host comprising: a Host Database API that operates to accept a CS_id and return a corresponding Host_id and to accept a Host_id and return the CS_ids on the corresponding host; and a Link Database that stores links between source URLs and destination URLs, the link Database comprising: a Link Database API that operates to retrieve, for a given CS_id, the number of outlinks from the URL corresponding to the CS_id and the number of inlinks to that URL, wherein the device is constructed in accordance with a method comprising: (a) reading a set of links files; (b) creating a temporary URLs_info Table; (c) creating an B) Index from the URLs_info Table; (d) assigning CS_ids to URLs; (e) writing the CS_ids to the ID Index; (f) compressing URLs; (g) creating a URL Index; (h) creating a Host Table; (i) converting URL fingerprints to CS_ids; (j) creating outstarts and outlinks tables; and (k) writing instarts and inlink tables to a partitioned URL Database.

Claim 28

A device as defined in claim 24 , wherein the URL Database comprises at least three partitions and wherein Partition 0 is occupied by URLs with a respective indegree or outdegree greater than or equal to a first number, Partition 1 is occupied by URLs with a respective indegree or outdegree greater than or equal to a second number but less than the first number, and Partition 2 is occupied by URLs with a respective indegree or outdegree less than the second number.

Claim 29

A device as defined in claim 25 , wherein each of the URLs is compressed by: (i) discarding the URL scheme; (ii) performing a first, prefix, compression; and (iii) performing a second compression.

Claim 30

A device as defined in claim 26 , wherein the prefix compression comprises the steps: (ii.a) writing a number followed by a first URL; and (ii.b) for each URL i subsequent to the first URL, writing a one-byte integer followed by a remainder, where the one-byte integer represents the length of a common prefix shared by a URL i and a URL (i−1) and where the remainder is the portion of URL i following the common prefix.

Claim 31

A device as defined in claim 27 , wherein the Host Database comprises a Host Table, the Host Table in turn comprising a plurality of rows containing information regarding: (1) a starting CS_id of a consecutive series of CS_ids on the same host; (2) the number of CS_ids in the series; (3) the Host_id for the series; and (4) the row number of the next highest row containing the same Host.

Claim 32

A device as defined in claim 28 , wherein the Host Database comprises a Host Index, where an i th entry in the Host Index contains the largest Host Table row number whose starting CS_id is less than or equal to i*P.

Claim 33

A device as defined in claim 24 , wherein in Step (b) links files are read and are decompressed; a fingerprint is computed for each URL and added to the URL_info Table; and upon the first instance of reading a source URL, the URL is written to a URL_sort buffer.

Claim 34

A device as defined in claim 30 , wherein in Step (c), fingerprints are copied to the ID Index from the temporary URLs_info Table if: (1) the fingerprint corresponds to a source URL; or (2) the fingerprint corresponds to a special URL that “appears;” or (3) the fingerprint corresponds to a URL with a n indegree greater than or equal to a predetermined number and that “appears,” where a URL “appears” if (i) the URL is a destination URL and appears in the links files at least a predetermined number of times, or (ii) the URL is a destination URL, is a special URL, and appears in the links files at least once.

Claim 35

A device as defined in claim 31 , wherein a fingerprint is calculated for each URL in accordance with a deterministic mathematical function.

Claim 36

A device as defined in claim 32 , wherein a fingerprint is calculated for each URL according to a hash function that returns a unique integer value corresponding to each unique URL string.