System and method for subset searching and associated search operators

• US 10,691,709 B2
• Filed: 10/21/2016
• Issued: 06/23/2020
• Est. Priority Date: 10/28/2015
• Status: Active Grant

• Current Assignee: Open Text Sa Ulc (Open Text Corporation)
• Original Assignee: Open Text Sa Ulc (Open Text Corporation)
• Inventors: Pidduck, Patrick Thomas Sidney, Tausky, David Alan
• Primary Examiner(s): Owyang, Michelle N
• Application Number:
  US15/331,327
• Publication Number:
  US 20170124162A1
• Time in Patent Office: 1,341 Days
• Field of Search: 707705-780
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/248 Presentation of query results

Abstract

Embodiments as disclosed may provide a search operator that addresses the problem of query construction for finding objects that include some number (N) of a set of terms (M). Moreover, embodiments as disclosed herein may efficiently implement the searches specified by such subset operators using a subset process that combines results from a set of term processes where only one term process may be needed for each search term (or search term variant).

Claims

1. A search system, comprising:

a processor;

a data store, having a corpus and an index of the corpus stored thereon, the corpus comprising a set of objects, each object having a corresponding identifier the index including a set of terms, each of the set of terms associated with one or more identifiers of objects which include that term;

a computer readable medium, having instructions for;

receiving a search query having a set of search terms and a subset operator, the subset operator including a threshold and the set of search terms, wherein the threshold defines an amount of search terms of the set of search terms that are present in each object of the set of objects that satisfies the subset operator and the subset operator is executable for finding each object of the set of objects that includes the amount of search terms, wherein the amount of search terms is specified as a number value or a percentage value of the set of search terms; and

executing the subset operator by;

generating a search tree based on the set of search terms, the search tree having a subset operator node including a subset process configured according to the threshold, wherein the subset operator node includes a set of sub-nodes, each sub-node comprising a term process for a respective search term in the set of search terms;

executing the search tree using the index to determine one or more objects of the set of objects that satisfy the subset operator, wherein executing the search tree comprises;

for each term process;

identifying a result for that term process using the index, the result identifying one or more objects of the set of objects that include the respective term for that term process; and

returning the identified result for that term process identifying the one or more objects that include the respective term for that term process; and

executing the subset process by;

evaluating the results returned by each of the term processes by combining the respective results returned by each of the term processes to determine each of the one more objects having the amount of terms in the set of search terms equal or greater than the amount of search terms defined by the threshold; and

returning the identifiers for the one or more objects determined by the subset process that satisfy the subset operator.

2. The search system of claim 1, wherein each of the term processes is an iterator configured to evaluate the set of objects according to an order of the identifiers of the objects and the result is an identifier of the next object containing the search term associated with the term process according to the order.

3. The search system of claim 2, wherein the identifiers are numerical and the order of the identifiers is sequentially from lowest to highest.

4. The search system of claim 3, wherein the subset process is configured to call each of the term processes to determine the result for that term process.

5. The search system of claim 4, wherein evaluating the results from each of the term processes further comprises determining if a number of returned respective results from each of the term processes with a minimum value is equal to, or exceeds, the threshold and if so, adding the object in the retuned respective result associated with the identifier to the one or more objects determined by the subset process that satisfy the subset operator.

6. The search system of claim 5, wherein the subset process obtains a next result from each term process whose result is the minimum value of all the results returned by the term processes.

7. A non-transitory computer readable medium, comprising instructions for:

storing a corpus and an index of the corpus in a data store, the corpus comprising a set of objects, each object having a corresponding identifier the index including a set of terms, each of the set of terms associated with one or more identifiers of objects which include that term;

receiving a search query having a set of search terms and a subset operator, the subset operator including a threshold and the set of search terms, wherein the threshold defines an amount of search terms of the set of search terms that are present in each object of the set of objects that satisfies the subset operator and the subset operator is executable for finding each object of the set of objects that includes the amount of search terms, wherein the amount of search terms is specified as a number value or a percentage value of the set of search terms; and

executing the subset operator by;

