Method and system of generating and using a geographical hierarchy model

• US 10,409,857 B2
• Filed: 07/29/2014
• Issued: 09/10/2019
• Est. Priority Date: 07/29/2014
• Status: Active Grant

• Current Assignee: Yahoo Assets LLC
• Original Assignee: Oath Inc. (Verizon Communications Inc.)
• Inventors: Shamma, David Ayman, Kafsi, Mohamed, Cramer, Henriette
• Primary Examiner(s): Savla, Arpan P.
• Assistant Examiner(s): Vo, Cecile H
• Application Number:
  US14/445,724
• Publication Number:
  US 20160034564A1
• Time in Patent Office: 1,869 Days
• Field of Search: 706 58, 707752, 707E17018, 707E1711, 707E17014, 707999107, 707E17059, 707736, 707766, 707778, 707E17067, 707E17111, 707E17095, 707724, 707803, 707919, 700224, 700226
• CPC Class Codes: G06F 16/5866 using information manually generated, e.g. tags, keywords, comments, manually generated location and time information
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Geographical regions are each characterized using a distribution of terms, tags, etc. A model may be generated that identifies characteristics of each geographic region. The geographic regions may be organized using a geographical hierarchical model.

Claims

1. A method comprising:

obtaining, by a processing unit of a search system, data comprising a plurality of tags and geographic location information associated with each tag of the plurality of tags, the geographic location information associated with a tag, of the plurality of tags, identifying a geographic location that is a part of a geographic region, the geographic region is one of a plurality of geographic regions, each geographic region is associated with a level of a geographic region hierarchy, the geographic region hierarchy comprising a plurality of levels, each child level of the geographic region hierarchy has a corresponding parent level of the geographic region hierarchy, the geographic region associated with the child level is a part of the geographic region associated with the corresponding parent level;

determining, by the processing unit and using the obtained data, a plurality of probability distributions corresponding to the plurality of geographic regions, the determining comprising determining a probability distribution for each geographic region of the plurality of geographic regions, each geographic region'"'"'s probability distribution comprising a numeric locality measure, for each tag of the plurality of tags, each numeric locality measure is associated with a tag, of the plurality of tags, and a geographic region, of the plurality of geographic regions, and specifies a probability that the associated tag is descriptive of the associated geographic region;

assigning, by the processing unit and to a geographic region of the plurality of geographic regions, a number of tags, of the plurality of tags, the assigning using the probability distribution, of the plurality of probability distributions, corresponding to the geographic region, each tag of the number of tags assigned to the geographic region having a numeric locality measure indicating that the tag is descriptive of the geographic region;

receiving, by the processing unit, a request to identify at least one geographic region of the plurality of geographic regions; and

using, by the processing unit, at least some of the plurality of probability distributions, each of which specifying, for each tag of the plurality, the numeric locality measure determined for the tag and indicating the probability that the tag is descriptive of a geographic region of the plurality of geographic regions, to identify the at least one geographic region of the plurality for a response to the request.

2. The method of claim 1, further comprising:

determining, by the processing unit and in the geographic region hierarchy formed using the plurality of geographic regions, at least one tag of the plurality of tags that is shared by a number of nodes at the child level of the geographic hierarchy, the number of nodes at the child level having a common node at the parent level of the geographic hierarchy; and

assigning, by the processing unit, the at least one tag of the plurality of tags to the common node at the parent level of the geographic hierarchy.

3. The method of claim 1, further comprising:

determining, by the processing unit and in the geographic region hierarchy formed using the plurality of geographic regions, at least one tag of the plurality of tags that is unique to the child node of a number of child nodes at a respective level of the geographic hierarchy; and

identifying, by the processing unit, the at least one tag of the plurality of tags as belonging to the child node.

4. The method of claim 1:

the receiving further comprising receiving a request to identify two similar geographic regions; and

the using further comprising comparing at least one pair of probability distributions of the at least some probability distributions to identify a similarity between a pair of geographic regions as the two similar geographic regions.

5. The method of claim 4, the comparing further comprising:

determining, for each pair of the at least one probability distribution pair, a cosine similarity between the pair.

6. The method of claim 1:

the receiving further comprising receiving a request to identify a geographic region of the plurality with unique local character; and

the using further comprising examining the at least some of the plurality of probability distributions to identify the geographic region of the plurality with unique local character, relative to other geographic regions of the plurality, the geographic region with unique local character having a higher proportion of local tags identified using its probability distribution.

7. The method of claim 6, the examining further comprising:

determining, for each geographic region corresponding to a probability distribution of the at least some of the plurality of probability distributions, a proportion of local tags using a mixture coefficient.

