Collaborative driving directions

• US 8,478,515 B1
• Filed: 05/23/2007
• Issued: 07/02/2013
• Est. Priority Date: 05/23/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Foucher, Trevor, Golding, Andrew R.
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Amin, Bhavesh V
• Application Number:
  US11/752,896
• Time in Patent Office: 2,232 Days
• Field of Search: 701/200, 701/201, 701/202, 701/206, 701/208, 701/209
• US Class Current: 701/400
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3641 Personalized guidance, e.g. limited guidance on previously travelled routes

Abstract

Methods and systems for generating directions are disclosed. In an embodiment of the invention, there is a system that includes a human-provided directions module for receiving and processing human-provided directions, a database for storing human-provided directions processed by the human-provided directions module, and a directions generator for receiving a directions query from a client. In response to the query, the directions generator accesses the database, retrieves at least one human-provided direction, generates a set of directions based thereupon, and provides the set of generated directions to the client.

Claims

1. A computer implemented method of generating a set of directions, the method comprising:

storing a database of driving directions, including human-provided directions that have been extracted by automatically parsing text of webpages from a plurality of websites;

receiving a request for a set of directions to a destination from a client device;

responsive to the request, generating a set of directions to the requested destination based on at least one human-provided direction stored in the database; and

providing the generated set of directions to the client device.

2. The method of claim 1, further comprising:

generating a plurality of sets of directions to the destination, each set of directions based on at least one human-provided direction stored in the database;

scoring each generated set of directions based on a measure of directions quality; and

providing the generated set of directions with the highest score of the plurality of generated sets of directions to the client device.

3. The method of claim 1, wherein the request comprises a user direction preference and the directions are generated responsive to the user direction preference.

4. The method of claim 3, wherein the user direction preference comprises at least one of:

a user direction preference inferred based on past user behavior, a preference for human-provided directions, and a preference for directions that include non-street landmarks.

5. A computer program product comprising a computer readable medium with code for execution on a computer, including the code for performing the method comprising:

receiving a plurality of direction inputs, each input comprising human-provided directions to a destination, the direction inputs including at least webpages from a plurality of websites;

automatically parsing text of each direction input and extracting a set of human-provided directions therefrom;

determining a rating for each set of human-provided directions; and

storing in a database each set of human-provided directions and its rating.

6. The computer program product of claim 5, wherein determining comprises evaluating the share of directions in each set of human-provided directions that is human-provided.

7. The computer program product of claim 5, wherein determining comprises evaluating an importance rating of a direction input from which a set of human-provided directions has been extracted.

8. The computer program product of claim 5, wherein determining comprises evaluating an extent to which directions in a set of human-provided directions represent contiguous human-provided directions from a common source.

9. The computer program product of claim 5, wherein determining comprises evaluating an extent to which non-street landmarks are referenced in a set of human-provided directions.

10. The computer program product of claim 5, wherein determining comprises evaluating at least one of:

an extent to which colloquial language is used in a set of human-provided directions, and user ratings of directions in a set of human-provided directions.

11. The computer program product of claim 5, further comprising providing the plurality of generated sets of directions and the scores of each of the generated sets of directions to the client device.

12. The computer program product of claim 5, comprising retrieving with a crawler direction inputs in the form of webpages from a plurality of websites, wherein the webpages include human-provided directions.

13. The computer program product of claim 5, wherein the plurality of direction inputs are provided in a plurality of languages, and wherein the method comprises storing in the database information about the language of the plurality of languages of each set of human-provided directions.

14. The computer program product of claim 5, wherein a direction input of the direction inputs comprises:

a set of directions submitted by a user and corrections to a set of directions provided by a user.

15. The computer program product of claim 5, wherein extracting comprises extracting context information from which the destination of the set of human-provided directions can be determined.

16. The computer program product of claim 5, wherein storing is performed when a rating for a set of human-provided directions is above a pre-determined threshold.

17. The computer program product of claim 5, wherein the database comprises a map database, and storing comprises one of:

adding each human-provided direction to a data layer comprising human-provided directions, and annotating route segments in the map database with each human-provided direction.

18. The computer program product of claim 5, wherein the method further comprises storing metadata about each set of human-provided directions.

19. A system for generating and serving directions, the system comprising:

a human-provided directions module for receiving and processing human-provided directions, wherein processing human-provided directions includes at least extracting human-provided directions by automatically parsing text of webpages from a plurality of websites;

a database for storing human-provided directions processed by the human-provided directions module;

a directions generator for receiving a directions query from a client, and, responsive to the query;

accessing the database and retrieving at least one human-provided direction therefrom;

generating a set of directions based on the at least one human-provided direction and one or more computer-generated directions; and

providing the generated set of directions to the client.

20. The system of claim 19, wherein the human-provided directions module comprises a directions analyzer for decomposing a set of human-provided directions received by the human-provided directions module into individual direction segments for storage in the directions database.

21. The system of claim 20, wherein decomposing comprises determining a start point and an end point for the set of human-provided directions.

22. The system of claim 20, wherein decomposing comprises determining the geographic orientation of a set of human-provided directions.

23. The system of claim 20, wherein decomposing comprises associating an individual direction of the set of human-provided directions with a path on a map.

24. The system of claim 20, wherein decomposing comprises one or more of:

determining a start point and an end point for the set of human-provided directions and associating an individual direction of the set of human-provided directions with a path on a map.

