Methods and apparatuses for searching content

• US 7,987,169 B2
• Filed: 06/12/2007
• Issued: 07/26/2011
• Est. Priority Date: 06/12/2006
• Status: Active Grant

• Current Assignee: Lana Ivanovna Babayan
• Original Assignee: Zalag Corporation
• Inventors: Epstein, Samuel S.
• Primary Examiner(s): Pham; Khanh
• Assistant Examiner(s): CHEEMA, AZAM M
• Application Number:
  US11/761,948
• Publication Number:
  US 20070288438A1
• Time in Patent Office: 1,505 Days
• Field of Search: None
• US Class Current: 707/706
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Embodiments of methods and apparatuses for searching contents, including structured search are described herein. Embodiments of the present invention use tree structures (or more generally, graph structures), layout structures, and/or content category information to capture within search results relevant content that would otherwise be missed, to reduce the incidence of false positives within search results, and to improve the accuracy of rankings within search results. Embodiments of the present invention further use tree structures (or more generally, graph structures), layout structures, and/or content category information to extend search results to include sub-document constituents. Embodiments of the present invention also support the use of distribution properties as criteria for ranking search results. And embodiments of the present invention support search based on structural proximity, search expressions with recursively embedded operators, predicates, and/or quantifiers, and applications to selection of advertisements.

Claims

1. A machine implemented method comprising:

receiving by a search engine, from a content searching or consuming application, an atomic search term, the search engine and the content searching or consuming application being operated on one or more different or same computing devices;

receiving a content page nominally associated with the atomic search term, or access information of the content page, by the search engine;

generating in response, by the search engine, one or more scores for one or more structures of the content page indicative of relative relevance of the content page or one or more portions of the content page to the atomic search term, wherein a structure includes substructures, wherein the generating of a score for a structure is based at least in part on a distance function and a scoring function, wherein the distance function measures distances between sub-structures within the structure being scored to facilitate determining of mutual relevance of occurrence positions, and wherein the scoring function is positionally sensitive, yielding different scores for at least some different occurrence positions of the atomic search term in substructures of the structure being scored, irrespective of substructure category memberships; and

conditionally providing or not providing the content page or one or more portions of the content page, or access information of the content page or one or more portions of the content page, to the content searching or consuming application, by the search engine, based at least in part on the generated one or more scores.

2. The method of claim 1, wherein the atomic search term comprises a plurality of words, and wherein a structure comprises a string of words of the content page, a markup string of the content page, a tree corresponding to a parsed markup portion of the content page, or a deduced semantic tree corresponding to a portion of the content page.

3. The method of claim 1, wherein the structure comprises a tree corresponding to a parsed markup portion of the content page, and a deduced semantic tree corresponding to a portion of the content page, wherein nodes of the tree corresponding to the parsed markup portion are annotated with pointers pointing to nodes of the deduced semantic tree, and wherein the nodes of the deduced semantic tree correspond to instances of content categories, and are annotated with pointers pointing to the nodes of the tree corresponding to the parsed markup portion.

4. The method of claim 1, wherein the content page comprises a web page of a web application, an XML document in a XML repository, a document in a document corpus, or a database object in a database.

5. The method of claim 1, wherein the structure comprises a tree corresponding to parsed markup of a portion of the content page, annotated with measurement information derived from layout structures associated with the content page.

6. The method of claim 5, further comprising deriving the measurement information and annotating the tree structure.

7. The method of claim 1 wherein the content page comprises a plurality of constituents, and the method further comprises building a structure by recursively forming higher sub-structures from lower sub-structures of the constituents of the content page.

8. The method of claim 1, wherein the content page comprises a plurality of constituents, and the generating of a score for a structure comprises generating one or more score for one or more atomic ones of the constituents, one or more aggregate ones of the atomic constituents, one or more aggregate ones of the aggregates, or one or more aggregate ones of the aggregates and atomic constituents.

9. The method of claim 8, wherein the generating of a score for a structure having an aggregate comprises calculating an overall score for the aggregate as a match for the atomic search term by calculating c₁* D+c₂*Δ

, where D is a density of the atomic search term on the aggregate, Δ

is a distribution score for the atomic search expression on the aggregate, and c_i and c₂ are positive real numbers such that c_i+c₂≦

1.

10. The method of claim 9, wherein the generating of a score for a structure further comprises calculating either D, Δ

or both, based at least in part on relevance values assigned to children of the aggregate.

11. The method of claim 8, wherein the generating of a score for a structure further comprises assigning relevance values to children of the aggregate by assigning a child (i) a relevance value of 0 if the aggregate contains no occurrences of the atomic search term, and (ii) a relevance value of Σ

