HK1127761A - System and method for providing a virtual database environment and generating digital map information - Google Patents

Abstract

A system and method for providing a virtual map database, referred to herein as the "Virtual Database System" (VDB). The VDB allows integration of map data, often from various sources, in a consistent manner for supply to an end user, while simultaneously ensuring that the entity best able to support a particular data source retains control over the data. In accordance with an embodiment, the VDB environment enables third-party data providers to associate their third-party-files with a base map or file-of-reference, thereby allowing for the creation of dynamic relationships between digital map features and other third-party data providers. The integration may be performed in a dynamic or real-time fashion, receiving up-to-date information from the various sources, creating links, and composing virtual maps, as needed or on-demand.; Since the information is linked between the map providers and the various third parties, whenever an item of information or a link between items is updated in either the file-of-reference or in one of the third-party files, that updated information can be propagated back to all of the third-parties for further use in their software applications.

Description

System and method for providing a virtual database environment and generating digital map information

Copyright notice

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the patent and trademark office patent file or records, but otherwise reserves all copyright rights whatsoever.

Claim of priority

The present application claims the benefit of U.S. patent application No. 11/742,937 entitled "SYSTEM and METHOD FOR PROVIDING a VIRTUAL DATABASE ENVIRONMENT and generating digital map INFORMATION" (SYSTEM AND METHOD FOR PROVIDING a VIRTUAL DATABASE ENVIRONMENT and generating digital map INFORMATION "), which claims the benefit of U.S. provisional patent application No. 60/797,130 entitled" SYSTEM and METHOD FOR PROVIDING a VIRTUAL DATABASE ENVIRONMENT and generating digital map INFORMATION "(SYSTEM and METHOD FOR PROVIDING a VIRTUAL DATABASE ENVIRONMENT and generating digital map INFORMATION ANDGENERATING DIGITAL MAP INFORMATION)" applied on 5/1/2007 and incorporated herein by reference.

Technical Field

The present invention relates to systems for providing digital maps, and in particular, to systems and methods for providing digital map information using virtual database techniques.

Background

The use of digital geographic or map data has become commonplace in modern society. Map data, commonly referred to as "electronic maps" or "digital maps", have been used in a variety of applications. A typical application is in the travel industry, where digital maps are used to search for travel destinations, vacation facilities, and alternative routes. Internet-based business-to-consumer (B2C) companies often use digital maps to guide consumers to theaters, stores, restaurants, and other commercial merchants. Digital maps are also commonly used in an industrial setting, for example, to calculate routes for transport drivers, or to provide directions for emergency and medical personnel to follow when responding to emergency calls.

Digital map providers have increasingly shifted from the process of digitizing paper-based maps alone, and are now more appropriately viewed as collectors and organizers of ever-larger kinds of data, covering for example the following topics, in order to support the latest applications: street address, transportation network, body of water, community site administrative area, census data, demographic information, commercial merchants, and entertainment facilities. Meanwhile, the multiple uses of this map data have also been expanded to include, for example, in-vehicle driving assistance; PDA and cell phone based navigation; and applications that focus on local news, media, and yellow pages information services. With this increase in utility, it has become apparent that many of these software applications require the underlying map data to be combined with location-related information from other sources to provide a more useful end product.

Some companies have tried to make personal map databases with richer contents by themselves. However, this is neither efficient nor desirable for digital map companies in businesses that constantly collect and maintain a large amount of information about each and every point of interest (including attributes of those places). Rather, digital map companies should ideally be allowed to focus on what they do best, i.e., to create accurate digital maps. By focusing on this aspect of map commerce, and intelligently integrating their digital map data with digital map data of other organizations, all parties can increase the value of their data products and applications that use them.

A typical approach to map data integration is to create an "overlay map" in which one digital map is used as a base map, and then additional information from another source (or sources) is overlaid on the base map, to at least provide the illusion of a more complex map. This is a method used in many internet-based map information systems. For example, if a company wishes to provide an online restaurant search utility, they may provide a first map a (which may be a typical map with streets, parks, and other such locations displayed thereon). They may then overlay map a with a second map B containing restaurant information and comments. In response to a user request for a restaurant map, the company may display a portion or all of map a overlaid with a portion or all of map B so that matching restaurants are highlighted on the map as a flag. This process can be extended to many maps overlaid on each other to give the impression of a very informative map. However, a problem with this technique is that its simplicity limits its usefulness. The map items themselves are not relevant between individual maps, as the process of overlaying maps provides only the virtual illusion of a single integrated map. Thus, coverage maps are limited to providing simple virtual impressions. Overlay maps cannot be used for further development by users because they do not contain the relationship information necessary to jump from one map item to another. Additionally, because the relationships between map items are essentially ignored in the overlay, there may be a problem with accuracy, i.e., features may not properly line up in the final image at all. Commercial applications of this type of map are typically limited to map displays that provide yahoo, city search (city search), google, and other online dictionaries and information services familiar to users.

An additional concern with successfully integrating map information is maintaining consistency between the various data sets. When a single application uses information collected from multiple data collection jobs, there is always a risk of losing consistency. This risk exists even if the data is collected from internal resources, but is amplified when the data is collected from other third parties. One approach might be to maintain or store all the required information in a common repository or database. However, as increasing amounts of data are added, the database can become quite complex and confusing, such that performance and maintenance requirements will become unacceptable. However, ownership of data will also become more complex, as many third parties may prefer to retain full control and ownership of their particular data, and will not wish to have their data encroached into a common database. In many cases, the third party is also the entity that is most able to maintain the accuracy and freshness of its particular data. This accuracy may be lost if the data is integrated into a monolithic database that no longer receives frequent updates from the original data sources. These considerations of accuracy and consistency are increasingly working when considering the problem of geospatial data, as solving this problem also requires social thinking that the highest quality data is produced by some party with a given interest in it. For example, hotel chains attempting to attract consumers consider it extremely important to provide their consumers with an accurate direction, and in fact, their business depends on this functionality. For some vendors, attractive local maps may be one of their most important sources of advertising. Local knowledge is also considered to be the best knowledge when representing local information (e.g., neighbor or community information). In each of these cases, a third party that produces its own data sources may be better located to create and update locally-directed or locally-focused data than is possible with a centralized map data company that operates a single database.

Despite the shortcomings of centrally stored or integral map databases, if a company were to provide the end user with the desired integration of information from multiple data sources, there must still be some form of central coordination of this data. Central coordination ensures that the data collection effort is standardized and comprehensive. This is an important element in producing quality products with a consistent and appealing appearance over the larger geographic area that the software application can then use. As a rule of thumb, the more relaxed or less rigid a particular data model or schema, the easier it is to enter data into the schema. Conversely, the more rigid the schema, the more difficult it is to input data, and the greater the likelihood that information will be lost during the import process. This is a problem that occurs when someone executes a particular world view. While some common data structures are needed to provide the order, the world represented by the map is paradoxical in time and can be seen from many different angles. Ideally, a digital map should impose a sufficient order within its schema to meet the functional requirements of the application and to create an aesthetically pleasing appearance. Imposing a rigid mode beyond this is detrimental.

Another important element of digital mapping is quality control. Automated data collection and processing algorithms can manipulate information in a consistent manner in speed and logic that humans cannot match. However, there is no computerized alternative to human intelligence in identifying and correcting certain types of data problems. The human operator is also better able to determine whether the digital map is a fair representation of the world that he wants to replicate. Therefore, in any mapping environment, having the best tools for visualizing data is critical to quality. As described above, a third party may be located in the best position to perform these necessary quality control checks and corrections.

The reader will note that many of these observations, if taken individually, may suggest opposite considerations, noting that the need to create a digital map provides for integration of various data sources while allowing different entities to retain control over the various data sources. An optimal design should properly balance these considerations. In particular, the design should allow for a consistent and flexible means of integration, while allowing control of some data sources to stay with the entity best suited to ensure the quality and accuracy of the data. Typically, this would mean sharing control of the final overall map product between the digital map provider company and one or more third party companies. Another important consideration is that, in order to be useful in end-user applications, any third-party or externally sourced application data must be consistent or queued with, for example, the road network used within a digital map, must be accessible through a single common simple interface, and must allow querying in a standard manner (e.g., by identifier, coordinate window, address, object type or classification, and/or relationship to another object). To date, no system has been available that provides these benefits.

Disclosure of Invention

As disclosed herein, a system and method for providing digital map information is described. A "virtual database system" (VDB) balances the seemingly opposite considerations in allowing map data (often from a variety of sources) to be integrated in a consistent manner for provision to end users while ensuring that the entity most able to support a particular data source retains control over that data. In particular, the VDB allows sharing (or in some cases delegating) control and ownership of each component that will become the final overall map product between the digital map provider and one or more third parties or between third parties. According to an embodiment, the VDB environment enables third party data providers to easily associate or geocode their data or "third party files" onto a digital map provider's "base map" or "reference file," thereby allowing for the creation of dynamic relationships between digital map features and other third party data providers. The VDB can also be accessed by an application provider to seamlessly purchase and retrieve integrated data from multiple vendors through a single organization, and then provide that data to an end user. As disclosed herein, a reference file may be a geospatial database, data structure, document, or digital map for storing geographic data. Similarly, the third party file may also be a geospatial database, data structure, document or digital map for storing geographic data. In some embodiments, the integration may be performed on-demand or on-demand in a dynamic or real-time manner, receiving up-to-date information from various sources, creating links, and composing virtual maps. An additional benefit is that since the information is linked between the map provider and various third parties, whenever the link between an item or items of information is updated in a reference file or in one of the third party files, the updated information can be propagated back to all third parties for further use in their own software applications. Thus, while each party maintains control over their data sets, if they so choose, they may automatically receive updated or corrected information from each of the other parties, and may then choose to update their data sets in the manner they deem appropriate. In this way, everyone benefits from the opportunity to automatically share updated information.

Drawings

FIG. 1 shows an illustration of a virtual database environment, according to an embodiment of the invention.

FIG. 2 shows an illustration of a means of integrating multiple map databases according to conventional methods.

FIG. 3 shows an illustration of a means of integrating multiple map databases using a virtual database system, according to an embodiment of the invention.

FIG. 4 shows an illustration of using a virtual database system or environment to interact between different parties, according to an embodiment of the invention.

FIG. 5 shows a flow diagram of a method of using a virtual database system in accordance with an embodiment of the invention, wherein a location identifier is created first after the virtual database is created.

FIG. 6 shows a flow diagram of a method of using a virtual database system in which a pre-existing location identifier is used in creating a virtual database in accordance with an embodiment of the present invention.

FIG. 7 shows a diagram of a virtual database system architecture according to an embodiment of the invention.

FIG. 8 shows a flow chart including steps in a general method of using a virtual database according to an embodiment of the invention.

FIG. 9 shows an illustration of how third party data may be integrated with additional content in a virtual database with different confidence levels, according to an embodiment of the invention.

FIG. 10 shows an illustration of a virtual database using ULROs, according to an embodiment of the invention.

FIG. 11 shows the steps of a general method of using a virtual database according to an embodiment of the invention.

FIG. 12 shows additional steps of a general method of using a virtual database according to an embodiment of the invention.

FIG. 13 shows additional steps of a general method of using a virtual database according to an embodiment of the invention.

FIG. 14 shows additional steps of a general method of using a virtual database according to an embodiment of the invention.

FIG. 15 shows additional steps of a general method of using a virtual database according to an embodiment of the invention.

FIG. 16 shows additional steps of a general method of using a virtual database according to an embodiment of the invention.

FIG. 17 shows additional steps of a general method of using a virtual database according to an embodiment of the invention.

FIG. 18 shows additional steps of a general method of using a virtual database according to an embodiment of the invention.

FIG. 19 shows steps in a method of using a virtual database with a ULRO in accordance with an embodiment of the present invention.

FIG. 20 shows additional steps in a method of using a virtual database with a ULRO in accordance with an embodiment of the present invention.

FIG. 21 shows additional steps in a method of using a virtual database with a ULRO in accordance with an embodiment of the present invention.

FIG. 22 shows additional steps in a method of using a virtual database with a ULRO in accordance with an embodiment of the present invention.

FIG. 23 shows additional steps in a method of using a virtual database with a ULRO in accordance with an embodiment of the present invention.

FIG. 24 shows additional steps in a method of using a virtual database with a ULRO in accordance with an embodiment of the present invention.

FIG. 25 shows additional steps in a method of using a virtual database with a ULRO in accordance with an embodiment of the present invention.

FIG. 26 shows additional steps in a method of using a virtual database with a ULRO in accordance with an embodiment of the present invention.

FIG. 27 shows an illustration of an exemplary application of a VDB system.

FIG. 28 shows another illustration of an exemplary application of a VDB system.

Detailed Description

As disclosed herein, a system and method for providing digital map information is described. A "virtual database system" (VDB) balances the seemingly opposite considerations in allowing map data (often from a variety of sources) to be integrated in a consistent manner for provision to end users while ensuring that the entity most able to support a particular data source retains control over that data. In particular, the VDB allows sharing (or in some cases delegating) control and ownership of each component that will become the final overall map product between the digital map provider and one or more third parties or between third parties. According to an embodiment, the VDB environment enables third party data providers to easily associate or geocode or otherwise locate their data or "third party files" onto a digital map provider's "base map" or "reference file," thereby allowing for the creation of dynamic relationships between digital map features and other third party data providers. The VDB can also be accessed by an application provider to seamlessly purchase and retrieve integrated data from multiple vendors through a single organization, and then provide that data to an end user. As disclosed herein, a reference file may be a geospatial database, data structure, document, or digital map for storing geographic data. Similarly, the third party file may also be a geospatial database, data structure, document or digital map for storing geographic data. In some embodiments, the integration may be performed on-demand or on-demand in a dynamic or real-time manner, receiving up-to-date information from various sources, creating links, and composing virtual maps. An additional benefit is that since the information is linked between the map provider and various third parties, whenever the link between an item or items of information is updated in a reference file or in one of the third party files, the updated information can be propagated back to all third parties for further use in their own software applications. Thus, while each party maintains control over their data sets, if they so choose, they may automatically receive updated or corrected information from each of the other parties, and may then choose to update their data sets in the manner they deem appropriate. In this way, everyone benefits from the opportunity to automatically share updated information.

Depending on the implementation, the virtual database system allows map information or third party files from many sources to be intelligently combined in real-time and then presented to the user in response to the user's request. In this way, map information is retrieved, linked and integrated only when received and in response to a request, thereby ensuring that the provided information is as up-to-date as possible. In other implementations, the virtual database system allows map information from many sources to be combined intelligently at product build time, i.e., when a particular map-based software product is built to be supplied to a consumer. The VDB ensures that the latest information is integrated into the product at the exact time of establishment. In other embodiments, a virtual database system may be used to automatically transfer multi-source map information to other systems for further use by those systems.

Since the information used to generate the map is stored virtually, i.e., dynamically created in response to a request, it need not be centrally located within a single data structure. However, in some implementations, it may still be desirable to place or otherwise store such a virtual map in cache for later use, particularly when the system responds to many subsequent requests for the same map data.

Creating a virtual map also allows pieces of information (i.e., third party files) to originate from and be maintained by different business entities, and to be modified or updated independently of one another. In fact, from the perspective of the end user, the user feels a single map filled with all the information important to them. From the perspective of the data provider, the system enables sharing of information otherwise owned or controlled by multiple entities to provide a single unified product offering.

According to an embodiment, the virtual database system is of particular use in a company combining digital basic map offerings of a digital map data provider (e.g., telia or another commercial mapping company, which is generally referred to as "digital map provider" within the context of this document) with one or more third parties (e.g., yahoo, google, city search, incrustation (Expedia), borrelid (Travelocity), or chagat (Zagat), which focus on the offerings of travel-related, neighbors, places, yellow pages, dictionaries, or similar information). By using the VDB method, digital basic map or reference file information provided by a digital map provider is combined with data from various third parties during the establishment of a specific product or in real time to create a virtual digital map. For greater accuracy, third party data providers may geocode their data files in accordance with the underlying map or reference file. For example, they may use coincident latitude/longitude information, or may map addresses in a reference file with a ULRC in a third party file, or may use a combination of objects and location codes. The third party data provider may also place those features in spatial alignment with the base map or reference file by geocoding or associating the features with geographic locations within the base map.

According to some embodiments, the virtual database system also enables third party data providers to link their data to features within the base map or reference file by using unique identifiers. Since integration is performed in a dynamic manner or upon request to build an application, this information can be dynamically embedded in the virtual map at the time of the user's request whenever a change is made to one data source (e.g., when a change is made to restaurant reviews in the database of Chart).

According to some embodiments, the links between the reference file and the various third party data sources may be provided by a Universal Location Reference Object (ULRO). As described in further detail below, a ULRO includes a permanent identification code designed to identify a selected location, which may then be associated with one or more geographic items. The ULRO may be used to establish traversable links or connections between digital base maps or reference files and third party data files. In this context, a reference is a geospatial file for permanently storing geographic data of the file owner. The third party file is a geospatial file for permanently storing the third party's geographic data. Additional information regarding the use of ULRO is provided in a pending U.S. patent application entitled "METHOD and System FOR creating Universal LOCATION reference object (A METHOD AMD SYSTEM FOR CREATING UNIVERSAL LOCATION REFERENCEING OBJECTS)" filed on 10.11.2005, entitled "application number 11/271,436, which is incorporated herein by reference. In embodiments using ULROs or similar generic objects, ULROs can be viewed as an example of a technique to provide links between a map provider's reference files and various third party files. The VDB can then be viewed as a technique that takes advantage of this linking in the process of generating a virtual map.

The goal of a virtual database system includes at least three aspects of improving data processing capabilities relative to third party map data providers: dynamic integration, as digital map data providers and their third party partners can share data, but still retain control over their data so that they can continue to update their individual databases according to their own product cycle; increased map quality by delegating control to those parties that are best suited to detect data deviations and ensure a tight link between the core digital map data and the third party's data during the integration process; and easy sharing, by a common framework that enables data from multiple sources to be aggregated together in a consistent manner.

An additional benefit of this approach is that third party data providers do not need to use the precise latitude and longitude coordinates used in the base map to encode their information. Rather, they may benefit from and provide information to other third parties. For example, the third party may provide information about a map feature (e.g., a restaurant or parking garage) within the map. Another third party may provide information about the attributes of those map features, such as business hours for a particular restaurant. Another third party may provide a link that relates a particular restaurant to the parking garage closest to the restaurant. The corresponding information may all be linked together in the final virtual map to present the map from the perspective of a third party, rather than from the perspective of the digital map provider. Additionally, during the creation of the virtual database, features and feature imagery not yet in the base map may fall onto the map using a variety of links to any number of third parties.

These and other benefits will be apparent from the description contained herein.

Glossary of terms

The following sections define some of the terms used in the context of this document:

digital map provider-a digital map provider is a commercial, governmental, or other type of entity or company that develops, maintains, and provides reference files or digital base maps or supplies data including reference files or digital base maps. The digital map provider may also act as a third party file provider in some cases. Examples of commercial digital map providers include tulia atlas and other mapping companies.

Third party-a third party, third party data provider, or third party data source is a business, government, content provider, or other type of entity that is typically independent of the digital map provider, that provides third party data or content for use with the reference file or digital base map. If a third party is involved in a syndicated data providing operation with a digital map provider, then both of them may be considered third party partners.

Reference file-a reference file is a geospatial database, data structure, document or digital map used to permanently store the geographic data of the document owner. The reference file may typically be transformed into other formats that may be more suitable for certain applications. The term "permanent" as used herein is not meant to imply a state, as the data is of course updatable, but instead the term indicates that the data in the reference file is stored more "permanently" than the data in the virtual map that was dynamically created in response to the request. According to an embodiment, there is only one reference file database. Each other data source or geographic database is then considered a third party. However, these references are descriptive labels and not anything else, as in other embodiments, either the data file or the data source may act as a reference file, treating the other data files as third party files. As used herein, a reference may sometimes be referred to as a "digital base map" to illustrate that it is typically provided and sold as a digital map by a digital map provider.

Third party files-third party files are also geospatial databases, data structures, documents or digital maps used to permanently store the geographic data of the document owner, with the difference that the data in the third party files is supplied by a third party for use with the reference file. As described above, these headings are intended to be descriptive labels and not anything else, as in other embodiments, any of the data files or data sources may act as third party files, treating the other data files as references.

Virtual database/virtual database system-a virtual database is a means of manipulating data distributed across multiple databases as if they belonged to a single database. The system that provides the virtual database is then referred to as a virtual database system (VDB). The terms "virtual database" and "virtual database system" are somewhat similar in that they each refer to a system, means, or technique for creating a virtual database or virtual map in which objects and features within both a reference file and one or more third party files are linked to form a virtual database. In embodiments utilizing ULROs or similar generic objects, ULROs may be viewed as an example of a technique to provide links between a map provider's reference files and various third party files. The VDB can then be viewed as a technique that takes advantage of this linking in the process of generating a virtual map.

Virtual map-a virtual map is an intermediate database, or in some cases the output of a VDB, and is conceptually the same as the virtual database described above, i.e. it is a means of processing data distributed over multiple map sources as if they belonged to a single map. The term "virtual map" has a more realistic meaning than the term "virtual database" and is essentially a complex digital map. In addition, since virtual maps are dynamically created at runtime from many additional independent sources, virtual maps are more flexible, easily updated, and thus more useful than just an overview of map data.

An integration database-according to some embodiments, an integration database, also referred to herein as a cross-reference (XREF) database, is a database or data structure that integrates reference documents with third-party documents or third-party data belonging to one or more third parties. In some embodiments, the consolidated database is an actual database structure stored on physical media. In other embodiments, the integration database is a dynamically created data structure that links the reference file with third party files.

Application database-according to some embodiments, the application database is the medium of transfer of virtual map data from parties to end users. Depending on the particular implementation, the application database may take many different forms, including a traditional database format, a web page, or some other data presentation means.

ULRO-in embodiments that utilize a Universal Location Record Object (ULRO), the ULRO includes a permanent identification code and sufficient information designed to uniquely identify a particular location within a reference file or third party file. The location, in turn, may be associated with one or more geographic items. ULROs can be used to establish traversable links between reference files and third party files to obtain a wide range of database formats. ULROs may similarly be used to establish traversable links between two or more third party files. In some embodiments, a ULRO may refer to a location of a single map feature, a segment of a map line feature, or a collection of related map features. In some embodiments, the ULRO may encode location information relating to the referenced object, or it may simply be an assigned number. The map may contain multiple features, each sharing the same location, and the same ULRO. Once a ULRO is invalidated, it can no longer be used, in embodiments that use ULRO or similar generic objects, the ULRO can be viewed as an example of a technique that provides links between the map provider's reference files and various third party files. The VDB can then be viewed as a technique that takes advantage of this linking in the process of generating a virtual map. Additional information regarding the use of ULRO is provided in pending U.S. patent application entitled "METHOD and System for creating Universal LOCATION reference object (A METHOD AMD SYSTEM FOR RCREATING UNIVERSAL LOCATION REFERENCEING OBJECTS)" filed on 10.11.2005, entitled "11/271,436, which is incorporated herein by reference.

Map-as used herein, the term "map" is a general term used to refer to a geospatial database, a digital map, or map data contained therein.

Map object-a map object is a map item or, more suitably, a data object instantiated within a geospatial database or map.

Feature/geographic feature-a geographic feature (also referred to herein simply as a "feature") is an idealized map representation of an actual object from the real world for which it is useful. Features may have dimensions and most often, but not always, geometric representations. Features may be virtually invisible in the real world: such as a boundary or intersection, the features may nonetheless be represented in the map model. Features have types and categories that collectively allow the system to distinguish one feature from another while also preserving similarity between similar features.

The scale of a feature-a feature is typically represented in a simpler manner in a map model than in its full "real world" complexity. Often the real world complexity is more of a nuisance than of value to the model, which simply attempts to capture several salient aspects of the real world in order to perform some particular function. Thus, the scale of the features does not reflect real world facts, but rather the representation that has been rendered. According to an embodiment, the features are divided into five scales to include point features, line features, area features, volume features, and composite features. Real world features represented as points are referred to as point features. For example, restaurants (although they are volumetric objects with complex shapes in the real world, they are conveniently represented as point features when represented in a map model. this is true, for example, for the junction where two or more road elements intersect each other. line features are represented as linear or simply curved line segments (and thus have a meaning that extends between point features or intermediate shape points.) roads, boundaries, railways, and rivers are some examples of line features. But typically with much less detail. Finally, composite features are features that are not defined "automatically".

Type of feature and class of feature-type and class of feature are subclasses of features that enable distinguishing between different features. Roads, rivers, train tracks, cities, counties, mountains, bus stops, intersections, bridges, restaurants, hotels, rest areas are just a few examples of types of features. In most commercial map models, there may be thousands of different feature types. For example, the ISO-GDF (geographic data file) map format is a standard format that attempts to enumerate, among other things, a full set of well-known feature types. In the ISO specification "ISO 14825: the complete details of the GDF format are described in the Intelligent delivery System-Geographic Data File (GDF) general Data Specification (ISO 14825: Intelligent transport Systems-Geographic Data Files (GDF) overhead Data Specification) ". Variations are also possible within a particular type of feature. For example, there are different kinds of roads in the world: freeways, arterial roads, secondary roads, rural roads, residential roads, turnouts, dirt roads, and mountain roads. Although these are all feature types "roads," they differ in their various classification methods, so the feature classifications are subordinate to the feature types.

Geometry of a feature-in computer map models, a feature typically has a geometric representation of the feature's shape. For example, a point feature is a representation by a single node. Line features are typically represented by linear line segments (edges, which may extend through a sequence of shape points). An area feature may be represented by a collection of faces, each face consisting of edges delineating its boundary. The area features may be disjointed, or may even have holes therein. The volume feature may be represented by a volume geometry, which may contain a cavity.

Topology-topology is a set of mathematical properties that are used as a means to capture the consistency relationships between real features even when the geometry (shape) of the features may undergo some change. Some scale geometries are bounded by less scale geometries. For example, a volume is bounded by an area, which is bounded by linear line segments; the linear geometry is delimited by points. Instead, the points are collectively bounded by a linear geometry; the linear boundaries are collectively bounded by an area; and the areas are collectively bounded by the volume. Topology may be an aspect of the feature itself, or an aspect of the geometry that captures its shape.

Simple features-point features, line features, area features, and volume features are referred to as simple features because they can be directly modeled by assigning geometric shapes to them.

Composite features-in contrast to simple features, composite features can be defined indirectly by other features (simple or composite), or by direct geometric rendering. For example, the state of california cannot be represented by extending its boundaries with shape points (which would make it a simple area feature), but rather as a sum of the various counties of the state of california (which may themselves be simple or compound features). The state of california reproduced as a composite feature is a single feature that is defined in a composite manner by reference to other features. A road consisting of two road elements (one element in one direction of traffic) is another common example of a composite feature. When two composite roads meet, a composite feature, a composite intersection, is declared. Typically intersections can be considered as four junctions, where simple road elements cross each other.

Multiple features-both simple and compound features described above are examples of a single feature. However, it is sometimes useful to consider several features simultaneously, thus creating multiple features. For example, a collection of all restaurants in san Francisco, or all counties in California serve as examples of multiple features. Note that multiple features (e.g., all counties of california) are different concepts than a single composite feature of the state of california (although in this example, they do have the same geometric footprint).

Feature subsets-it is sometimes convenient to identify a portion, subset, or part of a single feature. At times such portions may be characterized by their own right, but at other times such portions are merely fragments that themselves would not be an actual feature. Examples of subsets of features include a single county of california features, a segment of road elements spanning only a small portion of a square between two junctions, or 4-17 floors of a 30-floor building.

Attribute-A feature, a plurality of features, and a subset of features can have attributes. The attributes are provided in a large catalog, and there may be thousands of different attributes applied to features in a real-world commercial computer map model. An attribute type is something that captures different attributes from a directory. Speed limits, length, direction of traffic flow, and restaurant hours of operation are just a few examples of such attributes.

Relationship-a relationship comprises two or more features that "participate" in some meaningful connection with each other. For example, a road element may be split into several road elements at some junction point, and thus all those features are in a "fork" relationship with each other (each feature playing a different role). Relationships are also provided in large directories, and as with attributes, hundreds or thousands of such relationships are possible in an actual commercial digital map model. Not all relationships are geometric relationships, as many are formed by simulating real-world activities. For example, a restaurant that validates parking in a particular parking garage represents one type of business relationship between the two features.

Geographic item-for purposes of this description, the term "geographic item" is a non-ISO standard item. A geographic item is defined herein as a feature, a plurality of features, a subset of features, or an attribute.

Location-defining location as where a feature is in the real world is a different concept than the feature itself. For example, while a feature may be a particular restaurant, its location may be specified as a certain latitude, longitude (latitude/longitude) coordinate pair, or coordinates from a similar geodetic reference system, or as a human-readable address (e.g., "battle Street 322 san francisco). A location should not be confused with features or with other geographic items associated with the location.

Level of features-features typically form a level of construction. For example, a country may consist or consist of states or provinces, while a state may consist of a county, and so on. In a similar manner, a pavement surface is made up of a number of square pavement elements. Roads and parks and buildings of composite area including the "Stanford university campus area" are part of a larger feature. The hierarchy of features is a special case of relationships between features, and it may be explicitly captured and represented, or implicitly captured and represented.

A point of interest-a point of interest (POI) is a special type of point feature. In particular, POIs are feature types that may include other more specific types, such as restaurants, hotels, or museums.

Relational linking — according to some embodiments, a relational link is an entry in a table that defines a relationship between data objects. In embodiments utilizing ULROs, a relational link may correlate two ULROs, or a ULRO with third party data lacking ULROs (e.g., file names or URLs). Not every embodiment uses relational links.

Markers-according to some embodiments, markers (or "position markers") may be used. Individual map features, segments of map line features, or sets of related map features are associated. These features may be located in a database maintained by the digital map data provider or a third party vendor, however, the digital map data provider will maintain the indicia. In some embodiments, the relationship information is not stored in the ULRO, and in these cases, a flag is appropriate. However, in most cases, marking is not necessary or desirable. Not every embodiment uses a marker.

Object markup-an object markup is a specific type of markup and, as described above, may be used as an optional feature in certain embodiments. According to some embodiments, the object marker is a reference associating the location marker with the data object. The data object may be located in a reference file or database maintained by the digital map data provider, or it may be located in a third party file maintained by a third party. Not all embodiments use object tagging.

Relationship tag-a relationship tag is a particular type of tag and, as noted above, may be used as an optional feature in certain embodiments. Relationship tags (or "relationship tags") are relationships between data objects. Not all embodiments use relational tags.

Metadata registration system-according to some embodiments, a metadata registration system may be used. In those embodiments that utilize ULROs, the metadata registration system is a registration system that identifies third party data providers, their data content, coverage areas or quality levels, and the applicable scope of the ULROs assigned to them. Not all embodiments use a metadata registry system.

Virtual database environment

Generally described, embodiments of the present invention provide a virtual database system or environment. The virtual database environment allows spatial information to be "joined" in real time. This process is similar to that used in a traditional database environment, where a set of database tables are combined to collectively respond to requests from users that would otherwise span many tables. The process is substantially different from the conventional overlay type map combination described in the background section above. Given that the coverage map lacks any relational information, the virtual database environment provides a means to link each item (including points, locations, areas, buildings, or business properties) within the combined or joined map, as well as any other information that may be associated with those items. The resulting virtual database or virtual map may have the visual appearance of a traditional overlay map to the end user. However, unlike overlay maps, when using the virtual database approach, the user can click on one map item to reach any other linked map item. In fact, all information related to map items may be available via a linking mechanism. An additional benefit over traditional coverage techniques is that while coverage maps are fully dependent on geographic information, they can be inaccurate, and virtual database approaches are not so limited.

Since in a virtual database system some information may have been retrieved from a reference file, the techniques allow for linking between data owned, controlled and maintained by different business entities, although other information may have been retrieved from a third party file. An example OF the type OF linking mechanism that may be used within a virtual database environment is described in pending U.S. patent application entitled "method and system for associating text with a graphical view OF map information (SYSTEMAND METHOD FOR ASSOCIATING TEXT AND GRAPHICAL VIEWS OF mapping"), filed on 7/31/2002, entitled gio-fornices, 10/209,750, and which is incorporated herein by reference. As described in the patent application, map items are linked by semantic relationships, allowing attributes of one map item to be linked to attributes of another map item. However, the links in this case are primarily between map items in a single map. An example of the type of linking mechanism that may be used within a virtual database environment and between multiple maps or multiple data sources is described in pending U.S. patent application entitled "METHOD and system FOR CREATING a universal location reference object (a METHOD AMD SYSTEM FOR CREATING universal location reference object)" filed on 10.11.2005, entitled "application No. 11/271,436, to gio-forster, and which is incorporated herein by reference.

The utility of the virtual database may be considered in the example of the restaurant application described above. If a company wishes to provide online restaurant search functionality, they may provide a link to a first data source or first map a (which may be a typical geographic map with streets, parks, and other such locations shown above) using a virtual database approach. They may also provide a link to a second data source or second map B (which contains restaurant information, reviews, and the like). In response to a user request for a restaurant map, instead of just overlaying the map, the company may retrieve and display map a linked with the data of map B, so that restaurants are highlighted as flags on the map as previously described. However, by using the virtual database, any element of information associated with the restaurant provided by map B is fully linked to the element of map a. The virtual database is thus a virtual link of different map data sets to create a composite map structure, in which all map items are linked, at least during a temporary time period in response to a user request. Similar to the map overlay process, the virtual database process may present many maps of information relative to each other to give the end user the impression of a map with rich information. However, map coverage is merely an illusion. Unlike the map overlay process, by using the virtual database approach, each subsequent set of data that is linked is also linked by its map item to other map items in the collection. Furthermore, since one set of data (e.g., map a) may be received in real-time from one entity (say a digital map provider), while another set of data (e.g., map B) may be received in real-time from a different entity (say a third party), the virtual database allows responsibility and control of each data source to be attributed to the owner of the particular data.

FIG. 1 illustrates a virtual database environment according to an embodiment of the present invention. As shown in fig. 1, the virtual database environment 2 includes a virtual database 3, a reference file 4, and one or more third party files 6. As noted above, the reference is provided by the digital map provider 8, and the digital map provider 8 is a commercial, governmental, or other entity or company that develops, maintains, and provides the reference or digital base map. The third party files are provided by third party businesses or other entities 12, the third party businesses or other entities 12 are typically independent of the digital map provider and retain control over the specific data in their files. The reference file and the third party file may be geospatial databases, data structures, documents, or digital maps. However, the above is a descriptive tag and not anything else, as in other embodiments, any of the data files or data structures may serve as reference files, treating the other data files as third party files. A virtual database is a means of manipulating data distributed across reference and third party files into a single database as if those data sets belong to a single database. Any system that provides a virtual database in this manner may then be suitably referred to as a virtual database system.

In those embodiments that use ULROs or similar generic objects, the ULROs can be viewed as an example of a technique to provide links between a map provider's reference files and various third party files. The VDB can then be viewed as a technique that takes advantage of this linking in the process of generating a virtual map. According to an embodiment, the reference file contains a database of geospatial or map information, each item in the database containing certain identifying information. This identification information may be the name, latitude and longitude of the item. In embodiments using a ULRO or similar generic object, the ULRO may contain identification information for the item by specifying the ULRC for the item.

According to one embodiment, each reference file also contains a database of geospatial or map information, and each item contains certain identifying information. This identifying information may similarly be a name, latitude and longitude, or ULRO. The virtual database is created in response to a user request 15 or, if an application is established, the application is established in response to the request. The response to the user request may be the actual displayable map, some map-related information, a web package (e.g., an XML message), an API function call, or another form of response 18.

According to one embodiment, during the creation of the virtual database, "ghost" objects or images corresponding to items in the reference file may be created in memory. These objects are then linked to corresponding items in the reference file as necessary so that they can be populated with third party data prior to responding to the request. The information used to retrieve information from the various files of each object in memory is the common name of the item, longitude, latitude, ULRO or other information. Not all embodiments use phantom objects.

Since the virtual database or virtual map is created in response to a request from a user, according to an embodiment, the lifetime of the virtual database may be allowed to last the lifetime of the user session. After the session terminates, the virtual database may then be erased. Subsequent requests will cause the system to create new semaphores of the virtual data, however, in some implementations it may still be desirable to place a virtual map into cache or otherwise store a virtual map for a longer period of time, particularly when the virtual map is to be used to respond to many subsequent requests for the same map data.

If a digital map provider and a third party share a common file format, then integrating the two sets of data is essentially a one-to-one task. However, since the object of the present invention is to allow separate control of the respective data sets, it is more likely that the digital map provider and the third party will not share a common file format. To access information in third party files, third party providers must provide an interface that allows common data retrieval and linking. Alternatively, the digital map provider may provide an interface for use by third parties.

In embodiments using a ULRO or similar generic object, if the system receives third party data that does not have an existing ULRO, the system may assign a new ULRO to the project.

Fig. 2 and 3 illustrate the benefits of a virtual database system over traditional third party map integration solutions from an end user perspective. As shown in fig. 2, when using a traditional integration solution, the user 20 must make multiple requests/responses 30 to each of the multiple digital map providers 22 and third party data providers 24, 26, 28. As referred to herein, a "user" may be an actual individual, or may be a software program, a computer system, or other requestor of map-based information. In some cases, an automated process or layer may encapsulate multiple requests and responses (using an overlay process) such that they are presented to the end user as a single set of data. However, the data is still received independently from third party data providers, which leads to problems of reconciling and fully integrating the data, as described above. As shown in FIG. 3, when using a virtual database environment, a user 40 need only make a single request 50 and receive a single response 54. The virtual database environment takes care of integrating data from each of the plurality of digital map providers 42 and third party data providers 44, 46, 48 into the virtual database 3. According to one embodiment, the reference file data 4 from the digital map provider is linked 52 in real time with third party file data 56, 58, 60 from a third party data provider to populate the virtual database and dynamically respond to user requests.

It is noted that in view of FIG. 3 illustrating a process in which a user request is received and then an appropriate link to a third party source is invoked, and the resulting set of information is used to create a virtual database, it will be appreciated that in other embodiments, the integration of data may be performed in different ways. For example, according to some embodiments, upon receiving a first user query, a preliminary set of links to an initial third-party data set may be created. If a user makes a more specific request, additional sources with additional data and additional links may be included to satisfy the more specific request. According to other embodiments, a "federation" of third party data may be created such that, for example, when a data source of third party a is used to create a virtual database, then a data source of third party B is also used. Other embodiments and implementations will be apparent to those skilled in the art regarding the timing and scope of the links.

FIG. 4 illustrates how different entities interact within a virtual database environment. As shown in FIG. 4, a plurality of users 40, 41, 43 and one or more digital map providers 42 and third party data providers 44, 46, 48 share map related data via the virtual database environment 2. As described above, a "user" may be an actual individual, or may be a software program, computer system, or other requester of map-based information. In addition, the tags used in FIG. 4 are descriptive tags and not anything else, as in other embodiments, either the data file or the data source may act as a reference file, treating the other data files as third party files.

Fig. 5 and 6 illustrate a flow diagram of a process used by a virtual database environment according to an embodiment of the present invention. As shown in fig. 5, in step 61, the system allows the user or another system to make a request for map information. Alternatively, the process may be initiated by a request to establish an application. Based on this request, in step 62, the system accesses a reference file containing the item and a location code, such as a name, latitude, longitude, or ULRO. In step 63, the system identifies or creates a location identifier (e.g., ULRO) for each location within the map. According to the embodiment shown in FIG. 5, some information associated with a particular location may be used at runtime to create a ULRO. According to other embodiments, such as the embodiment shown below in FIG. 6, the ULRO need not be created at runtime, but instead has been defined in the reference. Additional information regarding the creation of ULROs is described in pending U.S. patent application entitled "METHOD and System FOR creating Universal LOCATION reference object (A METHOD AMD SYSTEM FOR CREATING UNIVERSAL LOCATION REFERENCEING OBJECTS)" filed on 10.11.2005, entitled "11/271,436, which is incorporated herein by reference. In step 64, the system then determines which additional third party files or third party information sources may be needed to fully respond to the request, and in step 65, third party data is retrieved into the system. In step 66, the item information in the reference file and the third party file are linked by common identification information (e.g., ULRO or another identifier), in step 67, a virtual database is then created using the fully linked data set, and in step 68, the initial request is responded to.

FIG. 6 illustrates a flow diagram of a process used by a virtual database environment in which a location identifier or ULRO has been assigned to some or all of the locations in a reference file or third party file in accordance with an embodiment of the present invention. As shown in fig. 6, the system again allows the user or another system to make a request for map information in step 71. In step 72, the system accesses a reference file containing the item and a location code, such as a name, latitude, longitude, or ULRO. In step 73, the system looks up or identifies an existing location identifier (e.g., ULRO) for each location within the map. In step 74, the system then determines which additional third party files or third party information sources may be needed to fully respond to the request, and in step 75, third party data is retrieved into the system. In step 76, the item information in the reference file and the third party file are linked by a common identification information (e.g., ULRO or another identifier). The data is then used to create a virtual database in step 77, and the system responds to the initial request in step 78.

The determination as to which reference files and which third party sources or files should be included in the process of creating the virtual database may be performed in a number of ways, including, for example, registering each third party source in a central location or registration system, and then including those registered third party files when creating the virtual database. Alternatively, third party sources may be registered based on the type of data contained herein, such that when a request is received that requires the return of a particular type of data, then only those data sources that match the data type need be accessed. Other means may include allowing third party data sources to advertise their data files for inclusion in the virtual database, allowing dynamic registration of third party sources. Additional embodiments that allow for the registration of third party sources with references will be apparent to those skilled in the art.

According to an embodiment, to better facilitate the process of linking multiple data sources, the virtual database environment may utilize foreign objects. Foreign objects may be considered map objects provided as third party data, i.e. they are foreign to the reference file. These foreign objects contain foreign properties and foreign relationships. The foreign relationship may exist between an object in the reference file and one of the third party objects, or may exist between two third party objects. Rather than importing these objects into a reference file to make them local, the virtual database environment keeps them as foreign objects. When the virtual map is subsequently created, a pointer or pointer-like mechanism is then used to provide the mapping. Depending on the implementation, various mappings may exist.

In a first type of mapping, the reference file does not contain its own map item instance, in which case the join operation may identify another source of the map item, and create a "shadow" of the item in the virtual database (and in some cases also display the shadow on the map), along with the attributes of the item and the relationship to all its neighbors plus all neighbors already in the reference file.

In a second type of mapping, the system allows recognition that there is a foreign object with some properties unknown to the reference file, but some instance of the foreign object already exists. In this case, the join operation does not import the object itself, but rather an attribute that is not already present in the reference file. This can be considered an import of properties rather than objects.

A third type of mapping may include a relationship between one foreign object and another foreign object. During the join operation, the virtual database may add those relationships to any other instance of the object already in the reference file.

It will be appreciated that these examples of mappings are the most commonly used examples, but other types of mappings may be used. It will also be appreciated that the term "foreign object" is more a label than anything else, since in a multi-source environment the term "foreign" depends to a large extent on which data sources are selected as references (all other databases will be "foreign"). As described above, in some cases, many data sources may themselves serve as reference files. Thus, the term "foreign object" has meaning only in the context of a particular embodiment.

According to an embodiment, the relationship between map items is not maintained by pointers, but instead by a Universal Location Reference Object (ULRO). ULRO is described in greater detail in pending U.S. patent application entitled "method and System FOR CREATING Universal LOCATION reference object (AMETHOD AMD SYSTEM FOR CREATING UNIVERSAL LOCATION REFERENCENGOBJECTS)" filed on 10.11.2005, entitled "11/271,436, and incorporated herein by reference. Many maps do not have the same electronic format, and thus in order to link objects from separate maps, the system typically must perform some form of translation. However, this can be a computationally expensive operation. The use of ULRO provides fast and efficient translation. This particular embodiment of the virtual database is useful in situations where, for example, a first party a identifies a map object as identifier X, which same object is understood by a second party B as identifier Y. Since the parties can change the way they identify their own map objects at any time and independently, it can be difficult to maintain a rigid pointer over different data sets. When using ULRO, all map objects in the reference file receive these codes, while all map objects in the foreign map also receive the codes. During the creation of the virtual database, the system only has to compare the code to detect matches between the various objects.

In the various examples provided below, the use of both pointers and generic location references to provide links between map objects is described. It will be appreciated that other implementations may use one, both, or a different one of these techniques. The virtual database technique is flexible enough that other forms of mapping can be utilized between different data sets.

VDB architecture

According to one embodiment, the system includes two or more databases (or more properly data sets or data sources) that together make up a virtual database environment. These databases include an integration database and an application database. The integration database may be a conventional database residing between references of digital map data providers and third party data sources, and integrates the references with the third party data using a combination of mappings, pointers, ULROs, or similar mechanisms. The application database then serves as a medium for the transfer of this data from the parties to the end user. Thus, the application database represents the available aspects of the VDB. Depending on the particular implementation, the application database may take a variety of different forms, some of which may be similar to traditional databases. Alternatively, the application database may use a data format other than the traditional database format, such as a web page or other such data presentation means.

FIG. 7 shows an illustration of a virtual database environment or system 2, according to an embodiment of the invention. As shown in fig. 7, the system comprises a virtual database 3, as well as a user interface 86 and a data output interface 88, which can be combined into a single interface. The system further comprises means 85 for communicating with a plurality of various data sources, according to an embodiment the system comprises an interface to the data source 84, which in turn comprises a link to each of the digital map provider's reference files or third party data sources. In response to a user request, or to transfer map data to another system, a selection of a data source is selected and the map data set of the data source is linked with the map data set of the reference file to create the integration database 80. Each map object within the various map data is linked to other map objects by a pointer, or in some embodiments, by a ULRO identifier, to populate the consolidation database. According to one embodiment, one data source is considered a reference file with local objects, while the other data sources are considered third party databases with foreign objects. Map objects provided as third party data may be considered "foreign objects" and may include foreign attributes and foreign relationships. Map objects may also be "partially foreign" in that some of their attributes are common with the reference file and some attributes are foreign. During the populating of the integration database, these extrinsic properties and extrinsic relationships are mapped between objects in the reference file and third party objects. Thus, the virtual database environment is a virtual linking of different sets of map data to create a virtual map structure 89 in memory, where all map items are linked to give the user the impression of a map with rich information. Unlike conventional map overlay processes, when using the virtual database approach, each subsequent set of data brought into the system is linked by its map item to some or all of the other map items already present in the collection, so that the map is truly a fully operational and interactive digital map.

As further shown in fig. 7, the virtual database environment includes an integration database 80 and an application database 82. According to one embodiment, the consolidated database may be a single conventional database, or similar data structure, and the application database is the delivery medium for all this data to the end user.

It should be noted that while the components described above include a virtual database system, this does not necessarily mean that the various components are stored on any one platform or in any one location. Indeed, it is possible that several components (in particular, the reference file and the third party database) may be stored and accessible from remote locations. Further, while the system shown in FIG. 7 includes an application database, other embodiments may utilize different data transport means, such as a web-based interface, a web package (XML message), an API function call, or some other form of data transfer.

FIG. 8 shows a flowchart of a process for using a virtual database environment according to an embodiment of the invention. As shown in fig. 8. The process includes a step 90 of accessing a reference file representing a set of locations. In step 91, the system determines which additional third party information sources may be needed and retrieves third party data or third party files into the system. In step 92, the system uses the consolidated database location code and other location information to match the information in the reference with third party data. In step 93, this linked set of data is used with the application database to create a virtual database. In step 94, the virtual map data may be provided to the requestor. In step 95, the updated links and information from the virtual database may be provided to both the reference file and third parties for subsequent use by those parties. As again noted above, in view of FIG. 8 illustrating the process of the system accessing a reference file, creating an appropriate link to a third party source, and using the resulting set of information to create a virtual database, it will be appreciated that in other embodiments, the integration of data may be performed in different ways. For example, according to some embodiments, a preliminary set of links to an initial third party data set may be created the first time a reference file or third party data is accessed. If more detailed information is needed, additional sources with additional data and additional links may be included to meet the more detailed needs.

Optional VDB enhancement

The above description describes embodiments of a virtual database environment. The virtual database may be implemented in different ways depending on the implementation, and may include a variety of optional components, including map format information, object references, tags, metadata, access registration systems, and several Application Program Interfaces (APIs) for third party data, version updates, geocoding services, application providers, address point update processes, and third party data-to-tag mapping. Each of these components and interfaces is described in further detail below. These features are not intended to be used or required in every embodiment.

Third party data API

According to an embodiment, the virtual database contains a third party data API. The third party data API allows third party data providers to transfer their data to the virtual database environment. More specifically, the third party data API allows foreign objects to be imported into the virtual database. A certain amount of information (e.g., a unique identifier) from each data provider is required to achieve proper cross-referencing. Sufficient address information must also be supplied if a third party requires the geocoding service of the digital map data provider. If geocoding is not necessary, object latitude and longitude (latitude/longitude) information should be supplied along with address information. Only the minimal details of those needed to geocode or locate the third party identifier need be stored in the virtual database. The actual details at the object or information presentation location may continue to be stored externally and controlled by third parties. According to some embodiments, the system may also utilize offset pointer addressing techniques described below: pending PCT application entitled "arrangement and method for two-dimensional and three-dimensional precision position and orientation determination (ARRANGEMENT FOR AND METHOD OF TWO DIMENSIONAL AND THREEDIMENSIONAL PRECISION LOCATION AND ORIENTATION DETERMINATION)" filed on 11/2006, pending PCT application No. PCT 2006/000552; pending PCT application No. PCT/NL2006/050264 entitled "METHOD AND APPARATUS FOR detecting AND locating PLANAR OBJECTS IN an image (METHOD AND APPATUS FOR DETECTION AND POSITION DETERMINATION OF PLANAR OBJECTS IN MAGES)" filed on 3.11.2006; AND pending PCT application No. PCT/NL2006/050269, entitled "METHOD AND APPARATUS for detecting OBJECTS FROM land-BASED movement mapping data" (METHOD AND APPARATUS for detecting OBJECTS FROM group project basic MOBILE MAPPING DATA) "filed on 30, 2006, AND the inventors of the above three pending PCT applications are Hans ulishi oerstmann (Hans Ulrich Otto) AND are incorporated herein by reference.

Third party data sharing scenarios

FIG. 9 shows an illustration of how third party data may be integrated with additional content in a virtual database with different confidence levels, according to an embodiment of the invention. As shown in fig. 9, depending on the particular embodiment, the various data sources and databases may include:

reference file database (TA DB). This provides geographic reference and address point retrieval and creation services.

Cross reference database (XREF). For content providers, XREF serves two purposes: describing content to potential application developers; and maintain links (geographical references) between their objects and reference files over time.

The content provider queries a database (CSQ). This database contains POI names, types and sub-types, keywords, addresses, tags and address point IDs, addresses, etc.; basically anything needed to complete a basic Location Based Service (LBS) query and return sufficient results so that a point can be displayed on a map. The database may be hosted at a specially designated data host or at the content provider's own site.

Content provider source database (CSS). This database contains the raw data that the content provider must provide to the VDB before being geo-referenced. The raw data will have many unique contents that are not available in the CSQ (unless they are merged into a CSSQ; see below), such as phone numbers, contacts, web pages, email addresses, faxes, text descriptions, etc.

The database may be accessed at different sites by using SOAP or another protocol's page services. For each class of database, there may be standard web service definitions to support the specific use. This then allows the system to support a number of interfaces, including:

TA2H — ("Tally atlas to host"). Made available to the services of the host of third-party content by a digital map provider (e.g., toliarlas). Allowing the host to register itself as a data provider, describe its data source, define rules for sharing its content with other VDB participants. The host is allowed to submit requests for new XREF tags, addressing points and other location references by submitting a subset of its own content.

H2TA — ("host to Taliazaras"). Made available to the services of a digital map provider (e.g., tailiadaras) by a host of third party content. Allowing the map provider to "push" an updated list (e.g., new or moved address points) to the content provider.

TA2AD — ("telia atlas to application developer"). Made available to the application developer's services by the map provider. Allowing application developers to register themselves on the content network and search for metadata about content providers that suit their needs. Allowing application developers to pay for the services of a particular content provider.

H2AD — ("host to application developer"). Made available to the application developer's services by the host of third party content.

If a content provider has two databases, one supporting LBS queries linked to a base map hosted at a third party site, and the other (the origin database) can use the origin schema available through id at its own site, they can communicate with the following web services: CS2H — ("content provider to host") and H2CS — ("host to content provider").

Fig. 9A illustrates an environment for sharing primary content using a standard CSQ database, the details of which are made available by the content provider in the original database. Content providers need to provide simple web services to query objects by ID and provide updates to CSQs. This is a better solution for highly dynamic data providers who do not want to modify their local databases.

Figure 9B illustrates an environment in which data may be made available to application developers via a CSSQ database in an extended mode (to include additional content from the vendor). Updates are made available by the content provider via a simple web service. This is a better solution for moderate dynamic data and content providers where the local database will not support end-user queries.

Figure 9C illustrates an environment in which data is made available to application developers via a CSSQ database in an extended standard mode (extended to include additional content from the vendor). This is an effective solution for data that is not highly dynamic.

Fig. 9D illustrates that the content provider uses its own database to manipulate its own data in any format as long as they support and are tuned to the network service. This is a better solution for technically sophisticated content providers that protect their dynamic content.

Fig. 9E illustrates an accumulator environment that makes content from multiple CSQs available from a single network service. Sometimes, for performance reasons, it is valuable to accumulate the content of multiple providers into a single database. Some application developers do this to ensure a particular level of service. Content from multiple volunteer providers may be accumulated into a single CSQ and made available through an H2AD interface, as shown in fig. 9E. This is particularly useful for accumulating similar content from distributed organizations (e.g., state governments), where accumulated CSQs may provide a wider coverage.

Map format translation

Many third party data sources use different and otherwise incompatible map formats. To address this issue, some form of mapping information may be provided within a Virtual Database (VDB) environment to translate this information into address points, Traffic Message Channel (TMC) location codes, and geocoding services. If a fixed map format is not used, a pointer, ULRO or other form of link may be used instead. According to one embodiment, the reference file contains address points and TMC location codes, which serve as permanent location references in the digital map. These references are then used to link and relocate third party data onto the digital map. For example, if an edge of a particular map object is moved, the address points related to that edge will move accordingly. This automatic repositioning minimizes the need to re-geocode third party data in response to revisions to the reference.

Address point

According to an embodiment, an address point may be provided. In a typical reference file or base map, not every location with an address will have an actual point in the map. For example, each of the street addresses "bartry street 1" and "bartry street 2" may not have its own discrete map points, but may be included in the more general range "bartry street 1-10". According to an embodiment, each of these map locations may be given its own discrete address point. Advantages of address points include ease of use and faster execution speed with reference to any particular location in the map. A disadvantage is that care must be taken when giving address points a large number of map locations, as the corresponding database can become quite large.

Enhanced consolidated database

According to one embodiment, the consolidated database provides the following additional functions: (1) registering online third party data objects in a central location (only the data necessary for registration needs to be stored at the center, most of which is maintained at the third party's site); (2) providing or creating (in some embodiments) a permanent location marker within the reference file for repositioning purposes; (3) annotate changes and differences in information (e.g., street address information) and report such changes to interested parties; (4) storing any relevant metadata about various third party data sources, what they contain, and how the third party data sources can be accessed and displayed; (5) allowing application developers to create relationships (including binary relationships, one-to-many relationships, and many-to-many relationships) between reference files and third-party data sources, and between different third-party data sources; and (6) providing automated relationship building services for geospatially related objects, according to one embodiment, the integration database accepts map identifiers (including address points, TMC locations, and other location information) from digital map providers and links this location information with third party data. The mapping may be returned to the third party data provider for its own purposes. While all proprietary third party data is saved at the source of each data provider, application developers can then utilize various APIs to retrieve digital map data from the map provider and merge it with the third party data to create the final product. Because the integration database is positioned between the reference file and the third-party database, the system allows the third-party data supplier to update the database according to the self issuing progress; allowing third parties to submit requests for location markers (described in further detail below) without those markers automatically becoming part of the reference document; defining ownership and responsibility for data objects, since the quality of data or information in third party data sources is still the responsibility of those third parties; avoiding the reference file interfering with anything other than what the digital map provider itself is responsible for maintaining; and allows the development of various databases and data sources to occur in parallel and largely independently of one another.

Object reference

According to one embodiment, any existing address points, location codes, and other location references may be extracted from pointer or ULRO information to provide a mechanism for linking third party data to a geographic location on a reference file. When third party data is geocoded onto a reference file, matching is performed to locate a corresponding address point. If an address identifier, such as an address point, is not present at the geocoded or provided location, a temporary address identifier or point may be created. This is useful to add features to addresses that may not already exist in the reference file to start with, for example, a particular building address (e.g., "bartrient street 220").

Marking

According to one embodiment, multiple tags may be provided in the aggregated database. A token is a record that refers to a single entity in one of the various databases or data sources participating in the virtual database environment. The markers make it easier to track changes to the digital reference files and third party databases, making periodic reintegration more reliable and efficient. According to one embodiment, various types of markers may be used, including location markers, object markers, and relationship markers.

Metadata

According to one embodiment, metadata information may be stored with the address points and tags. The metadata stores information about external third party data sources and facilitates seamless data integration between the virtual database and the application providers and data resellers. The metadata may contain, for example, the following information: data sources, connection information, content/mode, coverage area, and data quality, object type and category, and data specific relationship information (e.g., restaurant location and parking lot closest to the location). Not all embodiments of a virtual database environment utilize metadata.

Access registration system

Data providers may need sufficient protection of their data to ensure that their data continues to have commercial value, according to one embodiment, an access registration system is provided to maintain this level of security by creating constraints on which consumers or third parties can view their data and in which relationships between their data and other third party data providers may be allowed.

Version update API

According to one embodiment, a version update API is provided to allow the reference file to be easily updated with a new release cycle (using a "push" process to push data updates to the reference file, or a "pull" process that allows the virtual database system to pull the updated data into the reference file). By using the version update API, the reference file can be updated through a complete republishing of the map or through an incremental publishing process.

Geocoding service API

According to one embodiment, a geocoding service is provided to perform address cleanup/standardization and geocode addresses onto a provider's digital map with some automated and/or semi-automated means.

Application provider API

According to one embodiment, an application provider API is provided to allow third party application developers to access a virtual database and have a seamless view of the provider's map (reference file) integrated with all third party data.

Address point update procedure API

According to one embodiment, an address point update process API is included to allow requests from third parties to add additional address points to a reference file.

Third party data to tag mapping API

According to one embodiment, a third party data to tag mapping API is provided to allow third party data providers to obtain geocoding results to which tags and/or their data have been mapped.

ULRO-based virtual database environment

As described above, according to an embodiment, the system may utilize a permanent marker, referred to as a Universal Location Reference Object (ULRO) for map features. FIG. 10 shows an illustration of a virtual database environment or system according to another embodiment of the invention. According to this embodiment, the virtual database environment uses ULROs. As shown in fig. 10, the virtual database environment 2 includes reference file data 4 and third party data 6, which are linked together to form a virtual database 3. According to this embodiment, the reference file and third party file contain, respectively, ULRC 100, 102 associated with each geographic location 103, or data items associated with geographic location 105. As described in further detail in pending U.S. patent application No. 11/271,436 entitled "METHOD and system FOR CREATING a UNIVERSAL LOCATION reference object (a METHOD of and system FOR CREATING UNIVERSAL LOCATION reference object)" filed on 10.11.2005 and incorporated herein by reference, ULRO comprises a permanent identification code designed to identify a selected LOCATION. Also, a location may be associated with one or more geographic items, and a ULRO may be used to establish a traversable link or connection between a reference file and a third party file. According to one embodiment, ULROs 104, 106 are stored in ULRO library 98, which may or may not be part of the reference file data. ULRO comprises eight major components, some or all of which may be utilized depending on the particular implementation: (1) a set of name information; (2) a superset of coordinates; (3) a Universal Location Reference Code (ULRC) uniquely corresponding to the location; (4) a reference file pointer field comprising a reference file pointer; (5) a third-party file pointer field comprising one or more third-party file pointers; (6) a reference file back pointer field comprising a reference file back pointer; (7) a third-party file back-pointer field comprising one or more third-party file back-pointers; and (8) a metadata field.

Digital map provider and third party roles

As described above, the fundamental principle behind the VDB approach is to enable digital map providers to provide their consumers with highly reliable links between their digital maps and data belonging to multiple third party data providers. A useful side effect of the linking process is to provide feedback to improve the quality of data belonging to both the digital map data provider and its third party partners. Once a link is created between the third party data and the reference file, the link can be maintained indefinitely. The apparent persistence of these links makes it easier to integrate third party data between subsequent data versions.

Identification of third party data

The third party data object contains information needed to derive relationships between the third party data and the digital map provider data or between two or more third party data sources. While much of the content of these objects is handled in a generalized manner, whatever entity manipulates the virtual database, it should be familiar with the information that is particularly needed to create and maintain the relationships. The most important category of relationship is between examples of third party data objects and examples of map features, referred to herein as "links". Links can be used to locate third party map features relative to the transport element; tethering third party data to the segment of the delivered element; tethering the third party data to the map feature as a whole; and describes the relationship between map features.

Identifying content of third party data for linking

According to one embodiment, the third party data source must provide enough information to enable the VDB administrator to create the necessary links to his data. This information is then encoded into a database table in one form or another. Some of the types of information that may be provided include: (1) a link for locating a third party data object relative to a reference file delivery network; (2) links that involve segments of the transport network and that specify segments of the transport element to be linked to dynamic third party properties or other descriptive information; (3) a link connecting the third party data object to a map feature. This link is different from the previous category because it is a reference to the entire feature, not a reference to a single feature; and (4) links between map features. This allows the VDB administrator to integrate the relationships between map features from third party data sources.

VDB third party linking Process

As described above, according to one embodiment, information in a reference file may be linked with third party data in real time to form a virtual database. Fig. 11-18 show various steps in a method of creating and using a virtual database according to an embodiment of the invention. In particular, in FIG. 11, a permanent identifier is first assigned to a feature in a reference file of a digital map data provider.

In fig. 12, the location information (e.g., address or coordinates) is copied and transferred from the third party's database or data source into a temporary table in or associated with the reference file along with any third party object descriptors, ids, or link types, where applicable.

In fig. 13, the system uses a combination of automated tools (geocoding, database queries) and, if necessary, manual intervention to create links to references.

In fig. 14, the link created in the previous step is passed or transmitted to a third party. At this point, a third party software product or user interface may be established to utilize the link in a number of different ways, such as providing a virtual map to the end user.

The above steps may occur dynamically, i.e., in real time upon a request from a user or from another system to access a virtual map or map information. In some embodiments, the digital map provider may create the virtual map itself. This allows third parties to also create virtual maps, as the links can be passed to the third parties. As described above, the creation of a virtual map may be a step-by-step process in which some preliminary information is returned in response to an initial request, and subsequent information is returned in response to a more specific request.

In FIG. 15, the system is now in a steady state, which allows for maintenance by the parties to their respective data sets. The digital map data provider is responsible for annotating changes in the links due to any modification, deletion, and creation of map features in its own data set (i.e., reference file). The third party is similarly responsible for annotating changes in the link due to deletion or relocation of data objects within its data set (i.e., the third party data file).

In FIG. 16, the system allows resynchronization, for example if the information has changed in a third party file, and the third party passes the updated list of locations and broken links to the digital map data provider.

In fig. 17, the system allows repair. Unneeded links are removed from the reference file. New links are regenerated as well as links in any of the databases that are broken due to some change.

In FIG. 18, the system re-communicates any updated links and other information to the third party. This ensures that map data from multiple data sources will be consistent when the virtual database is populated in response to a user request. Also, at this point a software product, user interface or functional API may be established that utilizes the new link. In particular, since the third party also receives updated information, the third party benefits from being able to use this updated information in its own software product.

FIGS. 19 through 26 show various steps in a method of creating and using a virtual database using ULROs according to another embodiment of the invention. Fig. 19 to 26 largely duplicate the operations of fig. 11 to 18, respectively. The difference here is that instead of a standard map format, a pointer map, or some other form of mapping, ULROs are used instead to form the basis for creating links. Additionally, the ULRO is stored in a ULRO library, which is shown in fig. 19-26 with a digital map provider, but can be located anywhere in the system, including independent of the map provider or a third party. The ULRO library maintains links within the ULRO, which are automatically updated when necessary. In most other respects, the steps are the same, i.e., fig. 19 shows the system assigning and maintaining a permanent identifier, now in the form of a ULRO, to a feature in a digital map data provider map (reference). In fig. 20, the system copies location information (e.g., address or coordinates) from a third party's database into a corresponding one of the ULROs, along with a third party object descriptor, ID, and link type (where applicable). In fig. 21, the system uses a combination of automated tools (geocoding, database queries) and, if necessary, manual intervention to create links to the reference files. At this point, the ULRO is assigned to a third party map object, if necessary, given a similar identifier (which may be the ULRC in a ULRO implementation) to the same object in the reference. ULRO is described in further detail in pending U.S. patent application entitled "METHOD and System FOR CREATING Universal position reference object (A METHOD AMD SYSTEM FOR CREATING UNIVERSALLOCATION REFERENCE OBJECTS)" filed on 10.11/2005, entitled "11/271,436, and incorporated herein by reference. In FIG. 22, the link created or copied to the ULRO pointer field in the previous step is passed to the third party. At this point, a software product or user interface can be established to utilize the link in a number of different ways. As with the embodiments described above, the above steps may also occur dynamically, i.e., in real-time upon a request from a user or from another system to access a virtual map or map information. In some embodiments, the digital map provider may create the virtual map itself, or a third party may create the virtual map as well, as the link may be communicated to the third party. In fig. 23, the system allows different data sets to be maintained by the party responsible for the particular data set. The digital map data provider is responsible for annotating changes in the links due to any modification, deletion, and creation of map features. The third party is responsible for annotating changes in the link due to deletion or relocation of data objects within its (third party) data. Simple changes in third party data, such as modifying attributes of features within a map, may not require any changes to the links themselves, as the same links will be used to traverse to the new attributes when the virtual database is generated. In fig. 24, the system allows resynchronization, where a third party passes an updated list of locations and broken links to the digital map data provider. In FIG. 25, the system allows for repairs where unneeded links are removed from the reference file. In FIG. 26, the system re-communicates the updated link to the third party. However, since ULROs are dynamic features and may exist independently of map providers or third parties; and further since the ULRO library maintains links within the ULROs, automatically updating the links as necessary, the latter few steps shown in FIGS. 24-26 are unnecessary according to most embodiments. Finally, as also described above, since the third party also receives the updated information, the third party benefits from being able to use this updated information in its own software product. At this point, a software product or user interface may be established to utilize the new link.

In all of the examples described above, the link update process is shown between a reference file and a single third party file. However, it will be appreciated that in other embodiments, the link update may occur in the opposite direction, i.e., starting with an update at the third party file and then updating the reference file. Additionally, while the examples illustrated above show a link update process between a reference file and a single third-party file, it will be appreciated that link updates may occur between a reference file and many third-party files, or between one third-party file and another third-party file. As discussed above, these headings are intended as descriptive labels and not anything else, as in other embodiments, any of the data files or data sources may act as third party files, treating the other data files as references.

Examples of VDB use

Fig. 27-28 show an illustration of one embodiment when a VDB system can be used to provide map information to an end user in an actual life situation. As shown in fig. 27, a map provider (e.g., tolira atlas) provides a reference file, or a set of equivalent digital map data. Third party data providers (only one of which is shown here) provide information about a set of points of interest (POIs). The term "point of interest" as used herein may also be used to refer to lines, areas, complexes, and other map features, not necessarily just points. The new POI may be transmitted to the map provider and eventually incorporated into the reference file. In response to a request from an end-user, information from the map provider (reference) is integrated with information from a third party and delivered to the end-user via an application of the application vendor.

As shown in fig. 28, the virtual database environment allows the reference file map to be updated independently of third party points of interest (POIs). The third party data provider updates its database according to its own needs and gets the tags from the map provider for each new or updated POI. The POI server takes care of communicating POI updates to the application server, which in this case acts as both an integration server and a delivery vehicle for the end user. In response to a user request, the application server provides the appropriately updated and integrated information. Depending on the particular embodiment, the updates may be pushed to or pulled from the end user 474. By using this update technique, POIs and associated content can be intelligently searched and examined before selection is made in response to a particular user request. When creating an application, a third party application may be shipped with media containing the most up-to-date POI data available from the POI source.

The foregoing description of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art.

As will be appreciated by those skilled in the computer art, the present invention may be conveniently implemented using a conventional general purpose or a specialized digital computer or microprocessor coded according to the techniques of the present disclosure. Appropriate software coding can readily be prepared by skilled programmers based on the teachings of the present disclosure, as will be apparent to those skilled in the software art. The invention may also be implemented by the preparation of application specific integrated circuits or by interconnecting an appropriate network of conventional component circuits, as will be readily apparent to those skilled in the art.

The present invention includes a computer program product which is a storage medium having stored thereon/therein instructions which can be used to program a computer to perform any of the processes of the present invention. The storage medium may include, but is not limited to, any type of disk including floppy disks, optical disks, DVDs, CD-ROMs, microdrives, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, DRAMs, VRAMs, flash memory devices, magnetic or optical cards, nanosystems (including molecular memory ICs), or any type of media or device suitable for storing instructions and/or data.

Stored on any one of the computer-readable media, the invention includes software for controlling both a general purpose/special purpose computer or a microprocessor, and for enabling the computer or microprocessor to interact with a human user or other mechanism utilizing the results of the invention. Such software may include, but is not limited to, device drivers, operating systems, and user applications. Finally, this computer-readable medium further includes software for performing the present invention, as described above.

Included in the programming (software) of a general/special purpose computer or microprocessor are software modules for implementing the teachings of the present invention, including, but not limited to, capturing and annotating media streams, generating timelines of valid note events, linking still frames to points in segments of media streams or segments of media streams, recognizing any sliding changes, generation and distribution of media data describing at least a portion of a media stream, and communicating results in accordance with the processes of the present invention.

The foregoing description of the invention has been presented for purposes of illustration and description. The embodiments were chosen and described in order to best explain the principles of the invention and its practical applications, to thereby enable others skilled in the art to understand the invention for various embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalents.

Claims (22)

1. A system for providing digital map data in a virtual database format, comprising:

electronic map data covering a map area and including location codes for features within the map;

an interface that allows third party data to be received into the system, wherein the third party data defines additional feature information for some or all of the features that are geographically located within the map region;

an integration database linking location codes in the electronic map data with corresponding feature information in the third party data and providing the linked information as a virtual database.

2. The system of claim 1, wherein the virtual database is also electronic map data and is used to generate a map display within which the feature information provided by the third party data is included.

3. The system of claim 1, wherein the location reference is a generic location reference uniquely assigned to each particular map location.

4. The system of claim 1, wherein the third party data is independently maintainable by a third party and combined with the electronic map data at runtime or upon request to create the virtual database.

5. The system of claim 1, wherein the system includes the third party data.

6. The system of claim 1, wherein the system receives the third party data from an external third party source via a network or other connection.

7. The system of claim 6, wherein the network or other connection is the internet.

8. The system of claim 1, wherein the system receives information from multiple third parties simultaneously.

9. The system of claim 1, wherein the system dynamically creates the virtual database upon receiving real-time data from the third party or upon request from a user.

10. The system of claim 1, wherein the virtual database is automatically updated independent of other data sources by updates to a portion or all of the electronic map data or the third party data.

11. A method for providing digital map data in a virtual database format, comprising the steps of:

providing electronic map data covering a map area and including location codes for features within the map;

receiving third party data, wherein the third party data defines additional feature information for some or all of the features that are geographically located within the map region; and

presenting the linked information as a virtual database using an integration database linking location codes in the electronic map data with corresponding feature information in the third party data.

12. The method of claim 11, wherein the virtual database is also electronic map data and is used to generate a map display within which the feature information provided by the third party data is included.

13. The method of claim 11, wherein the location reference is a generic location reference uniquely assigned to each particular map location.

14. The method of claim 11, wherein the third party data is independently maintainable by a third party and combined with the electronic map data at runtime or upon request to create the virtual database.

15. The method of claim 11, wherein the system includes the third party data.

16. The method of claim 11, wherein the system receives the third party data from an external third party source via a network or other connection.

17. The method of claim 16, wherein the network or other connection is the internet.

18. The method of claim 11, wherein the system receives information from multiple third parties simultaneously.

19. The method of claim 11, wherein the system dynamically creates the virtual database upon receiving real-time data from the third party or upon request from a user.

20. The method of claim 11, wherein the virtual database is automatically updated independent of other data sources by updates to a portion or all of the electronic map data or the third party data.

21. A computer-readable medium comprising instructions stored thereon that, when executed, cause the computer to perform the steps of:

providing electronic map data covering a map area and including location codes for features within the map;

receiving third party data, wherein the third party data defines additional feature information for some or all of the features that are geographically located within the map region; and

presenting the linked information as a virtual database using an integration database linking location codes in the electronic map data with corresponding feature information in the third party data.

22. A system for providing digital map data in a virtual database format, comprising:

a reference database including data covering a map area and including location codes for objects within the map;

one or more third party databases characterizing data of objects that may appear in the map;

a virtual database that provides end-users with data that includes linked information from the reference database and the one or more third-party databases, such that the users can query the virtual database to determine information and relationships between objects in the reference database and objects in the one or more third-party data.