Assigning document identification tags

• US 8,136,025 B1
• Filed: 07/03/2003
• Issued: 03/13/2012
• Est. Priority Date: 07/03/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhu, Huican, Acharya, Anurag
• Primary Examiner(s): Tran, Quoc A
• Application Number:
  US10/613,637
• Time in Patent Office: 3,176 Days
• Field of Search: 707/513, 707/5, 707 1- 4, 715/513, 715/500, 706/45
• US Class Current: 715/200
• CPC Class Codes: G06F 16/156 Query results presentation
• CPC Class Codes: G06F 16/214 Database migration support
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0246 Traffic
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/102 Entity profiles
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/14 Session management for real-time applications in data packet communications networks H04L65/1066
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Document identification tags are assigned to documents to be added to a collection of documents. Based on query-independent information about a new document, a document identification tag is assigned to the new document. The document identification tag so assigned is used in the indexing of the new document. When a list of document identification tags are produced by an index in response to a query, the list is approximately ordered with respect to a measure of query-independent relevance. In some embodiments, the measure of query-independent relevance is related to the connectivity matrix of the World Wide Web. In other embodiments, the measure is related to the recency of crawling. In still other embodiments, the measure is a mixture of these two. The provided systems and methods allow for real-time indexing of documents as they are crawled from a collection of documents.

Claims

1. A computer-implemented method of assigning a document identification tag to a new document, the new document to be added to a collection of documents, the method comprising:

subdividing a predetermined set of monotonically ordered document identification tags into a plurality of tiers, wherein each tier is associated with a respective subset of the set of document identification tags, and wherein the plurality of tiers are monotonically ordered with respect to a query-independent document importance metric;

receiving query-independent information about the new document, the information including the query-independent document importance metric;

selecting, based at least on the query-independent information, one of the tiers;

assigning to the new document a document identification tag from the respective subset of document identification tags associated with the selected tier, the assigned document identification tag not previously assigned to any of the documents in the collection of documents; and

storing an assignment of the document identification tag from the respective subset of document identification tags associated with the selected tier to the new document in a computer-readable medium.

2. The method of claim 1, wherein at least two of the respective subsets of document identification tags produced by said subdividing are of different sizes.

3. The method of claim 1, wherein each tier in the plurality of tiers is associated with a respective predetermined range of metric values;

and

wherein selecting a tier comprises selecting the tier for which the query-independent metric of the new document falls within the respective predetermined range of metric values associated with the selected tier.

4. The method of claim 3, wherein the respective predetermined ranges of metric values associated with the plurality of tiers are non-overlapping.

5. The method of claim 3,

wherein the respective subsets of the set of document identification tags associated with each tier monotonically increase with the position of the tier in the ordering;

and

wherein the respective predetermined range of metric values associated with each tier monotonically increases with the position of the tier in the ordering.

6. The method of claim 5, wherein assigning a document identification tag to the new document comprises assigning to the new document a minimum available document identification tag from the respective subset of document identification tags associated with the selected tier.

7. The method of claim 5, wherein assigning a document identification tag to the new document comprises assigning to the new document a maximum available document identification tag from the respective subset of document identification tags associated with the selected tier.

8. The method of claim 5, wherein the query-independent metric is a PageRank of the new document.

9. The method of claim 1, further comprising;

when a flush condition is satisfied, performing a flush operation, including building a sorted map, the sorted map relating globally unique identifiers to document identification tags assigned to documents since a prior flush operation.

10. The method of claim 9, further comprising;

when a merge condition is satisfied, performing a merge operation, the merge operation including merging a layered plurality of sorted maps produced by previous flushing operations, the merge operation further including producing a merged map relating globally unique identifiers to document identification tags assigned to documents.

11. The method of claim 1, further comprising;

when a flush condition is satisfied, performing a flush operation, the flush operation including building a first sorted map and a second sorted map;

wherein the first sorted map is keyed and sorted by globally unique identifiers, and includes for each globally unique identifier a corresponding document identification tag; and

wherein the second sorted map is keyed and sorted by document identification tags assigned to documents since a prior flush operation, and includes for each such document identification tag a corresponding globally unique identifier.

12. The method of claim 1, wherein the globally unique identifiers are URL fingerprints.

13. The method of claim 12, wherein each URL fingerprint comprises a value produced by applying a one way mapping function to an address associated with a document in the collection of documents.