<sub>1≦

i≦

k</sub>(1/(1+d_i)^x) if the aggregate contains at least one occurrence of the atomic search term, where k is the number of occurrences of the atomic search term in the aggregate, x is a “

distance attenuation exponent”

, a positive real number, and d_i is the distance between a child or sub-constituent and the i-th occurrence of the atomic search term.

12. The method of claim 11, wherein the distance between a child and an occurrence of the atomic search term is a selected one of a maximum, a minimum or an arithmetic mean of the distances between the child and sub-parts of the atomic search term.

13. The method of claim 8, wherein the generating of a score for a structure further comprises calculating D by calculating a selected one of an arithmetic mean, a median or a geometric mean of relevance values assigned to children of the aggregate.

14. The method of claim 13, wherein the generating of a score for a structure further comprises calculating Δ

by setting Δ

=1 if D=0, and setting Δ

=1−

AAD/(2*D) if D≠

0, where AAD is an absolute average deviation from D of the relevance values assigned to children of the aggregate.

15. The method of claim 14, further comprising selecting one or more advertisements to be provided in conjunction with a conditionally provided content page or a portion of a content page, the selecting of an advertisement comprising determining relative relevance of the advertisement to the conditionally provided content page or portion of the conditionally provided content page, and the determining including scoring the advertisement for relative relevance to the conditionally provided content page or the portion of the conditionally provided content page to one or more search expressions associated with the advertisement.

16. An apparatus comprising:

one or more processors; and

storage medium coupled to the processors, having stored therein a plurality of programming instructions to be operated by the one or more processors to cause the apparatus, in response to execution of the programming instructions by the one or more processors, to perform the method of claim 1.

17. A machine implemented method comprising:

receiving by a search engine, from a content searching or consuming application, a search expression having a first and a second proximally associated atomic sub-expression, the search engine and the content searching or consuming application being operated on one or more different or same computing devices;

receiving a content page nominally associated with the search expression, or access information of the content page, by the search engine;

generating in response, by the search engine, one or more scores for one or more structures of the content page indicative of relative relevance of the content page or one or more portions of the content page to the search expression, wherein a structure includes substructures, wherein the generating of a score for a structure is based at least in part on a distance function and a scoring function, wherein the distance function measures distances between sub-structures within the structure being scored to facilitate determining of mutual relevance of occurrence positions, and wherein the scoring function is positionally sensitive, yielding different scores for at least a first and a second situation where the distance between the occurrence positions of the first and second proximally associated atomic sub-expressions is same in both the first and second situations, when the occurrence positions of the first proximally associated atomic sub-expression have no category membership or same category membership in the first and second situations, and the occurrence positions of the second proximally associated atomic sub-expression have no category membership or same category membership in the first and second situations; and

conditionally providing or not providing the content page or one or more portions of the content page, or access information of the content page or one or more portions of the content page, to the content searching or consuming application, by the search engine, based at least in part on the generated one or more scores.

18. The method of claim 17, wherein either or both of the first and second atomic sub-expressions comprises a plurality of words, and wherein a structure comprises a string of words of the content page, a markup string of the content page, a tree corresponding to a parsed markup portion of the content page, or a deduced semantic tree corresponding to a portion of the content page.

19. The method of claim 17, wherein the first and second atomic sub-expressions are proximally associated explicitly by a proximity operator.

20. The method of claim 19, wherein the proximity operator comprises a selected one of ##, %% or ˜

, where ## denotes proximately located, %% denotes proximately disjointed, and ˜

denotes proximately complementary.

21. The method of claim 17, wherein the content page comprises a web page of a web application, a XML document in a XML repository, a document in a document corpus, or a database object in a database.

22. The method of claim 17, wherein the structure comprises a tree corresponding to a parsed markup portion of the content page, and a deduced semantic tree corresponding to a portion of the content page, wherein nodes of the tree corresponding to the parsed markup portion are annotated with pointers pointing to nodes of the deduced semantic tree, and wherein the nodes of the deduced semantic tree correspond to instances of content categories, and are annotated with pointers pointing to the nodes of the tree corresponding to the parsed markup portion.

23. The method of claim 22, wherein the structure comprises a tree corresponding to parsed markup of a portion of the content page, annotated with measurement information derived from layout structures associated with the content page.

24. The method of claim 17, wherein the search expression further comprises a third atomic sub-expression proximally associated with the proximally associated first and second atomic sub-expressions, and the generating being associatively sensitive yielding different scores for different associations of the proximally associated first, second and third atomic sub-expressions.

