Systems and methods for updating query results based on query deltas

• US 7,720,845 B2
• Filed: 08/13/2004
• Issued: 05/18/2010
• Est. Priority Date: 08/13/2004
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Hunt, Patrick David, Stata, Raymond P.
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Reyes; Mariela D
• Application Number:
  US10/917,742
• Publication Number:
  US 20060036580A1
• Time in Patent Office: 2,104 Days
• Field of Search: None
• US Class Current: 707/732
• CPC Class Codes: G06F 16/3349 Reuse of stored results of previous queries

Abstract

Systems and methods for automatically updating queries on a data store, such as a personal content database (PCDB), are provided. A query engine runs queries against two indexes: a first index that represents a previous state of documents and a second index that represents a current state of documents. The query is run twice and a delta analysis is performed, i.e., a determination is made as to which documents have changed in some respect from the previous state to the current state, and a view or a count associated with at least one query changes in accordance with the delta analysis. Transactions may be batched dynamically by a transaction manager until an optimal number of documents have changed or a certain amount of time has passed prior to re-running the query and performing the delta analysis.

Claims

1. A computer-implemented method, comprising:

generating a first representation of a set of one or more documents of a plurality of documents, wherein the first representation represents a state of the set of one or more documents before at least one change is made to at least one document of said plurality of documents;

after said at least one change is made to at least one document of said plurality of documents, performing the steps of;

causing a currently-stale view or currently-stale count for at least one current query to be displayed on a user interface;

wherein the currently-stale view or currently-stale count is based at least in part on a result set of at least one previously-executed query that was executed on said plurality of documents before said at least one change was made;

generating a second representation of the set of one or more documents of the plurality of documents, wherein the second representation represents a state of the set of one or more documents after said at least one change was made, whereby said first representation and said second representation together represent at least all of the documents affected by said at least one change;

comparing the first and second representations outputting an updated view or count by, to form a third representation that includes representations of differences between said first and second representations;

while said currently-stale view or currently-stale count is displayed, on said user interface utilizing said third representation to update said currently-stale view or currently-stale count on said user interface to reflect said at least one change;

wherein the step of comparing is performed by one or more processors.

2. The computer-implemented method according to claim 1, wherein said currently-stale view or currently-stale count comprises:

an output of a function applied to the result set.

3. The computer-implemented method according to claim 1, wherein said currently-stale view or currently-stale count comprises:

at least one of (a) information in the result set and (b) a count of information in the result set.

4. The computer-implemented method according to claim 3, wherein said utilizing step further comprises utilizing said third representation to update said count of information in the result set by determining individually whether the differences represented by said third representation represent additions or deletions of documents from said result set.

5. The computer-implemented method according to claim 4, wherein said utilizing step further comprises, for a difference represented by said third representation, incrementing said count of information in the result set if the difference represented by said third representation represents an addition and decrementing said result set count if the difference represented by said third representation represents a deletion.

6. The computer-implemented method according to claim 3, wherein said utilizing step further comprises utilizing said third representation to update said count of information in the result set by determining individually whether the differences represented by said third representation represent additions, modifications or deletions of documents from said result set.

7. The computer-implemented method according to claim 6, wherein said utilizing step further comprises, for a difference represented by said third representation, incrementing said count of information in the result set if the difference represented by said third representation represents an addition, decrementing said result set count if the difference represented by said third representation represents a deletion, and not modifying said result set count if the difference represented by said third representation represents a modification.

8. The computer-implemented method according to claim 1, wherein said at least one previously-executed query that was executed before said at least one change comprises:

at least part of at least two queries combined to form the result set.

9. The computer-implemented method according to claim 1, further comprising:

caching at least a part of the third representation as a result to be shared among at least two queries during utilizing said third representation to update said view or count to reflect said at least one change.

10. The computer-implemented method according to claim 1, whereby said first representation and said second representation include at least one document not affected by the at least one change.

11. The computer-implemented method according to claim 1, wherein said comparing step further comprises identifying whether the differences between said first and second representations represent an addition of a document, a deletion of a document or a change to a document.

12. The computer-implemented method according to claim 11, wherein said comparing step further comprises identifying whether said differences represent a change to at least one metatag of a document.

