Efficient processing for vector tile generation

A vector tile generator receives map features from a database of raw map data. Each map feature includes geometry data and property data. The vector tile generator stores the property data in a property store. The vector tile generator generates, based on the geometry data, a set of zoom data organized into a plurality of zoom levels. Each zoom level includes at least some of the map features. The vector tile generator maps the map features of the set of zoom data to a plurality of tiles that includes a set of tiles for each of the zoom levels. For each tile, the vector tile generator clips map features mapped to the tile based on a boundary of the tile, encodes the clipped map features to a vector format, and merges the encoded clipped map features with the stored property data corresponding to the map features in the tile.

BACKGROUND

This disclosure relates to digital maps. More specifically, this disclosure relates to generating vector tiles for map data.

Digitally stored electronic maps are used to represent geographic information of an area and are displayed to users of mobile and other computing devices, for example, using any of a wide array of standalone map or direction application programs or apps. Electronic maps are commonly represented as tiles. Segments of maps are represented as tiles, which can be joined together for analysis or display. Tiles are typically available at various zoom levels having different levels of detail. For example, an area represented by a single tile at one zoom level may be represented by four smaller, more detailed tiles at the next higher zoom level.

Digital map systems create tiles based on data describing various geographic features, such as built features (roads, buildings, etc.), geological features (rivers, lakes, etc.), political features (e.g., borders of countries, states, counties, etc.). Current methods for creating tiles are inefficient and require significant computing power. In current implementations, tile generation involved defining the boundaries of each tile, pulling raw data relevant to each tile, and processing the relevant data to generate the tile. Because many map features span across multiple tiles, current tile generation methods often involve pulling and processing data for such features many times, e.g., for each tile that includes a particular feature. This makes processing data sets slow and resource-intensive. In addition, inefficient tile processing makes it difficult or impossible for current digital map systems to integrate new data to their maps on an as-needed basis. As a result, digital map systems often are unable to capture latest or temporary changes in map data, such as road constructions and temporary detours, new or temporary building features, areas that are temporarily inaccessible (e.g., because of flooding), etc. Without the ability to quickly create and update map tiles, a map application may not provide up to date information to users relying on the map data.

SUMMARY

This disclosure relates to an efficient method for generating map tiles based on raw map feature data. As used herein, map features, also referred to as features, are any shapes that represent physical features on a map. For example, map features can represent built features (roads, buildings, etc.), geological features (rivers, lakes, mountains, etc.), and political features (e.g., borders of countries, states, counties, etc.). Map features can be represented on a map using various geometries, such as points, polygons, and lines. To generate a map tile from raw feature data, tile generation systems identify features located within the map tile, simplify the identified features based on the zoom level of the map tile, and the clip the features to the size of the tile. For example, a map includes a river having a number of increasingly small tributaries. For a given map tile that includes a portion of a river and some of the tributaries, the tile generation system retrieves the feature data describing the river and tributaries, simplifies the features by removing some tributaries that are not displayed for that tile's zoom level, and clips the features by isolating the portion of the river that crosses that map tile. As described above, performing this processing tile-by-tile is slow and inefficient. The tile generation process described herein improves speed and efficiency compared to previous tile generation processed.

In an embodiment, a vector tile generator identifies a set of map features from a database of raw map data. The raw map data includes geometry data and property (or attribute) data for each feature. For example, for a road, the geometry data describes the path of the road, the width of the road, and other data describing the physical shape and location of the road within the map. The property data for the road may include the name of the road, the speed limit, the direction of travel, and other types of information describing the road that does not relate to the road geometry. The vector tile generator stores the property data and operates on the geometry data. First, the vector tile generator operates on the geometry data at various zoom levels. In particular, at each zoom level, the vector tile generator simplifies the geometry data based on the zoom level, e.g., by retaining many feature details at lower zoom levels, and retaining large features and removing smaller features at higher zoom levels. The vector tile generator then maps the geometry data remaining at each zoom level to tiles for the zoom level. The vector tile generator clips the geometry data for each tile to the size of the tile, and encodes the tile data in a standard vector tile format. The vector tile generator then retrieves the properties for each feature in each tile, and merges the properties data with the encoded geometry data to produce the completed map tiles.