25. The method of claim 17, wherein the content page comprises a plurality of constituents, and the generating of one or more scores comprises generating a score for one or more atomic ones of the constituents, one or more aggregate ones of the atomic constituents, one or more aggregates of the aggregates, or one or more aggregates of the aggregates and atomic constituents.

26. The method of claim 25, wherein the generating of a score for a structure having an aggregate comprises calculating (a) a deviation score of the search expression, and (b) for each sub-expression of the search expression, a density and a relevance center of the sub-expression, for the aggregate, the calculating being performed using at least relevance geometry of the aggregate, one or more deviation scores of the search expression of each child of the aggregate, and a density of each sub-expression of the search expression for each child of the aggregate.

27. The method of claim 26, wherein the generating a score for a structure having an aggregate comprises calculating an overall score for the aggregate as a match for the search expression by calculating c₁*D+c₂*Δ

, where D is a density of the search expression on the aggregate, Δ

is a distribution score for the search expression on the aggregate, and c₁ and c₂ are positive real numbers such that c₁+c₂≦

1.

28. The method of claim 26, further comprising assigning relevance geometry to the aggregate, including assigning relative sizes to children of the aggregate, assigning relative distances between children of the aggregate or correlating distances within children of the aggregate with distances between children of the aggregate.

29. The method of claim 26, wherein the generating of a score for a structure having an aggregate comprises calculating the density as (Σ

<sub>1≦

i≦

n</sub> (A_i*v_i))/(Σ

<sub>1≦

i≦

n</sub> A_i), where n is the number of children of the aggregate, A, is a relevance size of the i-th child of the aggregate, and where v_i is a relevance value for the searched expression assigned to the i-th child of the aggregate.

30. The method of claim 29, further comprising assigning a relevance value to each sub-expression of the search expression for each child of the aggregate, and calculating the one or more deviation scores of the search expression of one or more children of the aggregate, and the density of each sub-expression of the search expression for each child of the aggregate, based at least in part on the assigned relevance values of the sub-expressions of the search expression for the children of the aggregate.

31. The method of claim 30, wherein assigning a relevance value to a sub-expression of the search expression for a child of the aggregate comprises computing the relevance value based on pre-normalized relevance values assigned to the children of the aggregate for the sub-expression, in accordance with

v/(Σ

<sub>1≦

i≦

k</sub>(A_i/(1+d_i)^x)),

where v is the pre-normalized relevance value for the sub-expression assigned for the child,

k is the number of children of the aggregate,

x is a distance attenuation exponent,

A_i is the relevance size of the i-th child of the aggregate, and

d_i is a minimum relevance distance between constituents of the child and constituents of the i-th child of the aggregate.

32. The method of claim 31, wherein assigning a pre-normalized relevance value for an sub-expression to a child comprises assigning (i) a pre-normalized relevance value of 0 for the sub-expression if a density of the sub-expression is zero for all children of the aggregate;

(ii) a pre-normalized relevance value of Σ

<sub>1≦

i≦

k</sub> (A_i*D_i/(1+d_i)^x) if at least one child of the aggregate has non-zero density for the sub-expression, where k is the number of children of the aggregate, x is a distance attenuation exponent, a positive real number, A_i is the relevance size of the i-th child of the aggregate, D_i is a density of the sub-expression in the i-th child of the aggregate, and d_i is the relevance distance between the relevance center of the child and the relevance center of the sub-expression in the i-th child of the aggregate.

33. The method of claim 26, wherein the generating of a score for a structure having an aggregate comprises calculating a relevance center of matches for the search expression for the aggregate by calculating (Σ

<sub>1≦

i≦

n</sub> (A_i*v_i*p_i))/(Σ

<sub>1≦

i≦

n</sub> (A_i*v_i)), where n is a number of children of the aggregate, A_i is the relevance size of the i-th child of the aggregate, v_i is the relevance value for the search expression assigned to the i-th child of the aggregate, p_i is a position of the relevance center for the search expression for the i-th child of the aggregate in a space corresponding to the aggregate.

34. The method of claim 26, wherein the generating of score for a structure having an aggregate comprises calculating a pre-normalized relevance value of a search sub-expression of the search expression for a child of the aggregate, the search sub-expression having a plurality of proximally associated sub-expressions, from previously calculated densities and relevance centers of the proximally associated sub-expressions for children of the aggregate, and from previously calculated pre-normalized relevance values for the individual sub-expressions for the children of the aggregate.

35. The method of claim 34, wherein the calculating of a pre-normalized relevance value of a search sub-expression of the search expression for a child of the aggregate, comprises calculating

