Systems and methods of adaptively screening matching chunks within documents

• US 8,126,880 B2
• Filed: 02/22/2008
• Issued: 02/28/2012
• Est. Priority Date: 02/22/2008
• Status: Active Grant

• Current Assignee: Stripe, Inc.
• Original Assignee: TigerLogic Corporation
• Inventors: Smik, Robert, Dexter, Jeffrey Matthew
• Primary Examiner(s): WILSON, KIMBERLY LOVEL
• Application Number:
  US12/035,600
• Publication Number:
  US 20090216765A1
• Time in Patent Office: 1,467 Days
• Field of Search: 707/999.006, 707/723
• US Class Current: 707/723
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A computer identifies within a document multiple matching chunks in response to a search request from a user. The search request includes one or more search keywords and each of the multiple matching chunks matches at least one of the search keywords. The computer partitions the matching chunks into multiple groups. The matching chunks within a respective group have an associated matching level to the search request. The computer returns one or more groups of the matching chunks to the user in an order consistent with their respective matching levels to the search request.

Claims

1. A computer-implemented method, comprising:

at a computer having memory and one or more processors;

identifying within a document multiple matching chunks in response to a search request from a user, wherein the search request includes one or more search keywords and each of the multiple matching chunks matches at least one of the search keywords;

partitioning the matching chunks into multiple groups, wherein matching chunks within a respective group have an associated matching level to the search request;

selecting at least first and second groups of matching chunks from the multiple groups of matching chunks, wherein the first group of matching chunks is selected if the first group'"'"'s associated matching level is higher than a first minimum matching level and the second group of matching chunks is selected if the second group'"'"'s associated matching level is higher than a second minimum matching level that is lower than the first minimum matching level; and

returning the first group of matching chunks and at least a subset of the second group of matching chunks to the user in an order consistent with the first and second groups'"'"' respective matching levels to the search request for concurrent display to the user of the computer.

2. The method of claim 1, wherein each of the search keywords has an associated weight indicative of the search keyword'"'"'s relevance to the user'"'"'s search interest.

3. The method of claim 2, wherein one of the search keywords has an associated weight of zero.

4. The method of claim 1, wherein the matching level of a respective group of matching chunks is, at least partially, determined by summing the weights of unique search keywords within one of the matching chunks.

5. The method of claim 1, wherein the matching level of a respective group of matching chunks is, at least partially, determined by the number of unique search keywords within one of the matching chunks.

6. The method of claim 1, wherein partitioning the matching chunks into multiple groups further includes:

selecting one of the matching chunks;

determining the selected matching chunk'"'"'s matching level and length;

invalidating the selected matching chunk if the selected matching chunk'"'"'s length is outside a predefined range; and

inserting the selected matching chunk into one of the groups of matching chunks if the selected matching chunk'"'"'s matching level is not less than the minimum matching level and the selected matching chunk'"'"'s length is not outside the predefined range.

7. The method of claim 6, wherein the length of the matching chunk is the total word count of the matching chunk'"'"'s textual content.

8. The method of claim 6, wherein the length of the matching chunk is the total character count of the matching chunk'"'"'s textual content after white-space normalization.

9. The method of claim 6, wherein inserting the selected matching chunk into one of the groups of matching chunks further includes:

identifying a respective group of matching chunks whose matching levels are the same or similar to the selected matching chunk'"'"'s matching level; and

adding the selected matching chunk to the group of matching chunks.

10. The method of claim 9, further comprising:

identifying within a group of matching chunks one or more matching chunks that are descendants of the selected matching chunk in a hierarchical data model of the document; and

invalidating the identified descendant matching chunks from the group of matching chunks.

11. The method of claim 6, further comprising:

after inserting the selected matching chunk into one of the groups of matching chunks,

determining a total count of matching chunks whose matching levels are no less than a minimum matching level;

updating the minimum matching level if the total count of matching chunks is greater than a predefined count threshold; and

invalidating at least a subset of one of the groups of matching chunks whose matching levels are less than the updated minimum matching level.

