METHODS AND APPARATUSES FOR SEARCHING CONTENT

• US 20160012131A1
• Filed: 04/24/2015
• Published: 01/14/2016
• Est. Priority Date: 06/12/2006
• Status: Abandoned Application

• Current Assignee: Samuel S. Epstein
• Original Assignee: Zalag Corporation
• Inventors: Epstein, Samuel S.
• Application Number:
  US14/695,478
• Publication Number:
  US 20160012131A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/0256 User search
• CPC Class Codes: G06Q 50/10 Services

Abstract

Embodiments of methods and apparatuses for searching contents, including structured search for search expressions associated with documents, 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, including sub-document constituents, and/or to improve the accuracy of rankings within search results, and/or to classify documents within hierarchies of documents, and/or to cluster documents. 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, and influence received by a portion from lower levels. Other embodiments may be described and claimed.

Claims

1. A computer implemented method comprising:

receiving, by a computing device, a hierarchy of documents, a set having one or more documents, and a search expression associated with the set of documents, with a member of the set of documents, with a constituent of a member of the set of documents, or with a set of constituents of members of the set of documents;

generating, by the computing device, one or more scores for one or more structures of the hierarchy of documents indicative of relative relevance of the documents having the structure to the search expression,

wherein the generating of a score for a structure indicative of relative relevance of first one or more of the documents to the search expression 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 hierarchy of documents, and having nodes and/or text strings, wherein the sub-structures are hierarchically organized with the one or more portions of the hierarchy of documents 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 the structure for different occurrence positions of a given sub-structure; and

outputting the one or more scores for one or more structures of the hierarchy of documents indicative of relative relevance of the structures to the document or document constituent or set of documents or set of document constituents associated with the search expression.

2. The method of claim 1, wherein the scoring function, for different occurrence positions of a given sub-structure, generates different scores for the structure and for other sub-structures.

3. The method of claim 1, wherein the search expression is generated from a document or from a sub-structure of the structure.

4. The method of claim 3, wherein the document from which the search expression is generated is classified into a pre-terminal sub-structure of the structure according to a score for the search expression generated from the document.

5. The method of claim 3, wherein the scoring function calculates for each of two documents or sub-structures, a score for the search expression for the other document or sub-structure, and a secondary distance between the two documents or sub-structures wherein the secondary distance is calculated as a function of the two search scores.

6. The method of claim 5, further comprising applying cluster analysis to a set of documents t and/or sub-structures, based on these secondary distances.

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

8. The method of claim 1, wherein the hierarchy of documents comprises a plurality of web pages of one or more web applications, a plurality of XML documents in one or more XML repositories, a plurality of documents in one or more document corpora, or a plurality of database objects in one or more databases.

9. The method of claim 1, wherein for portions of the hierarchy of documents in a substructure at a level (N₁, . . . , N_k), iterating over one or more portions of the hierarchy of documents 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₁*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 search expression, and p_i is the position of N.

10. The method of claim 9, 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 search expression, such that the position of V is Σ

<sub>1≦

i≦

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

<sub>i≦

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 search expression, is Σ

<sub>1≦

i≦

k</sub>(A_i*D_i).

11. 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_i).

12. The method of claim 1, wherein for portions of the hierarchy of documents 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 search expression, where d_i is the distance, according to the geometry, between N_i and the virtual content item corresponding to the search expression, and where x is a distance attenuation exponent.

13. The method of claim 1, wherein a relevance value for N, 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.

14. The method of claim 1, wherein the search expression comprises sub-expressions E₁, . . . , E_m, and wherein for portions of the hierarchy in a substructure at a level corresponds to documents at the level (N₁, . . . , N_k), iterating over one or more portions of the hierarchy 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 item N_i and for each sub-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 document corresponding to E_j, where d_i,j is the distance, according to the geometry, between N_i and the virtual document corresponding to E_j, and where x is a distance attenuation exponent.

15. The method of claim 14, 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_j is based at least in part on pre-normalized relevance values for N_i for E_j1, . . . , E_jhj, where E_j1, . . . , E_jhj are children of E_j in the parse tree.

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

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

18. The method of claim 17, 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_j.

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

20. A computing apparatus, comprising:

one or more processors; and

means, operated by the one or more processors, for causing the apparatus to perform the computer implemented method of claim 1.

21. A computing apparatus, comprising:

one or more processors; and

means, operated by the one or more processors, for causing the apparatus to perform the computer implemented method of claim 14.

22. At least one non-transitory computer-readable storage medium comprising programming instructions configured, in response to execution of the programming instruction by a computing apparatus, to cause the computing apparatus to perform any the computer implemented method of claim 1.

23. At least one non-transitory computer-readable storage medium comprising programming instructions configured, in response to execution of the programming instruction by a computing apparatus, to cause the computing apparatus to perform any the computer implemented method of claim 14.