`Case: 1:20-cv-00578—MWM Doc #: 1-1 Filed: 07/24/20 Page: 1 of 28 PAGEID #: 19
`
`
`
`
`
`
`
`EXHIBIT A
`
`EXHIBIT A
`
`
`
`(12) United States Patent
`Keerthi
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,560,238 B2
`Oct. 15, 2013
`
`USOO856O238B2
`
`(54)
`
`(71)
`
`(72)
`(73)
`
`(*)
`
`(21)
`(22)
`(65)
`
`(63)
`
`(51)
`
`(52)
`
`(58)
`
`COMPUTING PATHS BETWEEN
`GEOGRAPHICAL LOCALITIES
`
`Applicant: Empire Technology Development LLC,
`Wilmington, DE (US)
`
`Inventor: Arvind Vijay Keerthi, Bangalore (IN)
`Assignee: Empire Technology Development LLC,
`Wilmington, DE (US)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`Appl. No.: 13/859,665
`Filed:
`Apr. 9, 2013
`
`Prior Publication Data
`US 2013/0226456A1
`Aug. 29, 2013
`
`Related U.S. Application Data
`Continuation of application No. 13/498,556, filed as
`application No. PCT/IB2011/052612 on Jun. 16,
`2011, now Pat. No. 8,457,885.
`
`(2011.01)
`
`Int. C.
`G06F 9/00
`U.S. C.
`USPC ........ 701/537; 701/533; 701/538; 379/88.01;
`379/88.03; 273/254; 273/256: 704/251: 370/251;
`370/328; 463/17
`
`Field of Classification Search
`USPC ............... 701/537,538,533:455/433,456.1,
`455/414.3: 463/17:379/88.01, 88.03;
`273/254, 256: 704/251: 370/251,328
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`7, 1991 Delorme
`5,030,117 A
`9/1995 Yokoyama et al.
`5,452,212 A
`5,848,373 A 12/1998 DeLorime et al.
`5,923,730 A
`7, 1999 Takaki
`7,389,181 B2
`6/2008 Meadow et al.
`7,660,441 B2
`2/2010 Chen et al.
`7,805,239 B2
`9/2010 Kaplanet al.
`8, 116,808 B2
`2/2012 Amine ....................... 455,550.1
`8,200,247 B1
`6/2012 Starenky et al.
`8,219,316 B2 * 7/2012 Goel ............................. TO1/422
`8,311,741 B1 * 1 1/2012 Lawther et al.
`701,527
`8,335,647 B2 * 12/2012 Kurtti et al. ...
`TO1 (533
`8,352,178 B2* 1/2013 Allen et al. .
`... 701 410
`8,457,885 B2 * 6/2013 Keerthi ......................... TO1/438
`2003. O182052 A1
`9, 2003 DeLorime et al.
`2006.0075442 A1
`4/2006 Meadow
`2009. O150389 A1
`6/2009 Knorr
`2009/0319172 A1 12/2009 Almeida et al.
`2010.008213.6 A1* 4/2010 Rosenblatt et al. ............. TOO.94
`2010.0082567 A1* 4/2010 Rosenblatt et al. ........... 707/705
`2010, 0118025 A1
`5, 2010 Smith et al.
`(Continued)
`OTHER PUBLICATIONS
`
`
`
`“Comparing Five Free Road Trip Planners.” Feb. 15, 2008,
`AreWeThereYet? AreWeThereYet? Travel with your children, not
`against them website.
`
`(Continued)
`Primary Examiner — McDieunel Marc
`(74) Attorney, Agent, or Firm — Perkins Coie LLP
`(57)
`ABSTRACT
`Technology is generally described for computing paths
`between geographical localities. The technology can receive
`a request for a path between two or more geographical locali
`ties, and compute a path based at least on a popularity rating
`of intermediate geographical localities.
`20 Claims, 17 Drawing Sheets
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 2 of 28 PAGEID #: 20
`
`
`
`SYSTEMMEMORY 306
`RMRAM
`OPERATING SYSTEM
`132
`APPLICATION 1322
`
`PATH GENERATOR
`(1326)
`
`PROGRAMDATA (324.)
`OCALITIES AND
`CONNECTIONS
`NFORMATION
`1328
`
`
`
`
`
`Ulufs
`Level level.
`CACHE
`CACHE
`13
`312
`
`ROCSSOR OR
`ALUEPSP
`EGISTERS
`1316
`
`ERY CNTRLER
`138
`
`MEMORY Bus (1308)
`
`STORAGEDEVICES 1332
`REMOVABLE
`NoN-REMOVABLE
`STORAGE (1336)
`STORAGE (1338)
`(e.g., HDD)
`(e.g., CD/DVD)
`
`BUSINTERFACE
`CONTROLLER
`(1330)
`
`sts
`STORAGE INTERFACEBUS 1334)
`
`GRAPHICS
`PROCESSING
`UNIT (1348)
`
`Audio
`PROCESSING
`UNIT (1350)
`-
`PERIPHERANTERFACES 344
`
`ERA
`INTERFACE
`CONTROLLER
`() 1334
`ARALE
`INTERFACE
`CCNTROLLER
`1338)
`-
`COMMUNICATIONCEWICES 1346
`
`li
`Port(s) ()
`(1358)
`
`COMM.
`NEWORK
`CoNTROLLER CPoRTs)
`(1360)
`(1384)
`
`cits
`Pip
`
`
`
`US 8,560.238 B2
`Page 2
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`7, 2010 Barker et al.
`2010.0185382 A1
`4/2011 Rhoads et al.
`2011/0098056 A1
`2011/01 17878 A1* 5, 2011 Barash et al. .............. 455,404.2
`2011/0208427 A1
`8/2011 Jansen et al.
`2011/0275441 A1* 11/2011 Wilson ............................ 463/42
`2012/0041777 A1
`2/2012 Case et al. ........................ 705/2
`2012/0154633 A1
`6/2012 Rodriguez
`
`2012/0158705 A1* 6/2012 Konig et al. .................. 707/723
`2012fO232796 A1
`9/2012 Keerthi
`
`OTHER PUBLICATIONS
`
`PCT International Search Report for International Application No.
`PCT/IB2011/052612, filed Jun. 16, 2011, mailing date: Sep. 28,
`2011.
`
`* cited by examiner
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 3 of 28 PAGEID #: 21
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 1 of 17
`
`US 8,560,238 B2
`
`
`
`FIG. IA
`
`FIG. IB
`
`(a)
`
`(D)
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 4 of 28 PAGEID #: 22
`
`FIG. IC
`
`(a)
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 2 of 17
`
`US 8,560,238 B2
`
`to
`
`Richmond TOWn
`
`BUS ROUte 335E
`
`MAHATMA GANDHI ROAD
`
`Metro Rail
`Next Train in 5 min
`
`Cricket Stadium
`
`Change Trains
`Catch Train at 10:20 AM
`Or take taxi
`
`Turf Club
`
`FIG. 2
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 5 of 28 PAGEID #: 23
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 3 of 17
`
`US 8,560,238 B2
`
`-o
`
`31 O
`
`
`
`
`
`3O4m
`
`
`
`302a
`
`Client 1
`
`306a
`
`
`
`
`
`306m
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 6 of 28 PAGEID #: 24
`
`FIG. 3
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 4 of 17
`
`US 8,560,238 B2
`
`400
`
`406
`404
`402
`N
`N.
`N.
`id geographical locality popularity rating
`408 N-1
`A
`5
`410 n-2
`B
`25
`412 N-3
`C
`10
`414 n-4
`D
`7
`416 N-5
`E
`15
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 7 of 28 PAGEID #: 25
`
`FIG. 4
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 5 Of 17
`
`US 8,560,238 B2
`
`500
`
`502
`
`504
`
`receive list of Websites
`
`506
`
`Select first Website
`
`
`
`
`
`
`
`Selected?
`
`
`
`
`
`
`
`510
`Compute popularity
`rating for selected
`Website
`
`51
`2
`
`Select next WebSite
`
`
`
`
`
`514
`
`return
`
`FIG. 5
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 8 of 28 PAGEID #: 26
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 6 of 17
`
`US 8,560,238 B2
`
`602
`
`-o
`
`604
`request and receive Web
`Site Content
`
`606
`identify geographical
`localities in Content
`
`608
`Select first identified
`geographical locality
`
`
`
`Selected?
`
`increment Count
`
`select next geographical
`locality
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 9 of 28 PAGEID #: 27
`
`FIG. 6
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 7 Of 17
`
`US 8,560,238 B2
`
`702
`popularity rating
`evaluator
`
`704
`
`list of Websites
`
`700
`706
`
`popularity ratings
`
`708
`Connections and
`s
`weights
`
`710
`
`712
`
`path generator
`
`identifier of
`geographical localities
`
`714.
`
`identifier of
`Connections between
`geographical localities
`
`
`
`716
`user preferences (e.g.,
`list of known
`geographical localities)
`
`
`
`
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 10 of 28 PAGEID #: 28
`
`FIG. 7
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 8 of 17
`
`US 8,560,238 B2
`
`802
`
`Start
`
`800
`
`804
`
`806
`
`generate directed graph based on
`Connections between origin, destination,
`and intermediate geographical localities
`808
`for each path from origin to destination,
`Compute sum of popularity ratings and
`Connection weights
`
`select path with preferred sums of
`popularity ratings and Connection weights
`
`810
`
`
`
`
`
`
`
`
`
`812
`return Selected
`path
`
`FIG. 8
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 11 of 28 PAGEID #: 29
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 9 Of 17
`
`US 8,560,238 B2
`
`P?
`
`
`
`
`
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 12 of 28 PAGEID #: 30
`
`
`
`U.S. Patent
`
`006
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 13 of 28 PAGEID #: 31
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 14 of 28 PAGEID #: 32
`Case: 1:20-CV-00578-MWM DOC #: 1-1 Filed: 07/24/20 Page: 14 0f 28 PAGEID #: 32
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 11 of 17
`
`US 8,560,238 132
`
`
`
`UCO£2.....
`
`
`\mun.Emzwgwflmx
`
`:25?203szcmm2Hoasmmfich
`
`2....262
`
`
`
` 338D
`
`“macfiSm
`
`
`
`
`
`\lEm:thsaflfim\I’m.m
`sea»...................hfianO/
`
`EEmmEmo0388.
`
`bWKwao
`n380/
`'Mfimda“
`
`P...“ta/om
`53%;
`
`
`
`Congo/\
`
` A{mm—........
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 12 of 17
`
`US 8,560,238 B2
`
`- to
`
`1002
`
`1004
`
`identify geographical
`OCalities
`
`1 OO6
`identify relevant connections
`between the identified localities
`
`1008
`
`Compute path
`
`1010
`respond to requests for paths
`
`1012
`
`return
`
`FIG. I.0
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 15 of 28 PAGEID #: 33
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 13 of 17
`
`US 8,560,238 B2
`
`1102
`Start
`11 O4
`receive list of Connections between a first geograhical
`locality and a second geographical locality
`
`- to
`
`select first Connection
`
`
`
`
`
`k
`
`1108
`
`selected?
`
`1106
`
`1110
`
`1112
`identify first and second geographical localities as neighboring
`localities if distance between localities is less than a specified
`threshold distance or one of the geographical localities is part of
`a set of geographical localities identified by user
`1114
`
`
`
`
`
`
`
`is there
`a road with less than
`a specified number of turns between the
`first and second geographical
`localities?
`
`
`
`
`
`distance between
`the first and the second
`geographical localities less than a specified
`threshold and are the geographical
`localities both in an
`rban area?
`
`
`
`
`
`1118
`
`are both
`
`geographical localities on a
`ommon public transi
`
`
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 16 of 28 PAGEID #: 34
`
`FIG. I. I.
`
`add Connection to list of
`preferred connections for
`path computation
`
`Select next Connection
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 14 of 17
`
`US 8,560,238 B2
`
`- to
`
`1202
`
`1204
`
`receive list of locations
`
`
`
`
`
`12O6
`Compute optimal path via
`locations
`
`
`
`1210
`respond to requests for
`paths
`
`1212
`
`return
`
`FIG. I2
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 17 of 28 PAGEID #: 35
`
`
`
`_
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 18 of 28 PAGEID #: 36
`8
`2
`6
`
`2a1PaosSaoCU
`
`
`
` _.>_<~u_\_>_OmW@353n_0ozammoomn.we?>m0§m§E596_0.tmoinzmw__wn_0.m_
`
`
`40__25_W1_mmjoEzoo20.2583__fla_muEmEz.IAmF.Smzofiomzzoo__wM$33dj<m<n_m”51:05on
`
`EOEmEoz<8:353__WSIm‘.VNQ<203200mm__lmmjoEzoom85:__1..mofimmfiz.m.mmmpwawm__#.BU6%:__Cmmmmoinisé«52%sz12¢__ma(mmoo
`
`
`
`
`
`
`
`5.55szEmuO__own3__MO0.93mOmmmuomn.__Hmm?zOfi<o§E<__ML833%:__Wcozmwmoomn.
`
`32..B#8D3
`
`/f
`
`S
`
`
`mo<m9m_07_3989502929232200llllllllllllllllllI._21___xmozpmzImug__mm?wmoSmo6mm:moEEm6mm:fU__0__8fix:6%:an:$38550$3_1@5502%:8%:IEjoEzoo$5.on_.&@EomImmjoEzoomoimmpzzmamEm<>0§mméoz£355”..._g.3500
`
`
`
`
`
`
`
`
`
`
`
`a2,.G0MNUN“61lllllllllllllllllllllllllllllllllllllllM59__8oo_can:mammoEmEz
`moéfim_
`
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 16 of 17
`
`US 8,560,238 B2
`
`1400
`
`1404
`receiving a set of four or more identifications of geographical
`localities, at least one of the geographical localities generally
`identifiable by a name or region but not a postal street address
`
`receiving a set of Connections between at least a subset of the
`set of four or more geographical localities, wherein a
`Connection between any two geographical localities indicates a
`path between the two geographical localities
`
`1408
`identifying a popularity rating for at least the first geographical
`locality, wherein the popularity rating for the first geographical
`locality exceeds the popularity rating for the second
`geographical locality
`
`
`
`1410
`receiving a request to provide directions from the second
`geographical locality to the third geographical locality, the
`directions specified by one or more paths, each path specified
`as a sequence of Connections
`
`1412
`determining that there exist at least two paths from the second
`geographical locality to the third geographical locality, wherein
`there does not exist a Connection between the Second and the
`third geographical localities, wherein a first path includes the
`first geographical locality but not the fourth geographical locality
`and a second path includes the fourth geographical locality but
`not the first geographical locality
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 19 of 28 PAGEID #: 37
`
`1414
`identifying the first path as a preferable path because the
`popularity rating for the first geographical locality exceeds the
`popularity rating for the fourth geographical locality, the first
`path thereby comprising connections from the second
`geographical locality to the first geographical locality to the third
`geographical locality
`1416
`
`return
`
`FIG. I.4
`
`
`
`U.S. Patent
`
`Oct. 15, 2013
`
`Sheet 17 Of 17
`
`US 8,560,238 B2
`
`
`
`1500
`
`component configured to receive a set of four or more
`identifications of geographical localities, at least one of the
`localities generally identifiable by a name or region but not
`a postal address
`
`component configured to receive a set of connections
`between at least a Subset of the Set of four or more
`geographical localities wherein the Connections between
`any two geographical localities indicates a path between
`the two geographical localities
`
`component configured to identify a popularity rating for at
`least a first geographical locality, wherein the popularity
`rating for the first geographical locality exceeds the
`popularity rating for a fourth geographical locality
`
`Component configured to receive a request to provide
`directions from a second geographical locality to a third
`geographical locality
`
`1510
`Component Configured to determine that there exist at
`least two paths from the second geographical locality to
`the third geographical locality, wherein there does not
`exist a Connection between the Second and the third
`geographical localities, wherein a first path includes the
`first geographical locality but not the fourth geographical
`locality and a second path includes the fourth
`geographical locality but not the first geographical locality
`1512
`Component configured to identify the first path as a
`preferable path because the popularity rating for the first
`geographical locality exceeds the popularity rating for the
`second geographical locality, the first path thereby
`Comprising connections from the second geographical
`locality to the first geographical locality to the third
`geographical locality
`
`FIG. I5
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 20 of 28 PAGEID #: 38
`
`
`
`US 8,560,238 B2
`
`1.
`COMPUTING PATHS BETWEEN
`GEOGRAPHICAL LOCALITIES
`
`2
`tive aspects, embodiments, and features described above, fur
`ther aspects, embodiments, and features will become appar
`ent by reference to the drawings and the following detailed
`description.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIGS. 1A-1C are block diagrams illustrating graphs
`depicting paths through geographical localities.
`FIG. 2 is a path diagram illustrating a path through a
`sequence of geographical localities.
`FIG. 3 is a block diagram illustrating components of the
`disclosed technology in various embodiments.
`FIG. 4 is a table diagram illustrating tables that the dis
`closed technology may employ in various embodiments.
`FIG. 5 is a flow diagram illustrating a routine for collecting
`popularity ratings for multiple websites that the disclosed
`technology may invoke in various embodiments.
`FIG. 6 is a flow diagram illustrating a routine for comput
`ing a popularity rating for a geographical locality based on
`website content that the disclosed technology may invoke in
`various embodiments.
`FIG. 7 is a block diagram illustrating components of the
`disclosed technology in various embodiments.
`FIG. 8 is a flow diagram illustrating a routine for comput
`ing a path from an origin to a destination that the disclosed
`technology may invoke in various embodiments.
`FIG.9A is a map diagram illustrating a map of a geographi
`cal area.
`FIG.9B is a graph diagram illustrating a graph of geo
`graphical localities corresponding to the geographical area
`illustrated in FIG.9A.
`FIG.9C is a map diagram with the graph diagram of FIG.
`9B superimposed on it.
`FIG.10 is a flow diagram illustrating a routine for respond
`ing to requests for paths between origins and destinations that
`the disclosed technology may invoke in various embodi
`mentS.
`FIG. 11 is a flow diagram illustrating a routine for identi
`fying connections between geographical localities that may
`be suitable for use in paths that the disclosed technology may
`invoke in various embodiments.
`FIG. 12 is a flow diagram illustrating a routine for respond
`ing to requests for paths between multiple locations that the
`disclosed technology may invoke in various embodiments.
`FIG.13 is a block diagram of an illustrative embodiment of
`a computing device that is arranged for computing paths
`between geographical localities in accordance with at least
`Some embodiments of the present disclosure.
`FIG. 14 is a flow diagram illustrating a routine for comput
`ingapath that the disclosed technology may invoke in various
`embodiments.
`FIG. 15 is a block diagram illustrating components of the
`technology in various embodiments.
`
`DETAILED DESCRIPTION
`
`In the following detailed description, reference is made to
`the accompanying drawings, which form a parthereof. In the
`drawings, similar symbols typically identify similar compo
`nents, unless context dictates otherwise. The illustrative
`embodiments described in the detailed description, drawings,
`and claims are not meant to be limiting. Other embodiments
`may be utilized, and other changes may be made, without
`departing from the spirit or scope of the Subject matter pre
`sented herein. It will be readily understood that the aspects of
`the present disclosure, as generally described herein, and
`
`CROSS-REFERENCE TO RELATED
`APPLICATION(S)
`This application is a Continuation of U.S. patent applica
`tion Ser. No. 13/498,556, filed May 9, 2012, now U.S. Pat.
`No. 8,457,885 issued June 4, 2013, which is a U.S. National
`Stage entry of PCT Application No. PCT/IB2011/052612,
`filed Jun. 16, 2011, which claims priority to Indian Patent
`Application No. 00296/CHF/2011 filed on Feb. 1, 2011 (en
`titled COMPUTING PATHS BETWEEN GEOGRAPHIC
`LOCALITIES), each of which is herein incorporated by ref
`erence in its entirety.
`
`10
`
`15
`
`BACKGROUND
`
`Various techniques exist for computing paths between geo
`graphical localities. As examples, BING(R) MAPS,
`GOOGLE(R) MAPS, and MAPQUESTR) are online services
`that receive an origin and destination and compute paths from
`the origin to the destination. In all three cases, however,
`directions are provided in terms of turn-by-turn directions.
`Turn-by-turn directions are directions suitable for people
`who are familiar with reading maps or who reside in devel
`oped areas where all streets have names. However, in some
`areas, e.g., in some developing countries, not all Streets have
`street names. Moreover, many people in these areas do not
`think of directions in terms of streets, distances, and turns.
`
`25
`
`30
`
`SUMMARY
`
`Technology is described for computing paths between geo
`graphical localities. The technology can receive a request for
`35
`a path between two or more geographical localities, and com
`pute a path based at least on a popularity rating of intermedi
`ate geographical localities.
`The technology can receive a set of four or more identifi
`cations of geographical localities, wherein at least one of the
`geographical localities is generally identifiable by a name or
`region but not a postal street address; receive a set of connec
`tions between at least a subset of the set of four or more
`geographical localities, wherein a connection between any
`two geographical localities indicates a path between the two
`geographical localities; identify a popularity rating for at least
`the first geographical locality, wherein the popularity rating
`for the first geographical locality exceeds the popularity rat
`ing for the second geographical locality; receive a request to
`provide directions from the second geographical locality to
`the third geographical locality, wherein the directions are
`specified by one or more paths, each path specified as a
`sequence of connections; determine that there exist at least
`two paths from the second geographical locality to the third
`geographical locality, wherein there does not exist a connec
`tion between the second and the third geographical localities,
`wherein a first path includes the first geographical locality but
`not the fourth geographical locality and a second path
`includes the fourth geographical locality but not the first
`geographical locality; and identify the first path as a prefer
`able path because the popularity rating for the first geographi
`cal locality exceeds the popularity rating for the fourth geo
`graphical locality, the first path thereby comprising
`connections from the second geographical locality to the first
`geographical locality to the third geographical locality.
`The foregoing Summary is illustrative only and is not
`intended to be in any way limiting. In addition to the illustra
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 21 of 28 PAGEID #: 39
`
`
`
`US 8,560,238 B2
`
`5
`
`10
`
`15
`
`25
`
`35
`
`40
`
`45
`
`3
`illustrated in the Figures, can be arranged, Substituted, com
`bined, separated, and designed in a wide variety of different
`configurations, all of which are explicitly contemplated
`herein.
`In some geographical areas, people think of directions in
`terms of geographical localities and connections between the
`geographical localities. Examples of geographical localities
`are landmarks, neighborhoods, stores, intersections, religious
`locations and artifacts, etc. As an example, when providing a
`direction from an origin to a destination, a person may Sug
`gest walking to a popular nearby Store, embarking on a bus
`identified by a bus number, disembarking at a stadium, walk
`ing toward a temple, and then walking toward some large
`signs identifying an upcoming movie or political rally. Some
`of these geographical localities may not even have a postal
`address. As an example, a pillar in the middle of the road, a
`flyover intersection of a major thoroughfare, or a park may
`not have a postal address.
`Technology is described for computing paths between geo
`graphical localities (“the technology’). In various embodi
`ments, the technology computes directions using popularity
`ratings for geographical localities: the more popular a geo
`graphical locality is, the more likely it may be included in a
`path from an origin to a destination when the geographical
`locality lies on the path from the origin to the destination. As
`an example, if there are two paths from an origin to a desti
`nation, with a first path transiting a more popular geographi
`cal locality and a second path transiting a less popular geo
`graphical locality, the technology may select the first path.
`Popular geographical localities will generally be more easily
`locatable, e.g., by people unfamiliar with the area, because
`more people will know where the geographical locality is and
`how to get there. Therefore, travelers may be able to more
`easily navigate the path, e.g., by asking for directions from
`others.
`The popularity rating for a particular geographical locality
`can be computed using various means. As examples, the
`popularity rating can be computed by regularly scanning
`informational sources, e.g., Internet websites, social net
`working websites, news sources, etc. Whenever a particular
`geographical locality is found in informational sources, its
`popularity rating can be increased. By “crowd-sourcing the
`popularity ratings for geographical localities, the technology
`is able to adapt to changing popularities or popular knowl
`edge of geographical localities. By computing and employing
`popularity ratings, the technology is able to provide relevant
`directions to users. As an example, the directions can include
`a popular movie theater or political rally site one month, but
`include a new, nearby department store a different month—
`both for the same origin and destination.
`50
`In various embodiments, the technology can take into con
`sideration the desirability of transiting particular connections
`between geographical localities. Connections can have asso
`ciated with them importance metrics (or “weights'). As an
`example, a highway with multiple modes of transportation
`(e.g., multiple bus routes with frequent buses) may be more
`desirable (e.g., more “important” or have more “weight')
`than a winding footpath. On the other hand, a footpath that is
`a shortcut and substantially reduces the transit time between
`two geographical localities as compared to traveling on roads
`may be more desirable than the roads.
`In various embodiments, the technology can receive an
`origin and a list of multiple destinations, and create a path that
`includes all of the destinations. As an example, the user may
`desire to visit a grocery store, a doctor, and a pharmacy. The
`technology can identify popular nearby grocery stores, doc
`tors, and pharmacies, and/or compute a path transiting popu
`
`30
`
`Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 22 of 28 PAGEID #: 40
`
`55
`
`60
`
`65
`
`4
`lar geographical localities. The popularity for the various
`destinations can be computed in a similar manner to that
`described above for geographical localities. The computed
`path may be one that minimizes travel time or distance. The
`origin may also be a final destination.
`In various embodiments, the technology can enable per
`Sonalization of paths. As an example, the technology may
`enable the user to provide a set of known geographical locali
`ties. A user may know the location of a particular department
`store, landmark, Street, etc. and may be familiar with various
`paths to that location. When computing a path between an
`origin and a destination, the technology can scan the set of
`known geographical localities and attempt to employ them in
`the path, e.g., when connections exist via the known geo
`graphical localities. The technology may ignore the known
`geographical localities when these localities would take the
`traveler on a highly circuitous route or significantly increase
`travel time (e.g., by more than 25%).
`The technology will now be described with reference to the
`Figures. FIGS. 1A-1C are block diagrams illustrating graphs
`100, 150, and 180, respectively, each depicting one or more
`paths through geographical localities. FIG. 1A depicts a
`graph 100. The graph 100 includes five geographical locali
`ties: A102, B104, C106, D108, and E 110. The geographical
`localities are depicted in varying sizes in which a larger size
`indicates a higher popularity rating. Thus, for example, geo
`graphical locality B104, which is larger than geographical
`locality C 106, has a higher popularity rating than geographi
`cal locality C 106. The graph 100 also includes connections
`between the geographical localities: a connection 112
`between geographical localities A102 and C 106; a connec
`tion 114 between geographical localities A102 and B104; a
`connection 116 between geographical localities B104 and C
`106; a connection 118 between geographical localities B104
`and D108; a connection 120 between geographical localities
`B 104 and E 110; a connection 122 between geographical
`localities D 108 and E 110; and a connection 124 between
`geographical localities C 106 and D 108. Some connections
`may be more desirable or “important than others, e.g.,
`because there may be multiple modes of transportation, fre
`quent public transportation, etc. More important connections
`can be illustrated by using a thicker line than a less important
`connection illustrated by using a thinner line. As examples,
`connections 112 and 118 may be more important than the
`other connections, as illustrated by the thicker corresponding
`lines.
`FIG. 1B illustrates a graph 150 having a path from geo
`graphical locality A 102 via geographical locality B 104 to
`geographical locality D 108. The selected connections are
`connections 152 and 154. The technology has selected con
`nections 152 and 154 (corresponding to connections 114 and
`118 of FIG. 1A, respectively) because of the higher popular
`ity rating of geographical locality B 104 as compared to
`geographical locality C 106.
`In contrast, FIG. 1C illustrates a graph 180 having a path
`from geographical locality A102 via geographical locality C
`106 to geographical locality D 108. The selected connections
`are connections 182 and 184. The technology has selected
`connections 182 and 184 (corresponding to connections 112
`and 124 of FIG. 1A, respectively) because connection 112 is
`more important (or desirable) than connection 114. In some
`embodiments, the technology can employ various heuristics
`to determine whether to give additional weight to the popu
`larity rating of a geographical locality or the importance
`rating of a connection. As an example, the importance of a
`connection may be weighted more when the distances are
`long because a traveler probably wants to spend less time
`
`
`
`US 8,560,238 B2
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`5
`traveling even if it means transiting a less popular geographi
`cal locality. Thus, for example, the technology may have
`selected connections 182 and 184 because the distances
`between geographical localities A102 and both B104 and C
`106 are long.
`FIG. 2 is a path diagram illustrating a path 200 through a
`sequence of geographical localities. A path 200 is illustrated
`from Richmond Town to the Turf Club. The path transits abus
`route 335E, Mahatma Gandhi Road (“MG Road”), a Metro or
`rail link, a cricket stadium, and an option to take a train or a
`taxi. The illustrated path indicates when the next trains are
`scheduled to arrive. In various embodiments, the technology
`may display the illustrated path on a screen, transmit step-by
`step geographical localities or connections via text messag
`ing, e.g., to a mobile device Such as a mobile telephone, or
`transmit the path via electronic mail. In some embodiments,
`the technology may provide a “fisheye' view to paths. As an
`example, the technology may provide more granular direc
`tions near an origin or a destination of the path and less
`granular directions near transitory geographical localities
`between the origin and destination of the path. By doing so, a
`user may be able to easily find geographical localities perti
`nent to the path. By providing more granular directions near
`an origin or destination, the technology enables a traveler to
`more easily find the origin or destination. By providing less
`granular directions between the origin and destination, the
`technology enables a traveler to employ pertinent geographi
`cal localities, e.g., when asking for directions or identifying
`public transit stops. The technology may automatically
`sequence through the identified connections and geographi
`cal localities, e.g., by monitoring the user's position. As an
`example, a mobile device that the user is carrying may trans
`mit the user's location and, when the user is at or near a
`geographical locality or connection forming the path, one or
`more next geographical localities or connections may be
`transmitted to the user.
`FIG. 3 is a block diagram illustrating components 300 of
`the disclosed technology in various embodiments. Compo
`nents 300 can include one or more server computing devices,
`e.g., a server 1302a to a server m302m. The servers may be
`communicably coupled with one or more storage devices,
`e.g., storage devices 304a to 304m. The servers may be com
`municably coupled with client computing devices, e.g., client
`computing devices 306a to 306m via a network 310. The
`network 310 can be an intranet, the Internet, or other type of
`45
`network. The client computing devices may also be commu
`nicably coupled with one or more storage devices, e.g., Stor
`age devices 308a to 308n. The storage devices can be used to
`store data, executable code, etc.
`The server computing devices may store various informa
`tion pertinent to computing paths between geographical
`localities. As examples, the server computing devices may
`store geographical localities, popularity ratings, connections,
`importance or weights of connections, user preferences, and
`So forth. The server computing devices may respond to client
`requests, e.g. client requests that arrive via the Internet, text
`messaging