12. The method of claim 1, wherein returning the first and second groups of the matching chunks to the user further includes:

returning the first group of matching chunks to the user; and

returning the subset of the second group of matching chunks to the user until the total count of the returned matching chunks is not less than a predefined count threshold.

13. The method of claim 1, wherein returning the first and second groups of the matching chunks to the user further includes:

displaying a respective relevancy indicator adjacent each of the returned matching chunks.

14. The method of claim 13, wherein the relevancy indicator comprises image, text, number or a combination thereof.

15. A computer system, comprising:

memory;

one or more processors;

one or more programs stored in the memory and configured for execution by the one or more processors, the one or more programs including;

instructions for identifying within a document multiple matching chunks in response to a search request from a user, wherein the search request includes one or more search keywords and each of the multiple matching chunks matches at least one of the search keywords;

instructions for partitioning the matching chunks into multiple groups, wherein matching chunks within a respective group have an associated matching level to the search request;

instructions for selecting at least first and second groups of matching chunks from the multiple groups of matching chunks, wherein the first group of matching chunks is selected if the first group'"'"'s associated matching level is higher than a first minimum matching level and the second group of matching chunks is selected if the second group'"'"'s associated matching level is higher than a second minimum matching level that is lower than the first minimum matching level; and

instructions for returning the first group of matching chunks and at least a subset of the second group of matching chunks to the user in an order consistent with the first and second groups'"'"' respective matching levels to the search request for concurrent display to the user of the computer.

16. The computer system of claim 15, wherein each of the search keywords has an associated weight indicative of the search keyword'"'"'s relevance to the user'"'"'s search interest.

17. The computer system of claim 16, wherein one of the search keywords has an associated weight of zero.

18. The computer system of claim 15, wherein the matching level of a respective group of matching chunks is, at least partially, determined by summing the weights of unique search keywords within one of the matching chunks.

19. The computer system of claim 15, wherein the matching level of a respective group of matching chunks is, at least partially, determined by the number of unique search keywords within one of the matching chunks.

20. The computer system of claim 15, wherein the instructions for partitioning the matching chunks into multiple groups further include:

instructions for selecting one of the matching chunks;

instructions for determining the selected matching chunk'"'"'s matching level and length;

instructions for invalidating the selected matching chunk if the selected matching chunk'"'"'s length is outside a predefined range; and

instructions for inserting the selected matching chunk into one of the groups of matching chunks if the selected matching chunk'"'"'s matching level is not less than the minimum matching level and the selected matching chunk'"'"'s length is not outside the predefined range.

21. The computer system of claim 20, wherein the length of the matching chunk is the total word count of the matching chunk'"'"'s textual content.

22. The computer system of claim 20, wherein the length of the matching chunk is the total character count of the matching chunk'"'"'s textual content after white-space normalization.

23. The computer system of claim 20, wherein the instructions for inserting the selected matching chunk into one of the groups of matching chunks further include:

instructions for identifying a respective group of matching chunks whose matching levels are the same or similar to the selected matching chunk'"'"'s matching level; and

instructions for adding the selected matching chunk to the group of matching chunks.

24. The computer system of claim 23, further comprising:

instructions for identifying within a group of matching chunks one or more matching chunks that are descendants of the selected matching chunk in a hierarchical data model of the document; and

instructions for invalidating the identified descendant matching chunks from the group of matching chunks.

25. The computer system of claim 20, further comprising:

instructions for determining a total count of matching chunks whose matching levels are no less than a minimum matching level;

instructions for updating the minimum matching level if the total count of matching chunks is greater than a predefined count threshold; and

instructions for invalidating at least a subset of one of the groups of matching chunks whose matching levels are less than the updated minimum matching level.

26. The computer system of claim 15, wherein the instructions for returning the first and second groups of the matching chunks to the user further include:

instructions for returning the first group of matching chunks to the user; and

instructions for returning the subset of the second group of matching chunks to the user until the total count of the returned matching chunks is not less than a predefined count threshold.

27. The computer system of claim 15, wherein the instructions for returning the first and second groups of the matching chunks to the user further includes:

