METHODS AND APPARATUSES FOR SEARCHING CONTENT

• US 20130173578A1
• Filed: 02/27/2013
• Published: 07/04/2013
• 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 9,047,379 B2
• Time in Patent Office: Days
• US Class Current: 707/706
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/0256 User search

Abstract

Embodiments of methods and apparatuses for searching contents, including structured search for atomic search expressions, including proximately associated atomic search expressions, are described herein. Embodiments may use tree structures (or more generally, graph structures), layout structures, and/or other information to capture within search results relevant content, include sub-document constituents, to reduce the incidence of false positives within search results, and/or to improve the accuracy of rankings within search results. Embodiments may use distance and/or scoring functions to generate scores for the structures to indicate relevance, including usage of local geometry, and linear iteration over portions of the content at a level to capture potential of a portion to influence other portions of the level, and influence received by a portion from the other portions of the level. Other embodiments may be described and claimed.

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 content nominally associated with the atomic search term, or access information of the content, by the search engine;

generating, by the search engine, one or more scores for one or more structures of the content indicative of relative relevance of the content or one or more portions of the content 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, and having content nodes and/or text strings, wherein the sub-structures are hierarchically organized with the one or more portions of the content in a sub-structure at a level respectively assigned one or more positions according to a geometry established for that level, 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 at each level, linearly iterating over one or more portions of the content at the level to capture potential of a portion to influence other portions of the level, and influence received by a portion from the other portions of the level.

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 1, wherein for portions of the content in a substructure at a level (N₁, . . . , N_k), iterating over one or more portions of the content at the level to capture potential of a portion to influence other portions of the level comprises iterating over N₁, . . . , N_k to compute Σ

<sub>1≦

i≦

k</sub>(A_i), Σ

<sub>1≦

i≦

k</sub>(A_i*D_i), Σ

<sub>1≦

i≦

k</sub>(A_i*p_i), and Σ

<sub>1≦

i≦

k</sub>(A_i*D_i*p_i), wherein A_i is relevance size of N_i, D_i is the density of N_i for the atomic search term, and p_i is the position of N_i.

7. The method of claim 6, wherein the method further comprises calculating a virtual sibling content item V that corresponds to a combined capacity of N₁, . . . , N_k to influence relevance to the atomic search term, such that the position of V is Σ

<sub>1≦

i≦

k</sub>(A_i*D_i*p_i)/Σ

<sub>1≦

i≦

k</sub>(A_i*D_i), and such that the influence capacity of V, corresponding to a product of relevance size with density for the atomic search term, is Σ

<sub>1≦

i≦

k</sub>(A_i*D_i).

8. The method of claim 6, wherein the method further comprises calculating a virtual sibling content item that corresponds to a maximum combined capacity of N₁, . . . , N_k to influence relevance to any search term, such that the position of is Σ

<sub>1≦

i≦

k</sub>(A_i*p_i)/Σ

<sub>1≦

i≦

k</sub>(A_i), and such that the influence capacity of , corresponding to a product of relevance size with maximum density, is Σ

<sub>1≦

i≦

k</sub>(A).

9. The method of claim 1, wherein for portions of the content in a substructure at a level (N₁, . . . , N_k), iterating over one or more portions of the content at the level to capture influence received by a portion from the other portions of the level comprises iterating over N₁, . . . N_k, where for each sibling content item N_i, a pre-normalized relevance value for N_i is X/(1+d_i)_x, where X is the influence capacity of a virtual content item corresponding to the atomic search expression, where d_i is the distance, according to the geometry, between N_i and the virtual content item corresponding to the atomic search expression, and where x is a distance attenuation exponent.

10. The method of claim 1, wherein a relevance value for N_i is a pre-normalized relevance value for N_i, divided by X/(1+d_i)^x, where X is the influence capacity of a virtual content item corresponding to a maximum combined capacity of N₁, . . . , N_k to influence relevance to any search term, where d_i is the distance, according to the geometry, between N_i and the virtual content item corresponding to the maximum combined capacity of N₁, . . . , N_k to influence relevance to any search term, and where x is a distance attenuation exponent.

28. An apparatus, comprising:

one or more processors; and

means, operated by the one or more processors, for causing the apparatus to perform any one of the methods of claims 1-10.

30. At least one 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 perform any one of the methods of claims 1-27.

11. 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 content nominally associated with the search expression, or access information of the content, by the search engine;

generating, by the search engine, one or more scores for one or more structures of the content indicative of relative relevance of the content or one or more portions of the content 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, and having content nodes and/or text strings, wherein the sub-structures are hierarchically organized with the one or more portions of the content in a sub-structure at a level respectively assigned one or more positions according to a geometry established for that level, 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 at each level, linearly iterating over one or more portions of the content at the level to capture potential of a portion to influence other portions of the level, and influence received by a portion from the other portions of the level.

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

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