generating a search tree based on the set of search terms, the search tree having a subset operator node including a subset process configured according to the threshold, wherein the subset operator node includes a set of sub-nodes, each sub-node comprising a term process for a respective search term in the set of search terms;

executing the search tree using the index to determine one or more objects of the set of objects that satisfy the subset operator, wherein executing the search tree comprises;

for each term process;

identifying a result for that term process using the index, the result identifying one or more objects of the set of objects that include the respective term for that term process; and

returning the identified result for that term process identifying the one or more objects that include the respective term for that term process; and

executing the subset process by;

evaluating the results returned by each of the term processes by combining the respective results returned by each of the term processes to determine each of the one more objects having the amount of terms in the set of search terms equal or greater than the amount of search terms defined by the threshold; and

returning the identifiers for the one or more objects determined by the subset process that satisfy the subset operator.

8. The non-transitory computer readable medium of claim 7, wherein each of the term processes is an iterator configured to evaluate the set of objects according to an order of the identifiers of the objects and the result is an identifier of the next object containing the search term associated with the term process according to the order.

9. The non-transitory computer readable medium of claim 8, wherein the identifiers are numerical and the order of the identifiers is sequentially from lowest to highest.

10. The non-transitory computer readable medium of claim 9, wherein the subset process is configured to call each of the term processes to determine the result for that term process.

11. The non-transitory computer readable medium of claim 10, wherein evaluating the results from each of the term processes further comprises determining if a number of returned respective results from each of the term processes with a minimum value is equal to, or exceeds, the threshold and if so, adding the object in the retuned respective result associated with the identifier to the one or more objects determined by the subset process that satisfy the subset operator.

12. The non-transitory computer readable medium of claim 11, wherein the subset process obtains a next result from each term process whose result is the minimum value of all the results returned by the term processes.

13. A method for implementing a subset search on a search system, comprising:

storing a corpus and an index of the corpus in a data store, the corpus comprising a set of objects, each object having a corresponding identifier the index including a set of terms, each of the set of terms associated with one or more identifiers of objects which include that term;

receiving a search query having a set of search terms and a subset operator, the subset operator including a threshold and the set of search terms, wherein the threshold defines an amount of search terms of the set of search terms that are present in each object of the set of objects that satisfies the subset operator and the subset operator is executable for finding each object of the set of objects that includes the amount of search terms, wherein the amount of search terms is specified as a number value or a percentage value of the set of search terms; and

executing the subset operator by;

generating a search tree based on the set of search terms, the search tree having a subset operator node including a subset process configured according to the threshold, wherein the subset operator node includes a set of sub-nodes, each sub-node comprising a term process for a respective search term in the set of search terms;

executing the search tree using the index to determine one or more objects of the set of objects that satisfy the subset operator, wherein executing the search tree comprises;

for each term process;

identifying a result for that term process using the index, the result identifying one or more objects of the set of objects that include the respective term for that term process; and

returning the identified result for that term process identifying the one or more objects that include the respective term for that term process; and

executing the subset process by;

evaluating the results returned by each of the term processes by combining the respective results returned by each of the term processes to determine each of the one more objects having the amount of terms in the set of search terms equal or greater than the amount of search terms defined by the threshold; and

returning the identifiers for the one or more objects determined by the subset process that satisfy the subset operator.

14. The method of claim 13, wherein each of the term processes is an iterator configured to evaluate the set of objects according to an order of the identifiers of the objects and the result is an identifier of the next object containing the search term associated with the term process according to the order.

15. The method of claim 14, wherein the identifiers are numerical and the order of the identifiers is sequentially from lowest to highest.

16. The method of claim 15, wherein the subset process is configured to call each of the term processes to determine the result for that term process.

17. The method of claim 16, wherein evaluating the results from each of the term processes further comprises determining if a number of returned respective results from each of the term processes with a minimum value is equal to, or exceeds, the threshold and if so, adding the object in the retuned respective result associated with the identifier to the one or more objects determined by the subset process that satisfy the subset operator.

18. The method of claim 17, wherein the subset process obtains a next result from each term process whose result is the minimum value of all the results returned by the term processes.