13. The computer-implemented method according to claim 1, wherein said first and second representations include a mix of forward and inverted representations.

14. The computer-implemented method according to claim 1, wherein said first and second representations include inverted representations.

15. The computer-implemented method according to claim 1, further comprising batching a plurality of instances of said at least one change prior to said generating the second representation.

16. The computer-implemented method according to claim 15, wherein said batching step comprises batching dynamically based upon a change rate for changes to be made.

17. The computer-implemented method according to claim 1, wherein said comparing step further comprises mapping said at least one change to a change in said currently-stale view or currently-stale count by determining whether said at least one change represents an addition to the result set, a modification to the result set, or a deletion to the result set.

18. A computing device comprising means for performing the computer-implemented method of claim 1.

19. A computer readable storage medium storing one or more computer executable instructions, which, when executed on one or more processors, causes performance of the computer-implemented method of claim 1.

34. The computer-implemented method according to claim 1, further comprising:

causing a plurality of batched results to be returned to the user interface;

optimizing a batch size dynamically in view of a number of changes and an amount of time passed since a last batch was processed.

35. The computer-implemented method according to claim 1, further comprising:

a mutator making changes to the at least one document of the plurality of documents in units known as transactions;

wherein when a transaction rate is high, the mutator batches multiple transactions into a single old/new pair, thereby amortizing overhead.

36. The computer-implemented method according to claim 1, further comprising:

a plurality of query runners running more than one query in parallel so that common parts across these multiple queries are computed only once and are shared.

37. The computer-implemented method according to claim 36, further comprising:

sharing results common to multiple queries across different query runners using caching.

38. The computer-implemented method according to claim 1, further comprising:

running a large number of fixed queries against a stream of new and changing documents.

39. The computer-implemented method according to claim 1, further comprising:

performing continuous rather than discrete querying.

40. The computer-implemented method according to claim 1, further comprising:

using queries to populate aspects of the user interface that need to be updated based at least in part on changes to the at least one document of said plurality of documents.

41. The computer-implemented method according to claim 1, further comprising:

saving a predetermined number of searches.

42. The computer-implemented method according to claim 41, further comprising:

naming the saved searches and listing them in a location visible to an end-user.

43. The computer-implemented method according to claim 42, wherein the location is a left-hand side of the user interface.

44. The computer-implemented method according to claim 34, further comprising:

enabling scalable concurrency of queries by running a large number of query runners in parallel.

45. The computer-implemented method of claim 1, further comprising:

generating a first index that represents an old state of the set of one or more documents; and

generating a second index that represents a new state of the set of one or more documents.

20. A computing device comprising a processor in communication with a data store, wherein said data store stores a plurality of documents in at least one storage unit, the computing device including:

a data store component configured to identify at least one change to be made to the data store;

an old state data structure generation component configured to generate a first data structure representing a set of one or more documents of the plurality of documents, wherein the first data structure represents a state of the set of one or more documents before at least one change is made to content of the data store;

a user interface component configured to cause a currently-stale view or currently-stale count for at least one current query to be displayed on a user interface after said at least one change is made to the data store, based at least in part on a result set of at least one previously-executed query that was executed on said plurality of documents before said at least one change was made;

a new state data structure generation component configured to generate a second data structure of the set of one or more documents of the plurality of documents, wherein the second data structure represents a state of the set of one or more documents after the at least one change was made, whereby said first data structure and said second data structure together represent at least all of the documents affected by the at least one change;

a comparator configured to perform an analysis involving the first and second data structures, to form a third data structure that includes representations of differences between said first and second data structures;

an update component configured to utilize said third data structure to update said currently-stale view or currently-stale count, while said currently-stale view or currently-stale count is displayed on said user interface, to reflect said at least one change.

46. The computing device of claim 20, wherein:

as part of the analysis, the comparator is configured to execute the at least one current query against a first index for the first data structure, and is configured to execute the at least one current query against a second index for the second data structure.

21. A computer-implemented method comprising:

after at least one change is made to content of an email data store, performing the steps of;

transmitting via an application programming interface (API) at least one current query to be executed on said email data store to a query handler for said email data store;

receiving, by said API in response to the at least one current query, a third representation from said query handler that is based at least in part on a comparison of;

