High efficiency document search

• US 7,657,515 B1
• Filed: 03/30/2007
• Issued: 02/02/2010
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: Alexa Internet Inc (Amazon.com, Inc.)
• Original Assignee: Alexa Internet Inc (Amazon.com, Inc.)
• Inventors: Jewell, Andrew Donaldson
• Primary Examiner(s): Al-Hashemi; Sana
• Application Number:
  US11/694,681
• Time in Patent Office: 1,040 Days
• Field of Search: 707/3, 707100-102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3332 Query translation
• CPC Class Codes: G06F 16/3341 using boolean model
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A computer-implemented search method and system is provided whereby a file is received including a query, typically for trademark search, having a first list of query terms and a second list of industry terms. The first and second lists may include tens or hundreds of terms. An AND-OR tree is constructed to represent the query terms and the industry terms and traversed to logically combine each of the query terms with each of the industry terms to form sub-queries which are executed in parallel. The results from each sub-query execution are limited according to a sub-query result limit. The sub-query results are combined to construct a query result for the original query included in the file. Duplicate results are removed from the query result and an ordinal number is included for each term in the query result before returning the query result.

Claims

1. A computer-implemented document search method comprising, by execution of program instructions by a computer system that comprises one or more computing devices:

in response to receiving a query including first and second lists of query terms, logically combining terms from the first and second lists to form document search sub-queries, each sub-query comprising at least one term from the first list and at least one term from the second list;

searching a data store by executing the sub-queries such that at least two of the document search sub-queries are executed in parallel, to identify responsive documents;

obtaining results from executing the document search sub-queries, the results including location information identifying the location of any of the terms from the first and second lists in the responsive documents;

combining the results from all sub-queries to form a single query result that includes the location information; and

returning the query result.

2. The method of claim 1, further comprising constructing an AND-OR tree to represent the terms included in the first and second lists of query terms.

3. The method of claim 1, further comprising constructing an AND-OR_N tree to represent the terms included in the first and second lists of query terms.

4. The method of claim 3, wherein the AND-OR_N tree is traversed using an OR_N logical process on the first and second lists of query terms.

5. The method of claim 1, wherein the first list includes more than one hundred terms.

6. The method of claim 5, wherein the second list includes more than one hundred terms.

7. The method of claim 1, wherein the first list includes more than a thousand terms.

8. The method of claim 7, wherein the second list includes more than a thousand terms.

9. The method of claim 1, including limiting the number of results obtained from each sub-query to a predetermined number.

10. The method of claim 1, wherein the information that identifies the terms from the first and second lists is an ordinal number that represents the position of the query term in the document.

11. The method of claim 1, further comprising removing duplications from the single query result.

43. The method of claim 1, wherein said sub-queries are formed in response to a determination that the size of the first or second lists exceeds a threshold.

44. The method of claim 1, wherein at least one of the lists of query terms is selected from a file containing one or more lists of terms.

12. A computer-implemented system for document searching, the system comprising:

(a) a computing system that comprises one or more computing devices coupled to a computer network said computing system operable to receive queries;

(b) a data store coupled to the computing system operable to store document data in a form suitable for computerized searching; and

(c) a software search component running on the computing system that, in response to the computing system receiving a query that includes first and second lists of query terms;

(i) logically combines the first and second lists of query terms to form sub-queries, each sub-query comprising at least one term from the first list and at least one term from the second list;

(ii) searches the data store by executing the sub-queries such that at least two of the sub-queries are executed in parallel;

(iii) obtains results from each sub-query execution, the results including information that identifies the locations of the terms from the first and second lists in the document data stored in the data store;

(iv) combines the results from all sub-queries to create a single query result;

(v) removes duplicate results from the single query result; and

(vi) returns the single query result.

13. The system of claim 12, wherein the data store comprises a local database, a remote database, or a distributed database.

14. The system of claim 12, wherein the software search component comprises a Web service.

15. The system of claim 13, wherein the Web service includes a search engine.

16. The system of claim 12, further including a search engine running on the computing system.

17. The system of claim 16, wherein the search engine is coupled to the software search component.

18. The system of claim 12, wherein the first and second lists of query terms are represented in said computing system by an AND-OR tree that is processed by the software search component.

19. The system of claim 12, wherein the first and second lists of query terms are represented in said computing system by an AND-OR_N tree that is processed by the software search component.

