Managing information about entities using clusters of received observations

• US 8,706,732 B1
• Filed: 07/12/2011
• Issued: 04/22/2014
• Est. Priority Date: 07/12/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Strohm, Alan C., Stern, Steven M., Sahuguet, Arnaud, de Alvarenga Oliveira, Ademir, Harb, Boulos, Janos, Joseph
• Primary Examiner(s): DWIVEDI, MAHESH H
• Application Number:
  US13/181,367
• Time in Patent Office: 1,015 Days
• Field of Search: 707/705, 707/737
• US Class Current: 707/737
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for managing entities using observations. In one aspect, a method includes receiving an observation, the observation including an updated piece of information about an entity and a context, wherein the context includes at least one value of an attribute describing the entity to which the updated piece of information relates; matching the received observation with a first cluster of observations representing the entity using the context; and associating the received observation with the first cluster of observations.

Claims

1. A method for managing information about entities, the method comprising:

receiving an observation, by one or more computers, the observation including an updated piece of information about an entity having a geographic location and a context, wherein the context includes at least one value of an attribute describing the entity to which the updated piece of information relates;

storing, by the one or more computers, the received observation as an immutable observation that includes the updated piece of information about the entity having the geographic location and the context, wherein the immutable observation is not modifiable after storage of the immutable observation;

matching, by the one or more computers, the immutable observation with a first cluster of observations representing the entity using the context;

the matching comprising;

generating a query derived from one or more values of attributes included in the context;

identifying, by the one or more computers, one or more candidate clusters of observations responsive to the generated query;

generating, by the one or more computers, a respective score for the one or more candidate clusters, wherein the respective score is based on a comparison of one or more attribute values from the context and a corresponding one or more attribute values of the one or more candidate clusters; and

matching, by the one or more computers, the immutable observation with a select candidate cluster having the highest respective score; and

associating, by the one or more computers, the immutable observation with the first cluster of observations.

2. The method of claim 1, wherein the updated piece of information is a modified value of an attribute of the entity.

3. The method of claim 1, wherein the updated piece of information is a user review or a user rating of the entity.

4. The method of claim 1, wherein the received observation does not include a system-generated identifier for the entity.

5. The method of claim 1, further comprising:

providing data identifying the first cluster to a summarization system; and

obtaining from the summarization system a summarized cluster that includes attribute values that describe a current state of the entity represented by the first cluster.

6. The method of claim 5, further comprising:

updating a cluster index with information from the summarized cluster.

7. The method of claim 6, wherein identifying one or more candidate clusters of observations responsive to the generated query comprises:

identifying one or more candidate clusters of observations responsive to the generated query using the cluster index.

8. The method of claim 7, wherein a respective summarized cluster for each of the one or more candidate clusters includes at least one attribute value that is included in the generated query.

9. The method of claim 7, wherein generating a respective score for one or more of the candidate clusters comprises:

generating a respective score for one or more of the candidate clusters using the cluster index.

10. A method performed by a system of one or more computers, the method comprising:

receiving a plurality of observations, each observation including an updated piece of information about a respective entity and a context, wherein the context includes at least one value of an attribute describing the respective entity to which the updated piece of information relates, the plurality of observations including a first observation and a second observation;

storing the plurality of received observations as a plurality of immutable observations that includes the updated piece of information about the entity having the geographic location and the context, wherein each immutable observation is not modifiable after storage of the immutable observation;

clustering each of the immutable observations based on their contexts into a first cluster of observations, wherein the first cluster is regarded as representing a first entity;

receiving additional observations, each additional observation including an updated piece of information about a respective entity and a context, wherein the context includes at least one value of an attribute describing the respective entity to which the updated piece of information relates;

storing the plurality of received additional observations as a plurality of immutable additional observations that includes the updated piece of information about the entity having the geographic location and the context, wherein each immutable additional observation is not modifiable after storage of the immutable additional observation;

generating a first score for the first cluster, wherein the first score is based on a comparison of the at least one attribute value from the context of the immutable additional observations and a corresponding at least one attribute value of the first cluster;

generating a second score for the second cluster, wherein the second score is based on a comparison of the at least one attribute value from the context of the immutable additional observations and a corresponding at least one attribute value of the second cluster;

matching the immutable additional observations with the first cluster if the first score is higher than the second score; and

matching the immutable additional observations with the second cluster if the second score is higher than the first score.

11. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving an observation, the observation including an updated piece of information about an entity and a context, wherein the context includes at least one value of an attribute describing the entity to which the updated piece of information relates;

storing the received observation as an immutable observation that includes the updated piece of information about the entity having the geographic location and the context, wherein the immutable observation is not modifiable after storage of the immutable observation;

matching the immutable observation with a first cluster of observations representing the entity using the context;

the matching comprising;

generating a query derived from one or more values of attributes included in the context;

identifying one or more candidate clusters of observations responsive to the generated query;

generating a respective score for the one or more candidate clusters, wherein the respective score is based on a comparison of one or more attribute values from the context and a corresponding one or more attribute values of the one or more candidate clusters; and

matching the immutable observation with a select candidate cluster having the highest respective score; and

associating the immutable observation with the first cluster of observations.

12. The computer storage medium of claim 11, wherein the updated piece of information is a modified value of an attribute of the entity.

13. The computer storage medium of claim 11, wherein the updated piece of information is a user review or a user rating of the entity.

14. The computer storage medium of claim 11, wherein the received observation does not include a system-generated identifier for the entity.

