Incorporating geographical locations in a search process

• US 8,903,837 B2
• Filed: 04/13/2010
• Issued: 12/02/2014
• Est. Priority Date: 04/13/2010
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Murugappan, Anand
• Primary Examiner(s): Bhatia, Ajay
• Assistant Examiner(s): MINA, FATIMA P
• Application Number:
  US12/759,453
• Publication Number:
  US 20110252064A1
• Time in Patent Office: 1,694 Days
• Field of Search: 701/33.9, 701/32.6, 707/758, 707/785, 707/770, 707/791, 707/768, 707/769, 707/756.748, 707/749
• US Class Current: 707/758
• CPC Class Codes: G06F 16/487 using geographical or spatial information, e.g. location

Abstract

In one embodiment, accessing a search query and a document identified in response to the search query; extracting a first geographical location from the search query or from information associated with a user issuing the search query or a device used by the user to issue the search query; determining a first minimum bounding region enclosing the first geographical location; computing a threshold for the first geographical location; extracting one or more second geographical locations from the document; for one of the second geographical locations, determining a second minimum bounding region enclosing the one second geographical location; computing a distance between the first minimum bounding region and the second minimum bounding region; and if the distance is greater than the threshold, then discarding the document by not including the document in a search result identified in response to the search query.

Claims

1. A method, comprising:

by one or more computing devices, accessing a search query and a document identified in response to the search query;

determining a probability that the search query has a local intent relating to a first geographical location;

wherein in response to the probability meeting or exceeding a threshold probability value;

determining a first minimum bounding region enclosing the first geographical location;

computing a threshold location value for the first geographical location based on a combination of the probability and a normalized population of the first geographical area;

extracting one or more second geographical locations from the document;

for the one or more second geographical locations,

determining a second minimum bounding region enclosing the one or more second geographical locations;

computing a distance between the first minimum bounding region and the second minimum bounding region; and

in response to determining that the distance is greater than the threshold location value, discarding the document by not including the document in a search result identified in response to the search query.

2. The method recited in claim 1, further comprising:

computing a normalized population density of the first geographical location based on a population density of the first geographical location and a population density of a country in which the first geographical location is located.

3. The method recited in claim 2, wherein the threshold probability for the first geographical location is computed based on a combination of a predetermined threshold value, the probability that the search query has the local intent relating to the first geographical location, and the normalized population density of the first geographical location.

4. The method recited in claim 1, wherein:

the first minimum bounding region comprises a first minimum bounding rectangle;

the second minimum bounding region comprises a second minimum bounding rectangle; and

computing the distance between the first minimum bounding rectangle and the second minimum bounding rectangle comprises;

determining whether the first minimum bounding rectangle and the second minimum bounding rectangle overlap;

in response to determining that the first minimum bounding rectangle and the second minimum bounding rectangle overlap, setting the distance to 0; and

in response to determining that the first minimum bounding rectangle and the second minimum bounding rectangle do not overlap, setting the distance to the shortest distance between any one of four vertices of the first minimum bounding rectangle and any one of four vertices of the second minimum bounding rectangle.

5. The method recited in claim 1, further comprising:

determining one or more second minimum bounding regions enclosing the second geographical locations, wherein individual ones of the second minimum bounding regions enclose one of the second geographical locations;

computing one or more distances between the first minimum bounding region and the second minimum bounding regions, wherein individual ones of the distances are between first minimum bounding region and one of the second minimum bounding regions;

selecting the shortest one of the distances; and

in response to determining that the shortest one of the distances is greater than the threshold value, discarding the document by not including the document in a search result identified in response to the search query.

31. The method recited in claim 1, further comprising determining a value of the normalized population based on a population density of the first geographical location.

6. A method, comprising:

by one or more computing devices,

accessing a search query and a document identified in response to the search query;

determining a probability that the search query has a local intent relating to a first geographical location;

wherein in response to the probability meeting or exceeding a threshold probability value;

computing a threshold location value for the first geographical location based on a combination of the probability and a population density of the first geographical location;

constructing a first location feature for the search query based on the first geographical location and a location hierarchy, wherein the first location feature comprises the first geographical location;

extracting one or more second geographical locations from the document;

constructing a second location feature for the document based on the one or more second geographical locations and the location hierarchy, wherein the second location feature comprises one or more of the one or more second geographical locations;

comparing the first location feature and the second location feature and with respect to the threshold location value; and

in response to determining that there is no match between any geographical location of the first location feature and the one or more of the one or more geographical locations of the second location feature, discarding the document by not including the document in a search result identified in response to the search query.

7. The method recited in claim 6, wherein:

the location hierarchy comprises one or more geographical locations at one or more levels and along one or more branches;