8. The method of claim 1:

the receiving further comprising receiving a request to identify a geographic region associated with a content item, the content item having one or more associated tags; and

the using further comprising comparing each probability distribution of the at least some of the plurality of probability distributions with the content item'"'"'s associated tags to identify the geographic region associated with the content item.

9. The method of claim 8, further comprising:

identifying the geographic region associated with the content item using the identified geographic region'"'"'s probability distribution identifying one or more tags local to the geographic region and the one or more tags associated with the content item.

10. The method of claim 9, further comprising:

identifying an object depicted in the content item using the identified geographic region.

11. The method of claim 1:

the receiving further comprising receiving a request to identify a locality in connection with a search comprising at least one search term; and

the using further comprising comparing each probability distribution of the at least some of the plurality of probability distributions with the at least one search term to identify a geographic region as the locality of the search.

12. The method of claim 1, wherein the probability that the tag is descriptive of the geographic region represents an estimated likelihood of the tag being used in a description of the region.

13. The method of claim 1:

the receiving further comprising receiving a request to identify a geographic region of the plurality having a generic local character relative to other geographic regions of the plurality; and

the using further comprising examining the at least some of the plurality of probability distributions to identify the geographic region of the plurality with a greater generic local character, relative to other geographic regions of the plurality, the geographic region with the greater generic character having a lesser proportion of local tags identified using its probability distribution.

14. The method of claim 1, the geographic region hierarchy accounts for a mutual influence occurring among two or more geographic regions sharing common boundaries.

15. The method of claim 1:

the receiving further comprising receiving the request to identify a geographic region of the plurality for use in determining a level of confidence in an image recognition result for an image; and

the using further comprising examining the at least some of the plurality of probability distributions to identify the geographic region of the plurality as a likely location of an object depicted in the image.

16. A search system comprising:

at least one computing device, each computing device comprising a processor and a storage medium for tangibly storing thereon program logic for execution by the processor, the stored program logic comprising;

obtaining logic executed by the processor for obtaining data comprising a plurality of tags and geographic location information associated with each tag of the plurality of tags, the geographic location information associated with a tag, of the plurality of tags, identifying a geographic location that is a part of a geographic region, the geographic region is one of a plurality of geographic regions, each geographic region is associated with a level of a geographic region hierarchy, the geographic region hierarchy comprising a plurality of levels, each child level of the geographic region hierarchy has a corresponding parent level of the geographic region hierarchy, the geographic region associated with the child level is a part of the geographic region associated with the corresponding parent level;

determining logic executed by the processor for determining, using the obtained data, a plurality of probability distributions, the determining comprising determining a probability distribution for each geographic region of the plurality of geographic regions, each geographic region'"'"'s probability distribution comprising a numeric locality measure, for each tag of the plurality of tags, each numeric locality measure is associated with a tag, of the plurality of tags, and a geographic region, of the plurality of geographic regions, and specifies a probability that the associated tag is descriptive of the associated geographic region;

assigning logic executed by the processor for assigning, to a geographic region of the plurality of geographic regions, a number of tags, of the plurality of tags, the assigning using the probability distribution, of the plurality of probability distributions, corresponding to the geographic region, each tag of the number of tags assigned to the geographic region having a numeric locality measure indicating that the tag is descriptive of the geographic region;

receiving logic executed by the processor for receiving a request to identify at least one geographic region of the plurality of geographic regions; and

using logic executed by the processor for using at least some of the plurality of probability distributions, each of which specifying, for each tag of the plurality, the numeric locality measure determined for the tag and indicating the probability that the tag is descriptive of a geographic region of the plurality of geographic regions, to identify the at least one geographic region of the plurality for a response to the request.

17. The system of claim 16, the stored program logic further comprising:

determining logic executed by the processor for determining, in the geographic region hierarchy formed using the plurality of geographic regions, at least one tag of the plurality of tags that is shared by a number of nodes at the child level of the geographic hierarchy, the number of nodes at the child level having a common node at the parent level of the geographic hierarchy; and

assigning logic executed by the processor for assigning the at least one tag of the plurality of tags to the common node at the parent level of the geographic hierarchy.

18. The system of claim 16, the stored program logic further comprising:

determining logic executed by the processor for determining, in the geographic region hierarchy formed using the plurality of geographic regions, at least one tag of the plurality of tags that is unique to the child node of a number of child nodes at a respective level of the geographic hierarchy; and

identifying logic executed by the processor for identifying the at least one tag of the plurality of tags as belonging to the child node.

19. The system of claim 16:

the receiving logic further comprising receiving logic executed by the processor for receiving a request to identify two similar geographic regions; and

the using logic executed by the processor for using further comprising instructions to compare at least one pair of probability distributions of the at least some probability distributions to identify a similarity between a pair of geographic regions as the two similar geographic regions.

20. The system of claim 19, the comparing logic further comprising:

determining logic executed by the processor for determining, for each pair of the at least one probability distribution pair, a cosine similarity between the pair.

21. The system of claim 16:

the receiving logic further comprising receiving logic executed by the processor for receiving a request to identify a geographic region of the plurality with unique local character; and

the using logic executed by the processor for using further comprising instructions to examine the at least some of the plurality of probability distributions to identify the geographic region of the plurality with unique local character, relative to other geographic regions of the plurality, the geographic region with unique local character having a higher proportion of local tags identified using its probability distribution.

22. The system of claim 21, the examining logic further comprising:

determining logic executed by the processor for determining, for each geographic region corresponding to a probability distribution of the at least some of the plurality of probability distributions, a proportion of local tags using a mixture coefficient.

23. The system of claim 16:

the receiving logic further comprising receiving logic executed by the processor for receiving a request to identify a geographic region associated with a content item, the content item having one or more associated tags; and

the using logic further comprising comparing logic executed by the processor for comparing each probability distribution of the at least some of the plurality of probability distributions with the content item'"'"'s associated tags to identify the geographic region associated with the content item.

24. The system of claim 23, further comprising:

identifying logic executed by the processor for identifying the geographic region associated with the content item using the identified geographic region'"'"'s probability distribution identifying one or more tags local to the geographic region and the one or more tags associated with the content item.

25. The system of claim 24, further comprising:

identifying logic executed by the processor for identifying an object depicted in the content item using the identified geographic region.

26. The system of claim 16:

the receiving logic further comprising receiving logic executed by the processor for receiving a request to identify a locality in connection with a search comprising at least one search term; and

the using logic further comprising comparing logic executed by the processor for comparing each probability distribution of the at least some of the plurality of probability distributions with the at least one search term to identify a geographic region as the locality of the search.

27. The system of claim 16, wherein the probability that the tag is descriptive of the geographic region represents an estimated likelihood of the tag being used in a description of the region.

28. The system of claim 16:

the receiving logic further comprising receiving logic executed by the processor for receiving a request to identify a geographic region of the plurality having a generic local character relative to other geographic regions of the plurality; and

the using logic further comprising examining logic executed by the processor for examining the at least some of the plurality of probability distributions to identify the geographic region of the plurality with a greater generic local character, relative to other geographic regions of the plurality, the geographic region with the greater generic character having a lesser proportion of local tags identified using its probability distribution.

29. The system of claim 16, the geographic region hierarchy accounts for a mutual influence occurring among two or more geographic regions sharing common boundaries.

30. The system of claim 16:

the receiving logic further comprising receiving logic executed by the processor for receiving the request to identify a geographic region of the plurality for use in determining a level of confidence in an image recognition result for an image; and

the using logic further comprising examining logic executed by the processor for examining the at least some of the plurality of probability distributions to identify the geographic region of the plurality as a likely location of an object depicted in the image.

31. A computer readable non-transitory storage medium for tangibly storing thereon computer readable instructions that when executed cause at least one processor of a search system to:

obtain data comprising a plurality of tags and geographic location information associated with each tag of the plurality of tags, the geographic location information associated with a tag, of the plurality of tags, identifying a geographic location that is a part of a geographic region, the geographic region is one of a plurality of geographic regions, each geographic region is associated with a level of a geographic region hierarchy, the geographic region hierarchy comprising a plurality of levels, each child level of the geographic region hierarchy has a corresponding parent level of the geographic region hierarchy, the geographic region associated with the child level is a part of the geographic region associated with the corresponding parent level;

determine, using the obtained data, a plurality of probability distributions corresponding to the plurality of geographic regions, the determining comprising determining a probability distribution for each geographic region of the plurality of geographic regions, geographic region'"'"'s probability distribution comprising a numeric locality measure, for each tag of the plurality of tags, each numeric locality measure is associated with a tag, of the plurality of tags, and a geographic region, of the plurality of geographic regions, and specifies a probability that the associated tag is descriptive of the associated geographic region;

assigning, by the processing unit and to a geographic region of the plurality of geographic regions, a number of tags, of the plurality of tags, the assigning using the probability distribution, of the plurality of probability distributions, corresponding to the geographic region, each tag of the number of tags assigned to the geographic region having a numeric locality measure indicating that the tag is descriptive of the geographic region;

