HK1121625B - Bitmap array for optimally distributing map data content to wireless communications devices - Google Patents

Description

Bitmap array for optimal distribution of map data content to wireless communication devices

Technical Field

The present disclosure relates generally to wireless communication devices, and in particular, to techniques for distributing map content to wireless communication devices.

Background

Such as the short news companySuch wireless communication devices enable users to access network-based data sources (e.g., BlackBerry Maps)^TMOr Google Maps^TM) And downloading the map content. In BlackBerry Maps^TMIn the case of (2), the map data is in a vector format, which means that valleys, lakes, oceans, islands, continents, etc. are represented by polygons, and highways, streets, roads, etc. are represented by broken lines. Mathematically, polygons and polylines are sets of coordinate points (points defined in terms of latitude and longitude).

When a user wants to view a map on his or her wireless communication device, the user selects a place or area of interest (AOI) by triggering a request to the map server, through the client device, for map data corresponding to the particular area or place requested by the user. The server retrieves map data and sends the map data back to the client device to enable the device to dynamically render a map using the received map data. In BlackBerry Maps^TMIn the context of (2), the server first replies with an index of all available map data for the area of interest (AOI), which enables the device to select only those aspects of its required map data, thus saving wireless bandwidth. Despite the use of this indexing technique for reducing over-the-air data transfer, the amount of data transferred for an area of interest remains very large. Specifically, when a user requests a map of a high zoom level (e.g., 10km × 10km or more), it is assumed that a low or the like is being soughtLevel of detail, then the amount of vector data being transmitted is excessive, i.e., only a portion of the total map data being transmitted to the wireless device is actually used to render the map. For example, as shown in FIG. 1, the large scale map in the middle North America shows not only five large lakes, but also a myriad of smaller lakes, providing a level of detail that most users do not necessarily require or desire. Downloading all of these "extra" map vector data places an unnecessary burden on the wireless link and does not provide any practical benefit to the user. Similarly, as shown in FIG. 2, a map showing a highway intersection with an entrance, an exit, and a sidewalk may provide excessive detail to a user requesting a map at that zoom level. Furthermore, at this zoom level, the routes may appear to overlap each other, thus confusing the user and causing problems for on-screen marking.

Accordingly, a technique for optimally distributing map data content to wireless communication devices is highly desirable.

Disclosure of Invention

In general, the present technology provides a method for more efficiently distributing map content to wireless communication devices by using a bitmap array to process vector map data at a map server to efficiently analyze polygonal map features (e.g., lakes, islands, valleys, etc.) and/or polyline map features (e.g., highways, streets, roads) to determine whether to retain the features or whether to suppress (suppress) the features (due to being unnecessarily refined features) or to overlap or partially overlap. A bitmap array is generated for a given zoom level, where each bitmap cell of the bitmap array represents a discrete portion of the vector map data. Map features can be efficiently analyzed by computing attributes of the bitmap array. For example, the area of a polygonal map feature may be approximated by summing a plurality of bitmap cells representing the polygonal map feature. If the approximated area is less than the threshold, the polygon map feature is suppressed because it is too small (too much detail). For polyline map features, the features may be prioritized (by importance or size) and the corresponding cells marked for the highest priority polyline. Subsequent fold lines are marked on the array unless the folds coincide with previously marked cells. The unmarked cells and marked cells are counted and their ratio is compared to a threshold to determine if the two polylines overlap or partially overlap. If so, the lower priority polyline is suppressed (or, alternatively, incorporated into the higher priority polyline). Similarly, a buffer may be created next to the polyline(s) to ensure a minimum spacing between adjacent polylines. The overlap and proximity analysis may be applied not only to polylines, but also to polygons, to ensure that polygonal map features do not overlap when rendered, or alternatively, to ensure that polygonal map features are not too close to each other when rendered. Thus, overly granular features of the map that are not useful or necessary at a given zoom level are suppressed, thereby minimizing the total amount of map data transmitted to the wireless communication device. Thus, wireless bandwidth is conserved without unduly sacrificing details of the map content. Parameters such as bitmap size, bitmap resolution, thresholds, and buffer bandwidth may be adjusted to enable a user (of the client device) or a system administrator (of the server side) to adjust the degree of map detail to be provided. Once the vector map data is collapsed (collapse) into a bitmap and a determination is made as to which features to omit (i.e., suppress or remove), the map data associated with the remaining features may be transmitted in vector format, or alternatively, the bitmap itself may be transmitted (in which case the device receives the bitmap collapsed from the vector map data). This process of "data reduction" or "data generalization" can be done in real time (by generating and analyzing bitmaps), but bitmaps can be pre-processed more efficiently for different zoom levels.

Accordingly, one aspect of the present technology is a method for distributing map data from a map server to a wireless communication device. The method comprises the following steps: obtaining vector map data in response to a request for map data received at a map server from a wireless communication device; generating a bitmap array representing vector map data for a zoom level specified in the request; calculating attributes of the bitmap array to determine which map features to retain and which map features to suppress; and transmits only map data for the map features to be retained to the wireless communication device.

