Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 1 of 29 PAGEID #: 47
`Case: 1:20-cv-00578—MWM Doc #: 1-2 Filed: 07/24/20 Page: 1 of 29 PAGEID #: 47
`
`
`
`
`
`
`
`EXHIBIT B
`
`EXHIBIT B
`
`

`

`(12) United States Patent
`Keerthi
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,731,833 B2
`*May 20, 2014
`
`USOO873 1833B2
`
`(54) COMPUTING PATHS BETWEEN
`GEOGRAPHICAL LOCALITIES
`(71) Applicant: Empire Technology Development LLC,
`Wilmington, DE (US)
`
`(72) Inventor: Arvind Vijay Keerthi, Bangalore (IN)
`(73) 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.
`This patent is Subject to a terminal dis
`claimer.
`
`(21) Appl. No.: 13/949,125
`
`(22) Filed:
`
`Jul. 23, 2013
`
`(65)
`
`O
`O
`Prior Publication Data
`US 2013/0311090 A1
`Nov. 21, 2013
`
`Related U.S. Application Data
`(63) Continuation of application No. 13/859,665, filed on
`Apr. 9, 2013, now Pat. No. 8,560,238, which is a
`continuation of application No. 13/498,556, filed as
`application No. PCT/IB2011/052612 on Jun. 16,
`2011, now Pat. No. 8,457,885.
`
`Foreign Application Priority Data
`(30)
`Feb. 1, 2011
`(IN) ......................... OO296/CHFA2011
`
`(51) Int. Cl.
`G06F 9/00
`GOIC 2L/00
`GOIC 21/34
`A63 F.3/OO
`
`(2011.01)
`(2006.01)
`(2006.01)
`(2006.01)
`
`(52) U.S. Cl.
`CPC ............ G0IC 21/00 (2013.01); G0IC 21/3476
`(2013.01); A63F 2003/00201 (2013.01); A63F
`3/00072 (2013.01)
`USPC ........... 701/537; 701/533; 273/254; 273/256;
`379/88.01
`
`(58) Field of Classification Search
`CPC ................ G01C 21/00; G01C 21/3476; A63F
`2003/00201: A63F 3/00072
`USPC ................... 701/400, 516, 537; 707/999.005,
`707/999.104,999.01, 999.1, 706, 710,918,
`707/919; 455/433,445, 456.1,414.3, 440;
`379/9.02, 88.01, 88.03; 273/254, 256;
`196/132; 704/251: 370/328; 463/17
`See application file for complete search history.
`References Cited
`
`(56)
`
`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,058,395 B2 *
`6/2006 Dowling et al. ........... 455,414.2
`(Continued)
`OTHER PUBLICATIONS
`U.S. Appl. No. 13/859,665, filed Apr. 19, 2013, Keerthi.
`Continued
`(Continued)
`in a
`Primary Examiner McDieunel Marc
`(74) Attorney, Agent, or Firm — Perkins Coie LLP
`(57)
`ABSTRACT
`Technology is generally described for computing paths
`between geographical localities. In some examples, the tech
`nology can receive a request for a path between two or more
`geographical localities, and compute a path based at least on
`a popularity rating of intermediate geographical localities.
`
`20 Claims, 17 Drawing Sheets
`
`AMGArt
`CNNASAY
`TURE LUE.
`CriCK
`STAUM
`t
`Fre. N
`W
`Y-
`A.
`/ NA
`
`-------
`
`\
`
`AAA
`GANX-rCAD
`
`---
`-->
`f MAJESTIC \
`-
`w
`r
`- N-
`------ BREN
`-- :
`\ }
`ARK
`:ENFA.
`N.
`x Boy'R.Ns'
`s-\ SEV f
`Ci-Eg:
`w
`w
`/.
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 2 of 29 PAGEID #: 48
`
`
`
`\
`
`y
`
`\
`
`y
`
`\
`
`----
`
`.
`
`w
`
`N--
`fySR
`(ARES
`
`W f.
`vi - tige
`a
`TOWN
`
`