(P+Σ

<sub>1≦

i≦

k</sub>W_i−

Σ

<sub>1≦

i≦

k</sub>(Π

<sub>1≦

j≦

m</sub>w_i,j))^1/m,

where k is a number of children of the aggregate,

P is a product of the pre-normalized relevance values of the individual sub-expression for the child,

W_i is A_i*D_i/(1+d_i)^x, where x is a distance attenuation exponent,

A_i is a relevance size of the i-th child of the aggregate,

D_i is a density of the proximally associated sub-expressions in the i-th child of the aggregate, and

d_i is relevance distance between a relevance center of the child and a relevance center of the proximally associated search sub-expressions in the i-th child of the aggregate; and

w_i,j is A_i*D_i,j/(1+d_i,j)^x, where x is a distance attenuation exponent,

A_i is a relevance size of the i-th child of the aggregate,

D_i,j is a density of the i-th sub-expression in the i-th child of the aggregate, and

d_i,j is relevance distance between a relevance center of the child and a relevance center of the i-th search sub-expression in the i-th child of the aggregate.

36. The method of claim 26, wherein the generating of a score for a structure having an aggregate comprises calculating a relevance value for a search sub-expression of the search expression for a child of the aggregate, the search sub-expression having a plurality of proximally associated search sub-expressions, from a pre-normalized relevance value v for the proximally associated sub-expressions for a child, by calculating

v/(Σ

<sub>1≦

i≦

k</sub>(A_i/(1+d_i)^x)),

where k is the number of children of the aggregate,

x is a distance attenuation exponent,

A_i is a relevance size of the i-th child of the aggregate, and

d_i is the minimum relevance distance between constituents of the child and constituents of the i-th child of the aggregate.

37. The method of claim 26, wherein the generating of a score for a structure having an aggregate comprises assigning a relevance value for a child of the aggregate for a plurality of disjointed sub-expressions of the search expression, to a maximum of a number of relevance values previously calculated or assigned to a child of the aggregate for the sub-expressions.

38. The method of claim 26, wherein the generating of a score for a structure having an aggregate comprises assigning a relevance value for a child of the aggregate for a complement of a sub-expression of the search expression, with 1 minus a relevance value previously calculated or assigned to a child of the aggregate for the sub-expression.

39. The method of claim 26, wherein the aggregate corresponds to a region and children of the aggregate corresponds to sub-regions of the region, the generating of a score for a structure having the aggregate comprises calculating a relevance center of matches for the search expression for the aggregate by calculating

x=(Σ

<sub>1≦

i≦

n</sub>(A_i*v_i*x_i))/(Σ

<sub>1≦

i≦

n</sub>(A_i*v_i)), and 

 

(a)

y=(Σ

<sub>1≦

i≦

n</sub>(A_i*v_i*y_i))/(Σ

<sub>1≦

i≦

n</sub>(A_i*V_i)), 

 

(b)

where n is the number of children of the aggregate,

A_i is the relevance size of the i-th child of the aggregate,

v_i is the relevance value for the search expression assigned to the i-th child of the aggregate,

x is x-coordinate of the relevance center for the search expression for the aggregate,

y is y-coordinate of the relevance center for the search expression for the aggregate,

x_i is x-coordinate of the relevance center for the search expression for the i-th child of the aggregate, and

y_i is y-coordinate of the relevance center for the expression for the i-th child of the aggregate.

40. The method of claim 17, further comprising selecting one or more advertisements to be provided in conjunction with a conditionally provided content page or a portion of a content page, the selecting of an advertisement comprising determining relative relevance of the advertisement to the conditionally provided content page or portion of the conditionally provided content page, and the determining including scoring the advertisement for relative relevance to the conditionally provided content page or the portion of the conditionally provided content page to one or more search expressions associated with the advertisement.

41. An apparatus comprising:

one or more processors; and

storage medium coupled to the processors, having stored therein a plurality of programming instructions to be operated by the one or more processors to cause the apparatus, in response to execution of the programming instructions by the one or more processors, to perform the method of claim 17 on the apparatus.

42. A machine implemented method comprising:

receiving by a search engine, from a content searching or consuming application, a search expression having a plurality of recursively embedded sub-expressions, the search engine and the content searching or consuming application being operated on one or more different or same computing devices;

receiving a content page nominally associated with the search expression, or access information of the content page, by the search engine;