14. A computer-implemented method of assigning a plurality of document identification tags to a plurality of new documents, the plurality of new documents to be added to a collection of documents, the method comprising:

partitioning a set of valid globally unique document identifiers into a plurality of segments, each segment associated with a respective subset of the set of valid globally unique document identifiers;

subdividing each of the segments into a plurality of tiers, wherein the plurality of tiers are monotonically ordered with respect to a query-independent document importance metric, each segment having an associated, predetermined set of monotonically ordered document identification tags, and each tier of a respective segment having an associated subset of the set of document identification tags for the respective segment;

receiving query-independent information about a new document, the information including the query-independent document importance metric and a globally unique document identifier;

selecting, based at least in part on the globally unique document identifier, one of the segments;

selecting, based at least on the query-independent information, one of the tiers associated with the selected segment;

assigning to the new document a document identification tag from the subset of document identification tags associated with the selected tier, wherein the document identification tag assigned to the new document is unique with respect to document identification tags assigned to other documents in the collection of documents;

storing an assignment of the document identification tag from the subset of document identification tags associated with the selected tier to the new document in a computer-readable medium; and

repeating the receiving, selecting a segment, selecting a tier, assigning, and storing with respect to one or more additional new documents;

wherein the assigned document identification tags are assigned to documents in the collection of documents having globally unique document identifiers associated with the respective segment.

15. The method of claim 14, wherein the set of document identification tags for a first segment includes a plurality of document identification tags in the set of document identification tags for a second segment.

16. A system for assigning a document identification tag to a new document, the new document to be added to a collection of documents, the system comprising:

at least one central processing unit; and

a communications bus for connecting the central processing unit to a computer readable medium;

the computer readable medium comprising;

a data structure representing a subdivision of a predetermined set of monotonically ordered document identification tags into a plurality of tiers, wherein the plurality of tiers are monotonically ordered with respect to a query-independent document importance metric, wherein each tier is associated with a respective subset of the set of document identification tags;

an interface configured to receive query-independent information about the new document, the information including the query-independent document importance metric; and

a tag assignment module configured to

select, based at least on the query-independent information, one of the tiers;

assign to the new document a document identification tag from the respective subset of document identification tags associated with the selected tier, the assigned document identification tag not previously assigned to any of the documents in the collection of documents; and

store an assignment of the document identification tag from the respective subset of document identification tags associated with the selected tier to the new document in the computer readable medium.

17. The system of claim 16, wherein the subdivision represented by the data structure includes a first subset of document identification tags having a first set size and a second subset of document identification tags having a second set size, wherein the first set size is not equal to the second set size.

18. The system of claim 16,

wherein the data structure further represents an association of each tier in the plurality of tiers with a respective predetermined range of metric values;

and

wherein the tag assignment module selects the tier for which the query-independent metric of the new document falls within the respective predetermined range of metric values associated with the selected tier.

19. The system of claim 18, wherein the predetermined ranges of metric values associated with the plurality of tiers, represented by the data structure, are non-overlapping.

20. The system of claim 18,

wherein the respective subsets of the set of document identification tags associated with each tier monotonically increases with the position of the tier in the ordering;

and

wherein the respective predetermined range of metric values associated with each tier monotonically increases with the position of the tier in the ordering.

21. The system of claim 20, wherein the tag assignment module is configured to assign a document identification tag to the new document by assigning to the new document a minimum available document identification tag from the respective subset of document identification tags associated with the selected tier.

22. The system of claim 20, wherein the tag assignment module is configured to assign a document identification tag to the new document by assigning to the new document a maximum available document identification tag from the respective subset of document identification tags associated with the selected tier.

23. The system of claim 16, wherein the query-independent metric is a PageRank of the new document.

24. The system of claim 16, wherein the tag assignment module is further configured to detect satisfaction of a flush condition, when the flush condition is satisfied the tag assignment module performing a flush operation, including building a sorted map, the sorted map relating globally unique identifiers to document identification tags assigned to documents since a prior flush operation.

25. The system of claim 24, wherein the tag assignment module is further configured to detect satisfaction of a merge condition, when the merge condition is satisfied the tag assignment module performing a merge operation, the merge operation including merging a plurality of sorted maps produced by previous flushing operations, the merge operation further including producing a merged map relating globally unique identifiers to document identification tags assigned to documents.