`

`US 8,731.833 B2
`Page 2
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6, 2008 Meadow et al.
`7,389,181 B2
`2/2010 Chen et al.
`7,660,441 B2
`9/2010 Kaplanet al.
`T805.239 B2
`2/2012 Amine
`sió808 B2
`6/2012 Starenky et al.
`8,200,247 B1
`7, 2012 Goel
`8,219,316 B2
`1 1/2012 Lawther et al.
`8,311,741 B1
`8,335,647 B2 12/2012 Kurtti et al.
`8,352,178 B2
`1/2013 Allen et al.
`8,457,885 B2 * 6/2013 Keerthi ......................... TO1/438
`2003/0182052 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.
`2010, OO82567 A1
`4/2010 Rosenblatt et al.
`2010, 0118025 A1
`5, 2010 Smith et al.
`
`7, 2010 Barker et al.
`2010.0185382 A1
`4/2011 Rhoads et al.
`2011/0098056 A1
`5, 2011 Barash et al.
`2011/01 17878 A1
`8/2011 Jansen et al.
`2011/0208427 A1
`2011/0275441 A1 11, 2011 Wilson
`2012,0041777 A1
`2/2012 Case et al.
`2012. O154633 A1
`6/2012 Rodriguez
`2012/0158705 A1
`6/2012 Konig et al.
`2012fO232796 A1
`9/2012 Keerthi
`
`OTHER PUBLICATIONS
`
`“Comparing Five Free Road Trip Planners.” Feb. 15, 2008,
`AreWeThereYet? AreWeThereYet? Travel with your children, not
`against them website.
`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-2 Filed: 07/24/20 Page: 3 of 29 PAGEID #: 49
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 1 of 17
`
`US 8,731,833 B2
`
`
`
`FG. A
`
`F.G.
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 4 of 29 PAGEID #: 50
`
`F. C.
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 2 of 17
`
`US 8,731,833 B2
`
`200 -
`
`rico ow
`
`3S Rte 335
`
`VA-AMA GAND ROAD
`
`Vetro Rai
`Next gain ir, S ir
`
`Cricket Stadium
`
`Change Trains
`Catch ran at O2C A?
`Or take taxi
`
`rf City
`
`FG, 2
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 5 of 29 PAGEID #: 51
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 3 of 17
`
`US 8,731,833 B2
`
`3C
`
`w 1
`
`310
`\
`N
`K
`
`N-
`
`8
`
`-->
`Sever set is
`is -
`:
`304m s/
`3O2
`Y
`Y-1 a...............................................
`
`f
`
`v
`
`
`
`Server in m
`
`Network
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 6 of 29 PAGEID #: 52
`
`F.G. 3
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 4 of 17
`
`US 8,731,833 B2
`
`4.04
`432
`4:06
`\
`s
`N
`y
`id geographical locality popularity rating
`
`i
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 7 of 29 PAGEID #: 53
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 5 Of 17
`
`US 8,731,833 B2
`
`-500
`
`SO2
`
`M
`
`start
`
`3O4.
`
`receive ist of websites
`
`56
`
`seect first website
`
`-
`
`508
`
`Y-510
`Compute popularity
`rating for selected
`website
`
`512
`
`Select next website
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 8 of 29 PAGEID #: 54
`
`54
`
`return
`
`C return D
`F.G.
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 6 of 17
`
`US 8,731,833 B2
`
`
`
`6O2
`*
`
`-1 8O
`
`p
`
`request and receive web
`Site Cotent
`
`identify geographical
`ocalities in Content
`
`Select first identified
`geographica Ocality
`
`SO
`
`Selected
`
`Y
`
`N
`
`62
`
`8a.
`select next geographical
`iocaity
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 9 of 29 PAGEID #: 55
`
`616
`
`F.G. 6
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 7 Of 17
`
`US 8,731,833 B2
`
`
`
`700
`
`popularity rating
`evailator
`
`popularity ratings
`
`ist of websites
`
`Connections and
`w
`weights
`
`path generator
`
`identifier of
`geographical iocalities
`
`identifier of
`Coinections between
`geographical localities
`
`user preferences (e.g.,
`ist of kown
`geographical localities)
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 10 of 29 PAGEID #: 56
`
`FIG. 7
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 8 of 17
`
`US 8,731,833 B2
`
`generate directed graph based on
`connections between origin, destination,
`and intermediate geographical iocalities
`
`for each path from origin to destination,
`compute sun of popularity ratings and
`connection weights
`
`select path with preferred sums of
`popularity ratings and connection weights
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`retur Selected
`path
`
`FIG. 8
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 11 of 29 PAGEID #: 57
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 9 Of 17
`
`US 8,731,833 B2
`
`
`
`
`
`
`
`
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 12 of 29 PAGEID #: 58
`
`

`