25. The system of claim 19, wherein the human-provided directions module comprises an extractor for automatically parsing each of a plurality of direction inputs and, for each of the direction inputs, returning a set of human-provided directions.

26. The system of claim 19, wherein the human-provided directions module comprises a directions evaluator for evaluating the quality of human-provided directions, and responsive to a determination that a set of human-provided directions is of below a threshold quality, discarding the set of human-provided directions.

27. The system of claim 19, wherein the directions generator comprises a path generator for generating a plurality of path candidates based on the directions query.

28. The system of claim 19, wherein the directions generator comprises a directions scorer for scoring a plurality of direction candidates generated responsive to the directions query.

29. The system of claim 19, wherein the human-provided directions module is configured to receive human-provided directions in the form of at least one of:

a webpage, an XML feed, a user-provided direction correction, and a user-provided direction.

30. A computer implemented method of generating directions, comprising:

retrieving, from a plurality of websites, webpages comprising directions;

automatically parsing text of each webpage and extracting a set of directions therefrom;

scoring each set of directions based on a measure of quality;

selectively retaining sets of the directions based on their respective scores; and

storing in a database each retained set of directions.

31. The method of claim 30, wherein the directions are human-provided driving directions.

32. The method of claim 31, further comprising:

responsive to at least one set of directions not being associated with a destination, inferring a destination for the set of directions from a context of the webpage from which the set of directions were extracted.

33. The method of claim 30, wherein the measure of direction quality for a direction is based upon a source website of the webpage from which the direction was extracted.

34. The method of claim 30, wherein the measure of direction quality for a direction is based upon a measure of an importance of the webpage from which the direction was extracted.

35. The method of claim 30, wherein the measure of direction quality for a direction is based upon information indicating whether the directions are to a place of business, and extracted from a website provided by the business itself.

36. The method of claim 30, wherein the measure of direction quality for a direction is based upon a number of landmarks included in the directions.

37. The method of claim 30, wherein retrieving, from a plurality of websites, webpages comprising directions comprises:

identifying a website that contain directions based on at least one keyword contained in the website.

38. The method of claim 30, wherein automatically parsing each webpage and extracting a set of directions therefrom comprises:

retaining from a webpage the directions, direction-related context associated with the directions, and metadata associated with the directions; and

discarding text, graphics, images, or formatting not related to the directions.

39. A computer program product comprising a computer readable medium with code for execution on a computer, including the code for performing the method comprising:

retrieving, from a plurality of websites, webpages comprising directions;

automatically parsing text of each webpage and extracting a set of directions therefrom;

scoring each set of directions based on a measure of direction quality;

selectively retaining sets of the directions based on their respective scores; and

storing in a database each retained set of directions.

40. The computer program product of claim 39, wherein the directions are human-provided driving directions.

41. The computer program product of claim 39, the method further comprising:

responsive to at least one set of directions not being associated with a destination, inferring a destination for the set of directions from a context of the webpage from which the set of directions were extracted.

42. The computer program product of claim 39, wherein the measure of direction quality for a direction is based upon a source website of the webpage from which the direction was extracted.

43. The computer program product of claim 39, wherein the measure of direction quality for a direction is based upon a measure of an importance of the webpage from which the direction was extracted.

44. The computer program product of claim 39, wherein the measure of direction quality for a direction is based upon information indicating whether directions are to a place of business, and extracted from a website provided by the business itself.

45. The computer program product of claim 39, wherein the measure of direction quality for a direction is based upon a number of landmarks included in the directions.

46. The computer program product of claim 39, wherein retrieving, from a plurality of websites, webpages comprising directions comprises:

identifying a website that contains directions, based on at least one keyword contained in the website.

47. The computer program product of claim 39, wherein automatically parsing each webpage and extracting a set of directions therefrom comprises:

retaining from a webpage the directions, direction-related context associated with the directions, and metadata associated with the directions; and

discarding text, graphics, images, or formatting not related to the directions.

48. A computer system for generating and storing directions, the system comprising:

a directions database, configured to store directions;

a directions input module, configured to retrieve webpages from a plurality of websites;

a direction extraction module, configured to automatically parse text of the retrieved webpages and extract therefrom directions; and

an evaluator module, configured to score the directions based on a measure of quality, and to selectively retain directions based on their scores, and to store the retained directions in the directions database.

49. The computer system of claim 48, wherein the directions are human-provided driving directions.

50. The computer system of claim 48, wherein the evaluator module is further configured:

responsive to at least one set of directions not being associated with a destination, to infer a destination for the set of directions from a context of the webpage from which the set of directions were extracted.

51. The computer system of claim 48, wherein the measure of quality for a direction is based upon source website of the webpage from which the direction was extracted.

52. The computer system of claim 48, wherein the measure of quality for a direction is based upon a measure of an importance of the webpage from which the direction was extracted.

53. The computer system of claim 48, wherein the measure of direction quality for a direction is based upon information indicating whether the directions are to a place of business, and extracted from a website provided by the business itself.

54. The computer system of claim 48, wherein the measure of quality for a direction is based upon a number of landmarks included in the directions.

55. The computer system of claim 48, wherein the directions input module is configured to identify a website that contains directions based on at least one keyword contained in the website.

56. The computer system of claim 48, wherein the extractor module is further configured to:

retain from a webpage the directions, direction-related context associated with the directions, and metadata associated with the directions; and

discard text, graphics, images, or formatting not related to the directions.