one or more of the geographical locations are at individual levels;

one or more of the geographical locations form individual branches from the first level to a last level of the branch; and

individual ones of the geographical locations, except one of the geographical locations at the first level, have a parent geographical location within which the geographical location is located.

8. The method recited in claim 7, wherein:

the first location feature further comprises zero or more third geographical locations, wherein individual ones of the third geographical locations enclose the first geographical location and is at a level above the level of the first geographical location and on the same branch as the first geographical location in the location hierarchy;

individual ones of the one or more second geographical locations in the second location feature do not enclose any other one of the second geographical locations extracted from the document in the location hierarchy; and

comparing the first location feature and the second location feature comprises comparing the first geographical location and the third geographical locations in the first location feature and the second geographical locations in the second location feature.

9. The method recited in claim 7, wherein:

the first location feature further comprises;

the level of the first geographical location in the location hierarchy;

zero or more third geographical locations, wherein individual ones of the third geographical locations are on the same branch as the first geographical location and at a level above the level of the first geographical location in the location hierarchy; and

the level of individual ones of the third geographical locations in the location hierarchy;

the second location feature further comprises;

all of the one or more second geographical locations extracted from the document;

the level of individual ones of the one or more second geographical locations; and

zero or more fourth geographical locations, wherein individual ones of the fourth geographical locations are on the same branch as one of the one or more second geographical locations and at a level above the level of the one of the second geographical locations in the location hierarchy; and

comparing the first location feature and the second location feature comprises comparing the first geographical location and the third geographical locations in the first location feature and the second geographical locations and the fourth geographical locations in the second location feature, wherein one of the geographical locations in the first location feature and one of the geographical locations in the second location feature are compared in response to determining that the two geographical locations are at substantially the same level in the location hierarchy.

10. The method recited in claim 9, wherein:

the first location feature further comprises one or more null locations, wherein in response to determining that there is any level below the level of the first geographical location on the branch of the first geographical location in the location hierarchy, the levels below the level of the first geographical location on the branch of the first geographical location has a null location in the first location feature; and

the second location feature further comprises one or more null locations, wherein in response to determining that there is any level below the level of any one of the second geographical locations on the branch of the one or more of the one or more second geographical locations in the location hierarchy, the levels below the level of the one of the geographical locations on the branch of the one of the geographical locations has a null location in the first location feature.

11. A system, comprising:

a memory comprising instructions executable by one or more processors; and

one or more processors coupled to the memory to execute the instructions, the instructions being operable to;

access a search query and a document identified in response to the search query;

determine a probability that the search query has a local intent relating to a first geographical location;

wherein in response to the probability meeting or exceeding a threshold probability value, the instructions being further operable to;

determine a first minimum bounding region enclosing the first geographical location;

compute a threshold location value for the first geographical location based on a combination of the probability and a population density of the first geographical location;

extract one or more second geographical locations from the document;

for one or more of the one or more second geographical locations,

determine a second minimum bounding region enclosing the one or more second geographical locations;

compute a distance between the first minimum bounding region and the second minimum bounding region; and

in response to determining that the distance is greater than the threshold location value, the instructions being further operable to discard the document by not including the document in a search result identified in response to the search query.

12. The system recited in claim 11, wherein the one or more processors are further operable to execute the instructions to:

compute a normalized population density of the first geographical location based on a population density of the first geographical location and a population density of a country in which the first geographical location is located.

13. The system recited in claim 12, wherein the threshold location value for the first geographical location is operable to be computed based on a predetermined threshold, the probability that the search query has the local intent relating to the first geographical location, and the normalized population density of the first geographical location.

14. The system recited in claim 11, wherein:

the first minimum bounding region comprises a first minimum bounding rectangle;

the second minimum bounding region comprises a second minimum bounding rectangle; and

to compute the distance between the first minimum bounding rectangle and the second minimum bounding rectangle comprises;

to determine whether the first minimum bounding rectangle and the second minimum bounding rectangle overlap;

in response to a determination that the first minimum bounding rectangle and the second minimum bounding rectangle overlap, set the distance to 0; and

in response to a determination that the first minimum bounding rectangle and the second minimum bounding rectangle do not overlap, set the distance to the shortest distance between any one of four vertices of the first minimum bounding rectangle and any one of four vertices of the second minimum bounding rectangle.

15. The system recited in claim 11, wherein the one or more processors are further operable to execute the instructions to:

determine one or more second minimum bounding regions enclosing the second geographical locations, wherein individual ones of the second minimum bounding regions enclose one of the second geographical locations;

compute one or more distances between the first minimum bounding region and the second minimum bounding regions, wherein individual ones of the distances are between first minimum bounding region and one of the second minimum bounding regions;