Another aspect of the present technology is a computer program product comprising code adapted to perform the above-mentioned method steps when said computer program product is loaded into a memory and executed on a processor of a wireless communication device.

Another aspect of the technology is a map server for distributing map data to a wireless communication device. The server having a data port for receiving a request for map data from a wireless communication device; and a processor coupled to the memory for processing the request and obtaining vector map data in response to the request for map data, generating a bitmap array representing the vector map data for a zoom level specified in the request, calculating attributes of the bitmap array to determine which map features to retain and which map features to suppress, and transmitting only the map data for the map features to retain to the wireless communication device through the data port.

Another aspect of the technology is a wireless communication device having: an input device for enabling a user to request map data; a processor coupled to the memory for transmitting the request to the map server; and a display for displaying a map rendered from map data received from the map server, the map server transmitting only map data associated with map features to be retained after processing the map data using a bitmap array from which attribute data of the map features are calculated to determine whether to retain or omit the map features.

Another aspect of the present technology is a method for processing vector map data in a map server, the method comprising the steps of: generating a bitmap array of vector map data representing a particular location specified in a request for map data received by a map server; calculating attributes of the bitmap array to determine which map features to retain and which map features to omit; and enables transmission of only map data for map features to be retained to the wireless communication device.

Drawings

Other features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings, in which:

FIG. 1 is a screen shot showing a large scale (scale) map in the middle North America that provides an undesirable high level of detail typical of most current drawing applications;

FIG. 2 is a screen shot of a highway intersection that also provides an undesirably high level of detail that results in overlapping and partially overlapping roads;

FIG. 3 is a block diagram of key components of a wireless communication system for implementing the present technology;

FIG. 4 is a flowchart outlining the method steps for distributing map content to wireless communication devices in accordance with the present technique, wherein bitmaps are processed in real time;

FIG. 5 is a flowchart outlining method steps for distributing map content to wireless communication devices in accordance with the present technique, wherein bitmaps are preprocessed;

FIG. 6 is a screen shot of the same portion of the middle North America presented in FIG. 1, but with the simplified map content with all small lakes omitted;

FIG. 7 is a screenshot of the same intersection presented in FIG. 2, but with simplified map content with overlapping or partially overlapping roads suppressed;

FIG. 8 depicts a bitmap array generated by folding vector map data showing maps of three differently sized lakes;

FIG. 9 depicts a bitmap array generated by folding vector map data for a map with streets overlapping a highway;

FIG. 10 depicts a bitmap array generated using a buffer unit to ensure that roads (or other line drawing features) are not too close to each other;

FIG. 11 is a screen shot of a large scale map of Paris that provides an undesirable high level of detail described by most current drawing applications;

FIG. 12 is a screen shot of a large scale map of Paris after processing map data in accordance with the present technique;

fig. 13A is a system block diagram of a network component providing mapping functionality for a wireless communication device;

FIG. 13B illustrates a message exchange between a mobile communication device and a map server for downloading map content to the mobile communication device based on the system of FIG. 13A; and

fig. 13C is a diagram showing a Maplet data structure according to an exemplary embodiment using an embodiment of the present technology.

It should be noted that throughout the drawings, like features are identified with like reference numerals.

Detailed Description

The details and features of these aspects of the present technology are described in detail below by way of example with reference to the accompanying drawings.

Fig. 3 is a block diagram of key components of a wireless communication system for implementing the present technology. It should be clearly understood that this figure is intended to be simplified and only shows certain components; of course, each of the system, map server and wireless communication device includes other components than those shown in fig. 3.

As shown in fig. 3, the system includes a wireless communication device 100, the wireless communication device 100 having a microprocessor 102 (or simply "processor") for interacting with memory in the form of RAM 104 and flash memory 106, as is well known in the art. The device 100 includes an RF (radio frequency) transceiver 108 for wireless communication with one or more base stations 200. The device 100 may optionally include a GPS (global positioning system) receiver chipset 110 for receiving GPS radio signals transmitted from one or more orbiting GPS satellites 300. In terms of an input/output device or User Interface (UI), device 100 typically includes a display 112 (e.g., a small LCD screen), a thumbwheel and/or trackball 114, a keyboard or keypad 116, a USB 118 or serial port for connection to a peripheral device, a speaker 120, and a microphone 122. The processor and memory thus enable drawing applications (e.g., BlackBerry Maps)^TM) Can run on a wireless device enabling the user of the device to download and view map content from a map server 220 over the internet 210. Similarly, the processor and memory may enable other Location Based Services (LBS) applications to run on the device, such as split segment navigation. Speaker 120, microphone 122, and RF transceiver circuitry 108 form part of a voice communication subsystem that enables cellular communications.