This process increases efficiency for several reasons. First, by initially operating on the geometry data at different zoom levels, the vector tile generator performs the simplification step once for each feature at each zoom level, unlike in prior methods where the same feature could be simplified multiple times for different tiles. Second, at each stage, the vector tile generator can process various parts of the map data in parallel. For example, the vector tile generator can simplify the geometry data for each zoom level in parallel, and clip the features for each tile in parallel (or in multiple parallel queues). Third, the processed geometry data moves from stage to stage, unlike prior processes which involved complex indexing of data and frequent querying of the raw map data.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS

In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention. Other embodiments, aspects and features will become apparent from the disclosure as a whole.

Example Computer System Implementation

FIG. 1illustrates an example computer system in which the techniques described may be practiced, according to one embodiment.

In an embodiment, a computer system100comprises components that are implemented at least partially by hardware at one or more computing devices, such as one or more hardware processors executing stored program instructions stored in one or more memories for performing the functions that are described herein. In other words, all functions described herein are intended to indicate operations that are performed using programming in a special-purpose computer or general-purpose computer, in various embodiments.FIG. 1illustrates only one of many possible arrangements of components configured to execute the programming described herein. Other arrangements may include fewer or different components, and the division of work between the components may vary depending on the arrangement.

FIG. 1illustrates a mobile computing device145that is coupled via a wireless network connection165to a server computer105, which is coupled to a database120. A GPS satellite is coupled via a wireless connection to the mobile computing device145. The server computer105comprises a mapping application110, an application programming interface (API)112, a vector tile generator115, and a database interface117. The database120comprises electronic map source data125, electronic map data130, telemetry data135, and aggregated telemetry data140. The mobile computing device145comprises a GPS transceiver150, client map application155, software development kit (SDK)157and wireless network interface159.

Server computer105may be any computing device, including but not limited to: servers, racks, workstations, personal computers, general purpose computers, laptops, Internet appliances, wireless devices, wired devices, multi-processor systems, mini-computers, and the like. AlthoughFIG. 1shows a single element, the server computer105broadly represents one or multiple server computers, such as a server cluster, and the server computer may be located in one or more physical locations. Server computer105also may represent one or more virtual computing instances that execute using one or more computers in a data center such as a virtual server farm.

Server computer105is communicatively connected to database120and mobile computing device145through any kind of computer network using any combination of wired and wireless communication, including, but not limited to: a Local Area Network (LAN), a Wide Area Network (WAN), one or more internetworks such as the public Internet, or a company network. Server computer105may host or execute mapping application110and may include other applications, software, and other executable instructions, such as database interface117, to facilitate various aspects of embodiments described herein.

In one embodiment, a database interface117is a programmatic interface such as JDBC or ODBC for communicating with database120. The database interface117may communicate with any number of databases and any type of database, in any format. Database interface117may be a piece of custom software created by an entity associated with mapping application110, or may be created by a third party entity in part or in whole.

In one embodiment, database120is a data storage subsystem consisting of programs and data that is stored on any suitable storage device such as one or more hard disk drives, memories, or any other electronic digital data recording device configured to store data. Although database120is depicted as a single device inFIG. 1, database120may span multiple devices located in one or more physical locations. For example, database120may include one or nodes located at one or more data warehouses. Additionally, in one embodiment, database120may be located on the same device or devices as server computer105. Alternatively, database120may be located on a separate device or devices from server computer105.

Database120may be in any format, such as a relational database, a noSQL database, or any other format. Database120is communicatively connected with server computer105through any kind of computer network using any combination of wired and wireless communication of the type previously described. Optionally, database120may be communicatively connected with other components, either directly or indirectly, such as one or more third-party data suppliers. Generally, database120stores data related to electronic maps including, but not limited to: electronic map source data125, electronic map data130, telemetry data135, and aggregated telemetry data140. These datasets may be stored as columnar data in a relational database or as flat files.