generating in response, by the search engine, one or more scores indicative of relative relevance of a content page or one or more portions of the content page to the search expression, wherein the generating by the search engine comprising recursively generating one or more scores for one or more structures indicative of relative relevance of the content page or one or more portions of the content page to each of the recursively embedded sub-expressions, wherein a structure includes substructures, wherein at least one of the recursively generating is based at least in part on a distance function, and a scoring function, wherein the distance function measures distances between sub-structures within the structure being scored to facilitate determining of mutual relevance of occurrence positions, and wherein the scoring function is positionally sensitive, yielding different scores for at least some different occurrence positions of a search sub-expression in substructures of the structure being scored, irrespective of substructure category memberships; and

conditionally providing or not providing the content page or one or more portions of the content page, or access information of the content page or one or more portions of the content page, to the content searching or consuming application, by the search engine, based at least in part on the generated one or more scores.

43. The method of claim 42, wherein one or more of the recursively embedded sub-expressions comprise one or more applications of predicates specifying one or more string-based relationships, one or more tree-based relationships, one or more graph-based relationships, one or more category memberships, or one or more search algorithms, recursively embedded using one or more Boolean logical operators, one or more scalar-valued logical operators or one or more quantifiers.

44. The method of claim 42, wherein the plurality of recursively embedded sub-expressions comprise a first sub-expression specifying a matching criterion for a content category and a second sub-expression specifying a matching criterion for a content page of a matching content category.

45. The method of claim 42, wherein the plurality of recursively embedded sub-expressions comprise first and second sub-expressions specifying first and second matching criteria for first and second content pages respectively, and the search expression further comprises directive directing return or non-return of the first or second matching content page.

46. The method of claim 45 wherein the search expression comprises an explicit directive directing return of the first content page when the first content is also associated with the second content page.

47. The method of claim 45, wherein the search expression implicitly direct non-return of the second content page, when the second content page is also associated with the first content page.

48. The method of claim 42, further comprising selecting one or more advertisements to be provided in conjunction with a conditionally provided content page or a portion of a content page, the selecting of an advertisement comprising determining relative relevance of the advertisement to the conditionally provided content page or portion of the conditionally provided content page, and the determining including scoring the advertisement for relative relevance to the conditionally provided content page or the portion of the conditionally provided content page to one or more composite search expressions formed by correspondingly associating the search expression with one or more search expressions associated with the advertisement.

49. An apparatus comprising:

one or more processors; and

storage medium coupled to the processors, having stored therein a plurality of programming instructions to be operated by the one or more processors to cause the apparatus, in response to execution of the programming instructions by the one or more processors, to perform the method of claim 42 on the apparatus.

50. A machine implemented method comprising:

receiving a content page and one or more advertisements or access information of the one or more advertisements, by an advertising engine operated by one or more computing devices;

determining by the advertising engine relative relevance of one or more advertisements to a content page, the determining including scoring an advertisement for relative relevance to the content page by scoring relative relevance of one or more structures of the content page to a composite search expression, wherein a structure includes substructures, and the composite search expression is formed by correspondingly associating a user search expression with a search expression associated with the advertisement being scored, wherein the generating of a score for a structure is based at least in part on a distance function and a scoring function, wherein the distance function measures distances between sub-structures within the structure being scored to facilitate determining of mutual relevance of occurrence positions, and wherein the scoring function is positionally sensitive, yielding different scores for at least some different occurrence positions of the composite search expression in substructures of the structure being scored, irrespective of substructure category memberships; and

conditionally selecting or not selecting one or more of the advertisements for rendering with the content page or one or more portions of the content page by a content searching or consuming application, based at least in part on the scoring of the one or more advertisements, the content searching or consuming application being operated on one or more different or same computing devices as the advertising engine.

51. The method of claim 50, wherein each of the composite search expressions is formed by applying a proximity operator to the user search expression and one of the search expressions associated with one of the advertisements.

52. The method of claim 51, wherein the applying comprises explicitly applying a proximity operator to proximally associate the user search expression and the search expression associated with the advertisement.

53. The method of claim 52, wherein the proximity operator comprises a selected one of ##, %% or ˜

, where ## denotes proximately located, %% denotes proximately disjointed, and ˜

denotes proximately complementary.

54. The method of claim 50, wherein the content page comprises a web page of a web application, a XML document in a XML repository, a document in a document corpus, or a database object in a database.

55. The method of claim 50, wherein the structure comprises a tree corresponding to parsed markup of a portion of the content page, annotated with measurement information derived from layout structures associated with the content page.

56. An apparatus comprising:

one or more processors; and

storage medium coupled to the processors, having stored therein a plurality of programming instructions to be operated by the one or more processors to cause the apparatus, in response to execution of the programming instructions by the one or more processors, to perform the method of claim 50 on the apparatus.