throbber
Case: 1:20-cv-00578-MWM Doc #: 1-1 Filed: 07/24/20 Page: 1 of 28 PAGEID #: 19
`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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket