Search templates

• US 7,774,353 B2
• Filed: 08/30/2007
• Issued: 08/10/2010
• Est. Priority Date: 08/30/2007
• Status: Active Grant

• Current Assignee: Perfect Search Corporation
• Original Assignee: Perfect Search Corporation
• Inventors: Higgins, John C., Inouye, Dillon K., Pratt, John P., Millett, Ronald P.
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Nguyen; Loan T
• Application Number:
  US11/847,869
• Publication Number:
  US 20090063479A1
• Time in Patent Office: 1,076 Days
• Field of Search: None
• US Class Current: 707/758
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Searching a data store for parameter patterns specified in a query. A method includes receiving a query from a user including N parameter patterns. One or more alternatives are associated to one or more of the N parameter patterns. One or more templates are created. Each of the templates describes a number of microsearches. Each of the microsearches includes one or more of the N parameter patterns or the alternatives. Microsearches described by at least one of the one or more templates are enumerated. One or more sub-microsearches are performed by searching for parameter patterns and/or alternatives. Each sub-microsearch may have less than all terms needed for a full microsearch. Based on the results of the one or more sub-microsearches, one or more microsearches are eliminated from searching. The data store is searched using one or more of the remaining microsearches.

Claims

1. In a computing environment including a data store, the data store including data items stored in records in the data store, a method of searching a data store for parameter patterns specified in a query, the method comprising:

receiving a query from a user including N parameter patterns;

associating one or more alternatives to one or more of the N parameter patterns with one or more of the N parameter patterns;

creating one or more templates, wherein each of the templates includes a plurality of microsearches, wherein each microsearch including one or more of the N parameter patterns or the alternatives;

assigning weights to each of the N parameter patterns and to each of the alternatives, wherein microsearches have weights based on the weights assigned to parameter patterns and/or alternatives in the microsearch;

determining a weight range for one or more of the templates based on the assigned weights;

enumerating specifically all or a portion of the microsearches described by at least one of the one or more templates, wherein enumerating microsearches is performed for a template in response to weights for microsearhes being searched from another template approaching a weight range of the template;

performing one or more sub-microsearches from the microsearches, wherein the sub-microsearch includes less than all the parameter patterns and the alternatives in the microsearch;

searching the sub-microsearches for parameter patterns and alternatives;

eliminating one or more microsearches from further searching if the parameter patterns and the alternatives do not appear in the same record of the data store based on the results of the one or more sub-microsearches; and

searching the data store using one or more of the remaining microsearches.

2. The method of claim 1, wherein searching the data store using one or more of the remaining microsearches is performed until a predetermined condition is satisfied.

3. The method of claim 2, wherein the predetermined condition comprises finding a prespecified number of records that satisfy the query.

4. The method of claim 3, wherein satisfying the query comprises finding a record for a microsearch.

5. The method of claim 1, further comprising:

assigning weights to each of the N parameter patterns and to each of the alternatives, wherein microsearches have weights based on the weights assigned to parameter patterns and/or alternatives in the microsearch;

based on the assigned weights, determining a weight range for one or more of the templates; and

wherein the act of enumerating microsearches is performed for a template in response to weights for microsearches being searched from another template approaching a weight range of the template.

6. The method of claim 5, wherein creating one or more templates comprises creating templates on an as needed basis in determining that weights for microsearches being searched are approaching a weight range of the template.

7. The method of claim 5, wherein creating one or more templates comprises creating all templates prior to performing one or more microsearches.

8. The method of claim 1, wherein performing one or more sub-microsearches comprises searching an index for parameter patterns and/or alternatives.

9. The method of claim 8, wherein the index is an abbreviated index.

10. The method of claim 8, wherein searching an index comprises searching for index entries that index combinations of parameter patterns and/or alternatives.

11. The method of claim 8, wherein searching an index comprises searching for index entries that index ranges of parameter patterns and/or alternatives.

12. The method of claim 11, wherein the ranges are defined by a systematic methodology and wherein the methodology is generally recognized as a methodology for computation or description of at least one of proximity, distance, or metric between entities.

13. The method of claim 12, wherein the systematic methodology is expressed by a computer executable algorithm.

14. The method of claim 12, wherein the systematic methodology is expressed by a recursive partial function.

15. The method of claim 11, wherein the ranges comprise numeric proximity ranges.

16. The method of claim 11, wherein the ranges comprise geographic proximity ranges.

17. The method of claim 11, wherein the ranges comprise linguistic proximity ranges.

18. The method of claim 1, wherein performing one or more sub-microsearches comprises selecting sub-microsearch terms to facilitate eliminating one or more entire templates and corresponding described microsearches from searching.

19. In a computing environment including a data store, the data store including data items stored in records in the data store, a computer readable medium storing computer executable instructions that when executed by one or more processors cause one or more processors to perform the following:

receiving a query from a user including N parameter patterns;

associating one or more alternatives to one or more of the N parameter patterns;

creating one or more templates, wherein each of the templates includes a plurality of microsearches, wherein each microsearch including one or more of the N parameter patterns or the alternatives;

assigning weights to each of the N parameter patterns and to each of the alternatives, wherein microsearches have weights based on the weights assigned to parameter patterns and/or alternatives in the microsearch;

determining a weight range for one or more of the templates based on the assigned weights;

enumerating specifically all or a portion of the microsearches described by at least one of the one or more templates, wherein enumerating microsearches is performed for a template in response to weights for microsearches being searched from another template approaching a weight range of the template;

performing one or more sub-microsearches from the microsearches, wherein the sub-microsearch includes less than all the parameter patterns and the alternatives in the microsearch;

searching the sub-microsearches for parameter patterns and alternatives;

eliminating one or more microsearches from further searching if the parameter patterns and the alternatives do not appear in the same record or the data store based on the results of the one or more sub-microsearches; and

searching the data store using one or more of the remaining microsearches.

20. In a computing environment including a data store, the data store including data items stored in records in the data store, a system for searching a data store for parameter patterns specified in a query, the system comprising:

one or more processors;

a computer readable memory coupled to the one or more processors, the computer readable memory storing computer executable instructions that when executed by the one or more processors cause the one or more processors to perform the following acts;

receiving a query from a user including N parameter patterns;

associating one or more alternatives to one or more of the N parameter patterns;

creating one or more templates, wherein each of the templates includes a plurality of microsearches, wherein each microsearch including one or more of the N parameter patterns or the alternatives;

assigning weights to each of the N parameter patterns and to each of the alternatives, wherein microsearches have weights based on the weights assigned to parameter patterns and/or alternatives in the microsearch;

determining a weight range for one or more of the templates based on the assigned weights;

enumerating specifically all or a portion of the microsearches described by at least one of the one or more templates, wherein enumerating microsearches is performed for a template in response to weights for microsearches being searched from another template approaching a weight range of the template;

performing one or more sub-microsearches from the microsearches, wherein said sub-microsearch includes less than all the parameter patterns and the alternatives in the microsearch;

searching the sub-microsearches for parameter patterns and alternatives;

eliminating one or more microsearches from further searching if the parameter patterns and the alternatives do not appear in the same record of the data store based on the results of the one or more sub-microsearches; and

searching the data store using one or more of the remaining microsearches.