Methods and apparatuses for searching content

• US 8,140,511 B2
• Filed: 04/10/2009
• Issued: 03/20/2012
• 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:
  US12/421,969
• Publication Number:
  US 20090254549A1
• Time in Patent Office: 1,075 Days
• Field of Search: None
• US Class Current: 707/706
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 30/0256 User search

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, 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 the generating of a score for a structure is based at least in part on a distance function and a scoring function, wherein the structure has sub-structures structurally describing at least a portion of the content page, and having content nodes and/or text strings, wherein the distance function measures distances between sub-structures within the structure, and the scoring function is positionally sensitive, yielding different scores for different occurrence positions of the atomic search term in the sub-structures; and

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

wherein the generating of a score for a structure further includes establishing a bound on a number of children content nodes considered for each content node and/or a bound on a size of each of the text strings considered.

2. The method of claim 1, wherein the atomic search term comprises a plurality of words.

3. The method of claim 1, wherein the structure comprises one or more strings of words, one or more markup strings, one or more trees corresponding to parsed markup, one or more deduced semantic trees, one or more database records or one or more database objects.

4. The method of claim 1, wherein the content page comprises one or more web pages of one or more web applications, one or more XML documents in one or more XML repositories, one or more documents in one or more document corpora, or one or more database objects in one or more databases.

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

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 the structure by recursively forming higher sub-structures from lower sub-structures of the constituents of the content.

8. The method of claim 1, wherein the content page comprises a plurality of constituents, and the generating of one or more scores comprises generating one or more scores 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 an aggregate comprises calculating an overall score for the aggregate as a match for the atomic search term by calculating c₁*D+c₂*Δ

+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, ρ

is the r-value for the atomic search expression on the aggregate, and c_l, c₂, and c₃ are non-negative real numbers such that c₁+c₂+c₃≦

1, wherein (Σ

<sub>1≦

i≦

m</sub>(c_i*P_i^ei)*Å

<sub>m+1≦

i≦

n</sub>P_i^ei provides the overall score, P₁, . . . , P_m being beneficial properties and P_m+1, . . . , P_n being detrimental properties.

10. The method of claim 9, wherein the generating 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 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+d_i)^x), where 0<

ε

≦

1, 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 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 each generating 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. 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, 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 the generating of a score for a structure is based at least in part on a distance function and a scoring function, wherein the structure have sub-structures structurally describing at least a portion of the content page, and having content nodes and/or text strings, wherein the distance function measures distances between sub-structures within the structure, and the scoring function is positionally sensitive, yielding different scores for different occurrence positions of either or both of the proximally associated first and second atomic sub-expressions in the sub-structures; and

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

wherein the generating of a score for a structure further includes establishing a bound on a number of children content nodes considered for each content node and/or a bound on a size of each of the text strings considered.

17. The method of claim 16, wherein either or both of the first and second atomic sub-expressions comprises a plurality of words.

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

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

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

denotes proximately complementary.

20. The method of claim 16, wherein the content page comprises one or more web pages of one or more web applications, one or more XML documents in one or more XML repositories, one or more documents in one or more document corpora, or one or more database objects in one or more databases.

21. The method of claim 16, wherein the structure comprises one or more strings of words, markup strings, trees corresponding to parsed markup, database records or database objects.

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

23. The method of claim 16, 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.

24. The method of claim 16, wherein the content page comprises a plurality of constituents, and the generating of one or more scores comprises generating one or more scores 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.

25. The method of claim 24, wherein the generating of scores for 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, wherein the density is bounded asymptotically as a function of text length.

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

+c₃*ρ

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

is a distribution score for the search expression on the aggregate, ρ

is the r-value for the search expression on the aggregate, and c₁, c₂, and c₃ are non-negative real numbers such that c₁+c₂+c₃≦

1, wherein (Σ

<sub>1≦

i≦

m</sub>(c_i*P_i^ei))*Å

<sub>m+1≦

i≦

n</sub>P_i^ei provides the overall score, P₁, . . . , P_m being beneficial properties and P_m+1, . . . , P_n being detrimental properties.

27. The method of claim 25, 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.

28. The method of claim 25, wherein the generating for 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_i 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.

29. The method of claim 25, wherein the generating for 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.

30. The method of claim 25, wherein the generating for 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.