In one embodiment, electronic map source data125are raw digital map data that are obtained, downloaded or received from a variety of sources. The raw digital map data may include satellite images, digital street data, building or place data or terrain data. Example sources include National Aeronautics and Space Administration (NASA), United States Geological Survey (USGS), and DigitalGlobe. Electronic map source data125may be updated at any suitable interval and may be stored for any amount of time. Once obtained or received, electronic map source data125are used to generate electronic map data130.

In one embodiment, electronic map data130are digital map data that are provided, either directly or indirectly, to client map applications, such as client map application155, using an API. Electronic map data130are based on electronic map source data125. Specifically, electronic map source data125may be processed and organized as a plurality of vector tiles which may be subject to style data to impose different display styles. Electronic map data130may be updated at any suitable interval and may include additional information beyond that derived from electronic map source data125. For example, various additional information may be stored in the vector tiles, such as traffic patterns, turn restrictions, detours, common or popular routes, speed limits, new streets, and any other information related to electronic maps or the use of electronic maps.

In one embodiment, telemetry data135are digital data that are obtained or received from mobile computing devices145via function calls that are included in a Software Development Kit (SDK) that application developers use to integrate and include electronic maps in applications. In one embodiment, telemetry data135are anonymous sensor data that are corrected from various users of the map applications155that are installed in the mobile computing devices145based on users' voluntary reporting. The telemetry data135may include various anonymous map-related data collected by the mobile computing devices145. As indicated by the dotted lines, telemetry data135may be transiently stored, and are processed as discussed below before storage as aggregated telemetry data140.

More specifically, the telemetry data135include time observations and location information based on GPS signals. In one embodiment, the time and location of telemetry data135associated with a single mobile computing device145is referred to as a trace. Telemetry data135may additionally include one or more digitally stored events, in which each event comprises a plurality of event attribute values. Telemetry events may include session start, map load, map pan, map zoom, map tilt or rotate, location report, speed and heading report, or a visit event including dwell time plus location. Telemetry event attributes may include latitude-longitude values for the then-current position of the mobile device, a session identifier, instance identifier, application identifier, device data, connectivity data, view data, and timestamp.

In one embodiment, aggregated telemetry data140are telemetry data135that have been processed using anonymization, chunking, filtering, or a combination thereof. Anonymization may include removing any data that identifies a specific mobile device or person. Chunking may include segmenting a continuous set of related telemetry data into different segments or chunks representing portions of travel along a route. For example, telemetry data may be collected during a drive from John's house to John's office. Chunking may break that continuous set of telemetry data into multiple chunks so that, rather than consisting of one continuous trace, John's trip may be from John's house to point A, a separate trip from point A to point B, and another separate trip from point B to John's office. Chunking may also remove or obscure start points, endpoints, or otherwise break telemetry data into any size. Filtering may remove inconsistent or irregular data, delete traces or trips that lack sufficient data points, or exclude any type or portion of data for any reason. Once processed, aggregated telemetry data140may be stored in association with one or more tiles related to electronic map data130. Aggregated telemetry data140may be stored for any amount of time, such as a day, a week, or more. Aggregated telemetry data140may be further processed or used by various applications or functions as needed.

In one embodiment, mobile computing device145is any mobile computing devices, such as a laptop computer, hand-held computer, wearable computer, cellular or mobile phone, portable digital assistant (PDAs), or tablet computer. Although a single mobile computing device is depicted inFIG. 1, any number of mobile computing devices may be present. Each mobile computing device145is communicatively connected to server computer105through wireless network connection165which comprises any combination of a LAN, a WAN, one or more internetworks such as the public Internet, a cellular network, or a company network.

Mobile computing device145is communicatively coupled to GPS satellite160using GPS transceiver150. GPS transceiver150is a transceiver used by mobile computing device145to receive signals from GPS satellite160, which broadly represents three or more satellites from which the mobile computing device may receive signals for resolution into a latitude-longitude position via triangulation calculations.

Mobile computing device145also includes wireless network interface159which is used by the mobile computing device to communicate wirelessly with other devices. In particular, wireless network interface159is used to establish wireless network connection165to server computer105. Wireless network interface159may use Wi-Fi, WiMAX, Bluetooth, ZigBee, cellular standards or others.