receive a request to identify at least one geographic region of the plurality of geographic regions; and

use at least some of the plurality of probability distributions, each of which specifying, for each tag of the plurality, the numeric locating measure determined for the tag and indicating the probability that the tag is descriptive of a geographic region of the plurality of geographic regions, to identify the at least one geographic region of the plurality for a response to the request.

32. The computer readable non-transitory storage medium of claim 31, the instructions further comprising instructions to:

determine, in the geographic region hierarchy formed using the plurality of geographic regions, at least one tag of the plurality of tags that is shared by a number of nodes at the child level of the geographic hierarchy, the number of nodes at the child level having a common node at the parent level of the geographic hierarchy; and

assign the at least one tag of the plurality of tags to the common node at the parent level of the geographic hierarchy.

33. The computer readable non-transitory storage medium of claim 31, the instructions further comprising instructions to:

determine, in the geographic region hierarchy formed using the plurality of geographic regions, at least one tag of the plurality of tags that is unique to the child node of a number of child nodes at a respective level of the geographic hierarchy; and

identify the at least one tag of the plurality of tags as belonging to the child node.

34. The computer readable non-transitory storage medium of claim 31:

the instructions to receive further comprising instructions to receive a request to identify two similar geographic regions; and

the instructions to use further comprising instructions to compare at least one pair of probability distributions of the at least some probability distributions to identify a similarity between a pair of geographic regions as the two similar geographic regions.

35. The computer readable non-transitory storage medium of claim 34, the instructions to compare further comprising instructions to:

determine, for each pair of the at least one probability distribution pair, a cosine similarity between the pair.

36. The computer readable non-transitory storage medium of claim 31:

the instructions to receive further comprising instructions to receive a request to identify a geographic region of the plurality with unique local character; and

the instructions to use further comprising instructions to examine the at least some of the plurality of probability distributions to identify the geographic region of the plurality with unique local character, relative to other geographic regions of the plurality, the geographic region with unique local character having a higher proportion of local tags identified using its probability distribution.

37. The computer readable non-transitory storage medium of claim 36, the instructions to examine further comprising instructions to:

determine, for each geographic region corresponding to a probability distribution of the at least some of the plurality of probability distributions, a proportion of local tags using a mixture coefficient.

38. The computer readable non-transitory storage medium of claim 31:

the instructions to receive further comprising instructions to receive a request to identify a geographic region associated with a content item, the content item having one or more associated tags; and

the instructions to use further comprising instructions to compare each probability distribution of the at least some of the plurality of probability distributions with the content item'"'"'s associated tags to identify the geographic region associated with the content item.

39. The computer readable non-transitory storage medium of claim 38, further comprising instructions to:

identify the geographic region associated with the content item using the identified geographic region'"'"'s probability distribution identifying one or more tags local to the geographic region and the one or more tags associated with the content item.

40. The computer readable non-transitory storage medium of claim 39, further comprising instructions to:

identify an object depicted in the content item using the identified geographic region.

41. The computer readable non-transitory storage medium of claim 31:

the instructions to receive further comprising instructions to receive a request to identify a locality in connection with a search comprising at least one search term; and

the instructions to use further comprising instructions to compare each probability distribution of the at least some of the plurality of probability distributions with the at least one search term to identify a geographic region as the locality of the search.

42. The computer readable non-transitory storage medium of claim 31, wherein the probability that the tag is descriptive of the geographic region represents an estimated likelihood of the tag being used in a description of the region.

43. The computer readable non-transitory storage medium of claim 31, wherein the probability that the tag is descriptive of the geographic region represents an estimated likelihood of the tag being used in a description of the region.

44. The computer readable non-transitory storage medium of claim 31:

the instructions to receive further comprising instructions to receive a request to identify a geographic region of the plurality having a generic local character relative to other geographic regions of the plurality; and

the instructions to use further comprising instructions to examine the at least some of the plurality of probability distributions to identify the geographic region of the plurality with a greater generic local character, relative to other geographic regions of the plurality, the geographic region with the greater generic character having a lesser proportion of local tags identified using its probability distribution.

45. The computer readable non-transitory storage medium of claim 31, the geographic region hierarchy accounts for a mutual influence occurring among two or more geographic regions sharing common boundaries.

46. The computer readable non-transitory storage medium of claim 31:

the instructions to receive further comprising instructions to receive the request to identify a geographic region of the plurality for use in determining a level of confidence in an image recognition result for an image; and

the instructions to use further comprising instructions to examine the at least some of the plurality of probability distributions to identify the geographic region of the plurality as a likely location of an object depicted in the image.