Fig. 4 is a flowchart summarizing the method steps performed in real-time at the map server 220 for distributing map content to one or more wireless communication devices, in accordance with the present technique. As shown in fig. 4, an initial step 400 includes receiving a request for map data from a wireless communication device. In response to the request, vector map data for the area of interest (AOI) is obtained (step 402). The vector map data is obtained from the map server's own database or from other connected map servers or databases. At step 404, the map server generates a bitmap array representing vector map data for the zoom level specified in the request. At step 406, the map server computes attributes of the bitmap array to determine (at step 408) which map features to retain and which map features to suppress. At step 410, the map server determines whether to transmit the data to the wireless communication device in vector format or as a bitmap. At step 412, the map server 220 transmits only map data for the map feature to be retained to the wireless communication device if it is determined to transmit in vector format. Alternatively, the map server may simply transmit the bitmap itself to the wireless communication device at step 414.

FIG. 5 is a flowchart outlining another method step for distributing map content to one or more wireless communication devices in accordance with the present technique in which all or a portion of the map data is pre-processed at the map server according to different zoom levels. Upon receiving a request for map data (step 500), the map server determines if pre-processed data exists for a given AOI and zoom (step 502). If not, the map server generates a bitmap and performs data reduction calculations in real time according to the flowchart of FIG. 4 (step 504). If so, the map server obtains pre-processed data for the given AOI and zoom (step 506). The map server determines whether to transmit the data in vector format or as a bitmap (step 510), and then transmits it in vector format (step 512) or as a bitmap (step 514). Optionally, the bitmap may be reconverted back to vector format to further simplify or generalize the data. For example, depending on the nature of the map feature, the reconversion back to vector format may have the effect of smoothing the convoluted road or eliminating jagged edges of the polygon. However, in each of these cases, the data transmitted by the map server to the client device is less than that conventionally sent over the air, thereby conserving over-the-air bandwidth.

The above-described method steps may be embodied in coded instructions in a computer program product. In other words, the computer program product is a computer readable medium having recorded thereon software code for performing the above steps when loaded into a memory and running on a microprocessor of a wireless communication device.

FIG. 6 is a screen shot of the same portion of the middle North America presented in FIG. 1, but with simplified map content suppressing all small lakes, thus reducing the amount of data transmitted over the air. By comparing fig. 6 with fig. 1, the level of refinement is significantly reduced (small lakes are removed or suppressed), but still has utility to the user given the large scale of the map.

FIG. 7 is a screen shot of the same intersection (exchange) presented in FIG. 2, but with simplified map content with overlapping or partially overlapping roads suppressed. Again, not only is the amount of data reduced, but the map actually has the same utility to the user (utility will be greater as overlapping routes will confuse the user and will cause problems for on-screen markings).

Further implementation details for generating bitmap arrays and computing attributes of polygonal map features (e.g., lakes, valleys, islands, continents, etc.) and/or polygonal map features (highways, streets, or other types of highways or railways) are described below.