Mobile computing device145also includes other hardware elements, such as one or more input devices, memory, processors, and the like, which are not depicted inFIG. 1. Mobile computing device145also includes applications, software, and other executable instructions to facilitate various aspects of embodiments described herein. These applications, software, and other executable instructions may be installed by a user, owner, manufacturer, or other entity related to the mobile computing device. In one embodiment, mobile computing device145includes client map application155which is software that displays, uses, supports, or otherwise provides electronic mapping functionality as part of the application or software. Client map application155may be any type of application, such as a taxi service, a video game, a chat client, a food delivery application, etc. In an embodiment, client map application155obtains electronic mapping functions through SDK157, which may implement functional calls, callbacks, methods or other programmatic means for contacting the server computer to obtain digital map tiles, layer data, or other data that can form the basis of visually rendering a map as part of the application. In general, SDK157is a software development kit that allows developers to implement electronic mapping without having to design all of the components from scratch. For example, SDK157may be downloaded from the Internet by developers, and subsequently incorporated into an application which is later used by individual users.

In server computer105, the mapping application110provides the API112that may be accessed, for example, by client map application155using SDK157to provide electronic mapping to client map application155. Specifically, mapping application110comprises program instructions that are programmed or configured to perform a variety of backend functions needed for electronic mapping including, but not limited to: sending electronic map data to mobile computing devices, receiving telemetry data135from mobile computing devices, processing telemetry data to generate aggregated telemetry data140, receiving electronic map source data125from data providers, processing electronic map source data125to generate electronic map data130, and any other aspects of embodiments described herein. Mapping application110includes vector tile generator115, which is programmed or configured to generate the electronic map data130based on the electronic map source data125. In an embodiment, the mapping application110may also reside in the mobile computing device145.

Hardware Implementation

FIG. 2is a block diagram that illustrates a computer system200upon which an embodiment of the invention may be implemented. Computer system200includes a bus202or another communication mechanism for communicating information, and a hardware processor204coupled with bus202for processing information. Hardware processor204may be, for example, a general purpose microprocessor.

Computer system200also includes a main memory206, such as a random access memory (RAM) or another dynamic storage device, coupled to bus202for storing information and instructions to be executed by processor204. Main memory206also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor204. Such instructions, when stored in non-transitory storage media accessible to processor204, render computer system200into a special-purpose machine that is customized to perform the operations specified in the instructions.

Computer system200further includes a read-only memory (ROM)208or other static storage device coupled to bus202for storing static information and instructions for processor204. A storage device210, such as a magnetic disk or optical disk, is provided and coupled to bus202for storing information and instructions.

Computer system200may be coupled via bus202to a display212, such as an LCD screen, LED screen, or touch screen, for displaying information to a computer user. An input device214, which may include alphanumeric and other keys, buttons, a mouse, a touchscreen, or other input elements is coupled to bus202for communicating information and command selections to processor204. In some embodiments, the computer system200may also include a cursor control216, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor204and for controlling cursor movement on display212. The cursor control216typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

Computer system200may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and program logic which in combination with the computer system causes or programs computer system200to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system200in response to processor204executing one or more sequences of one or more instructions contained in main memory206. Such instructions may be read into main memory206from another storage medium, such as storage device210. Execution of the sequences of instructions contained in main memory206causes processor204to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

The term “storage media” as used herein refers to any non-transitory media that store data and instructions that cause a machine to operation in a specific fashion. Such storage media may comprise non-volatile media and volatile media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device210. Volatile media includes dynamic memory, such as main memory206. Common forms of storage media include, for example, a floppy disk, a flexible disk, hard disk, solid state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, NVRAM, any other memory chip or cartridge. In one embodiment, a memory (e.g., main memory206and ROM208) in the computer system200may include a non-transitory computer readable storage medium configured to store program code. The program code includes instructions that, when executed by a processor, cause the processor to perform various methods and processes described herein.

Storage media is distinct from but may be used in conjunction with transmission media. Transmission media participates in transferring information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus202. Transmission media can also take the form of acoustic, radio, or light waves, such as those generated during radio-wave and infra-red data communications, such as WI-FI, 3G, 4G, BLUETOOTH, or wireless communications following any other wireless networking standard.

Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor204for execution. For example, the instructions may initially be carried on a magnetic disk or solid state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system200can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus202. Bus202carries the data to main memory206, from which processor204retrieves and executes the instructions. The instructions received by main memory206may optionally be stored on storage device210either before or after execution by processor204.