26. The system of claim 16, wherein the tag assignment module is further configured to detect satisfaction of a flush condition, when the flush condition is satisfied the tag assignment module performing a flush operation, the flush operation including building a first sorted map and a second sorted map;

wherein the first sorted map is keyed and sorted by globally unique identifiers, and includes for each globally unique identifier a corresponding document identification tag; and

wherein the second sorted map is keyed and sorted by document identification tags assigned to documents since a prior flush operation, and includes for each such document identification tag a corresponding globally unique identifier.

27. The system of claim 16, wherein the globally unique identifiers are URL fingerprints.

28. The system of claim 27, wherein each URL fingerprint comprises a value produced by applying a one way mapping function to an address associated with a document in the collection of documents.

29. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism therein, the computer program mechanism comprising:

a data structure representing a subdivision of a predetermined set of monotonically ordered document identification tags into a plurality of tiers, wherein the plurality of tiers are monotonically ordered with respect to a query-independent document importance metric, wherein each tier is associated with a respective subset of the set of document identification tags, and wherein the data structure includes a representation of a monotonic ordering of the tiers;

an interface configured to receive query-independent information about a new document, the information including the query-independent document importance metric; and

a tag assignment module including instructions for

selecting, based at least on the query-independent information, one of the tiers; and

assigning to the new document a document identification tag from the respective subset of document identification tags associated with the selected tier, the assigned document identification tag not previously assigned to any of the documents in a collection of documents.

30. The computer program product of claim 29, wherein the subdivision represented by the data structure includes a first subset of document identification tags having a first set size and a second subset of document identification tags having a second set size, wherein the first set size is not equal to the second set size.

31. The computer program product of claim 30,

wherein the data structure further represents an association of each tier in the plurality of tiers with a respective predetermined range of metric values;

and

wherein the tag assignment module further includes instructions for selecting the tier for which the query-independent metric of the new document falls within the respective predetermined range of metric values associated with the selected tier.

32. The computer program product of claim 31, wherein the predetermined ranges of metric values associated with the plurality of tiers, represented by the data structure, are non-overlapping.

33. The computer program product of claim 31,

wherein the respective subsets of the set of document identification tags associated with each tier monotonically increases with the position of the tier in the ordering;

and

wherein the respective predetermined range of metric values associated with each tier monotonically increases with the position of the tier in the ordering.

34. The computer program product of claim 33, wherein the tag assignment module further includes instructions for assigning a document identification tag to the new document by assigning to the new document a minimum available document identification tag from the respective subset of document identification tags associated with the selected tier.

35. The computer program product of claim 33, wherein the tag assignment module further includes instructions for assigning a document identification tag to the new document by assigning to the new document a maximum available document identification tag from the respective subset of document identification tags associated with the selected tier.

36. The computer program product of claim 29, wherein the query-independent metric is a PageRank of the new document.

37. The computer program product of claim 29, wherein the tag assignment module further includes instructions for detecting satisfaction of a flush condition and for, when the flush condition is satisfied, executing a flush operation, including building a sorted map, the sorted map relating globally unique identifiers to document identification tags assigned to documents since a prior flush operation.

38. The computer program product of claim 37, wherein the tag assignment module further includes instructions for detecting satisfaction of a merge condition, and for, when the merge condition is satisfied, performing a merge operation, the merge operation including merging a layered plurality of sorted maps produced by previous flushing operations, the merge operation further including producing a merged map relating globally unique identifiers to document identification tags assigned to documents.

39. The computer program product of claim 29, wherein the tag assignment module further includes instructions for detecting satisfaction of a flush condition and for, when the flush condition is satisfied, performing a flush operation, the flush operation including building a first sorted map and a second sorted map;

wherein the first sorted map is keyed and sorted by globally unique identifiers, and includes for each globally unique identifier a corresponding document identification tag; and

wherein the second sorted map is keyed and sorted by document identification tags assigned to documents since a prior flush operation, and includes for each such document identification tag a corresponding globally unique identifier.

40. The computer program product of claim 39, wherein the globally unique identifiers are URL fingerprints.

41. The computer program product of claim 40, wherein each URL fingerprint comprises a value produced by applying a one way mapping function to an address associated with a document in the collection of documents.