Techniques for disambiguating clustered location identifiers

• US 10,846,343 B2
• Filed: 12/13/2018
• Issued: 11/24/2020
• Est. Priority Date: 09/11/2018
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Hirmer, Benedikt M., Bessiere, Kevin, Circlaeys, Eric
• Primary Examiner(s): Lu, Kuen S
• Application Number:
  US16/219,602
• Publication Number:
  US 20200081917A1
• Time in Patent Office: 712 Days
• Field of Search: 707737
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/906 Clustering; Classification
• CPC Class Codes: G06F 16/909 using geographical or spatial information, e.g. location spatiotemporally dependent retrieval from the web G06F16/9537
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

Embodiments of the present disclosure present devices, methods, and computer readable medium for disambiguating clustered location identifiers. A location identifier can be the name of a business or establishment. Digital assets contain a plurality of metadata that can be used to identify the location or establishment at which digital assets were captured. Techniques can use various types contextual information based on a category of the digital asset for disambiguation. Automatically labelling the digital assets assists a user in organizing and sharing the digital assets with friends and family. Users can search for digital assets by the name of the location where the digital assets were captured.

Claims

1. A method performed by one of more processors of a computing device, comprising:

identifying a collection of digital assets having at least a first digital asset and a second digital asset, the collection of digital assets being stored on the computing device;

generating a consolidated address for a location cluster of digital assets comprising the first digital asset and the second digital asset;

determining a first geographic location for the consolidated address based at least in part on location metadata associated with the first digital asset;

determining a first time for the first digital asset based at least in part on time metadata associated with the first digital asset;

calculating a distance range between the first geographic location and a second geographic location, the second geographic location based at least in part on location metadata associated with the second digital asset;

transmitting a request, to a web service, for a plurality of location identifiers within a target range of the first geographic location;

calculating a time range between the first time and a second time, the second time based at least in part on time metadata associated with the second digital asset;

calculating a confidence metric for the first digital asset indicating a degree of confidence that the first digital asset was generated at a location corresponding to at least one of the plurality of location identifiers, the confidence metric calculated in accordance with the distance range satisfying a minimum distance and the time range satisfying a minimum duration;

associating the first digital asset with the at least one of the plurality of location identifiers in accordance with the confidence metric exceeding a confidence threshold; and

updating a knowledge graph stored in the computing device to include the association between the first digital asset and the at least one of the plurality of location identifiers.

2. The method of claim 1, further comprising:

transmitting a request, to a second location service, the second location service tracking a history of geographic locations for the computing device over time, the request to the second location service requesting a length of time the computing device was located within a specified distance from the plurality of location identifiers within the target range of the first geographic location; and

modifying the confidence metric based at least in part on the length of time the computing device spent within the specified distance from the plurality of location identifiers within the target range of the first geographic location.

3. The method of claim 2, further comprising:

accessing the knowledge graph to for a determination that metadata for the first digital asset are consistent at least in part with a meaning associated with at least one of the plurality of location identifiers; and

modifying the confidence metric based at least in part on a correlation between the metadata for the first digital asset and the meaning associated with the one of the plurality of location identifiers.

4. The method of claim 1, further comprising:

collecting the plurality of location identifiers within the target range of the first geographic location;

verifying that the time range exceeds the minimum duration;

applying matching techniques to a plurality of metadata associated with the location identifiers;

filtering the location identifiers based at least in part on a statistical model; and

modifying the confidence metric based at least in part on applying the matching techniques and filtering the location identifiers.

5. The method of claim 1, further comprising:

associating the second digital asset with the at least one of the plurality of location identifiers in accordance with a determination that the confidence metric exceeds the threshold; and

updating the knowledge graph stored in the computing device to include the association between the second digital asset and the at least one of the plurality of location identifiers.

6. The method of claim 1, further comprising:

accessing a telephone call history on the computing device to correlate a call to the location; and

modifying the confidence metric based at least in part on a correlation between the location and the telephone call history.

7. The method of claim 1, further comprising:

accessing a calendar on the computer device to correlate an appointment at least one of the plurality of location identifiers; and

modifying the confidence metric based at least in part on a correlation between the one of the plurality of location identifiers and the appointment.

8. A computing device, comprising:

one or more memories; and

one or more processors in communication with the one or more memories and configured to execute instructions stored in the one or more memories to;

identify a collection of digital assets having at least a digital asset, the collection of digital assets being stored on the computing device;

determine a geographic location for the digital asset based at least in part on location metadata associated with the digital asset;

determine a creation time for the digital asset based at least in part on time metadata associated with creation of the digital asset;

generate a subset of the collection of digital assets, the subset comprising digital assets within a location range of the geographic location and a time range of the creation time;

transmit a request, to a web service, for a plurality of location identifiers corresponding to a target range of the geographic location;

calculate a distance range between a first location of a plurality of locations for the plurality of location identifiers and the geographic location of the digital asset;

calculate a confidence metric for the subset of the collection of digital assets indicating a degree of confidence that the subset of digital assets was generated at a location corresponding to at least one of the plurality of location identifiers, the confidence metric calculated in accordance with the distance range satisfying a minimum distance and the time range satisfying a minimum duration;