Computer system200also includes a communication interface218coupled to bus202. Communication interface218provides a two-way data communication coupling to a network link220that is connected to a local network222. For example, communication interface218may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface218may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface218sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link220typically provides data communication through one or more networks to other data devices. For example, network link220may provide a connection through local network222to a host computer224or to data equipment operated by an Internet Service Provider (ISP)226. ISP226, in turn, provides data communication services through the world wide packet data communication network now commonly referred to as the “Internet”228. Local network222and Internet228both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link220and through communication interface218, which carry the digital data to and from computer system200, are example forms of transmission media.

Computer system200can send messages and receive data, including program code, through the network(s), network link220and communication interface218. In the Internet example, a server230might transmit a requested code for an application program through Internet228, ISP226, local network222and communication interface218. The received code may be executed by processor204as it is received and be stored in storage device210, or other non-volatile storage for later execution.

Vector Tile Generator

FIG. 3is a block diagram illustrating the vector tile generator115, in accordance with an embodiment. The vector tile generator115includes a feature mapper310, a zoom level mapper320, a tile mapper330, a tile encoder340, a tile data merger350, and a properties store360that cooperate to generate vector tiles based on raw map data305, such as the electronic map source data125. Different and/or additional components may be included in the vector tile generator115, but those components are not shown inFIG. 3. Further, multiple components shown inFIG. 3may be combined into single components.

The vector tile generator115is used to generate electronic map data for maps that can be displayed in a graphical user interface, e.g., an interface of a routing application. Electronic map data are data that describe the territories, locations, coordinates, geometries, sizes, contours, elevations of objects (e.g., roads, buildings, etc.) and metadata that label the objects in the map and provide additional information to the map. Electronic map data may be arranged in the form of tiles. Tiles are building blocks of an electronic map. Electronic maps can be displayed at different zoom levels. A tile may be associated with a particular zoom level. When the zoom level of the map changes, different tiles are used to construct the map. For example, when a user chooses to zoom an electronic map from a less zoomed level to a more zoomed level, tiles corresponding to larger areas are replaced by tiles corresponding to smaller areas to construct a more zoomed-in map.

The vector tile generator115generates electronic map data in the form of vector tiles. Vectors are collections of mathematical values and directions that define geometries, road outlines, and other properties of an electronic map. Each tile may include multiple vectors that define the objects (e.g. roads, buildings, etc.) in the geographical location associated with the tile. In one embodiment, when a user specifies a location and a zoom level in the client map application115, the mapping application110requests and receives electronic map data130that includes one or more vector tiles generated by the vector tile generator115. The mapping application110then renders a map for display in a graphical user interface based on the retrieved vector tiles. When the user selects a different location and/or a different zoom level, different sets of vector tiles are transmitted to the mobile computing device145to construct different maps for display in the graphical user interface. For example, if a user zooms in, the mapping application110displays a map made up of tiles each showing a smaller area in more detail, and if a user zooms out, the mapping application110displays a map made up of tiles each showing a larger area in less detail. As another example, if the user pans to a different location at the same zoom level, the mapping application110displays a map made up of tiles each showing a different region from a previously-displayed region. If the new region partially overlaps with a previously-displayed region, the mapping application110reuses some of the previously-displayed tiles to display the new region.

To generate the vector tiles, the vector tile generator115retrieves data describing various map features from the raw map data305. The raw map data305is a database of raw digital map data, such as some or all of the electronic map source data125. The raw map data305includes data describing geometry of the features and properties of the features. Geometry data includes data related to the location, shape, and size of the spatial features, e.g., position, shape, width, length, elevation, etc. For example, for a road, the geometry data describes the path of the road and the width of the road. Some features may be represented using polygons, while other features may be represented as lines, joined line segments, points, or other geometric shapes. The vector tile generator115primarily operates on the geometry data to generate the geometries within each vector tile. Property data includes data that may not be relevant to the location, shape, and size of the spatial features, and that is not used to generate the geometries within the vector tiles. For example, property data for the road may include the name of the road, the roadway classification, the speed limit, the direction of travel, and other types of information describing the road that is potentially used or displayed by the mapping application110or client map application115, but that does not relate to the road geometry. In some embodiments, property data includes data that describes the shape or size of spatial features, but is not used in generating the vector geometries. For example, a height of a building, or a number of lanes in a roadway, describes sizes of these features, but this data may be classified as property data if it not used to generate vector tile geometries.

