Pseudo-anchor text extraction for vertical search

• US 7,657,507 B2
• Filed: 03/02/2007
• Issued: 02/02/2010
• Est. Priority Date: 03/02/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nie, Zaiqing, Shi, Shuming, Xing, Fei, Wen, Ji-Rong, Zhu, Mingjie
• Primary Examiner(s): Ehichioya; Fred I
• Application Number:
  US11/681,682
• Publication Number:
  US 20080215563A1
• Time in Patent Office: 1,068 Days
• Field of Search: 707/1, 707/2, 707/3, 707/100, 707/200, 707/205, 709/223, 709/224, 709/231, 719/316, 719/317, 719/320
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A search method uses pseudo-anchor text associated with search objects to improve search performance. The pseudo-anchor text may be extracted in combination with an identifier of the search objects (such as a pseudo-URL) from a digital corpus such as a collection of documents. Pseudo-anchor texts for each object are preferably extracted from candidate anchor blocks using a machine learning based approach. The pseudo-anchor texts are made available for searching and used to help ranking the objects in a search result to improve search performance. Method may be used in vertical search of objects such as published articles, products and images that lack explicit URL and anchor text information.

Claims

1. A computer-implemented method comprising:

via a processor executing computer-readable instructions;

extracting from a digital corpus an object;

extracting from the digital corpus a pseudo-anchor text associated with the object, wherein extracting the pseudo-anchor text comprises;

extracting from the digital corpus a parallel object identified with a second object identifier;

identifying an occurrence of the object in the digital corpus;

selecting a first candidate anchor block based on the occurrence of the object;

identifying an occurrence of the parallel object in the digital corpus;

selecting a second candidate anchor block based on the occurrence of the parallel object;

comparing similarity between the first identifier and the second identifier;

adding the first candidate anchor block and the second candidate anchor block to a common candidate anchor block set if the similarity between the first identifier and the second identifier satisfies a specified threshold; and

extracting the pseudo-anchor text from the common candidate anchor block set; and

making the pseudo-anchor text available for searching.

2. The method as recited in claim 1, wherein the digital corpus comprises documents collected from a specialized information source domain or field.

3. The method as recited in claim 1, wherein the digital corpus comprises a collection of published articles, and the object is one of the published articles.

4. The method as recited in claim 1, wherein the digital corpus comprises a collection of documents describing products, and the object is one of the products.

5. The method as recited in claim 1, wherein extracting an object comprises:

extracting entity information concerning the object, the entity information including a key information piece identifying the object; and

constructing an identifier of the object using the key information piece.

6. The method as recited in claim 5, wherein the object is a published article, and the identifier comprises at least one of the following information of the published article:

title, author, publication venue, and publication time.

7. The method as recited in claim 1, wherein making the pseudo-anchor text available for searching comprises:

using the pseudo-anchor text to help ranking the object in a search result.

8. The method as recited in claim 1, wherein extracting a pseudo-anchor text comprises:

identifying an occurrence of the object in the digital corpus;

selecting a candidate anchor block for the object based on the occurrence of the object;

adding the candidate anchor block to a candidate anchor block set for the object; and

extracting the pseudo-anchor text from the candidate anchor block set.

9. The method as recited in claim 8, wherein extracting the pseudo-anchor text from the candidate anchor block set is accomplished using a machine-learning algorithm.

10. The method as recited in claim 8, wherein extracting the pseudo-anchor text from the set of candidate anchor blocks is accomplished using a machine-learning algorithm to acquire a decision function through training, and wherein the machine-learning algorithm comprises a support vector machine (SVM) having a classifier with an input and an output, the input including a feature vector of a term contained in the candidate anchor block set, and the output indicating an importance level of the term.

11. The method as recited in claim 1, wherein the object is identified with a first identifier, the method further comprising:

extracting from the digital corpus a parallel object identified with a second object identifier;

comparing similarity between the first identifier and the second identifier; and

treating the parallel object and the object as the same object if the similarity between the first identifier and the second identifier satisfies a specified threshold.

12. The method as recited in claim 1, wherein extracting an object comprises:

extracting from the digital corpus a plurality of pseudo-URLs;