(A) a first representation of a set of one or more email documents of a plurality of email documents, wherein the first representation represents a state of the set of one or more email documents before the at least one change is made, and

(B) a second representation of the set of one or more email documents of the plurality of email documents, wherein the second representation represents a state of the set of one or more email documents after the at least one change is made, whereby said first representation and said second representation together represent at least all of the email documents affected by the at least one change;

displaying, on a user interface, a currently-stale view or currently-stale count for said at least one current query based at least in part on a result set of at least one previously-executed query that was executed on said plurality of email documents before said at least one change was made; and

while displaying said currently-stale view or currently-stale count, utilizing the third representation to update said currently-stale view or currently-stale count to reflect said at least one change;

wherein the step of comparing is performed by one or more processors.

22. The computer-implemented method according to claim 21, wherein said currently-stale view or currently-stale count comprises at least one of (a) information in the result set and (b) a count of information in the result set.

23. The computer-implemented method according to claim 21, wherein said third representation represents a mapping of said at least one change to a change in said currently-stale view or currently-stale count.

47. The computer-implemented method of claim 21, wherein said comparison includes:

retrieving first data from a first index that represents an old state of the email data store; and

retrieving second data from a second index that represents a new state of the email data store.

49. The computer-implemented method according to claim 21, further comprising storing said third representation in persistent memory.

24. A computer readable storage medium storing one or more computer executable instructions, which, when executed by one or more processors, causes performance of:

identifying at least one change to be made to at least one document of a plurality of documents;

generating a first representation of a set of one or more documents of the plurality of documents, wherein the first representation represents a state of the set of one or more documents before the at least one change is made to the at least one document in said plurality of documents;

after said at least one change is made to the at least one document, causing performance of;

causing a currently-stale view or currently-stale count for at least one current query to be displayed on a user interface based at least in part on a result set of at least one previously-executed query that was executed on said plurality of documents before said at least one change was made;

generating a second representation of the set of one or more documents of the plurality of documents, wherein the second representation represents a state of the set of one or more documents after the at least one change is made, whereby said first representation and said second representation together represent at least all of the documents affected by the at least one change to the data store;

comparing the first and second representations to form a third representation that includes representations of differences between said first and second representations; and

updating said currently-stale view or currently-stale count, while said currently-stale view or currently-stale count is displayed, on said user interface to reflect said at least one change based at least in part on the third representation.

25. The computer readable storage medium according to claim 24, wherein the one or more one or more computer executable instructions further causes performance of:

analyzing said third representation to update an output of a function applied to said result set.

26. The computer readable storage medium according to claim 24, wherein said currently-stale view or currently-stale count comprises:

at least one of (a) information in the result set and (b) a count of information in the result.

27. The computer readable storage medium according to claim 24, wherein said at least one previously-executed query that was executed before said at least one change comprises:

at least part of at least two queries combined to form the result set.

28. The computer readable storage medium according to claim 24, wherein the one or more one or more computer executable instructions further causes performance of:

caching at least a part of the third representation as a result to be shared among at least two queries during analysis of said third representation by analyzing to update said view or count to reflect said at least one change.

29. The computer readable storage medium according to claim 24, wherein said comparing comprises identifying whether said differences represent an addition of a document, a deletion of a document or a change to at least one metatag of a document.

30. The computer readable storage medium according to claim 24, wherein said first and second representations comprise a mix of forward and inverted representations.

31. The computer readable storage medium according to claim 24, wherein the one or more one or more computer executable instructions further causes performance of:

batching a plurality of changes of said at least one change prior to generating the second representation.

32. The computer readable storage medium according to claim 31, wherein said batching comprises batching dynamically based upon a change rate for changes to be made.

33. The computer readable storage medium according to claim 24, wherein said comparing further comprises mapping said at least one change to a change in said currently-stale view or currently-stale count by determining whether said at least one change represents an addition to the result set, a modification to the result set, or a deletion to the result set.

48. The computer readable storage medium of claim 24, wherein the one or more one or more computer executable instructions further causes performance of:

generating a first index that represents an old state of the set of one or more documents; and

generating a second index that represents a new state of the set of one or more documents.