METHODS AND APPARATUSES FOR SEARCHING CONTENT

• US 20090254549A1
• Filed: 04/10/2009
• Published: 10/08/2009
• Est. Priority Date: 06/12/2006
• Status: Active Grant

• Current Assignee: Lana Ivanovna Babayan
• Original Assignee: Zalag Corporation
• Inventors: Epstein, Samuel S.
• Granted Patent: US 8,140,511 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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;

generating in response, by the search engine, one or more scores indicative of relative relevance of a content or one or more portions of the content to the atomic search term, the generating by the search engine being based at least in part on a structure, a distance function, and a scoring function, the structure structurally describing the content having content nodes and/or text strings, the distance function measuring distances between sub-structures within the structure, and the scoring function being positionally sensitive, yielding different scores for different occurrence positions of the atomic search term in the content; 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 one or more scores includes establishing a bound on a number of children content nodes for each content node and/or a bound on a size of each of the text strings.

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 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 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 comprises a plurality of constituents, and the generating of one or more scores comprises generating said 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₁, 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 or a portion of a content, the selecting of an advertisement comprising determining relative relevance of the advertisement to the conditionally provided content or portion of the conditionally provided content, and the determining including scoring the advertisement for relative relevance to the conditionally provided content or the portion of the conditionally provided content 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;

generating in response, by the search engine, one or more scores indicative of relative relevance of a content or one or more portions of the content to the search expression, the generating by the search engine being based at least in part on a structure having children content nodes and/or text strings, a distance function, and a scoring function, the structure structurally describing the content, the distance function measuring distances between sub-structures within the structure, and the scoring function being 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 content; 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 one or more scores includes establishing a bound on a number of children content nodes for each content node and/or a bound on a size of each of the text strings.

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 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 comprises a plurality of constituents, and the generating of one or more scores comprises generating said 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 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³ⁱ 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

(a) x=(Σ

<sub>1≦

i≦

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

<sub>1≦

i≦

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

(b) 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.