associate the subset of the collection of digital assets with the at least one of the plurality of location identifiers in accordance with the confidence metric exceeding a confidence threshold; and

update a knowledge graph stored in the computing device to include the association between each of the digital assets of the subset of digital assets and the at least one of the plurality of location identifiers.

9. The computing device of claim 8, wherein the one or more processors are further configured to execute the instructions to:

transmit a request, to a second location service, the second location service tracking a history of geographic locations for the computing device over time, the request to the second location service requesting a length of time the computing device was located within a specified distance from the plurality of location identifiers within the target range of the geographic location; and

modify the confidence metric based at least in part on the length of time the computing device spent within the specified distance from the plurality of location identifiers within the target range of the geographic location.

10. The computing device of claim 9, wherein the one or more processors are further configured to execute the instructions to:

access the knowledge graph to for a determination that metadata for the digital asset are consistent at least in part with a meaning associated with at least one of the plurality of location identifiers; and

modify the confidence metric based at least in part on a correlation between the metadata for the digital asset and the meaning associated with the one of the plurality of location identifiers.

11. The computing device of claim 8, wherein the one or more processors are further configured to execute the instructions to:

collect the plurality of location identifiers within the target range of the geographic location;

verify that the time range exceeds the minimum duration;

apply matching techniques to a plurality of metadata associated with the location identifiers;

filter the location identifiers based at least in part on a statistical model; and

modify the confidence metric based at least in part on applying the matching techniques and filtering the location identifiers.

12. The computing device of claim 8, wherein the one or more processors are further configured to execute the instructions to:

associate a second digital asset with the at least one of the plurality of location identifiers in accordance with a determination that the confidence metric exceeds the threshold; and

update the knowledge graph stored in the computing device to include the association between the second digital asset and the at least one of the plurality of location identifiers.

13. The computing device of claim 8, wherein the one or more processors are further configured to execute the instructions to:

accessing a telephone call history on the computing device to correlate a call to an establishment associated with one of the plurality of location identifiers; and

modifying the confidence metric based at least in part on a correlation between the establishment and the telephone call history.

14. A non-transitory computer-readable medium storing a plurality of instructions that, when executed by one or more processors of a computing device, cause the one or more processors to perform operations comprising:

identifying a collection of digital assets having at least a digital asset, the digital asset collection being stored in a memory on the computing device;

determining a geographic location for the digital asset based at least in part on location metadata associated with the digital asset;

determining a creation time for the digital asset based at least in part on time metadata associated with the digital asset;

generating a subset of the collection of digital assets, the subset comprising only digital assets within a location range of the geographic location and within a time range of the creation time;

transmitting a request, to a web service, for a plurality of location identifiers corresponding to a target range of the geographic location;

calculate a distance range between a first location of a plurality of locations for the plurality of location identifiers and the geographic location;

calculating a confidence metric for the subset of digital assets indicating a degree of confidence that the subset of digital assets was generated at a location corresponding to the first location, the confidence metric calculated in accordance with the distance range satisfying a minimum distance and the time range satisfying a minimum duration;

associating the subset of the digital assets with a first location identifier in accordance with the confidence metric exceeding a confidence threshold; and

updating a knowledge graph stored in the computing device to include the association between each of the digital assets of the subset of digital assets and the first location identifier.

15. The non-transitory computer-readable medium of claim 14, further comprising:

transmitting a request, to a second location service, the second location service tracking a history of geographic locations for the computing device over time, the request to the second location service requesting a length of time the computing device was located within a specified distance from the plurality of location identifiers within the target range of the geographic location; and

modifying the confidence metric based at least in part on the length of time the computing device spent within the specified distance from the plurality of location identifiers within the target range of the geographic location.

16. The non-transitory computer-readable medium of claim 15, further comprising:

accessing the knowledge graph for a determination that metadata for the digital asset are consistent at least in part with a meaning associated with at least one of the plurality of location identifiers; and

modifying the confidence metric based at least in part on a correlation between the metadata for the first digital asset and the meaning associated with the one of the plurality of location identifiers.

17. The non-transitory computer-readable medium of claim 14, further comprising:

collecting the plurality of location identifiers within the target range of the geographic location;

verifying that the time range exceeds the minimum duration;

applying matching techniques to a plurality of metadata associated with the location identifiers;

filtering the location identifiers based at least in part on a statistical model; and

modifying the confidence metric based at least in part on applying the matching techniques and filtering the location identifiers.

18. The non-transitory computer-readable medium of claim 14, further comprising:

associating a second digital asset with the at least one of the plurality of location identifiers in accordance with a determination that the confidence metric exceeds the threshold; and

updating the knowledge graph stored in the computing device to include the association between the second digital asset and the at least one of the plurality of location identifiers.

19. The non-transitory computer-readable medium of claim 14, further comprising:

accessing a telephone call history on the computing device to correlate a call to an establishment associated with at least one of the plurality of location identifiers; and

modifying the confidence metric based at least in part on a correlation between the establishment and the telephone call history.

20. The non-transitory computer-readable medium of claim 14, further comprising:

accessing a calendar on the computer device to correlate an appointment at least one of the plurality of location identifiers; and

modifying the confidence metric based at least in part on a correlation between the one of the plurality of location identifiers and the appointment.