The feature mapper310receives data from the database of raw map data305. The feature mapper310identifies the features described by the raw map data305and separates the data for each identified feature into property data355and geometry data315. The feature mapper310passes the property data355to a property store360, which temporarily stores the property data355. The feature mapper310passes the geometry data315to the zoom level mapper320. The property data355and geometry data315are each identified by feature (e.g., using a feature identifier) so the property data for each feature can be rejoined with the geometry data315for the corresponding feature after the geometry data has been processed. The feature mapper310may assign feature identifiers to the various features, or the raw map data305may include feature identifiers.

The zoom level mapper320maps the geometry data315to multiple zoom levels. The zoom level mapper320generates multiple sets of feature data, one for each zoom level. The zoom level mapper320scales and simplifies the geometry data315based on the zoom level. Each zoom level includes at least a subset of the features represented by the geometry data315. The zoom levels include different levels of detail, and some zoom levels include more features than others. For example, a higher level of zoom (more zoomed in) includes a greater number of features and/or greater levels of geometric data for the features than a lower level of zoom (less zoomed in). The sets of modified geometry feature data for the multiple zoom levels are referred to jointly as zoom data325. The zoom level mapper320outputs the zoom data325to the tile mapper330. In some embodiments, the zoom level mapper320may store the zoom data325in a zoom data store for use later in the vector tile generation process. The zoom level mapper320can operate on multiple zoom levels in parallel. In particular, the zoom level mapper320can generate the zoom data325for each zoom level independently and in parallel, because each zoom level is generated based on the raw geometry data315.

As an example, for map data for the state of Maine, the zoom data325for a given zoom level includes various cities, such as Portland, Bangor, Augusta, and Bar Harbor, and major roads, such as I-95 and I-295, and a simplified outline of the coastline. At a higher zoom level, the zoom data325includes additional cities, such as Brunswick, Lewiston, and Waterville, smaller roads, and a more detailed coastline. The zoom level mapper320simplifies certain features, like the coastline and roadway curvature details, based on the zoom level. In addition, the zoom level mapper320selects features for a zoom level based on relative sizes, relative importance, or other factors. For example, for the lower zoom level, the zoom level mapper320may select to include Augusta but not Waterville because Augusta is the state capital, even though Waterville has a slightly larger population. As another example, the zoom level mapper320selects major interstates and larger state highways for the lower zoom level, and also selects smaller state highways at the higher zoom level. In some embodiments, the zoom level mapper320may retrieve property data355stored in the property store360and select features based on the property data355. In other embodiments, data that the zoom level mapper320uses to select features for different zoom levels, such as capital city designations, roadway designations, etc., is included in the geometry data315.

The tile mapper330receives the zoom data325from the zoom level mapper320and maps the features for each zoom level to tiles for each zoom level. At each zoom level, the tile mapper330divides the map into a set of tiles, and identifies the features that fall within each tile. This process involves laying a grid over the zoom data325for each zoom level, with the tiles corresponding to smaller areas at higher zoom levels, and the tiles corresponding to larger areas at lower zoom levels. The tile mapper330identifies, for each tile, the features that are included, either partially or fully, within the boundary of the tile. The tile mapper330may determine the features for a tile at a given zoom level by comparing the positions of the boundaries of each feature in the zoom level data325to the boundaries of the tile, and determining if any portion of each feature is within the boundaries of the tile. For example, one tile for the map of Maine may include Portland, I-95, and I-295, and another tile includes Bangor and also includes I-95. Because I-95 stretches across the state of Maine, many tiles include I-95. The tile mapper330generates tile data335, which lists, for each tile, a set of the features included in the tile.

