Systems and methods for updating query results based on query deltas

• US 20060036580A1
• Filed: 08/13/2004
• Published: 02/16/2006
• Est. Priority Date: 08/13/2004
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Hunt, Patrick David, Stata, Raymond P.
• Granted Patent: US 7,720,845 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method for computing differences between result sets for at least one query on a data store as the data store changes, wherein said data store stores a plurality of documents in at least one storage unit, including:

identifying at least one change to be made to the data store;

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

generating a second representation of at least one document of the plurality of documents, wherein the second representation represents a state of the at least one document 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; and

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

2. A method according to claim 1, further including:

utilizing said third representation to update an output of a function applied to a result set associated with at least one query to the data store.

3. A method according to claim 2, further including:

utilizing said third representation to update the presentation of information associated with the output of the function of a result set associated with at least one query to the data store.

4. A method according to claim 1, further including:

utilizing said third representation to update at least one of (a) a result set associated with at least one query to the data store and (b) a result set count associated with at least one query to the data store.

5. A method according to claim 4, wherein said utilizing includes utilizing said third representation to update a result set count associated with a query of the at least one query by determining individually whether the differences represented by said third representation represent additions or deletions of documents from the result set associated with the query.

6. A method according to claim 5, wherein said utilizing includes incrementing the result set count associated with the query of the at least one query if a difference represented by said third representation represents an addition and decrementing the result set count associated with the query of the at least one query if a difference represented by said third representation represents a deletion.

7. A method according to claim 4, wherein said utilizing includes utilizing said third representation to update a result set count associated with a query of the at least one query by determining individually whether the differences represented by said third representation represent additions, modifications or deletions of documents from the result set associated with the query.

8. A method according to claim 7, wherein said utilizing includes incrementing the result set count associated with the query of the at least one query if a difference represented by said third representation represents an addition, decrementing the result set count associated with the query of the at least one query if a difference represented by said third representation represents a deletion, and not modifying the result set count associated with the query if a difference represented by said third representation represents a modification.

9. A method according to claim 1, further including:

combining at least part of at least two standing queries to share a common result as part of utilizing said third representation to update outputs of a function applied to the result sets associated with the at least two standing queries.

10. A method according to claim 1, further including:

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 outputs of a function applied to the result sets associated with the at least two standing queries.

11. A method according to claim 1, whereby said first representation and said second representation together represent all of the documents affected by the at least one change and whereby said first representation and said second representation includes at least one document not affected by the at least one change to be made to the data store.

12. A method according to claim 1, wherein said comparing includes 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.

13. A method according to claim 12, wherein said comparing includes 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.

14. A method according to claim 1, wherein said first and second representations include a mix of forward and inverted representations.

15. A method according to claim 1, wherein said first and second representations include inverted representations.

16. A method according to claim 1, further including batching a plurality of changes of said at least one change prior to said generating of a second representation.

17. A method according to claim 16, wherein said batching further includes batching dynamically based upon a change rate for changes to be made to the data store.

18. A method according to claim 1, wherein said comparing includes mapping said at least one change to the data store to at least one change to a result set of a query of the at least one query by determining whether the changes to the data store represent an addition to the result set, a modification to the result set or a deletion to the result set.

19. A computing device comprising means for performing the method of claim 1.

20. A computer readable medium comprising computer executable modules including computer executable instructions for carrying out the method of claim 1.

21. A modulated data signal carrying computer executable instructions for performing the method of claim 1.

22. A computing device, in communication with a data store, that computes differences between result sets for at least one query on the data store as the data store changes, wherein said data store stores a plurality of documents in at least one storage unit, including:

a data store component that identifies at least one change to be made to the data store;

an old state data structure generation component that generates a first data structure representing at least one document of the plurality of documents, wherein the first data structure represents a state of the at least one document before the at least one change is made;

a new state data structure generation component that generates a second data structure of at least one document of the plurality of documents, wherein the second data structure represents a state of the at least one document after the at least one change is 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; and

a comparator that analyzes the first and second data structures to form a third data structure that includes representations of the differences between said first and second data structures.

23. A computing device according to claim 22, further including:

a query update component that receives said third data structure as input and, based on said third data structure, updates an output of a function applied to a result set associated with at least one query to the data store.

24. A computing device according to claim 23, further including:

a presentation refresh component that updates the presentation of information associated with the output of the function of a result set associated with at least one query to the data store based on said third data structure.

25. A computing device according to claim 22, further including:

a query update component that receives said third data structure as input and, based on said third data structure, updates at least one of (a) a result set associated with at least one query to the data store and (b) a result set count associated with at least one query to the data store.

26. A computing device according to claim 25, wherein said query update component utilizes said third data structure to update a result set count associated with a query of the at least one query by determining individually whether the differences represented by said third data structure represent additions or deletions of documents from the result set associated with the query.

27. A computing device according to claim 22, further including:

a query analysis component that combines at least part of at least two standing queries to share a common result as part of the analysis performed by a query update component that utilizes said third data structure to update outputs of a function applied to the result sets associated with the at least two standing queries.

28. A computing device according to claim 22, further including:

a query update component that caches at least a part of the third data structure as a result to be shared among at least two queries when the query update component utilizes said third data structure to update outputs of a function applied to the result sets associated with the at least two standing queries.

29. A computing device according to claim 22, whereby said first data structure and said second data structure together represent all of the documents affected by the at least one change and whereby said first data structure and said second data structure further include at least one document not affected by the at least one change to be made to the data store.

