Incorporating Geographical Locations in a Search Process

• US 20110252064A1
• Filed: 04/13/2010
• Published: 10/13/2011
• Est. Priority Date: 04/13/2010
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Murugappan, Anand
• Granted Patent: US 8,903,837 B2
• Time in Patent Office: Days
• US Class Current: 707/780
• 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;

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.

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

computing a probability that the search query is connected with the first geographical location; and

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 for the first geographical location is computed based on a predetermined threshold, the probability that the search query is connected with 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 is a first minimum bounding rectangle;

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

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

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

if the first minimum bounding rectangle and the second minimum bounding rectangle overlap, then setting the distance to 0; and

if the first minimum bounding rectangle and the second minimum bounding rectangle do not overlap, then 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 each one of the second minimum bounding regions encloses one of the second geographical locations;

computing one or more distances between the first minimum bounding region and the second minimum bounding regions, wherein each one of the distances is between first minimum bounding region and one of the second minimum bounding regions;

selecting the shortest one of the distances; and

if the shortest one of the distances 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.

6. A method, comprising:

by one or more computing devices,

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;

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 second geographical locations and the location hierarchy, wherein the second location feature comprises one or more of the second geographical locations;

comparing the first location feature and the second location feature; and

if there is no match between any geographical location of the first location feature and any geographical location of the second location feature, then 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 each level;

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

each one of the geographical locations, except one of the geographical locations at the first level, has 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 each one 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;

each one of the second geographical locations in the second location feature does 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 each one of the third geographical locations is 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 each one of the third geographical locations in the location hierarchy;

the second location feature further comprises;

all of the second geographical locations extracted from the document;

the level of each one of the second geographical locations; and

zero or more fourth geographical locations, wherein each one of the fourth geographical locations is on the same branch as one of the 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 only when the two geographical locations are at 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 if there is any level below the level of the first geographical location on the branch of the first geographical location in the location hierarchy, each of 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 if 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, each of 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 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;

extract 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;

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

compute a threshold for the first geographical location;

extract one or more second geographical locations from the document;

for one of the second geographical locations,

determine a second minimum bounding region enclosing the one second geographical location;

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

if the distance is greater than the threshold, then 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 when executing the instructions to:

compute a probability that the search query is connected with the first geographical location; and

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 for the first geographical location is computed based on a predetermined threshold, the probability that the search query is connected with 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 is a first minimum bounding rectangle;

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

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

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

if the first minimum bounding rectangle and the second minimum bounding rectangle overlap, then set the distance to 0; and

if the first minimum bounding rectangle and the second minimum bounding rectangle do not overlap, then 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 when executing the instructions to:

determine one or more second minimum bounding regions enclosing the second geographical locations, wherein each one of the second minimum bounding regions encloses one of the second geographical locations;

compute one or more distances between the first minimum bounding region and the second minimum bounding regions, wherein each one of the distances is between first minimum bounding region and one of the second minimum bounding regions;

select the shortest one of the distances; and

if the shortest one of the distances is greater than the threshold, then 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;

extract 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;

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 second geographical locations and the location hierarchy, wherein the second location feature comprises one or more of the second geographical locations;

compare the first location feature and the second location feature; and

if there is no match between any geographical location of the first location feature and any geographical location of the second location feature, then 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 each level;

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

each one of the geographical locations, except one of the geographical locations at the first level, has 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 each one 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;

each one of the second geographical locations in the second location feature does 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 compare the first geographical location and the third geographical locations in the first location feature and the second geographical locations in the second location feature.

19. The system recited in claim 17, 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 each one of the third geographical locations is 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 each one of the third geographical locations in the location hierarchy;

the second location feature further comprises;

all of the second geographical locations extracted from the document;

the level of each one of the second geographical locations; and

zero or more fourth geographical locations, wherein each one of the fourth geographical locations is on the same branch as one of the second geographical locations and at a level above the level of the one of the second geographical locations 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 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 if there is any level below the level of the first geographical location on the branch of the first geographical location in the location hierarchy, each of 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 if 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, each of 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.

21. One or more computer-readable tangible storage media embodying software operable when executed by one or more computer systems to:

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

extract 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;

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

compute a threshold for the first geographical location;

extract one or more second geographical locations from the document;

for one of the second geographical locations,

determine a second minimum bounding region enclosing the one second geographical location;

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

if the distance is greater than the threshold, then 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 probability that the search query is connected with the first geographical location; and

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.

23. The media recited in claim 22, wherein the threshold for the first geographical location is computed based on a predetermined threshold, the probability that the search query is connected with 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 is a first minimum bounding rectangle;

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

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

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

if the first minimum bounding rectangle and the second minimum bounding rectangle overlap, then set the distance to 0; and

if the first minimum bounding rectangle and the second minimum bounding rectangle do not overlap, then 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 each one of the second minimum bounding regions encloses one of the second geographical locations;

compute one or more distances between the first minimum bounding region and the second minimum bounding regions, wherein each one of the distances is between first minimum bounding region and one of the second minimum bounding regions;

select the shortest one of the distances; and

if the shortest one of the distances is greater than the threshold, then 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 tangible storage media embodying software operable when executed by one or more computer systems to:

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

extract 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;

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 second geographical locations and the location hierarchy, wherein the second location feature comprises one or more of the second geographical locations;

compare the first location feature and the second location feature; and

if there is no match between any geographical location of the first location feature and any geographical location of the second location feature, then 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 each level;

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

each one of the geographical locations, except one of the geographical locations at the first level, has 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 each one 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;

each one of the second geographical locations in the second location feature does 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 compare the first geographical location and the third geographical locations in the first location feature and the 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 each one of the third geographical locations is 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 each one of the third geographical locations in the location hierarchy;

the second location feature further comprises;

all of the second geographical locations extracted from the document;

the level of each one of the second geographical locations; and

zero or more fourth geographical locations, wherein each one of the fourth geographical locations is on the same branch as one of the second geographical locations and at a level above the level of the one of the second geographical locations 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 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 if there is any level below the level of the first geographical location on the branch of the first geographical location in the location hierarchy, each of 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 if 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, each of 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.