20. The system of claim 19, wherein the AND-OR_N tree is traversed using an OR_N logical operation.

21. The system of claim 12, wherein at least one of the first and second lists of query terms includes more than one hundred terms.

22. The system of claim 12, wherein at least one of the first and second lists of query terms includes more than a thousand terms.

23. The system of claim 12, wherein the number of results from each sub-query is limited to a predetermined number.

24. The system of claim 12, wherein the information that identifies the locations of the terms from the first and second lists in the document data is comprises an ordinal number that represents the position of each term in the document.

45. The system of claim 12, wherein the software search component only forms said sub-queries when the size of the first or second lists exceeds a threshold.

46. The method of claim 12, wherein at least one of the lists of query terms is selected from a file containing one or more lists of terms.

25. A computer-implemented document search method performed by a computing system configured with computer executable instructions, the method comprising:

executing sub-queries for searching a data store such that at least two search sub-queries are executed in parallel, wherein the search sub-queries are formed by logically combining each of a plurality of query terms from a first list with each of a plurality of query terms from a second list; and

obtaining results from each sub-query execution, the results including information that identifies the location of each of the query terms in document data stored in the data store.

26. The method of claim 25 further comprising:

combining the results from all sub-queries to create a single query result; and

returning the single query result.

27. The method of claim 26 further comprising removing duplicate results from the single query result.

47. The system of claim 25, wherein the sub-queries are executed only when the size of the first or second lists exceeds a threshold.

48. The method of claim 25, wherein at least one of the lists of query terms is selected from a file containing one or more lists of terms.

28. A computer-implemented system for document searching, the system comprising:

a data store;

a computing system that comprises one or more computing devices said computing system coupled to the data store; and

a Web service running on the computing system operable to form sub-queries by logically combining each of a plurality of query terms from a first list with each of a plurality of query terms from a second list, executing the sub-queries such that at least two of the sub-queries are executed in parallel, and obtaining results from each sub-query execution, the results including information that identifies the location of each of the query terms in document data stored in the data store.

29. The system of claim 28, wherein the results for all sub-queries are combined to create a single query result.

30. The system of claim 29, wherein duplicate results are removed from the single query result.

31. The system of claim 29, wherein each sub-query includes at least N query terms for at least one of the first list and the second list.

32. The system of claim 29, wherein each sub-query includes at least N query terms from the first list and M query terms from the second list.

49. The system of claim 28, wherein the sub-queries are executed only when the size of the first or second list of terms exceeds a threshold.

50. The method of claim 28, wherein at least one of the lists of query terms is selected from a file containing one or more lists of terms.

33. A computer-implemented method for document searching by execution of program instructions by a computer system that comprises one or more computing devices, the method comprising:

in response to receiving a query including first and second lists of query terms, logically combining the terms from the first and second lists to form document search sub-queries, each sub-query comprising at least a term from the first list and at least a term from the second list;

searching a data store by executing the document search sub-queries such that at least two of the document search sub-queries are executed in parallel to identify documents that contain terms of first and second lists of query terms;

obtaining results from executing the document search sub-queries;

limiting the number of results obtained from each sub-query to a predetermined number;

combining the predetermined number of results obtained from each sub-query to create a single query result; and

returning the single query result.

34. The method of claim 33, further comprising constructing an AND-OR tree to represent the terms included in the first and second lists of query terms.

35. The method of claim 33, further comprising constructing an AND-OR_N tree to represent the query terms included in the first and second lists of query terms.

36. The method of claim 35, wherein the AND-OR_N tree is traversed using an OR_N logical process on the first and second lists of query terms.

37. The method of claim 33, wherein the first list includes more than one hundred query terms.

38. The method of claim 37, wherein the second list includes more than one hundred query terms.

39. The method of claim 33, wherein the first list includes more than a thousand query terms.

40. The method of claim 39, wherein the second list includes more than a thousand query terms.

41. The method of claim 33, including limiting the number of results obtained from each sub-query to a predetermined number.

42. The method of claim 33, further comprising removing duplications from the single query results.

51. The system of claim 33, wherein the sub-queries are formed in response to a determination that the size of the first or second list of terms exceeds a threshold.

52. The method of claim 33, wherein at least one of the lists of query terms is selected from a file containing one or more lists of terms.