14. The method of claim 11, 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.

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

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

17. The method of claim 11, wherein the search expression comprises sub-expressions E₁, . . . , E_m, and wherein for portions of the content in a substructure at a level (N₁, . . . N_k), iterating over one or more portions of the content at the level to capture potential of a portion to influence other portions of the level comprises iterating over N₁, . . . N_k to compute Σ

<sub>1≦

i≦

k</sub>(A_i) and Σ

<sub>1≦

i≦

k</sub>(A_i*p_i), and iterating over E₁, . . . E_m for each N_i to compute, for each 1≦

i≦

k and 1≦

j≦

m, Σ

<sub>1≦

i≦

k</sub>(A_i*D_i,j), and Σ

<sub>1≦

i≦

k</sub>(A_i*D_i,j*p_i), wherein A_i is relevance size of N_i, D_i,j is the density of N_i for search expression E_j, and p_i is the position of N_i.

18. The method of claim 17, wherein the method further comprises calculating, for each search expression E_j, a virtual sibling content item V_V that corresponds to a combined capacity of N₁, . . . N_k to influence relevance to E_j, such that the position of V_V is Σ

<sub>1≦

i≦

k</sub>(A_i*D_i,j*p_i)/Σ

<sub>1≦

i≦

k</sub>(A_i,j*D_i), and such that the influence capacity of V_j, corresponding to a product of relevance size with density for E_j, is Σ

<sub>1≦

i≦

k</sub>(A_i*D_i,j).

19. The method of claim 17, wherein the method further comprises calculating a virtual sibling content item that corresponds to a maximum combined capacity of N₁, . . . N_k to influence relevance to any search term, such that the position of is Σ

<sub>1≦

i≦

k</sub>(A_i*p_i)/Σ

<sub>1≦

i≦

k</sub>(A_i), and such that the influence capacity of V, corresponding to a product of relevance size with maximum density, is Σ

<sub>1≦

i≦

k</sub>(A_i).

20. The method of claim 11, wherein the search expression comprises sub-expressions E₁, . . . E_m, and wherein for portions of the content in a substructure at a level corresponds to content items at the level (N₁, . . . , N_k), iterating over one or more portions of the content at the level to capture influences received by a portion from the other portions of the level comprises iterating over N₁, . . . N_k, where for each sibling content item N_i and for each search expression E_j, content-tree-synthesized input to a pre-normalized relevance value for N_i for E_j is X_j/(1+d_i,j)^x, where X_j is the influence capacity of a virtual content item corresponding to E_j, where d_i,j is the distance, according to the geometry, between N_i and the virtual content item corresponding to E_j, and where x is a distance attenuation exponent.

21. The method of claim 20, wherein E₁, . . . , E_m are ordered according to post-order for a parse tree of the search expression, wherein if E_j is non-atomic, search-expression-tree-synthesized input to the pre-normalized relevance value for N_i for E_i is based at least in part on pre-normalized relevance values for N_i for E_j1, . . . , E_jhj, where E_j1, . . . , E are children of E_j in the parse tree.

22. The method of claim 21, wherein the search-expression-tree-synthesized input to the pre-normalized relevance value for N_i for E_j is an arithmetic mean, a geometric mean, or a harmonic mean of the pre-normalized relevance values for N_i for E_j1, . . . , E.

23. The method of claim 11 wherein a pre-normalized relevance value for N_i for E_j is based at least in part on content-tree-synthesized input to a pre-normalized relevance value for N_i for E_j and search-expression-tree-synthesized input to a pre-normalized relevance value for N_i for E_j.

24. The method of claim 23, wherein a pre-normalized relevance value for N_i for E_j is a sum of a content-tree-synthesized input to a pre-normalized relevance value for N_i for E_j, and a search-expression-tree-synthesized input to a pre-normalized relevance value for N_i for E_E.

25. The method of claim 11, wherein a relevance value for N_i for a search sub-expression E_j is a pre-normalized relevance value for N_i for E_j, divided by X/(1+d_i,j)^x, where X is the influence capacity of a virtual content item corresponding to a maximum combined capacity of N₁, . . . N_k to influence relevance to any search term, where d_i,j is the distance, according to the geometry, between N_i and the virtual content item corresponding to the maximum combined capacity of N₁, . . . N_k to influence relevance to any search term, and where x is a distance attenuation exponent.

26. The method of claim 11, 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.

27. The method of claim 11, wherein the search expression comprises a plurality of recursively embedded sub-expressions, including a sub-expression having the first and second proximally associated atomic sub-expressions.

29. An apparatus, comprising:

one or more processors; and

means, operated by the one or more processors, for causing the apparatus to perform any one of the methods of claims 11-27.