displaying a respective relevancy indicator adjacent each of the returned matching chunks.

28. The computer system of claim 27, wherein the relevancy indicator comprises image, text, number or a combination thereof.

29. A non-transitory computer readable storage medium having stored therein instructions, which when executed by a computer system cause the computer system to:

identify within a document multiple matching chunks in response to a search request from a user, wherein the search request includes one or more search keywords and each of the multiple matching chunks matches at least one of the search keywords;

partition the matching chunks into multiple groups, wherein matching chunks within a respective group have an associated matching level to the search request;

select at least first and second groups of matching chunks from the multiple groups of matching chunks, wherein the first group of matching chunks is selected if the first group'"'"'s associated matching level is higher than a first minimum matching level and the second group of matching chunks is selected if the second group'"'"'s associated matching level is higher than a second minimum matching level that is lower than the first minimum matching level; and

return the first group of matching chunks and at least a subset of the second group of matching chunks to the user in an order consistent with the first and second groups'"'"' respective matching levels to the search request for concurrent display to the user of the computer.

30. The computer readable storage medium of claim 29, wherein each of the search keywords has an associated weight indicative of the search keyword'"'"'s relevance to the user'"'"'s search interest.

31. The computer readable storage medium of claim 30, wherein one of the search keywords has an associated weight of zero.

32. The computer readable storage medium of claim 29, wherein the matching level of a respective group of matching chunks is, at least partially, determined by summing the weights of unique search keywords within one of the matching chunks.

33. The computer readable storage medium of claim 29, wherein the matching level of a respective group of matching chunks is, at least partially, determined by the number of unique search keywords within one of the matching chunks.

34. The computer readable storage medium of claim 29, wherein the instructions for partitioning the matching chunks into multiple groups further include:

instructions for selecting one of the matching chunks;

instructions for determining the selected matching chunk'"'"'s matching level and length;

instructions for invalidating the selected matching chunk if the selected matching chunk'"'"'s length is outside a predefined range; and

instructions for inserting the selected matching chunk into one of the groups of matching chunks if the selected matching chunk'"'"'s matching level is not less than the minimum matching level and the selected matching chunk'"'"'s length is not outside the predefined range.

35. The computer readable storage medium of claim 34, wherein the length of the matching chunk is the total word count of the matching chunk'"'"'s textual content.

36. The computer readable storage medium of claim 34, wherein the length of the matching chunk is the total character count of the matching chunk'"'"'s textual content after white-space normalization.

37. The computer readable storage medium of claim 34, wherein the instructions for inserting the selected matching chunk into one of the groups of matching chunks further include:

instructions for identifying a respective group of matching chunks whose matching levels are the same or similar to the selected matching chunk'"'"'s matching level; and

instructions for adding the selected matching chunk to the group of matching chunks.

38. The computer readable storage medium of claim 37, further comprising:

instructions for identifying within a group of matching chunks one or more matching chunks that are descendants of the selected matching chunk in a hierarchical data model of the document; and

instructions for invalidating the identified descendant matching chunks from the group of matching chunks.

39. The computer readable storage medium of claim 34, further comprising:

instructions for determining a total count of matching chunks whose matching levels are no less than a minimum matching level;

instructions for updating the minimum matching level if the total count of matching chunks is greater than a predefined count threshold; and

instructions for invalidating at least a subset of one of the groups of matching chunks whose matching levels are less than the updated minimum matching level.

40. The computer readable storage medium of claim 29, wherein the instructions for returning the first and second groups of the matching chunks to the user further include:

instructions for returning the first group of matching chunks to the user; and

instructions for returning the subset of the second group of matching chunks to the user until the total count of the returned matching chunks is not less than a predefined count threshold.

41. The computer readable storage medium of claim 29, wherein the instructions for returning the first and second groups of the matching chunks to the user further includes:

displaying a respective relevancy indicator adjacent each of the returned matching chunks.

42. The computer readable storage medium of claim 41, wherein the relevancy indicator comprises image, text, number or a combination thereof.