For polygons, fig. 8 schematically depicts a bitmap array generated from map 600 (actual bounding box or AOI) vector map data showing three lakes (a big lake 602 and two small lakes 604 and 606). Typically, using conventional mapping techniques, vector map data for all three lakes will be transmitted over the air to the client device, thus burdening the wireless link even when a level of refinement at that particular zoom level is unnecessary or undesirable. According to the techniques presented herein, the map server "prunes" (or simplifies the vector map data by generating an array of bitmaps 610 that represent AOIs or bounding boxes. Bitmap array 610 is an m n two-dimensional array (i.e., m columns and n rows) of bitmap cells 612. In one example, if processed dynamically, the size of the bitmap array (or "bitmap board") will match the size of the bounding box or screen. The magnification factor (or reduction ratio) is defined in terms of the resolution or granularity sought. Bitmap size m is equal to longitude (right minus left in degrees) multiplied by the factor, and n is equal to latitude (top minus bottom in degrees) multiplied by the factor. For example, if one wants to represent a bitmap cell of 1 meter by 1 meter of ground square (at the equator), the magnification factor would be approximately 90,000. The size of the bitmap board (bitmap array) that represents the world map using this resolution would be 32,400,000 times 16,200,000.

As shown in fig. 8, the conversion from vector format to bitmap format effectively discretizes vector map data, providing an efficient way to compute attributes of polygonal map features such as lakes as shown in the figure. Thus, if data reduction requires suppression of lakes that are too small and thus may be insignificant at this zoom level, the lake regions in the bitmap representation can be approximated by simply counting the total number of bitmap cells representing the lake. For example, lake 606 is represented by 9 cells, while lake 604 is represented by 14 cells. In contrast, lake 602 has 86 cells. Thus, if the polygon area threshold is set to 20, then lakes 604 and 606 would be suppressed because they are relatively too small at that zoom level, while lake 602 would be retained because it is large enough. Thus, the map server will only transmit map data corresponding to lake 602 and remove or suppress map data corresponding to lakes 604 and 606. Bitmap size, bitmap resolution, and thresholds are parameters that can be adjusted to achieve a desired level of map detail.

With respect to polylines, FIG. 9 schematically depicts a map (or bounding box) 600 that, using conventional drawing tools, generally transmits and presents map data for more map details than are reasonably necessary or desired by the user at that particular zoom level. In this particular example, the map contains vector map data for presenting a first route "highway 1" represented by reference numeral 620, a second route "sidewalk 2" (which is a smaller route than the highway) represented by reference numeral second 622, and a third route "highway 2" represented by reference numeral 630. By generating a bitmap 610 having 6 columns and 4 rows of bitmap cells 612 (by way of example only), the vector map data is discretized and folded (collapse) into a bitmap format. In so doing, the primary route is marked on the array by marking the cells corresponding to the vector map data for the primary (high priority) route.

As shown in fig. 9, the marked cells 614 are gray in this figure, as was done in the previous figures. The bitmap array is shown at a much lower resolution than the bitmap array shown in the previous figures to illustrate that the resolution (granularity) of the bitmap array 610 (or bitmap panel) can vary. In the example shown in fig. 9, the granularity is larger (lower resolution) and thus more data may be discarded or suppressed than if the granularity was smaller (higher resolution).

In any case, these primary routes (freeway 1 and freeway 2) are "drawn" on the array by first marking the cells that represent the discretized primary routes. The map server will then attempt to "draw" or mark a smaller route (lower priority street) on the array (in this example, the sidewalk 622), but the cell corresponding to the sidewalk 622 in the bitmap array has been occupied by the high priority highway 1 (620). Thus, the detour 622 is considered to overlap the higher priority route and thus will be discarded or suppressed at the zoom level because even though bandwidth and processing resources are expended to transmit and present data for the smaller route, once presented on the screen, will overlap or partially overlap the highway 1, which is an aesthetically undesirable result and may also cause marking problems or may be annoying to the user when reviewing the map.

At least two things should be done in determining whether one polyline map feature (e.g., a route) overlaps or partially overlaps another polyline map feature. First, polylines should be prioritized such that higher priority (i.e., more important) polylines are marked first, so that lower priority polylines (e.g., less important routes) are easily suppressed and there are no other roads around. Prioritizing polylines, such as routes, may be accomplished according to one or more of a number of factors including: route categories (interstate highways, regional roads, streets, etc.), importance levels of the route (which may be predetermined subjectively or objectively and stored as metadata), speed limits associated with the route, and length of the route.

Second, once priorities are established for the polyline map features, the following methods may be used to determine whether any polyline map features are to be suppressed or deleted: first, as described above, bitmap cells corresponding to the first polyline map feature (high-priority feature) are marked in the bitmap array. Second, as described above, the bitmap cells corresponding to the second polyline map feature (of slightly lower priority) are marked in the bitmap array (assuming that the bitmap cells to be marked for the second polyline map feature do not coincide with the bitmap cells already marked for the first polyline map feature), thus providing a count of marked and unmarked cells of the second polyline map feature relative to the first polyline map feature. Once the count of marked and unmarked cells is complete, the map server compares the ratio of marked cells to unmarked cells to a threshold to determine whether the second polyline map feature is considered to overlap (or partially overlap) with the first polyline map feature. The threshold is also a parameter that can be adjusted to provide a variable degree of differentiation between adjacent routes or other polyline map features. An alternative technique for determining whether two features overlap is to calculate the ratio of marked cells to the total number of cells needed to render a map feature. It should also be noted that these techniques for determining whether a polyline map feature overlaps or partially overlaps another polyline map feature may also be used to determine whether a polygon map feature overlaps or partially overlaps another polygon map feature.

FIG. 10 depicts a bitmap array 610 generated using a buffer unit 650 to ensure that routes (or other polyline map features) are not too close to each other. In the example presented in FIG. 10, the map 600 would typically be presented using conventional mapping techniques, with a first route "main street" represented by reference numeral 640 being adjacent to another route "fifth street" represented by numeral 642. However, using conventional techniques, it often results in the route or other polyline being presented too close to one another in a manner that is aesthetically unappealing and can also be confusing. Using the present technology, the map server may also generate the bitmap array 610 by defining buffer cells 650 corresponding to buffers 645 on each side of the main street (640) along the high priority route, thereby ensuring that no other streets (e.g., the fifth major street) are present within the buffer area, i.e., not too close to the main street. In this example, the fifth major track (642) is within buffer 645. In bitmap array 610, a conflict is detected 660 when the map server attempts to mark the cell corresponding to the fifth major lane, but "finds" that some of these cells have been marked as buffer cells 650. If the ratio of conflicts (unmarked cells) to marked cells exceeds a predetermined threshold, the route or other polyline map features will be suppressed or removed. The threshold is a parameter that can be adjusted by a user (client side) or by a system administrator (server side). Similarly, buffer width is another parameter that can be adjusted to adjust the degree of map refinement to be provided. The buffering technique can thus be summarized as follows: first, the map server marks the bitmap cell corresponding to the first polyline map feature in the bitmap array, while also marking adjacent bitmap cells to define a buffer immediately adjacent to the buffer cell on each side of the bitmap cell corresponding to the first polyline map feature. The number of adjacent cells marked is a function of the array granularity and the desired width of the buffer. Although a uniform width buffer is preferred, in certain cases it is useful to define a buffer of non-uniform width. For example, the buffer may be thickened at the polyline midpoint to provide sufficient screen space for marking polyline features. Once the first polyline is marked on the array, the map server marks bitmap cells on the bitmap array corresponding to the second polyline map features (assuming that the bitmap cells to be marked for the second polyline map features do not coincide with bitmap cells already marked for the first polyline map features, or do not coincide with buffer cells for the first polyline map features), thus providing a count of the second polyline map features relative to the first polyline features and marked and unmarked cells of its buffer. The map server then compares the ratio of marked cells to unmarked cells to a threshold to determine whether the second polyline map feature overlaps or is too close to the first polyline map feature. As a result of this process, the map server removes data corresponding to polyline map features that would overlap or be too close to other polylines. Collapsing the rich vector map data into a simplified bitmap removes extraneous detail without sacrificing map readability to a greater extent. In other words, at high zoom levels, minute map details or map content, which are generally considered insignificant, are removed or suppressed, thereby enabling efficient transmission of data to the wireless communication device, thus conserving wireless bandwidth. This is further illustrated, again by way of example, with reference to fig. 11 and 12, both of which show large scale maps of paris. In fig. 11, a map is presented according to conventional mapping techniques. In fig. 12, a map is presented after map data has been processed in accordance with the present technique, with unnecessary refined map features removed or suppressed.

The above techniques may be used at any zoom level, but are typically applied to large scale AOI systems (e.g., 10km by 10km) where small map details are typically irrelevant to the device user. The map data may be greatly simplified by filtering out small area polygons and/or folding/reducing multiple polylines into a single polyline. As previously described, this data reduction (or data generalization) may be done in real-time, or the data may be pre-processed for various different zoom levels. The data may be pre-processed for a group of zoom levels (e.g., zoom levels 1-4, zoom levels 5-8, etc.) or for each individual zoom level. Whether the data is pre-processed or processed in real-time, the map server may transmit the folded vector data or the generated bitmap, depending on the system configuration and/or the preferences of the wireless device user.

Fig. 13A is a system block diagram of network components that provide mapping functionality in the wireless communication device 100. To implement the network component, a mapping application is also provided in the memory of the wireless communication device for presenting a visual map on the display. The wireless communication device 100 is connected to a mobile operator network 303 (via a base station 200) for communication with a relay station 307 through a firewall 305. A request for map data is received at the relay station 307 from any of the wireless communication devices 100 and is passed through the firewall 311 to the corporate enterprise server 313 and the corporate Mobile Data System (MDS) server 315 via the secure channel 309. The request is then passed via the firewall 317 to a public map server and/or to a server 321 of a public Location Based Service (LBS), the server 321 serving to provide the Location Based Service (LBS) to handle the request. The network may comprise a plurality of such map servers and/or LBS servers, wherein the requests are distributed and processed by the load distribution server. The map/LBS data may be stored in a network database 322 on the network server 321, or may be stored on a separate map server and/or LBS server (not shown). Private corporate data stored on the corporate map/LBS server 325 may be added to the public data through the corporate MDS server 315 on the secure return path to the wireless device 100. Alternatively, the request from the wireless device 100 may be passed to the common MDS server 327 via the relay station 307 without providing a corporate server, the common LDS server 327 sending the request to the common map/LBS server 321, the common map/LBS server 321 providing map data or other local based services in response to the request. For greater clarity, it should be understood that the wireless device may obtain map data from a "pure" map server that does not provide location-based services, from an LBS server that provides location-based services in addition to map content, or from a combination of servers that provide map content and LBS.

A Maplet data structure is provided that contains all of the graphics and markup content associated with a geographic area, e.g., a map feature such as a restaurant (point feature), street (line feature), or lake (polygon feature). Maplets are constructed in the data entry (DEntry) Layer identified by "Layer ID" to enable data from different sources to be deployed to the device and to be mutually coordinated (shared) for appropriate presentation. Each DEntry represents one or more artifacts (artifacts) or markers (or a combination of both) and includes coordinate information (also referred to as a "bounding box" or "bounding region") that identifies the area covered by the DEntry and a plurality of data points that collectively represent the artifacts, features, or markers. For example, a DEntry may be used to represent a street (or streets) on a city map, where bad (carious) points within the DEntry are divided into different portions representing various portions of an artifact or map feature (e.g., a portion of a street). The wireless device may issue a request to the map server to download only those dentries that are included within a particular area or bounding box representing the area of interest, which may be represented by, for example, a bottom left and top right coordinate pair.

As shown in fig. 13B, the wireless communication device issues one or more AOI (area of interest) requests, DEntry or data requests, and Maplet index requests to the map server for selectively downloading map data based on the user context. Thus, rather than transmitting the entire map data for an area in response to each request from a device, which would burden the wireless link, a local cache is used in conjunction with context filtering of the map data on the server. For example, if the user's wireless device supports GPS and the user is traveling on a car along a highway at 120km/h, contextual filtering may be employed to prevent the downloading of map data related to passing side lanes. Alternatively, if the user is traveling in an airplane that is 30,000 feet tall, contextual filtering may be employed to prevent the download of map data for whatever streets are involved. Further, for example, the context of the user may be defined in terms of occupation, e.g., a user whose occupation is a transport truck driver may employ contextual filtering to prevent download of map data for a side road to which the user's truck cannot travel, or a user whose occupation is to supplement the provision of soft drink meters may employ contextual filtering to download public map data showing user responsible geographic areas with irrelevant features such as filtered lakes and valleys, and private map data containing the locations of the soft drink meters overlaid on the public map data.

The Maplet index request results in the downloading of a Maplet index (i.e., only a portion of the Maplet that provides a table of contents of map data available within the Maplet, but not the entire Maplet) from the map server to the device, thereby saving OTA (over-the-air) bandwidth and device memory caching requirements. The Maplet index conforms to the same data structure as Maplet, but omits the data points. Thus, the Maplet index is small relative to the fully populated Maplet or traditional bitmap size (e.g., 300-400 bytes) and includes the DEntry bounding box and attributes (size, complexity, etc.) for all artifacts within the Maplet. As the field of view changes (e.g., for a location-aware device that displays a map while moving), the device (client) software evaluates whether additional data needs to be downloaded from the server. Thus, if the size attribute or complexity attribute of an artifact that begins to move within the field of view of the device (but has not yet been displayed) is not relevant to the viewer's current context, the device may choose not to display that portion of the artifact. On the other hand, if the portion of the artifact is suitable for display, the device accesses its cache to determine if the DEntry associated with the portion of the artifact has been downloaded, in which case the contents of the cache are displayed. Otherwise, the device issues a request to the map server to download all dentries associated with that artifact section.

By organizing the Maplet data structure in layers, information obtained from public and private servers can be seamlessly combined and displayed. For example, a device may display office buildings at a particular address on a street (e.g., the first z-th order attribute in the public database) adjacent to a river (e.g., the second z-th order attribute in the public database) whose overlapping ground level displays the various offices (e.g., the eleventh z-th order attribute in the private database, accessible through a firewall).

Referring back to fig. 13A, within a network having a map server and/or LBS server 321 and an accessible database 322, all map data for the world is divided and stored as a grid according to various resolution (zoom) levels (as shown in table a below). Thus, a single a-level Maplet represents a 0.05 x 0.05 degree grid area; a single B-level Maplet represents a 0.5 x 0.5 degree grid area; a single C-level Maplet represents a 5 x 5 degree grid area; a single D-level Maplet represents a 50 x 50 degree grid area; and a single E-level Maplet represents the entire world in a single Maplet. It should be understood that Table A is only an example of a particular Maplet grid; of course different meshing with finer or coarser granularity may be substituted. The Maplet can include sets of layers, each layer containing a set of dentries, each DEntry containing a set of data points.

TABLE A

Grade	Gridding (degree)	# of Maplets covering the world	# of Maplets covering north america	# of Maplets covering Europe
					A	0.05×0.05	25,920,000	356,000	100,000
B	0.5×0.5	259,200	6,500	1000
					C	5×5	2,592	96	10

D	50×50	32	5	5
					E	All over the world	1	1	1

As described above, three specific types of requests may be generated by a wireless communication device (i.e., client), namely AOI requests, DEntry requests, and Maplet index requests. The requests may be generated individually or in various combinations, as discussed in detail below. The AOI (region of interest) request calls all dentries in a given region (bounding box) for a predetermined or selected z-th order layer group. The AOI request is typically generated when the device moves to a new area, so that the DEntry is obtained before the device client knows to show what is available in the Maplet. The Maplet index request has exactly the same structure as Maplet, but does not contain a full DEntry (i.e. data points that actually represent artifacts and markers are omitted). Thus, the Maplet index defines what layers and dentries are available for a given Maplet. The data or DEntry request is a mechanism for bundling all the required dentries for a given Maplet together.

Typically, AOI and Maplet index requests are paired in the same message, but not necessarily, whereas DEntry requests are generated most often. For example, when the wireless device moves into an area where no information is stored at the device client, the Maplet index request returns a Maplet index indicating what data the client can request from the server 321 specifically, while the AOI request returns any DEntry within the area of interest for the specified layer (if any). In the example request shown in fig. 13B, the desired Maplet is identified within the DEntry request by specifying the bottom left Maplet coordinate. Further, the DEntry request may include a layer mask (mask) (so that unwanted layers are not downloaded), a DEntry mask (so that unwanted data points are not downloaded), and a zoom value that specifies a zoom level for the requested DEntry. Once the device client receives the requested Maplet index, the client typically issues multiple DEntry requests to request a particular DEntry (since the client knows all of the particular dentries available based on the Maplet index).

In this particular embodiment, a set of 20 × 20 a-level maplets (representing 1 × 1 degree squares) is compiled into a Maplet block file (. mbl). The. mbl file contains a header that specifies the offset and length of each Maplet in the. mbl file. A set of 20 × 20 of the same Maplet index data is compiled into a Maplet index file (. mbx). The structures of the. mbl and.mbx files are given in tables B and C, respectively.

Table B:

in table B, Maplet #0 offset is 0x0000 — 0000, because in this particular example, the data structure is based on the assumption that the base address (base address) for the actual Maplet data is 0x0000 — 0C 80. Thus, the absolute address for Maplet #0 data is: maplet #0 address ═ base address (0x0000_0C80) + Maplet #0 offset (0x0000 — 0000), and other Maplet addresses are calculated as: maplet # (n +1) offset Maplet # (n) length. If the Maplet has no data or does not exist, the length parameter is set to zero (0x0000 — 0000).

Table C:

in table C, the offset of the Maplet index is 0x0000 — 0000 because the data structure is based on the assumption that the base address for the actual Maplet index data is 0x0000 — 0C80 according to an exemplary embodiment. Thus, the absolute address for Maplet index #0 data is: maplet index #0 address ═ base address (0x0000_0C80) + Maplet index #0 offset (0x0000 — 0000), and other Maplet index addresses are calculated as: the Maplet index # (n +1) offset is Maplet index # (n) offset + Maplet index # (n) length. If the Maplet index has no data or does not exist, the length parameter is set to zero (0x0000 — 0000).

Fig. 13C and table D (shown below) collectively illustrate, by way of example only, a basic Maplet data structure. In general, as described above, the Maplet data structure can include a Maplet index (i.e., an index of dentries, each index representing either or both an artifact or a marker) and data points for each DEntry that actually forms such artifacts and markers. In this example, each Maplet includes a map ID (e.g., 0xA1B1C1D1), a # of layers in the Maplet, and a layer entry for each layer. The map ID identifies the data as a valid Maplet and, according to an alternative, can also be used to identify the version number of the data. Layer # is an integer indicating the number of layers (and thus layer entries) in the Maplet. Each layer entry defines a presentation attribute and precedes the DEntry list of each layer. The above forms the Maplet index. For a complete Maplet, each DEntry contains a data point (also referred to herein as a point) or set of tags. It should be noted that a layer may have multiple dentries, and the dentries and the full list of points are grouped by layer and separated by a layer separator (e.g., hexadecimal value 0 xeeeeeeeee). In this example, each layer entry is 20 bytes long and the DEntry is 12 bytes long. However, the number of layers, the number of DEntry per layer, and the number of points per DEntry depend on the map data and are generally variable.

Table D provides a high "byte level" description of the Maplet of this example.

Table D:

the new technology has been described in terms of specific embodiments and configurations by way of example only. Accordingly, the scope of the exclusive rights sought by the applicants are intended to be limited only by the appended claims.

Claims (26)

1. A method for distributing map data from a map server to a wireless communication device, the method comprising the steps of:

obtaining vector map data in response to a request for map data received at a map server from a wireless communication device;

generating a bitmap array representing vector map data for a particular location specified in the request;

calculating attributes of the bitmap array to determine which map features to retain and which map features to omit; and

only map data for map features to be retained is transmitted to the wireless communication device.

2. The method of claim 1, wherein the step of computing attributes of the bitmap array comprises the steps of: it is determined whether any polygonal map features are to be omitted.

3. The method of claim 2, wherein the step of determining whether any polygon map feature is to be omitted comprises the steps of: for each polygon map feature, calculating a total number of bitmap cells in the bitmap array to approximate a polygon area of the polygon map feature, and determining whether the total number of bitmap cells is less than a polygon area threshold, and if below the threshold, omitting the polygon map feature.

4. The method of claim 1, wherein the step of calculating attributes comprises the steps of:

marking bitmap cells in the bitmap array corresponding to the first map feature;

marking bitmap cells in the bitmap array corresponding to the second map feature, wherein it is assumed that the bitmap cells to be marked for the second map feature do not coincide with bitmap cells already marked for the first map feature, thus providing a count of marked and unmarked cells of the second map feature relative to the first map feature; and

the ratio of marked cells to unmarked cells is compared to a threshold to determine whether the second map feature is considered to overlap the first map feature.

5. The method of claim 4, further comprising the steps of: prioritizing the first map feature and the second map feature based on metadata characteristics of the first map feature and the second map feature to determine a suitable order for the priority of the cells populating the bitmap array.

6. The method of claim 5, wherein the first and second map features are routes, and the step of prioritizing is based on one or more of the following factors: a route category, an importance level of the route, a speed limit associated with the route, and a length of the route.

7. The method of claim 1, wherein the step of calculating attributes comprises the steps of:

marking bitmap cells in a bitmap array corresponding to a first map feature while also marking adjacent bitmap cells to define a buffer of buffer cells immediately adjacent to each side of the bitmap cell corresponding to the first map feature;

marking bitmap cells in the bitmap array corresponding to the second map feature, wherein it is assumed that the bitmap cells to be marked for the second map feature do not coincide with bitmap cells already marked for the first map feature, or do not coincide with buffer cells of the first map feature, thus providing a count of marked and unmarked cells of the second map feature relative to the first map feature and its buffer; and

the ratio of marked cells to unmarked cells is compared to a threshold to determine whether the second map feature is considered to overlap or be too close to the first map feature.

8. The method of claim 1, wherein the map data transmitted to the wireless communication device includes only vector map data for map features to be retained.

9. The method of claim 1, wherein the map data transmitted to the wireless communication device comprises bitmap data generated by folding vector map data into a bitmap array.

10. The method of claim 1, wherein the map data is pre-processed on a map server for a plurality of different zoom levels.

11. The method of claim 1, wherein the map data is processed in real-time on a map server.

12. The method of claim 1, further comprising the steps of: the user is enabled to adjust the performance of the map presented on the device by adjusting one or more of a plurality of adjustable parameters, including the bitmap size, the bitmap resolution, a threshold for determining when a map feature is to be omitted, and a buffer width for determining when a map feature is to be omitted due to being too close to another map feature, thereby adjusting the degree of map detail to be provided.

13. An apparatus for distributing map data from a map server to a wireless communication device, the apparatus comprising:

means for obtaining vector map data in response to a request for map data received at a map server from a wireless communication device;

means for generating a bitmap array representing vector map data for a particular location specified in the request;

means for computing attributes of the bitmap array to determine which map features to retain and which map features to omit; and

means for transmitting only map data for map features to be retained to the wireless communication device.

14. The apparatus of claim 13, wherein the means for calculating the attributes of the bitmap array comprises: means for determining whether any polygonal map features are to be omitted.

15. The apparatus of claim 14, wherein the means for determining whether to omit any polygon map features comprises: for each polygon map feature, means for calculating a total number of bitmap cells in the bitmap array to approximate a polygon area of the polygon map feature, and means for determining whether the total number of bitmap cells is less than a polygon area threshold, and if below the threshold, omitting the polygon map feature.

16. The apparatus of claim 13, wherein the means for calculating the attribute comprises:

means for marking bitmap cells in the bitmap array corresponding to the first map feature;

means for marking bitmap cells in the bitmap array corresponding to the second map feature, wherein it is assumed that the bitmap cells to be marked for the second map feature do not coincide with bitmap cells already marked for the first map feature, thereby providing a count of marked and unmarked cells of the second map feature relative to the first map feature; and

means for comparing the ratio of marked cells to unmarked cells to a threshold to determine whether the second map feature is deemed to overlap the first map feature.

17. The apparatus of claim 13, wherein the means for calculating the attribute comprises:

means for marking bitmap cells in the bitmap array corresponding to a first map feature while also marking adjacent bitmap cells to define a buffer of buffer cells immediately adjacent each side of the bitmap cell corresponding to said first map feature;

means for marking bitmap cells in the bitmap array corresponding to second map features, wherein it is assumed that the bitmap cells to be marked for the second map features do not coincide with bitmap cells already marked for the first map features or with buffer cells for the first map features, thus providing a count of marked and unmarked cells of the second map features relative to the first map features and its buffer; and

means for comparing the ratio of marked cells to unmarked cells to a threshold to determine whether the second map feature is deemed to overlap or be too close to the first map feature.

18. The device of claim 13, wherein the map data transmitted to the wireless communication device includes only vector map data for map features to be retained.

19. The device of claim 13, wherein the map data transmitted to the wireless communication device comprises bitmap data generated by folding vector map data into a bitmap array.

20. The apparatus of claim 13, wherein the map data is pre-processed on a map server for a plurality of different zoom levels.

21. The apparatus of claim 13, wherein the map data is processed in real-time on a map server.

22. The apparatus of claim 13, further comprising: means for enabling a user to adjust the performance of a map presented on a device by adjusting one or more of a plurality of adjustable parameters, thereby adjusting the degree of map detail to be provided, wherein the parameters include a bitmap size, a bitmap resolution, a threshold for determining when a map feature is to be omitted, and a buffer width for determining when a map feature is to be omitted due to being too close to another map feature.

23. A method for processing vector map data in a map server, the method comprising the steps of:

generating a bitmap array representing vector map data for a particular location specified in a request for map data received by a map server;

calculating attributes of the bitmap array to determine which map features to retain and which map features to omit; and

only map data for map features to be retained is made available for transmission to the wireless communication device.

24. The method of claim 23, wherein the step of calculating attributes of the bitmap array comprises the steps of: it is determined whether any polygonal map features are to be omitted.

25. The method of claim 24, wherein the step of determining whether any polygon map feature is to be omitted comprises the steps of: for each polygon map feature, calculating a total number of bitmap cells in a bitmap array to approximate a polygon area of the polygon map feature, and determining whether the total number of bitmap cells is less than a polygon area threshold, and if below the threshold, omitting the polygon map feature.

26. The method of claim 23, wherein the step of calculating attributes comprises the steps of:

marking bitmap cells in the bitmap array corresponding to the first map feature;

marking bitmap cells in the bitmap array corresponding to the second map feature, wherein it is assumed that the bitmap cells to be marked for the second map feature do not coincide with bitmap cells already marked for the first map feature, thus providing a count of marked and unmarked cells of the second map feature relative to the first map feature; and

the ratio of marked cells to unmarked cells is compared to a threshold to determine whether the second map feature is considered to overlap the first map feature.