`U.S. Patent
`
`US 8,731,833 B2
`
`006,
`
`
`
`
`
`
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 13 of 29 PAGEID #: 59
`
`\ \
`
`\
`
`/
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`US 8,731,833 B2
`
`
`
`
`
`
`
`
`
`JO6 (DI),
`
`*&---------
`
`?
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 14 of 29 PAGEID #: 60
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 12 of 17
`
`US 8,731,833 B2
`
`OOO
`
`1 OO2
`Stat. D
`
`O)4
`
`identify geographical
`OCaities
`
`O)8
`identify relevant connections
`between the identified localities
`
`O8
`
`compute path
`
`OO
`respond to requests for paths
`
`2
`
`( ret."
`
`FIG. It
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 15 of 29 PAGEID #: 61
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 13 of 17
`
`US 8,731,833 B2
`
`
`
`O4.
`receive ist of connections between a first geograhica:
`locality an a second geographical iocality
`
`select first coffection
`
`O
`)
`
`- s1108
`- Connection is N
`situ- return
`s 1
`2
`Y
`identify first and second geographical localities as neighboring
`localities if distance between iocaiities is ess that a specified
`threshoid distance of one of the geographical localities is part of
`a set of geographica ocaiities identified by user
`-is there
`-5, a road with iess than s
`- a specified nurber of its ris between the-Y
`s-
`first and second graphical
`ra
`
`---
`
`o
`
`Caies? s - is st 16 -
`
`
`
`
`
`
`
`
`
`u-distance between
`--
`- the first and the second is
`- geographical localities less than a specifieds...Y.
`s--threshold and are the geographical
`sfocalities both in an --
`sigrban area2
`w
`a? --
`Y (s -s 8
`- are both
`- the first and the seconds Y
`geographical localities on a -
`school, public transit
`s ir k? --
`
`'a
`
`
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 16 of 29 PAGEID #: 62
`
`-1 3.
`
`add connection to list of
`preferred connections for
`path Corptitation
`
`F.G.
`
`
`
`
`
`select rex coffection
`
`
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 14 of 17
`
`US 8,731,833 B2
`
`- 1200
`
`
`
`Corpute optima path via
`locations
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 17 of 29 PAGEID #: 63
`
`

`

`.e
`aP
`081
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 18 of 29 PAGEID #: 64
`C
`2
`._H21
`875O
`g
`
`O.tmm0t2a1P%S.a.CU
`
`02,DmMyWaM.M
`
`”F.m0
`
`O7mH40Q571Oaumem«M
`
`fU
`
`
`
` Mm#.3m3gmm.73989S
`
`HI.
`
`M
`
`W
`
`mmam:
`
`Amonn
`
`éwmmw
`
`moEmmEM
`
`3m:mmjom.m.zoo
`
`qw44<m<fl
`
`maximmté
`
`gm:muufiafizifizgfim
`
`m...............................mmmjomwzco
`
`
`mam:Sam2“Manama..@228
`$30Mxaozfimz
`
`m25:00
`
`).11917v0.I.\
`
`00
`
`3mg
`08 33W»
`
`
`
`Nvmwwm0m>mfl.Mbnrmbo
`
`wofnpummv
`
`mwzfimwooaa
`
`$32t2:
`
`06%
`
`02.3503
`
`
`
`8mm:.55
`
`wxo<oN#55
`
`mamflxbfinzmfix
`
`
`
`.mmoumewmmuomm
`
`3me
`
`KmE:mmmwmfivwm
`
`
`
`pwomw>KOEwE5w.m.w>m
`
`E<§§OK
`
`8mmw,
`
`
`
`Emfiwimwzgmmuo
`
`
`
`mm?zop<o§a<
`
`
`
` 6mm3m0k<mmzw01.5mm
`
`
`
`@4wa(EQQE<mwomm
`
`92$5353
`
`.9“9.55200
`
`.
`
`
`
`m...............295.23%:
`
`IxmfloEzoo
`
`muimmpzzwam
`
`.
`
`8mm:
`
`w4m<>0§mméoz
`
`awn:mmégw
`
`an:4%;
`
`Emgogmm
`
`H5559:03A$3“3mméxobm
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 16 of 17
`
`US 8,731,833 B2
`
`e
`
`1402
`
`.a.
`?
`
`receiving a set of four or more identifications of geographica
`locatities, at east one of the geographica ocaities generally
`identifiable by a name or region but not a postal street address
`
`receiving a set of Connections between at east a subset of the
`set of for or more geographica iocalities, wherein a
`Connection between any two geographical localities indicates a
`path between the two geographical localities
`
`identifying a popularity rating for at east the first geographica
`iocality, wherein the popularity rating for the first geographical
`locality exceeds the popularity rating for the second
`geographical ocaity
`
`40
`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 Confections
`
`412
`determining that there exist at least two paths from the second
`geographical locality to the third geographical locality, wherein
`there does not exist a Conection 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 iocality
`
`
`
`
`
`
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 19 of 29 PAGEID #: 65
`
`4
`
`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 iocality, the first
`path thereby comprising connections from the second
`geographical locality to the first geographica ocality to the third
`geographical iocality
`14.6
`
`( feturn
`
`FIG. 4
`
`

`

`U.S. Patent
`
`May 20, 2014
`
`Sheet 17 Of 17
`
`US 8,731,833 B2
`
`SOO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Corporefit configured to receive a set of four or more
`identifications of geographical iocalities, at east one of the
`localities generally identifiable by a name or region but not
`a posta address
`
`1504.
`component configured to receive a set of connections
`between at east a subset of the set of for or more
`geographical ocaities wherein the Connections between
`any two geographical iocalities indicates a path between
`the two geographical localities
`
`506
`Component configured to identify a popularity rating for at
`east a first geographical iocality, wherein the popularity
`rating for the first geographical locality exceeds the
`popularity rating for a fourth geographica ocality
`1508
`component configured to receive a request to provide
`directions from a second geographica locality to a third
`geographica ocality
`
`15
`component configured to determine that there exist at
`east two paths from the second geographical locality to
`the third geographical locality, wherein there does not
`exist a Conectio between the Second and the third
`geographical ocalities, wherein a first path includes the
`first geographical locality but not the fourth geographical
`iocaity and a second path includes the fourth
`geographical iocaity but not the first geographical locality
`52
`component configured to identify the first path as a
`preferable path because the popularity rating for the first
`geographica ocaity exceeds the popularity rating for the
`second geographical iocaity, the first path thereby
`Comprising Connections from the second geographica
`locality to the first geographica locality to the third
`geographical locality
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`F.G. 5
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 20 of 29 PAGEID #: 66
`
`
`
`

`

`US 8,731,833 B2
`
`1.
`COMPUTING PATHS BETWEEN
`GEOGRAPHICAL LOCALITIES
`
`2
`The foregoing Summary is illustrative only and is not
`intended to be in any way limiting. In addition to the illustra
`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
`
`CROSS-REFERENCE TO RELATED
`APPLICATION(S)
`This application is a Continuation of U.S. patent applica
`tion Ser. No. 13/859,665, filed Apr. 9, 2013, now U.S. Pat. No.
`8,560,238 issued Oct. 15, 2013, which is a Continuation of
`U.S. patent application Ser. No. 13/498,556, filed May 9,
`2012, now U.S. Pat. No. 8,457,885 issued Jun. 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 (entitled COMPUTING PATHS BETWEEN GEO
`15
`GRAPHIC LOCALITIES), each of which is herein incorpo
`rated by reference in its entirety.
`
`10
`
`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
`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.
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 21 of 29 PAGEID #: 67
`
`

`

`3
`sented herein. It will be readily understood that the aspects of
`the present disclosure, as generally described herein, and
`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
`50
`include a new, nearby department store a different month—
`both for the same origin and destination.
`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
`
`30
`
`Case: 1:20-cv-00578-MWM Doc #: 1-2 Filed: 07/24/20 Page: 22 of 29 PAGEID #: 68
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`US 8,731,833 B2
`
`10
`
`15
`
`25
`
`4
`technology can identify popular nearby grocery stores, doc
`tors, and pharmacies, and/or compute a path transiting popu
`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
`
`

`

`US 8,731,833 B2
`
`10
`
`15
`
`25
`
`30
`
`35
`
`5
`connection may be weighted more when the distances are
`long because a traveler probably wants to spend less time
`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
`40
`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
`45
`computing devices 306a to 306m via a network 310. The
`network 310 can be an intranet, the Internet, or other type of
`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 (e.g., SMS), etc.
`The client computing devices may transmit path requests
`and/or locality information to server com