The tile mapper330allows for a great deal of parallel processing. The tile mapper330can operate on the zoom data for different zoom levels in parallel, and determines the tile data for each zoom level independently of the other zoom levels, based on the zoom data325for the corresponding zoom level. In some embodiments, the tile mapper330can also operate on different tiles within a zoom level in parallel.

The tile encoder340receives the tile data335from the tile mapper330and clips and encodes the tile data335for each tile. The tile data335indicates the features that are included within each tile, but many features may span across multiple tiles. For each tile, the tile encoder340clips the features that extend beyond the tile to the boundaries of the tile. In some embodiments, the tile encoder340adds a buffer around the tile, and clips the features to the boundaries of the buffer around the tile. For example, the buffer can include an additional 10-25% of the tile width on each side of the tile. Other buffer sizes may be used; for example, the width buffer can be up to 100% of the tile width. To clip the features to the boundaries of the buffer, the tile encoder may compare the boundaries of each feature in a tile to the boundaries of the buffer, identify the portion or portions of the feature that are within the boundaries of the buffer, and retain the geometry data describing the portion or portions of the feature that are within the boundaries of the buffer, while discarding the geometry data for portions of the feature that are outside the boundaries of the buffer. For example, for the tile that includes Bangor and I-95, the tile encoder340determines the geometry of I-95 that falls within the boundaries of the buffer, and retains geometry data that describes the portion of I-95 within the tile or the buffer around the tile. For a given zoom level, each tile that includes I-95 includes the geometry data for distinct, non-overlapping portions of I-95. The buffer areas include overlapping portions; for example, geometry data within portion of a buffer along the right of a first tile is also included in the geometry data for a second tile to the right of the first tile. After determining the final geometry data for each tile, the tile encoder340encodes the geometry data of the tile using a standard vector tile format. The tile mapper330may determine that some tiles do not include any features. For each tile that does not include any features, the tile encoder340may encode a null feature set for the tile. The result of the clipping and encoding process is a data set of encoded tile features345. In some embodiments, a buffer is not used, and the features are clipped to the boundaries of the tiles themselves.

In some embodiments, the tile data335includes the geometry data for the features in each tile. However, because features can appear on multiple tiles, this can result in a large amount of data being passed from the tile mapper330to the tile encoder340(e.g., the feature data for I-95 may be included for each tile that includes some portion of I-95). To reduce the amount of data being passed, the zoom data325that includes the processed geometry data may be temporarily stored in a zoom data store, and the tile data335may include a list of features for each tile, but does not include the processed, zoom level geometry data. In this embodiment, the tile encoder340retrieves the processed geometry data from the zoom data store relevant to each particular tile being clipped and encoded.

As with the zoom level mapper320and the tile mapper330, the tile encoder340also enables a great amount of parallel processing. The tile encoder340can operate on different tiles in different zoom levels, or even within the same zoom level, independently and in parallel. Because the tile data335includes the tile boundaries and a list of features for each tile, the tile encoder340can access the zoom data store, clip the retrieved features, and encode the clipped features for each tile independently of the other zoom tiles.

The tile data merger350receives the encoded tile features345from the tile encoder340and merges the encoded tile features345, which describe the geometry of the features in each tile (and buffer), with the feature property data355, which the tile data merger350retrieves from the property store360. As noted above, the geometry data315and property data355each include feature identifiers for each feature, and the feature identifiers are retained for each feature as the geometry data315is processed by the zoom level mapper320, the tile mapper330, and the tile encoder340. For each feature on each tile, the tile data merger350retrieves the feature identifier, identifies the corresponding property data for the feature based on the feature identifier, and adds the corresponding property data to the encoded tile features. The output of the tile data merger350is a set of vector tiles at each of a set of zoom levels, each tile including both geometry data and property data.

While the vector tile generator115has been described as generating a set of vector tiles, in other embodiments, a tile generator can use a similar process to generate map tiles in different formats. For example, the tile encoder340can encode the clipped features as image data rather than vector data, and the tile data merger350outputs image tiles rather than vector tiles. As another example, the vector tile generator115can generate tiles for direction or search data, such as a road network graph or geocoding points. This vector tile generator115can operate on the direction or search data alone, or can bundle this data with vector data.

