(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2013/0124563 A1
`CaveLie et al.
`(43) Pub. Date:
`May 16, 2013
`
`US 2013 0124563A1
`
`(54) CONTROLLING PRE-FETCHING OF MAP
`DATA TLES BASED ON SELECTABLE
`PARAMETERS
`
`(75) Inventors: Hans-Olav CaveLie, San Francisco, CA
`(US); Thomas G. Nourse, Half Moon
`Bay, CA (US)
`
`(73) Assignee: GOOGLE INC., Mountain Vew, CA
`(US)
`
`(21) Appl. No.: 13/297,363
`
`(22) Filed:
`
`Nov. 16, 2011
`
`Publication Classification
`
`(51) Int. Cl.
`G06F 7/30
`
`(2006.01)
`
`(52) U.S. Cl.
`USPC ............. 707/770; 707/E17.032; 707/E17.044
`
`ABSTRACT
`(57)
`A system and method identifies pre-fetch map data to be
`downloaded from a remote server, having a map database, to
`a client device by using selectable parameters to control pre
`fetching. For example, device specific parameters, such as
`device model number, and user specific parameters, such as
`user interests, may be accessed by the system and method and
`analyzed to determine which pre-fetch map data should be
`downloaded from the remote server. These parameters may
`be automatically stored on the client device or may be manu
`ally entered by the user. The responsive pre-fetch map data
`may be identified by map data type, map points of interest,
`map Zoom level, or some other manner. Where the map data
`base stores map data in tiles, the remote server will send
`selected map data tiles to the client device as the pre-fetch
`map data.
`
`Server 105
`
`Pre-Fetch
`Engine
`750
`
`Map
`Database
`103
`
`180-MAPMEMORY
`BUFFER
`
`120
`
`130
`
`MAP MEMORY
`BUFFER
`MAP
`GENERATOR
`
`PROCESSOR
`
`
`
`136
`
`134
`
`MAP MEMORY
`BUFFER
`MAP
`GENERATOR
`
`
`
`130
`
`PROCESSOR
`
`Niantic's Exhibit No. 1004
`Page 001
`
`

`

`Patent Application Publication May 16, 2013 Sheet 1 of 14
`
`US 2013/O124563 A1
`
`100
`
`
`
`Server 105
`
`Pre-Fetch
`Engine
`750
`
`Map
`Database
`103
`
`136
`
`
`
`132
`
`134
`
`136 - 132
`
`134
`
`180-MAP MEMORY
`BUFFER
`
`MAP MEMORY
`BUFFER
`
`120
`
`130
`
`115
`
`136
`
`
`
`132
`
`134
`
`180-MAPMEMORY
`BUFFER
`
`120
`
`130
`
`FIG. 1
`
`Niantic's Exhibit No. 1004
`Page 002
`
`

`

`Patent Application Publication May 16, 2013 Sheet 2 of 14
`
`US 2013/O124563 A1
`
`120
`
`190
`
`
`
`MAP GENERATOR
`
`181
`
`DATABASE INTERFACE
`MODULE
`
`182
`
`PRE-FETCH SELECTION
`MODULE
`
`186
`
`MAPDATA
`SELECTION MODULE
`
`DEVICE
`PARAMETERS
`
`STATIC
`
`DYNAMIC
`
`PARAMETERS
`
`AUTOMATIC
`
`184
`
`DISPLAY MODULE
`
`USER DEFINED
`
`FIG. 2
`
`192
`
`195
`
`196
`
`197
`
`198
`
`Niantic's Exhibit No. 1004
`Page 003
`
`

`

`Patent Application Publication May 16, 2013 Sheet 3 0f 14
`
`US 2013/0124563 A1
`
`2_00
`
`202A
`
`204A 2048
`
`204C 204D 204E
`
`204F
`
`\/= 1
`
`\/= 1
`
`\/= 1
`
`2046
`
`204H 204|
`
`204J
`
`204K 204L
`
`2028
`
`\/= 1
`
`\/= 1
`
`\/= 1
`
`III-III.-
`
`204M 204N 2040
`
`204P
`
`204Q 204R
`
`V=2
`
`FIG. 3
`
`Niantic's Exhibit No. 1004
`
`Page 004
`
`Niantic's Exhibit No. 1004
`Page 004
`
`

`

`I‘uIE.‘«1‘!“iguana”IE
`
`iErw,.......m.uh‘D—g
`
`.4?.0."—
`
`
`
`.-
`
`Niantic's Exhibit No. 1004
`Page 005
`
`
`

`

`
`
`“himana?mhgwmwgm
`
`mmflfimu.
`
`Niantic's Exhibit No. 1004
`Page 006
`
`
`

`

`Patent Application Publication
`
`May 16, 2013 Sheet 6 of 14
`
`US 2013/O124563 A1
`
`
`
`N
`
`7` | |) L^Š?EPI NOEN?
`
`JAZ: T?
`----
`No.
`?.
`
`Niantic's Exhibit No. 1004
`Page 007
`
`

`

`Patent Application Publication May 16, 2013 Sheet 7 of 14
`
`US 2013/O124563 A1
`
`START
`
`700
`1.
`
`
`
`
`
`AWAT INITIALIZATION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PRE-FETCHSELECTION MODULE
`ACCESSESSELECTION PARAMETERS
`
`PRE-FETCHSELECTION MODULE
`DETERMINES PRE-FETCH MAPDATA
`POLICYBASED ON SELECTION
`PARAMETERS
`
`
`
`
`
`
`
`TRANSMIT PRE-FETCH MAPDATA
`POLICY REQUEST TO SERVER
`
`
`
`RECEIVE PRE-FETCH MAPDATA
`FROM SERVER
`
`STORE RECEIVED PRE-FETCH MAP
`DATA FOR VISUAL DISPLAY
`
`AWAIT USER INTERACTION
`
`IDENTIFY PRE-FETCH MAP DATA
`
`RENDER VISUAL MAPDISPLAY
`
`FIG. 5
`
`701
`
`702
`
`704
`
`PRE-FETCH DATA
`ENGINE
`
`710
`
`712
`
`714
`
`716
`
`Niantic's Exhibit No. 1004
`Page 008
`
`

`

`
`
` Jfl‘.Q...‘“.Ir.AF'..Illiflnfifig00
`
`
`"WleI!'13!“-
`
`
`iEggH
`
`.«g
`
`<9.0."—
`
`.HmhXEvSwmmN
`
`1%03NP
`
`00
`
`00
`
`Niantic's Exhibit No. 1004
`Page 009
`
`
`

`

`“himana?I.-.‘1‘in“-‘_atgay.m
`
`wmfimfimu.
`
`Niantic's Exhibit No. 1004
`Page 0010
`
`
`

`

`Patent Application Publication May 16, 2013 Sheet 10 of 14
`
`US 2013/O124563 A1
`
`
`
`MSY
`
`Niantic's Exhibit No. 1004
`Page 0011
`
`

`

`Patent Application Publication May 16, 2013 Sheet 11 of 14
`
`US 2013/O124563 A1
`
`800-
`
`FIG. 7
`
`IDENTIFY INITIAL PRE-FETCH
`MAPDATATILES
`
`CONSTRUCT AND DISPLAY
`INITIAL VISUAL MAPDISPLAY
`
`
`
`
`
`802
`
`804
`
`AWAIT USER INTERACTION
`
`806
`
`
`
`
`
`900 Y
`
`FIG. 8
`
`DECISIONMODULE ACCESSES INFORMATION
`AND DETERMINES DESIRED SELECTION
`PARAMETERS
`
`MAPDATA POLICY DECISIONMODULE
`ANALYZESSELECTION PARAMETERS
`USINGALOGICAL MODEL
`
`IDENTIFY MAPDATA TRAITS FOR FORMING
`THE MAPDATAPOLICY
`
`
`
`
`
`IDENTIFY DATA VALUES FOR MAPDATA TRAITS-908
`
`ASSEMBLE MAPDATA POLICY
`
`-910
`
`Niantic's Exhibit No. 1004
`Page 0012
`
`

`

`Patent Application Publication May 16, 2013 Sheet 12 of 14
`
`US 2013/O124563 A1
`
`1000
`1.
`
`ACCESS SELECTION PARAMETERS FROM
`BLOCK 902
`
`DO
`ANY SELECTION
`PARAMETERS CORRESPOND
`TO NEXT TRAIT IN
`
`ANALYZE SELECTION
`PARAMETERS TO
`DETERMINE TREATMENT
`OF MAPTRAIT IN MAP
`DATA POLICY
`
`
`
`
`
`
`
`
`
`
`
`
`
`SET NEXT
`MAP TRAIT
`
`
`
`
`
`
`
`
`
`ARE
`THERE ANY ADDITIONAL
`TRATS FOR MAPDATA
`POLICY?
`
`FIG. 9
`
`Niantic's Exhibit No. 1004
`Page 0013
`
`

`

`Patent Application Publication May 16, 2013 Sheet 13 of 14
`
`US 2013/O124563 A1
`
`START
`
`RECEIVE PRE-FETCH MAPDATA POLICY - 1102
`REQUEST
`
`EXAMINE REGUEST TO DETERMINE NEXT
`MAP DATA TRAIT FROM THE MAP DATA
`POLICY REQUEST
`
`DETERMINE PRE-FETCH MAPDATA
`CORRESPONDING TO THE CURRENT MAP
`DATA TRAT
`
`
`
`ARE
`THERE ADDITIONAL MAPDATA
`TRAITS?
`
`
`
`NO
`
`OPTIMIZE AND ASSEMBLE PRE-FETCH - 1110
`MAPDATA
`
`TRANSMIT PRE-FETCH MAPDATA TO CLIENT
`DEVICE
`
`1112
`
`END
`
`FIG. 10
`
`Niantic's Exhibit No. 1004
`Page 0014
`
`

`

`Patent Application Publication
`
`May 16, 2013 Sheet 14 of 14
`
`US 2013/O124563 A1
`
`
`
`Niantic's Exhibit No. 1004
`Page 0015
`
`

`

`US 2013/01 24563 A1
`
`May 16, 2013
`
`CONTROLLING PRE-FETCHING OF MAP
`DATATILES BASED ON SELECTABLE
`PARAMETERS
`
`FIELD OF TECHNOLOGY
`0001. The present disclosure relates to map data optimi
`Zation and more specifically to a system and a method to
`pre-fetch map data from a remote map database.
`
`BACKGROUND
`0002 With the widespread use of mobile devices, such as
`mobile phones, personal data assistants, tablet personal com
`puters, etc., consumer demand for ready access to varied
`types of data continues to grow at a high rate. These devices
`are used to transmit, receive, and store text, voice, image, and
`Video data. Consumers often look to store large numbers of
`applications on these devices, such that mobile devices are
`often touted more for the number of available applications,
`than internal processor speed. While consumers have come to
`desire fast access to data, the sheeramount of data required to
`run these applications places a premium on data management,
`both at the device level and at the network level. This pre
`mium limits the effectiveness of applications such as map
`ping applications, which typically require comparatively
`large amounts of network data.
`0003. Mapping applications are found in a variety of
`mobile devices, including car navigation systems, hand-held
`GPS units, mobile phones, and portable computers. These
`applications are among the most frequently used applications
`and are considered, by some, necessary for personal safety.
`Although the underlying digital maps are easy to use from a
`user's perspective, creating a digital map is a data intensive
`process. Every digital map begins with a set of raw data
`corresponding to millions of streets and intersections. That
`raw map data is derived from a variety of Sources, each
`providing different amounts and types of information. To
`effectively map a location, locate a driving route between a
`Source and a destination, identify points of interest, etc.
`requires Substantial amounts of data. Furthermore, many
`mapping applications require display of different map data at
`different Zoom levels, i.e., different scales, where the amount
`of detail and that nature of that detail changes at each Zoom
`level. For example, at a lowest Zoom level, scaled farthest
`away from a target, the map data may contain the boundaries
`of continents, oceans, and major landmasses. At Subsequent
`Zoom levels, that map data may identify countries, states,
`homelands, protectorates, and other major geographic
`regions. While at even further subsequent Zoom levels, that
`map data may contain major roads, cities, towns, until even
`tually the map data contains minor roads, buildings, down to
`even sidewalks and walkways depending on the region. The
`amount of detail is determined by the sources of information
`used to construct the map data at each Zoom level. But no
`matter the Zoom level, the amount of information is volumi
`nous and generally too large for storage, in total, on mobile
`devices and too large for continuous download overa wireless
`communication network.
`0004. In operation, mapping applications typically down
`load map data to the mobile device through a wireless com
`munication network and in response to a user entering a
`location of interest and/or based on the current location of the
`mobile device. Such as the current global positioning satellite
`(GPS) data or current cellular network location data for the
`
`device. A conventional technique for downloading map data
`is to have the mobile device communicate this location data to
`a remote processor on the wireless communication network,
`which, in response, downloads all map data to the mobile
`device or the map data requested for display to the user.
`0005 Generally speaking, the map data is stored in blocks
`known as map data tiles, where the number of map data tiles
`increases with Zoom level. The remote processor provides a
`subset of the available map data tiles for a particular location
`or region to the mobile device for storage and display at any
`particular time via a map display application. By providing
`large numbers of map data tiles, the mobile device may buffer
`the map data for display to the consumer as the consumer
`scrolls across an area using the mapping application looking
`for adjacent or other mapping locations. However, the larger
`the number of map tiles provided at any particular time
`increases the download time and buffer memory usage while
`the user is using the map display application.
`0006. This conventional downloading of large amounts of
`map data tiles taxes network infrastructure and requires siZ
`able memory allocation within the mobile device. As a result,
`there is a need to have more intelligent mechanisms for down
`loading map data, in particular map data tiles, to Sufficiently
`satisfy the needs of the user, while doing so in a manner that
`addresses network bandwidth limitations and scarce memory
`availability.
`
`SUMMARY
`
`0007. In an embodiment, a computer-implemented
`method comprises: identifying, on a client device, one or
`more pre-fetch selection parameters, where the pre-fetch
`selection parameters include at least one of device parameters
`associated with the client device and user parameters; deter
`mining, on the client device, from the one or more identified
`pre-fetch selection parameters, a pre-fetch map data policy;
`requesting, from a remote map database storing the map data,
`pre-fetch map data stored in the remote map database and
`corresponding to the pre-fetch map data policy determined on
`the client device, wherein the pre-fetch map data is to be
`stored on the client device for eventual rendering of a visual
`display of map data in response to a Subsequent user request;
`receiving, at the client device, the pre-fetch map data from the
`remote database and corresponding to the pre-fetch map data
`policy; and storing the received pre-fetch map data in a local
`memory on the client device until the Subsequent user request
`0008. In another embodiment, a computer-readable
`medium storing instructions, the instructions when executed
`by a processor cause the processor to: identify one or more
`pre-fetch selection parameters, where the pre-fetch selection
`parameters include at least one of device parameters associ
`ated with the client device and user parameters; determine,
`from the one or more identified pre-fetch selection param
`eters, a pre-fetch map data policy; request, from a remote map
`database storing map data, pre-fetch map data stored in the
`remote map database and corresponding to the pre-fetch map
`data policy determined on the client device, wherein the pre
`fetch map data is to be stored on the client device for eventual
`rendering of a visual display of map data in response to a
`Subsequent user request; receive, at the client device, the
`pre-fetch map data from the remote database; and store the
`received pre-fetch map data in a local memory on the client
`device until the Subsequent user request.
`
`Niantic's Exhibit No. 1004
`Page 0016
`
`

`

`US 2013/01 24563 A1
`
`May 16, 2013
`
`0009. In yet another embodiment, a computer system for
`fetching map data to be used in rendering a visual display of
`map data on a client device, the computer system comprises:
`a display module for rendering the visual display of the map
`data on the client device; a pre-fetch selection module to
`analyze pre-fetch selection parameters for the client device to
`determine a pre-fetch map data policy for the client device,
`wherein the pre-fetch selection parameters include at least
`one of device parameters associated with the client device and
`user parameters; and a database interface module to request,
`from a remote server having a map database, pre-fetch map
`data responsive to the pre-fetch map data policy, and to
`receive, from the remote server, the pre-fetch map data
`responsive to the pre-fetch map data policy, wherein the pre
`fetch map data is to be stored on the client device for eventual
`rendering of a visual display of map data in response to a
`Subsequent user request.
`0010. In a further embodiment, a computer-implemented
`method for downloading pre-fetch map data to a client device
`for use in rendering a visual display of map data on the client
`device, the method comprises: receiving a pre-fetch map data
`policy request from the client device, where the pre-fetch map
`data policy request comprises one or more map data traits and
`wherein the pre-fetch map data policy request depends on
`device parameters or user parameters for the client device;
`analyzing the one or map data traits in the pre-fetch map data
`policy request to determine pre-fetch map data corresponding
`to the device parameters or the user parameters for the client
`device, wherein the pre-fetch map data is to be stored on the
`client device for eventual rendering of a visual display of map
`data in response to a Subsequent user request; and transmit
`ting the pre-fetch map data to the client device.
`0011. In a still further embodiment, a computer-readable
`medium storing instructions, the instructions when executed
`by a processor cause the processor to: receive a pre-fetch map
`data policy request from the client device, where the pre-fetch
`map data policy request comprises one or more map data
`traits and wherein the pre-fetch map data policy request
`depends on device parameters or user parameters for the
`client device; analyze the one or map data traits in the pre
`fetch map data policy request to determine pre-fetch map data
`corresponding to the device parameters or the userparameters
`for the client device, wherein the pre-fetch map data is to be
`stored on the client device for eventual rendering of a visual
`display of map data in response to a Subsequent user request;
`and transmit the pre-fetch map data to the client device.
`0012. In yet another embodiment, a server for download
`ing pre-fetch map data to a client device for use in rendering
`a visual display of map data on the client device, the server
`comprises: a memory for storing a map database; and a pre
`fetch engine configured to, receive a pre-fetch map data
`policy request from the client device, where the pre-fetch map
`data policy request comprises one or more map data traits and
`wherein the pre-fetch map data policy request depends on
`device parameters or user parameters for the client device,
`analyze the one or map data traits in the pre-fetch map data
`policy request to identify from the map database pre-fetch
`map data corresponding to the device parameters or the user
`parameters for the client device, wherein the pre-fetch map
`data is to be stored on the client device for eventual rendering
`of the visual display of map data in response to a Subsequent
`user request, and transmit the pre-fetch map data to the client
`device.
`
`0013 The features and advantages described in this sum
`mary and the following detailed description are not all-inclu
`sive. Many additional features and advantages will be appar
`ent to one of ordinary skill in the art in view of the drawings,
`specification, and claims hereof.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`0014 FIG. 1 is high-level block diagram of a wireless
`network depicting a wireless base station connected to a
`server containing map data for selectively communicating
`that map data to a various client devices on the network.
`0015 FIG. 2 is a block diagram of an example map gen
`erator in the client device of FIG. 1.
`0016 FIG. 3 illustrates a portion of the data structure for
`the map database of FIG. 1.
`0017 FIGS. 4A, 4B, and 4C illustrate example renditions
`of map data at three different Zoom levels, respectively.
`0018 FIG. 5 illustrates an example process or flow dia
`gram for using selectable parameters to control pre-fetching
`of map data from a remote server.
`(0019 FIGS. 6A, 6B, and 6C illustrate example renditions
`of the map data of FIGS. 4A, 4B, and 4C, at three different
`Zoom levels, respectively, and showing points of interest at
`the different Zoom levels.
`0020 FIG. 7 illustrates an example process or flow dia
`gram for constructing and displaying pre-fetch map data visu
`ally.
`FIG. 8 illustrates an example process or flow dia
`0021
`gram for assembling a pre-fetch map data policy based on
`selectable parameters.
`0022 FIG. 9 illustrates an example process or flow dia
`gram as may be performed in illustration of FIG. 8 to identify
`map data traits that will form the pre-fetch map data policy.
`0023 FIG. 10 illustrates an example process or flow dia
`gram as may be performed on the remote server to identify
`pre-fetch map data and to communicate to a client device.
`0024 FIG. 11 illustrates an example pre-fetch map data
`policy request frame as may be communicated from the client
`device to the remote server in accordance with FIG. 10.
`
`DETAILED DESCRIPTION
`
`0025. The present application describes techniques for
`fetching map data over a selected Subset of the entire map data
`available, by analyzing one or more pre-fetch selection
`parameters. The techniques, which may be implemented on a
`client device such as a mobile or handheld device, will deter
`mine which map data to pre-fetch from a remote database
`based on the selection parameters. In this way, the client
`device may be populated with a portion of all available map
`data, where that portion is selected based on the parameters
`associated with the client device. These parameters may be
`device parameters, i.e., associated with the hardware itself.
`while in the other examples, these parameters may be user
`parameters, i.e., dependent on the user of the client device. In
`Some embodiments, the client device automatically deter
`mines which parameters are to be used in identifying pre
`fetch map data, e.g., based on a set of predetermined condi
`tions. In other embodiments, the particular parameters are
`manually determined, e.g., by input from the user.
`
`Niantic's Exhibit No. 1004
`Page 0017
`
`

`

`US 2013/01 24563 A1
`
`May 16, 2013
`
`0026. In some embodiments, the map data is stored at the
`remote server in the form of map data “tiles. In such
`examples, the techniques rely upon analysis of these pre-fetch
`selection parameters to identify map data tiles as the pre-fetch
`map data.
`0027 More particularly, the present application describes
`techniques for fetching map data over a selected Subset of the
`entire map data available by using selection parameters for
`each client device. These selection parameters may include
`device parameters, such as static parameters such as a hard
`ware platform type, a device model/version type, language
`setup, screen size, screen resolution, APIs available on the
`device and their versions and locale. Dynamic device param
`eters may be used such as a location of the client device,
`available memory, and network speed. In other embodiments,
`these selection parameters including user parameters, such as
`hobbies or items of interest, user usage patterns, user account
`type, number of bytes remaining in a users (e.g., monthly)
`service data plan of if the user has requested to limit or ramp
`up the amount of caching on the device. In yet other embodi
`ments, a combination of any of these or other Suitable selec
`tion parameters may be used. Stored values for these selection
`parameters are examined in Some embodiments at the client
`device and it other examples at least partially at a remote
`server—from which a pre-fetch map data policy can be iden
`tified. The identified pre-fetch map data policy may be used to
`identify different types of pre-fetch map data. In some
`embodiments, the selection parameters are used to determine
`a pre-fetch map data policy that identifies map data tiles, map
`points of interest, and/or Zoom levels.
`0028. When used to determine map points of interest and
`Zoom level, the client device identifies that data to a remote
`server that contains a map database of the entire map data,
`including map data for the points of interest. With the points
`of interest identified, the remote server begins transmitting
`the map data, corresponding to these points of interest, to the
`client device for storage and display to the user. Storing map
`data in data blocks known as map data “tiles, the remote
`server sends the map data in the form of a map data tiles. For
`each point of interest, the server may send an identified set of
`map data tiles, termed pre-fetch map data tiles.
`0029 Pre-fetching refers to requesting map data from a
`remote map database. Such as that of a remote server, prior to
`any specific user request for map data, so that map data may
`be collected and buffered on a device until a specific user
`request for map data. In this way, pre-fetching seeks to collect
`map data in the background, before that map data is called
`upon to construct a visual display, thereby reducing (and even
`eliminating) the need for a client device to request map data
`only after a user request. The pre-fetched map data is auto
`matically identified, requested, and stored on the client device
`for Subsequent use in constructing a visual display. As dis
`cussed in examples below, where that map data is stored in the
`remote map database in the form of map data tiles, the pre
`fetching is of map data tiles.
`0030 FIG. 1 is a high-level block diagram that illustrates
`a computing environment for a pre-fetch map data system 100
`that may be used to access and store map data within a map
`database. As illustrated in FIG. 1, the computing environment
`includes a map database 103 connected to or disposed within
`a server 105, which is, in turn, connected to a number of client
`devices 115 through a network 125. The network 125
`includes but is not limited to any combination of a LAN, a
`MAN, a WAN, a mobile, a wired or wireless network, a
`
`private network, or a virtual private network. While only three
`clients 115 are illustrated in FIG. 1 to simplify and clarify the
`description, it is understood that any number of client com
`puters are Supported and can be in communication with the
`Server 105.
`0031) Both the server 105 and the clients 115 are comput
`ers that may include a CPU 130 (only shown in the clients),
`one or more computer readable memories 132, one or more
`user interfaces 134 (keyboard, touch screen, etc.), a network
`interface 136, one or more peripheral interfaces, and other
`well known components. AS is known to one skilled in the art,
`other types of computers can be used that have different
`architectures. The client devices 115 represent any suitable
`handheld and/or mobile device, such as a mobile phone,
`personal data assistant, laptop computer, tablet personal com
`puter, car navigation system, hand-held GPS unit, or “smart”
`device. More broadly, the client devices 115 represent any
`personal computing device, database, server, or network of
`Such devices, or any other processing device having a user
`interface and CPU and capable of displaying a visual rendi
`tion of map data accessed from the map database 103 or other
`remote source of map data. Furthermore, while in some
`examples, the network 125 is described as a wireless network,
`the network 125 may be any wired or wireless network, where
`the clients 115 are devices on the network.
`0032. The server 105 and the clients 115 are also adapted
`to execute computer program modules for providing func
`tionality described herein. As used herein, the terms 'mod
`ule” and “routine” refer to computer program logic used to
`provide the specified functionality. Thus, a module or a rou
`tine can be implemented in hardware, firmware, and/or soft
`ware. In one embodiment, program modules and routines are
`stored on a storage device, loaded into memory, and executed
`by a processor or can be provided from computer program
`products that are stored in tangible computer-readable Stor
`age mediums (e.g., RAM, hard disk, optical/magnetic media,
`etc.).
`0033. The map database 103, which may be stored in or
`may be separate from the server 105, contains map data that
`can be used to generate a digital map or that can be used by, for
`example, a navigation system to determine routes between
`two locations. Physical roads, waterways, parks, landmarks,
`and other geographic elements may be represented in the map
`data by a list of nodes and segments that connect those nodes.
`Each node corresponds to a specific geographic location in
`the physical world. The data representation for each node
`generally includes a set of coordinates (e.g., latitude and
`longitude) and an association with one or more segments. For
`roads, each segment corresponds to a section of a physical
`location that begins at one node and ends at a different node.
`The data representation for each road segment, for example,
`can include a length and a number of attributes, such as a
`street name, a priority (e.g., a highway or a local road), speed
`information, a surface type, a road width, an indication of
`whether the road segment is a one-way segment, address
`ranges, usage (e.g., ramp or trail), etc.
`0034. The map data stored in the map database 103 can be
`obtained from several different sources such as the New York
`City Open Accessible Space Information System (OASIS)
`and the U.S. Census Bureau Topologically Integrated Geo
`graphic Encoding and Referencing system (TIGER). The
`map data can also be accessed by one of the map generators
`120, modified, and stored back into the database 103. Further,
`the database 103 does not need to be physically located within
`
`Niantic's Exhibit No. 1004
`Page 0018
`
`

`

`US 2013/01 24563 A1
`
`May 16, 2013
`
`server 105. For example, the database 103 can be partially
`stored within a client 115, can be stored in external storage
`attached to the server 105, or can be stored in a network
`attached storage. Additionally, there may be multiple servers
`105 that connect to a single database 103. Likewise, the map
`database 103 may be stored in multiple different or separate
`physical data storage devices.
`0035 Each client 115 executes one of the map generators
`120, each of which requests and receives pre-fetch map data
`from the server 105 and generates a visual display of the
`received map data that is presented to the user on a display of
`the interface 134. The map generator 120 is able to adjust that
`visual display in response to user interactions with the inter
`face 134, for example, adjusting which map data is visualized
`at any given time in response to a user selecting to Scroll (left,
`right, up, down, etc.) through the visual display, or in response
`to the user selecting to change the Zoom level (e.g., Scale) of
`the displayed map data.
`0036. As illustrated in the detailed example of FIG. 2, the
`client 115 may include various modules within or associated
`with the map generator 120, including a database interface
`module 181 that operates to retrieve map data from the server
`105 and map database 103. The map generator 120 further
`includes a pre-fetch selection module 182 that may be used to
`set a pre-fetch map data policy as discussed herein. The
`selection module 182 may identify one or more points of
`interest that are to be used by a display module 184 to create
`a visual map display of received map data on the interface
`134. The points of interest determined by the module 182 are
`communicated by the interface module 181 through the net
`work interface 136 through network 125 to the server 105,
`which responds by sending pre-fetch map data from the map
`database 103 back to the client device 115, where this pre
`fetch map data is received by the database interface module
`181 and is stored in a map buffer memory 180 of the client
`115.
`0037. A map data selection module 186 accesses the
`stored pre-fetch map data and determines which portion of
`that buffered map data is to be provided to the display module
`184 for creating the visual map display on the interface 134.
`The module 186, therefore, is responsive (after pre-fetching)
`to user interaction with the interface 134 to determine which
`portion of the pre-fetched map data should be displayed to the
`desires in response to a Subsequent user interaction, which is
`determined by a centralized map position, user Scrolling, and
`Zoom level, for example.
`0038. In some embodiments, the pre-fetch selection mod
`ule 182 identifies one or more Zoom levels in the pre-fetch
`map data policy, which one or more Zoom levels are commu
`nicated to the remote server 105 for identifying pre-fetch map
`data. The interface module 181 receives the pre-fetch map
`data from the server 105 and stores it in the buffer memory
`180 for eventual display using the map data selector module
`186 and the display module 184.
`0039. To set the pre-fetch map data policy, the selection
`module 182 accesses selection parameters stored in a
`memory 190, which may be portion of the memory 132.
`Generally speaking, the memory 190 contains any number of
`any Suitable kind of selection parameters storing values
`accessed by the selection module 182. In the illustrated
`embodiment, the memory 190 includes two types of param
`eters, device parameters 192 and user parameters 194. In the
`
`illustrated example, the device parameters memory block 192
`contains static device parameters 195 and dynamic device
`parameters 196, while the userparameters memory block 194
`contains two sets of parameters. Automatically determined
`parameters 197 represent those user parameters compiled by
`the client device without express user control, for example, by
`the client device executing routines or modules to automati
`cally track, monitor, and evaluate user-specific interactions.
`User determined parameters 198 are those set explicitly by
`the user, for example in response to a menu section, setup of
`the client device, or other techniques.
`0040. The pre-fetching selection module 182 will be dis
`cussed in further detail below. It is noted here, however, that
`the selection module 182 may include modules designed to
`further define pre-fetch map data.
`0041. Of course, some embodiments of the map generator
`120 may have different and/or other modules than the ones
`described herein. Similarly, the functions described herein
`can be distributed among the modules in accordance with
`other embodiments in a different manner than that described
`herein.
`0042 Generally speaking, in Some embodiments, map
`data in the map database 103 is stored in different Zoom levels
`each formed of a plurality of map data blocks, termed map
`tiles, which are used to construct a visual display of the map.
`FIG.3 illustrates an example data structure 200