select the shortest one of the distances; and

in response to a determination that the shortest one of the distances is greater than the threshold, discard the document by not including the document in a search result identified in response to the search query.

16. A system, comprising:

a memory comprising instructions executable by one or more processors; and

one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to;

access a search query and a document identified in response to the search query;

determine a probability that the search query has a local intent relating to a first geographical location;

wherein in response to the probability meeting or exceeding a threshold probability value, the instructions being further operable to;

construct a first location feature for the search query based on the first geographical location and a location hierarchy, wherein the first location feature comprises the first geographical location;

extract one or more second geographical locations from the document;

construct a second location feature for the document based on the one or more second geographical locations and the location hierarchy, wherein the second location feature comprises one or more of the one or more second geographical locations;

compute a threshold location value for the first geographical location based on a combination of the probability and a population density of the first geographical location;

compare the first location feature and the second location feature and with respect to the threshold location value; and

in response to determining there is no match between any geographical location of the first location feature and the one or more of the one or more second geographical locations of the second location feature, discard the document by not including the document in a search result identified in response to the search query.

17. The system recited in claim 16, wherein:

the location hierarchy comprises one or more geographical locations at one or more levels and along one or more branches;

one or more of the geographical locations are at the one or more levels;

one or more of the geographical locations form individual branches from a first level to a last level of the branch; and

the geographical locations, except one of the geographical locations at the first level, have a parent geographical location within which the geographical location is located.

18. The system recited in claim 17, wherein:

the first location feature further comprises zero or more third geographical locations, wherein individual ones of the third geographical locations encloses the first geographical location and is at a level above the level of the first geographical location and on the same branch as the first geographical location in the location hierarchy;

individual ones of the one or more second geographical locations in the second location feature do not enclose any other one of the second geographical locations extracted from the document in the location hierarchy; and

to compare the first location feature and the second location feature comprises a comparison of the first geographical location and the one or more third geographical locations in the first location feature and the one or more second geographical locations in the second location feature.

19. The system recited in claim 17, wherein:

the first location feature further comprises;

a level of the first geographical location in the location hierarchy;

zero or more third geographical locations, wherein individual ones of the third geographical locations are on the same branch as the first geographical location and at a level above the level of the first geographical location in the location hierarchy; and

the level of individual ones of the third geographical locations in the location hierarchy;

the second location feature further comprises;

the one or more second geographical locations extracted from the document;

the level of individual ones of the one or more second geographical locations; and

zero or more fourth geographical locations, wherein individual ones of the fourth geographical locations are on the same branch as one or more of the one or more second geographical locations and at a level above the level of the one or more of the one or more of the second geographical locations in the location hierarchy; and

to compare the first location feature and the second location feature comprises a comparison of the first geographical location and the third geographical locations in the first location feature and the second geographical locations and the fourth geographical locations in the second location feature, wherein one of the geographical locations in the first location feature and one of the geographical locations in the second location feature are compared only when the two geographical locations are at the same level in the location hierarchy.

20. The system recited in claim 19, wherein:

the first location feature further comprises one or more null locations, wherein in response to determining that there is any level below the level of the first geographical location on the branch of the first geographical location in the location hierarchy, individual ones of the levels below the level of the first geographical location on the branch of the first geographical location have a null location in the first location feature; and

the second location feature further comprises one or more null locations, wherein in response to determining that there is any level below the level of any one of the one or more second geographical locations on the branch of the one of the second geographical locations in the location hierarchy, individual ones of the levels below the level of the one of the geographical locations on the branch of the one of the geographical locations have a null location in the first location feature.

21. One or more computer-readable non-transitory storage media embodying software executable by one or more computer systems to:

access a search query and a document identified in response to the search query;

determine a probability that the search query has a local intent relating to a first geographical location;

wherein in response to the probability meeting or exceeding a threshold probability value;

determine a first minimum bounding region enclosing the first geographical location;

compute a threshold location value for the first geographical based on a combination of the probability and a population density of the first geographical location;

extract one or more second geographical locations from the document;

for one or more of the one or more second geographical locations,

determine a second minimum bounding region enclosing the one or more of the one or more second geographical locations;

compute a distance between the first minimum bounding region and the second minimum bounding region; and

in response to determining that the distance is greater than the threshold, discard the document by not including the document in a search result identified in response to the search query.

22. The media recited in claim 21, wherein the software is further operable when executed by one or more computer systems to:

compute a normalized population density of the first geographical location based on the population density of the first geographical location and a country population density of a country in which the first geographical location is located.

23. The media recited in claim 22, wherein the threshold location value for the first geographical location is operable to be computed based on a predetermined threshold, the probability that the search query has a local intent relating to the first geographical location, and the normalized population density of the first geographical location.

24. The media recited in claim 21, wherein:

the first minimum bounding region comprises a first minimum bounding rectangle;

the second minimum bounding region comprises a second minimum bounding rectangle; and

to compute the distance between the first minimum bounding rectangle and the second minimum bounding rectangle comprises;

determine whether the first minimum bounding rectangle and the second minimum bounding rectangle overlap;

in response to determining that the first minimum bounding rectangle and the second minimum bounding rectangle overlap, set the distance to 0; and

in response to determining that the first minimum bounding rectangle and the second minimum bounding rectangle do not overlap, set the distance to the shortest distance between any one of four vertices of the first minimum bounding rectangle and any one of four vertices of the second minimum bounding rectangle.

25. The media recited in claim 21, wherein the software is further operable when executed by one or more computer systems to:

determine one or more second minimum bounding regions enclosing the second geographical locations, wherein individual ones of the second minimum bounding regions enclose one or more of the one or more second geographical locations;

compute one or more distances between the first minimum bounding region and the second minimum bounding regions, wherein individual ones of the distances are between first minimum bounding region and one of the second minimum bounding regions;

select the shortest one of the distances; and

in response to determining that the shortest one of the distances is greater than the threshold, discard the document by not including the document in a search result identified in response to the search query.

26. One or more computer-readable non-transitory storage media embodying software executable by one or more computer systems to:

access a search query and a document identified in response to the search query;

determine a probability that the search query has a local intent relating to a first geographical location;

wherein in response to the probability meeting or exceeding a threshold probability value, the instructions are further operable to;

construct a first location feature for the search query based on the first geographical location and a location hierarchy, wherein the first location feature comprises the first geographical location;

extract one or more second geographical locations from the document;

construct a second location feature for the document based on the one or more second geographical locations and the location hierarchy, wherein the second location feature comprises one or more of the one or more second geographical locations;

compute a threshold location value for the first geographical location based on a combination of the probability and a population density of the first geographical location;

compare the first location feature and the second location feature and with respect to the threshold value; and

in response to determining that there is no match between any geographical location of the first location feature and any geographical location of the second location feature, discard the document by not including the document in a search result identified in response to the search query.

27. The media recited in claim 26, wherein:

the location hierarchy comprises one or more geographical locations at one or more levels and along one or more branches;

one or more of the geographical locations are at one or more levels;

one or more of the geographical locations form individual branches from the first level to a last level of the branch; and

individual ones of the geographical locations, except one of the geographical locations at the first level, have a parent geographical location within which the geographical location is located.

28. The media recited in claim 27, wherein:

the first location feature further comprises zero or more third geographical locations, wherein individual ones of the third geographical locations enclose the first geographical location and is at a level above the level of the first geographical location and on the same branch as the first geographical location in the location hierarchy;

individual ones of the one or more second geographical locations in the second location feature does not enclose any other one of the one or more second geographical locations extracted from the document in the location hierarchy; and

to compare the first location feature and the second location feature comprises compare the first geographical location and the third geographical locations in the first location feature and the one or more second geographical locations in the second location feature.

29. The media recited in claim 27, wherein:

the first location feature further comprises;

the level of the first geographical location in the location hierarchy;

zero or more third geographical locations, wherein individual ones of the third geographical locations are on the same branch as the first geographical location and at a level above the level of the first geographical location in the location hierarchy; and

the level of individual ones of the third geographical locations in the location hierarchy;

the second location feature further comprises;

the one or more second geographical locations extracted from the document;

the level of individual ones of the one or more second geographical locations; and

zero or more fourth geographical locations, wherein individual ones of the fourth geographical locations are on the same branch as one or more of the one or more second geographical locations and at a level above the level of the one or more of the one or more second geographical locations in the location hierarchy; and

to compare the first location feature and the second location feature comprises to compare the first geographical location and the third geographical locations in the first location feature and the second geographical locations and the fourth geographical locations in the second location feature, wherein one of the geographical locations in the first location feature and one of the geographical locations in the second location feature are compared only when the two geographical locations are at the same level in the location hierarchy.

30. The media recited in claim 29, wherein:

the first location feature further comprises one or more null locations, wherein in response to determining that there is any level below the level of the first geographical location on the branch of the first geographical location in the location hierarchy, levels below the level of the first geographical location on the branch of the first geographical location have a null location in the first location feature; and

the second location feature further comprises one or more null locations, wherein in response to determining that there is any level below the level of any one of the second geographical locations on the branch of the one of the second geographical locations in the location hierarchy, the levels below the level of the one of the geographical locations on the branch of the one of the geographical locations have a null location in the first location feature.