15. The computer storage medium of claim 11, the operations further comprising:

providing data identifying the first cluster to a summarization system; and

obtaining from the summarization system a summarized cluster that includes attribute values that describe a current state of the entity represented by the first cluster.

16. The computer storage medium of claim 15, the operations further comprising:

updating a cluster index with information from the summarized cluster.

17. The computer storage medium of claim 16, wherein identifying one or more candidate clusters of observations responsive to the generated query comprises:

identifying one or more candidate clusters of observations responsive to the generated query using the cluster index.

18. The computer storage medium of claim 17, wherein a respective summarized cluster for each of the one or more candidate clusters includes at least one attribute value that is included in the generated query.

19. The computer storage medium of claim 17, wherein generating a respective score for one or more of the candidate clusters comprises:

generating a respective score for one or more of the candidate clusters using the cluster index.

20. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a plurality of observations, each observation including an updated piece of information about a respective entity and a context, wherein the context includes at least one value of an attribute describing the respective entity to which the updated piece of information relates, the plurality of observations including a first observation and a second observation;

storing the plurality of received observations as a plurality of immutable observations that includes the updated piece of information about the entity having the geographic location and the context, wherein each immutable observation is not modifiable after storage of the immutable observation;

clustering each of the immutable observations based on their contexts into a first cluster of observations, wherein the first cluster is regarded as representing a first entity;

receiving additional observations, each additional observation including an updated piece of information about a respective entity and a context, wherein the context includes at least one value of an attribute describing the respective entity to which the updated piece of information relates;

storing the plurality of received additional observations as a plurality of immutable additional observations that includes the updated piece of information about the entity having the geographic location and the context, wherein each immutable additional observation is not modifiable after storage of the immutable additional observation;

generating a first score for the first cluster, wherein the first score is based on a comparison of the at least one attribute value from the context of the immutable additional observations and a corresponding at least one attribute value of the first cluster;

generating a second score for the second cluster, wherein the second score is based on a comparison of the at least one attribute value from the context of the immutable additional observations and a corresponding at least one attribute value of the second cluster;

matching the immutable observations with the first cluster if the first score is higher than the second score; and

matching the received additional observations with the second cluster if the second score is higher than the first score.

21. A system comprising one or more computers and one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:

receiving an observation, the observation including an updated piece of information about an entity and a context, wherein the context includes at least one value of an attribute describing the entity to which the updated piece of information relates;

storing the received observation as an immutable observation that includes the updated piece of information about the entity having the geographic location and the context, wherein the immutable observation is not modifiable after storage of the immutable observation;

matching the immutable observation with a first cluster of observations representing the entity using the context, the matching comprising;

generating a query derived from one or more values of attributes included in the context;

identifying one or more candidate clusters of observations responsive to the generated query;

generating a respective score for the one or more candidate clusters, wherein the respective score is based on a comparison of one or more attribute values from the context and a corresponding one or more attribute values of the one or more candidate clusters; and

matching the immutable observation with a select candidate cluster having the highest respective score; and

associating the immutable observation with the first cluster of observations.

22. The system of claim 21, wherein the updated piece of information is a modified value of an attribute of the entity.

23. The system of claim 21, wherein the updated piece of information is a user review or a user rating of the entity.

24. The system of claim 21, wherein the received observation does not include a system-generated identifier for the entity.

25. The system of claim 21, the operations further comprising:

providing data identifying the first cluster to a summarization system; and

obtaining from the summarization system a summarized cluster that includes attribute values that describe a current state of the entity represented by the first cluster.

26. The system of claim 25, the operations further comprising:

updating a cluster index with information from the summarized cluster.

27. The system of claim 26, wherein identifying one or more candidate clusters of observations responsive to the generated query comprises:

identifying one or more candidate clusters of observations responsive to the generated query using the cluster index.

28. The system of claim 27, wherein a respective summarized cluster for each of the one or more candidate clusters includes at least one attribute value that is included in the generated query.

29. The system of claim 27, wherein generating a respective score for one or more of the candidate clusters comprises:

generating a respective score for one or more of the candidate clusters using the cluster index.

30. A system comprising one or more computers and one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:

receiving a plurality of observations, each observation including an updated piece of information about a respective entity and a context, wherein the context includes at least one value of an attribute describing the respective entity to which the updated piece of information relates, the plurality of observations including a first observation and a second observation;

storing the plurality of received observations as a plurality of immutable observations that includes the updated piece of information about the entity having the geographic location and the context, wherein each immutable observation is not modifiable after storage of the immutable observation;

clustering each of the immutable observations based on their contexts into a first cluster of observations, wherein the first cluster is regarded as representing a first entity;

receiving additional observations, each additional observation including an updated piece of information about a respective entity and a context, wherein the context includes at least one value of an attribute describing the respective entity to which the updated piece of information relates;

storing the plurality of received additional observations as a plurality of immutable additional observations that includes the updated piece of information about the entity having the geographic location and the context, wherein each immutable additional observation is not modifiable after storage of the immutable additional observation;

generating a first score for the first cluster, wherein the first score is based on a comparison of the at least one attribute value from the context of the immutable additional observations and a corresponding at least one attribute value of the first cluster;

generating a second score for the second cluster, wherein the second score is based on a comparison of the at least one attribute value from the context of the immutable additional observations and a corresponding at least one attribute value of the second cluster;

matching the immutable additional observations with the first cluster if the first score is higher than the second score; and

matching the immutable additional observations with the second cluster if the second score is higher than the first score.