selecting a subgroup of the plurality of pseudo-URLs, wherein the subgroup has one or more pseudo-URLs which have a similarity satisfying a specified threshold; and

associating the subgroup of the pseudo-URLs with the object.

13. The method as recited in claim 1, wherein extracting an object comprises:

extracting from the digital corpus a plurality of pseudo-URLs;

calculating similarity of the plurality of pseudo-URLs using a similarity function; and

selecting pseudo-URLs having similarity that satisfies a specified threshold to be members of a subgroup of pseudo-URLs; and

associating the subgroup of the pseudo-URLs with the object.

14. The method as recited in claim 1, wherein extracting an object comprises:

extracting from the digital corpus a plurality of pseudo-URLs;

constructing a plurality of feature strings from the plurality of pseudo-URLs, at least one feature string for each pseudo-URL;

applying a hash function to the plurality of feature strings to calculate a hash value of each feature string;

placing the plurality of pseudo-URLs into slots of a hash-table according to the hash value of the at least one feature string of each pseudo-URL, such that each slot of the hash table contains pseudo-URLs each having at least one feature string with the same hash value;

calculating similarity of the pseudo-URLs in each slot of the hash-table using a similarity function;

selecting pseudo-URLs having similarity that satisfies a specified threshold to be members of a subgroup of pseudo-URLs; and

associating the subgroup of the pseudo-URLs with the object.

15. The method as recited in claim 1, wherein the object is identified with a pseudo-URL, the method further comprising:

parsing the digital corpus to construct pseudo-links associated with the pseudo-URL.

16. One or more computer-readable media having computer-readable instructions thereon which, when executed by one or more processors, cause the one or more processors to perform the following:

extracting from a digital corpus an object, wherein extracting the object comprises;

extracting from the digital corpus a plurality of pseudo-URLs;

constructing a plurality of feature strings from the plurality of pseudo-URLs, at least one feature string for each pseudo-URL;

applying a hash function to the plurality of feature strings to calculate a hash value of each feature string;

placing the plurality of pseudo-URLs into slots of a hash-table according to the hash value of the at least one feature string of each pseudo-URL, such that each slot of the hash table contains pseudo-URLs each having at least one feature string with the same hash value;

calculating similarity of the pseudo-URLs in each slot of the hash-table using a similarity function;

selecting pseudo-URLs having similarity that satisfies a specified threshold to be members of a subgroup of pseudo-URLs; and

associating the subgroup of the pseudo-URLs with the object;

extracting from the digital corpus a pseudo-anchor text associated with the object; and

making the pseudo-anchor text available for searching.

17. The computer-readable media as recited in claim 16, wherein extracting an object comprises:

extracting entity information concerning the object, the entity information including a key information piece identifying the object; and

constructing a pseudo-URL using the key information.

18. The computer-readable media as recited in claim 16, wherein the extracting a pseudo-anchor text associated with the object comprises:

selecting a set of candidate anchor blocks each comprising a digital content including a reference point associated with the object; and

extracting the pseudo-anchor text from the set of candidate anchor blocks.

19. A system for generating a search result upon receiving a query, the system comprising:

one or more processors;

one or more I/O devices; and

one or more computer-readable media having a collection of digital objects and computer-readable instructions thereon, wherein at least some of the digital objects being each associated with a pseudo-anchor text; and

wherein the computer readable instructions, when executed by the one or more processors, cause the one or more processors to perform the following acts;

extracting from a digital corpus an object, wherein extracting the object comprises;

extracting from the digital corpus a plurality of pseudo-URLs;

constructing a plurality of feature strings from the plurality of pseudo-URLs, at least one feature string for each pseudo-URL;

applying a hash function to the plurality of feature strings to calculate a hash value of each feature string;

placing the plurality of pseudo-URLs into slots of a hash-table according to the hash value of the at least one feature string of each pseudo-URL, such that each slot of the hash table contains pseudo-URLs each having at least one feature string with the same hash value;

calculating similarity of the pseudo-URLs in each slot of the hash-table using a similarity function;

selecting pseudo-URLs having similarity that satisfies a specified threshold to be members of a subgroup of pseudo-URLs; and

associating the subgroup of the pseudo-URLs with the object;

receiving a search query, and

ranking at least one of the digital objects at least partially based on the pseudo-anchor text.