Example Vector Tile Generation Process

FIGS. 4-8each show portions of a visual illustration of a vector tile generation process performed by the vector tile generator115.FIG. 4is an illustration of a portion of raw geometry data400, in accordance with an embodiment. The geometry data400shows the full level of detail available for each feature on the map portion. In the map portion shown inFIG. 4, the geometry data400includes several major roads410and minor roads420. As shown, the minor roads420are narrower than the major roads410. The geometry data400also includes two large buildings430, five small buildings440, and a lake450. The large buildings430are connected by driveways to one of the major roads410. The geometry data400describing these features410-450is provided to the vector tile generator115to generate vector tiles based on the geometry data. The feature mapper310may identify the various features included in the geometry data400, and store corresponding property data in the property store360, as discussed with respect toFIG. 3.

FIG. 5is an illustration of the portion of geometry data at a first zoom level500, in accordance with an embodiment. The first zoom level500is an example of one of the zoom levels generated by the zoom level mapper320based on the geometry data400. The first zoom level500is a relatively low level of zoom. As shown, the zoom level mapper320has scaled down the feature sizes relative to the feature sizes depicted in the raw geometry data400. In addition, the zoom level mapper320has removed multiple smaller features—the minor roads420, and both the large and small buildings430and440—to simplify the map for the lower zoom level.

FIG. 6is an illustration of the portion of geometry data at a second zoom level600with an overlaid set of tiles610-640, in accordance with an embodiment. The second zoom level600is an example of another one of the zoom levels generated by the zoom level mapper based on the geometry data400. The second zoom level600is a higher level of zoom than the first zoom level500. As shown, the zoom level mapper320have removed several smaller features—the small buildings440, and the driveways connecting the large buildings430to the road—to simplify the map. The zoom level mapper320has also slightly scaled down the feature sizes relative to the feature sizes depicted in the raw geometry data400.

Four full tiles are shown overlaid over the portion of geometry data at the second zoom level600. Zoom level2, tile A610includes most of the upper left quadrant of the portion of geometry data shown inFIG. 6. Zoom level2, tile B620includes most of the upper right quadrant; zoom level2, tile C630includes most of the lower left quadrant; and zoom level2, tile D640includes most of the lower right quadrant. Along the sides of these four tiles, additional tiles, partially shown inFIG. 6, encompass other portions of the geometry data600. The partially-shown tiles also may include geometry data outside the geometry data shown inFIG. 6. The tile mapper330overlays the tiles610-640over the geometry data for the second zoom level600.

FIG. 7is an illustration of features for a particular tile610and a buffer for the tile at the second zoom level, in accordance with an embodiment. A tile boundary710shows the boundary of Tile A610. Tile A610is surrounded by a buffer720, which is bounded by a buffer boundary730. The buffer720includes a portion of geometry data outside the tile boundary710.FIG. 7shows all of the features that are included in Tile A610and the buffer boundary720at zoom level2. As shown, portions of both major roads410, portions of two of the minor roads420, and a portion of the lake450are included within the buffer boundary730, and thus are included in the tile data for Tile A610. The large buildings430and one of the minor roads420do not fall within the buffer boundary730, so these features are not included in the tile data for Tile A610. The tile mapper330identifies the features that are partially or fully inside the buffer boundary730and associates them with Tile A610. In other embodiments, the tile mapper330identifies the features within the tile boundary710and associates them with Tile A610. In such embodiments, if a feature is included within the buffer boundary730, but not the tile boundary710, this feature is not associated with Tile A610. The tile mapper330passes the tile data listing the features included in Tile A610(or inside the buffer boundary730) to the tile encoder340.

FIG. 8is an illustration of clipped features for a particular tile at the second zoom level, in accordance with an embodiment. The tile encoder340clips the features included in Tile A, i.e., the two major roads410, the two minor roads420, and the lake450, to the buffer boundary730to generate the clipped tile A810shown inFIG. 8. The other portions of these features are included in other tiles. For example, as shown inFIG. 6, the lake450spans all four tiles610-640, so the other tiles620,630, and640each include different portions of the lake450. The tile encoder340encodes the clipped features, as described with respect toFIG. 3.