30. A computing device according to claim 22, wherein said comparator identifies whether the differences between said first and second data structures represent an addition of a document, a deletion of a document or a change to a metatag of a document.

31. A computing device according to claim 22, wherein said first and second data structures include a mix of forward and inverted representations.

32. A computing device according to claim 22, further including:

a batching component that batches a plurality of changes of said at least one change prior to said second data structure being generated by the new state data structure generation component.

33. A computing device according to claim 32, wherein said batching component batches dynamically based upon a change rate for changes to be made to the data store.

34. A computing device according to claim 22, wherein said comparator includes a mapping component that maps said at least one change to the data store to at least one change to a result set of a query of the at least one query by determining whether the changes to the data store represent an addition to the result set, a modification to the result set or a deletion to the result set.

35. An application programming interface (API) for use by email application software executing on a computing device in communication with an email data store that enables the computation of differences between result sets for at least one query on the email data store as the email data store changes, wherein said email data store stores a plurality of email documents in at least one storage unit, the API performing the method of:

transmitting at least one query to be executed on said email data store to a query handler for said email data store;

receiving in response a difference representation from said query handler that is based on comparison of (A) a first representation of at least one email document of the plurality of email documents, wherein the first representation represents a state of the at least one email document before the at least one change is made and (B) a second representation of at least one email document of the plurality of email documents, wherein the second representation represents a state of the at least one email document 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.

36. An API according to claim 35, further including:

utilizing said difference representation to update an output of a function applied to a result set associated with at least one query to the email data store.

37. An API according to claim 35, further including:

utilizing said difference representation to update at least one of (a) a result set associated with at least one query to the email data store and (b) a result set count associated with at least one query to the email data store.

38. An API according to claim 35, further including:

combining at least part of at least two standing queries to share a common result as part of utilizing said difference representation to update outputs of a function applied to the result sets associated with the at least two standing queries.

39. An API according to claim 35, further including:

caching at least a part of the difference representation as a result to be shared among at least two queries during utilizing said difference representation to update outputs of a function applied to the result sets associated with the at least two standing queries.

40. An API according to claim 35, whereby said first representation and said second representation together represent all of the email documents affected by the at least one change and whereby said first representation and said second representation includes at least one email document not affected by the at least one change to be made to the email data store.

41. An API according to claim 35, wherein said difference representation represents differences between said first representation and said second representation and said comparison of the first and second representations includes identifying whether said differences represent an addition of a email document, a deletion of a email document or a change to at least one metatag of a email document.

42. An API according to claim 35, wherein a plurality of changes of said at least one change are batched prior to said receiving based on a comparison of said first and second representations.

43. An API according to claim 35, wherein said difference representation represents a mapping of said at least one change to the email data store to at least one change to a result set of a query of the at least one query.

44. A user interface for presenting updated information based on computed differences between result sets for at least one query on an email data store as the email data store changes, wherein said email data store stores a plurality of documents in at least one storage unit, the user interface presenting said updated information based on the method of:

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

receiving, by said API in response, a third representation from said query handler that is based on comparison of (A) a first representation of at least one email document of the plurality of email documents, wherein the first representation represents a state of the at least one email document before the at least one change is made and (B) a second representation of at least one email document of the plurality of email documents, wherein the second representation represents a state of the at least one email document 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; and

based on said third representation, updating the user interface by presenting information associated with the output of a function of a result set associated with at least one query to the data store.

45. A user interface according to claim 44, wherein said updating includes utilizing said third representation to update and present at least one of (a) a result set associated with at least one query to the email data store and (b) a result set count associated with at least one query to the email data store.

46. A user interface according to claim 44, wherein said third representation represents a mapping of said at least one change to the email data store to at least one change to a result set of a query of the at least one query.

47. A computer readable medium comprising a plurality of computer executable modules having computer executable instructions, the modules comprising:

means for identifying at least one change to be made to the data store;

means for generating a first representation of at least one document of the plurality of documents, wherein the first representation represents a state of the at least one document before the at least one change is made;

means for generating a second representation of at least one document of the plurality of documents, wherein the second representation represents a state of the at least one document 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; and

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

48. A computer readable medium according to claim 47, further including:

means for analyzing said third representation to update an output of a function applied to a result set associated with at least one query to the data store.

49. A computer readable medium according to claim 47, further including:

means for analyzing said third representation to update at least one of (a) a result set associated with at least one query to the data store and (b) a result set count associated with at least one query to the data store.

50. A computer readable medium according to claim 47, further including:

means for combining at least part of at least two standing queries to share a common result as part of analyzing by a means for analyzing said third representation to update outputs of a function applied to the result sets associated with the at least two standing queries.

51. A computer readable medium according to claim 47, further including:

means for 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 a means for analyzing to update outputs of a function applied to the result sets associated with the at least two standing queries.

52. A computer readable medium according to claim 47, wherein said means for comparing includes means for 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.

53. A computer readable medium according to claim 47, wherein said first and second representations include a mix of forward and inverted representations.

54. A computer readable medium according to claim 47, further including means for batching a plurality of changes of said at least one change prior to generation of the second representation by said means for generating a second representation.

55. A computer readable medium according to claim 54, wherein said means for batching further includes means for batching dynamically based upon a change rate for changes to be made to the data store.

56. A computer readable medium according to claim 47, wherein said means for comparing includes means for mapping said at least one change to the data store to at least one change to a result set of a query of the at least one query by determining whether the changes to the data store represent an addition to the result set, a modification to the result set or a deletion to the result set.