31. The method of claim 30, 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^m−

Σ

<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.

32. The method of claim 25, wherein the generating for 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.

33. The method of claim 25, wherein the generating for 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.

34. The method of claim 25, wherein the generating for 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.

35. The method of claim 25, wherein for an aggregate corresponding to a region and children of the aggregate corresponding to sub-regions of the region, the generating for 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)),

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.

36. An apparatus, comprising:

one or more processors;

means, operated by the one or more processors, for receiving from a content searching or consuming application, an atomic search term;

means, operated by the one or more processors, for receiving a content page nominally associated with the atomic search term, or access information of the content page;

means, operated by the one or more processors, for generating 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 generation of a score for a structure is based at least in part on a distance function and a scoring function, wherein the structure has sub-structures structurally describing at least a portion of the content page, and having content nodes and/or text strings, wherein the distance function measures distances between sub-structures within the structure, and the scoring function is positionally sensitive, yielding different scores for different occurrence positions of the atomic search term in the sub-structures; and

means, operated by the one or more processors, for conditionally providing or not providing the content or one or more portions of the content, or access information of the content or one or more portions of the content, to the content searching or consuming application, based at least in part on the generated one or more scores;

wherein generation of a score for a structure further includes establishment of a bound on a number of children content nodes considered for each content node and/or a bound on a size of each of the text strings considered.

37. A tangible, non-transitory computer-readable storage medium comprising programming instructions configured, in response to execution of the programming instruction by an apparatus, to cause the apparatus to:

receive from a content searching or consuming application, an atomic search term;

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

generate 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 generation of a score for a structure is based at least in part on a distance function and a scoring function, wherein the structure has sub-structures structurally describing at least a portion of the content page, and having content nodes and/or text strings, wherein the distance function measures distances between sub-structures within the structure, and the scoring function is positionally sensitive, yielding different scores for different occurrence positions of the atomic search term in the sub-structures; and

conditionally provide or not provide the content or one or more portions of the content, or access information of the content or one or more portions of the content, to the content searching or consuming application, based at least in part on the generated one or more scores;

wherein generation of a score for a structure further includes establishment of a bound on a number of children content nodes considered for each content node and/or a bound on a size of each of the text strings considered.

38. An apparatus comprising:

one or more processors;

means operated by the one or more processors, for receiving from a content searching or consuming application, a search expression having a first and a second proximally associated atomic sub-expression;

means operated by the one or more processors, for receiving a content page nominally associated with the search expression, or access information of the content page;

means operated by the one or more processors, for generating 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 generation of a score for a structure is based at least in part on a distance function and a scoring function, wherein the structure have sub-structures structurally describing at least a portion of the content page, and having content nodes and/or text strings, wherein the distance function measures distances between sub-structures within the structure, and the scoring function is positionally sensitive, yielding different scores for different occurrence positions of either or both of the proximally associated first and second atomic sub-expressions in the sub-structures; and

means operated by the one or more processors, for conditionally providing or not providing the content or one or more portions of the content, or access information of the content or one or more portions of the content, to the content searching or consuming application, based at least in part on the generated one or more scores;

wherein generation of a score for a structure further includes establishment of a bound on a number of children content nodes considered for each content node and/or a bound on a size of each of the text strings considered.

39. A tangible, non-transitory computer-readable storage medium comprising programming instructions configured, in response to execution of the programming instruction by an apparatus, to cause the apparatus to:

receive from a content searching or consuming application, a search expression having a first and a second proximally associated atomic sub-expression;

receive a content page nominally associated with the search expression, or access information of the content page;

generate 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 generation of a score for a structure is based at least in part on a distance function and a scoring function, wherein the structure have sub-structures structurally describing at least a portion of the content page, and having content nodes and/or text strings, wherein the distance function measures distances between sub-structures within the structure, and the scoring function is positionally sensitive, yielding different scores for different occurrence positions of either or both of the proximally associated first and second atomic sub-expressions in the sub-structures; and

conditionally provide or not provide the content or one or more portions of the content, or access information of the content or one or more portions of the content, to the content searching or consuming application, based at least in part on the generated one or more scores;

wherein generation of a score for a structure further includes establishment of a bound on a number of children content nodes considered for each content node and/or a bound on a size of each of the text strings considered.