US20100250599A1 - Method and apparatus for integration of community-provided place data - Google Patents

Abstract

An approach is provided for integrating place metadata provided by a community of metadata builders, including receiving registration data that indicates one or more values for a corresponding one or more attributes that describe a place. A place is associated with a geographic location. Providing an indication of match between the registration data and metadata for a predetermined place is also initiated. In some embodiments, a new entry for a set of predetermined places is generated based on validating the registration data and a negligible degree of match. In some embodiments, a unique identifier for the place is included in indication of match for either a new place represented by the registration data or a matching predetermined place.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS
• This application claims benefit as a Continuation-in-part of application Ser. No. 12/414,101, filed Mar. 30, 2009, under 35 U.S.C. §120.
BACKGROUND
• The use of wireless, mobile communication devices has become pervasive, and is rapidly overtaking the use of traditional wired devices. As users' mobility increases, there is an increasing demand for content associated with the user's past, current or expected future location. For example, a popular application is determining restaurants or banks or other retail outlets in proximity to a user's past, current or expected future location. However, those service providers attempting to provide such location-based content are confronted with many challenges, including the consumption of vast resources to assemble and quality control the location-based content data for an extensive region or for global coverage.
SOME EXAMPLE EMBODIMENTS
• Therefore, there is a need for improved formation of location based content.
• According to one embodiment, a computer-readable storage medium carries instructions which, when executed by a processor, cause an apparatus to at least perform receiving registration data that indicates one or more values for corresponding attributes that describe a place that is associated with a geographic location. An indication of a match between the registration data and metadata for a predetermined place is provided.
• According to another embodiment, an apparatus comprises a processor and a memory storing executable instructions that if executed cause the apparatus to receive registration data that indicates one or more values for corresponding attributes that describe a place that is associated with a geographic location. An indication of a match between the registration data and metadata for a predetermined place is provided
• According to another embodiment, an apparatus comprises means for receiving registration data that indicates one or more values for corresponding attributes that describe a place that is associated with a geographic location. The apparatus includes means for providing an indication of a match between the registration data and metadata for a predetermined place.
• According to another embodiment, a method includes receiving registration data that indicates a value for a subset of place metadata that includes a plurality of attributes that describe a place that is associated with a geographic location. The method also includes providing an indication of a match between the registration data and metadata for a predetermined place.
• According to another embodiment, an apparatus comprises means for receiving registration data that indicates a value for a subset of place metadata that includes a plurality of attributes that describe a place that is associated with a geographic location. The apparatus also includes means for providing an indication of a match between the registration data and metadata for a predetermined place.
• Still other aspects, features, and advantages of the invention are readily apparent from the following detailed description, simply by illustrating a number of particular embodiments and implementations, including the best mode contemplated for carrying out the invention. The invention is also capable of other and different embodiments, and its several details can be modified in various obvious respects, all without departing from the spirit and scope of the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive.
BRIEF DESCRIPTION OF THE DRAWINGS
• The embodiments of the invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings, in which:
• FIG. 1 is a diagram of a system for integrating place metadata from a community of place builders, according to one embodiment;
• FIG. 2A is a diagram of an entry for a place metadata data structure, according to one embodiment;
• FIG. 2B illustrates example core categories, according to one embodiment;
• FIG. 2C andFIG. 2D illustrate an example XML document holding example place metadata, according to one embodiment;
• FIG. 3A is a diagram of a place registration message, according to one embodiment;
• FIG. 3B is a diagram of a place response message with a single place identifier, according to one embodiment;
• FIG. 3C is a diagram of a place response error message, according to one embodiment;
• FIG. 3D is a diagram of a place response message with one or more candidate places, according to one embodiment;
• FIG. 4A is a diagram of a message for selecting a candidate, according to one embodiment;
• FIG. 4B is a diagram of a message for requesting a place resource, according to one embodiment;
• FIG. 5A is a flowchart of a process at a place metadata service, according to one embodiment;
• FIG. 5B is a flowchart of a process at a permanent place ID service, according to one embodiment;
• FIG. 6A is a time sequence diagram that illustrates a sequence of messages and processes for accessing place metadata, according to one embodiment;
• FIG. 6B is a time sequence diagram that illustrates a sequence of messages and processes for registering a valid new place, according to one embodiment;
• FIG. 6C is a time sequence diagram that illustrates a sequence of messages and processes for registering a matched place, according to one embodiment;
• FIG. 6D is a time sequence diagram that illustrates a sequence of messages and processes for registering a partially matched place, according to one embodiment;
• FIG. 6E is a time sequence diagram that illustrates a sequence of messages and processes for registering a partially valid place, according to one embodiment;
• FIG. 7 is a diagram of hardware that can be used to implement an embodiment of the invention;
• FIG. 8 is a diagram of a chip set that can be used to implement an embodiment of the invention; and
• FIG. 9 is a diagram of a terminal that can be used to implement an embodiment of the invention.
DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS
• A method, apparatus, and software are disclosed for integration of community provided place data. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the embodiments of the invention. It is apparent, however, to one skilled in the art that the embodiments of the invention may be practiced without these specific details or with an equivalent arrangement. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the embodiments of the invention.
• Although several embodiments of the invention are discussed with respect to exchanging place metadata using extended markup language (XML) embedded in hypertext transfer protocol (HTTP) messages transmitted over a network between one client and two place service modules, a permanent place ID service and a place metadata service, embodiments of the invention are not limited to this context. It is explicitly anticipated that the metadata may be exchanged using any collection of attributes and values embedded in any network protocol or human interface between a community member and one or more processes operating on one or more computing devices with or without a network.
• As used herein the term “place” refers to the semantics/usage of a location. Although a place is always associated with a location, it is an object independent of a location. That is, a place (such as a restaurant or business) might change its physical location (i.e. geographic coordinates) over time and multiple places (such as a hotel and a restaurant) might be associated with the same location. Thus, a place is associated temporally and spatially with a geographic location. A particular place is distinguished from other places by a collection of values (place metadata) for a corresponding set of attributes (place metadata parameters) that uniquely indicate the place. In addition to the place metadata that uniquely indicates a particular place, there are place resources in some embodiments.
• Many organizations provide location related content and services (e.g. business directories, geographic information systems, restaurant guides, hotel booking services). Each of these organizations manages its specific set of metadata for its locations. Neither is this set of metadata standardized, nor does there exist an easy way to check whether two sets of metadata from independent organizations refer to the same location. Aggregation of metadata from various sources is a common task for many of these organizations. To ensure data quality and integrity, every organization has to implement data validation, enrichment, and duplicate removal on its own. On top of that, the community of place building organizations has to continuously revalidate their existing metadata (e.g. to identify entries that went out of business or moved to a different location. Therefore, there is a need for a system to integrate community-provided place data to assure data quality and avoid duplication.
• In some embodiments, place resources for a single place are provided as one or more network resources, such as a collection of one or more files or directories or web pages, which is accessed by corresponding universal resource locator (URL) names. A domain name server (DNS) on a network resolves URL names into Internet Protocol (IP) addresses that are used to route messages sent across an IP network, as is well known in the art. Thus a user of a web browser can access those place resources, once given the URL names. In some embodiments, the place resources are not maintained separately from a central database of palce metadata.
• According to some embodiments, a set of web services called Place Namespace Services (PNSS) provide services related to integrating data to support the concept of a place. In a particular embodiment, the PNSS includes several modules. A Permanent Place ID Service (PPIDS) creates and finds unique identifiers (IDs) for a place. This service tries to avoid creating duplicate places (creating multiple place IDs for the same physical place) by using matching logic (by comparing the metadata attributes of a place). Duplicate avoidance cannot be guaranteed, therefore PPIDS provides a way to merge place IDs as metadata becomes available, which indicates the place IDs refer to the same place. The merge is accomplished by marking one of the place IDs as merged. This service still guarantees that a place will remain accessible by any ID that was once assigned to that place. A Place Metadata Service (PMDS) stores and finds a standardized set of core metadata associated with places. In some embodiments, a Place Resource Service (PRS) binds web resources (as URLs) to a place, and a Global Place Name Service (GPNS) registers a globally unique name, called a place ID, for a place. In many embodiments, the processes performed by these latter two modules are omitted or incorporated in one of the other depicted modules. For example, the function of the GPNS is included in thePPIDS133 in some embodiments.
• In some embodiments, the PNSS checks place metadata validity and avoids duplication by recognizing when place metadata for a new place resource closely matches place metadata for an existing place resource. Having access to the PNSS relieves organizations from maintaining the core metadata of their places on their own. PNSS takes the burden to validate and enrich a place's core metadata, provides mechanisms to avoid duplicate creation and merge existing duplicates and allows organizations to register their own resources and services related to a place in a publicly accessible directory. By allowing several builders to contribute to the same shared place resources, a single builder's efforts are leveraged to gain access to a much broader scope of place data than would be possible to build alone. On top of that, all organizations that provide resources (e.g. services or content) related to places can use the place ID to interconnect their resources.
• The core problem that the PNSS has to solve, in these embodiments, is to identify a place based on the specific, potentially incomplete or even invalid set of metadata that users of the PNSS can provide. This feature is implemented in the PPIDS. To identify a place (and get its place ID) a user of the PNSS has to execute the register function of the PPIDS. This function expects some place metadata (at least name, location and category) and matches this data against predetermined place metadata known to the PNSS. In case there exists a perfect matching place in the PNSS, the PPIDS will return the place ID of this entry. Since one can't expect that the data provided by the user matches exactly to place metadata stored in the PNSS (e.g. due to slightly different names, names in different languages, different category-levels, partially wrong address, outdated address), only returning exact matches would prevent the core task of the service to avoid creation of duplicate entries for the same place.
• To address this problem, in some embodiments, PPIDS implements some fuzzy matching algorithm that matches places even if the metadata of the known places don't match exactly the metadata provided during registration. In this case PPIDS has to calculate some “quality-of-match” value, or degree of match value, that gives the user some hint about how close the data of each returned place is to the registration metadata the user did provide.
• In an illustrated embodiment, the fuzzy matching algorithm contains various components including location identification, category definition, name resolution, vicinity detection, and previous selection tracking. Location identification is based on commercially available address resolution services, such as the location reference object (LRO) digital map service of NAVTEQ™, and allows PPIDS to validate, enrich and identify the location of a place indicated by registration metadata. Category matching is performed by modelling categories of places as a combination of managed, globally-applicable “top level categories” and allowing additional arbitrary free text tags. Name matching is performed by maintaining multiple names that might be used to identify a place (both alternative names and translated names) and applying some word similarity measure, such as those used in spell checking algorithms. Vicinity matching (also called “nearby matching”) is employed because not all places are addressable by a unique address (or a PNSS user might not have the valid address). Thus PPIDS implements some vicinity search that checks for matches with places that are located near the provided address or geolocation coordinates. Previous selection matching is performed in case the user provides metadata that differs from the required metadata, because a prior registration attempt might have the missing metadata. Thus previous registration requests are stored for each user or group of users.
• Based on output from the various components of the matching algorithms, in the illustrated embodiment, PPIDS calculates the overall “quality-of-match” or degree of match for each of the predetermined places. PPIDS returns data identifying a list of one or more candidate places that demonstrate a degree of match value above a predetermined threshold. This list might also include a candidate for a new entry derived from the registration metadata, e.g., by correcting evident misspellings or transposed numerals. The PPIDS also returns, for each candidate in the list, a candidate token that indicates a difference between the registration metadata and the candidate place metadata. The user then selects one of the candidates, such as by executing a “selectCandidate” function of PPIDS, by submitting the candidate token for the selected candidate. PPIDS then returns the new or previously existing (extant) place ID of the selected candidate. Based on the token for the selected candidate, the PPIDS is able to “learn” which metadata was used identify a place and automatically create some additional matching metrics and heuristics to score the differences indicated in the token. These metric may be applied to future registration efforts by the same user or future registration efforts by several or all users.
• FIG. 1 is a diagram of asystem100 for integrating place metadata from a community of place builders, according to one embodiment. Thesystem100 includes acommunications network105, and network nodes that includemobile terminal120, place namespace service (PNSS) hosts130 andother host140. Community members operate onmobile terminal120 orother host140 and have their metadata properly integrated by the modules on the PNSS hosts130.
• In various embodiments,nodes120,130,140 can be any type of fixed terminal, mobile terminal, or portable terminal including desktop computers, laptop computers, handsets, stations, units, devices, multimedia tablets, Internet nodes, communicators, Personal Digital Assistants (PDAs), mobile phones, mobile communication devices, audio/video players, digital cameras/camcorders, televisions, digital video recorders, game devices, positioning devices, rack-mounted computers or computer blade systems, or any combination thereof. Moreover, the nodes may have a hard-wired energy source (e.g., a plug-in power adapter), a limited energy source (e.g., a battery), or both. It is further contemplated that thenodes120,131,140 can support any type of interface to the user (such as “wearable” circuitry, etc.). In the illustrated embodiment,node120 is a wireless mobile terminal (also called a mobile station and described in more detail below with reference toFIG. 10). Themobile terminal120 is connected to network105 by awireless link107.
• Community-sharedplace resources103 that describe or provide services related to places reside on nodes innetwork105 in the illustrated embodiment. In some embodiments, sharedplace resources103 are omitted.
• By way of example, thecommunication network105 ofsystem100 can include, in various embodiments, one or more wired and/or wireless networks such as a data network (not shown), a wireless network (not shown), a telephony network (not shown), or any combination thereof, each comprised of zero or more nodes. It is contemplated that the data network may be any local area network (LAN), metropolitan area network (MAN), wide area network (WAN), the Internet, or any other suitable packet-switched network, such as a commercially owned, proprietary packet-switched network, e.g., a proprietary cable or fiber-optic network, or any combination thereof. In addition, the wireless network may be, for example, a cellular network and may employ various technologies including code division multiple access (CDMA), enhanced data rates for global evolution (EDGE), general packet radio service (GPRS), global system for mobile communications (GSM), Internet protocol multimedia subsystem (IMS), universal mobile telecommunications system (UMTS), etc., as well as any other suitable wireless medium, e.g., microwave access (WiMAX), Long Term Evolution (LTE) networks, wireless fidelity (WiFi), satellite, and the like. In various embodiments,communication network105, or portions thereof, can support communication using any protocol, for example, the Internet Protocol (IP).
• The client-server model of computer process interaction is widely known and used. According to the client-server model, a client process sends a message including a request to a server process, and the server process responds by providing a service. The server process may also return a message with a response to the client process. Often the client process and server process execute on different computer devices, called hosts, and communicate via a network using one or more protocols for network communications. The term “server” is conventionally used to refer to the process that provides the service, or the host computer on which the process operates. Similarly, the term “client” is conventionally used to refer to the process that makes the request, or the host computer on which the process operates. As used herein, the terms “client” and “server” refer to the processes, rather than the host computers, unless otherwise clear from the context. In addition, the process performed by a server can be broken up to run as multiple processes on multiple hosts (sometimes called tiers) for reasons that include reliability, scalability, redundancy, and regional partitioning, among others. A well known client process available on most nodes connected to a communications network is a World Wide Web client (called a “web browser,” or simply “browser”) that interacts through messages formatted according to the hypertext transfer protocol (HTTP) with any of a large number of servers called World Wide Web servers that provide web pages. In the illustrated embodiment,mobile terminal120 andother host140 includebrowser117aandbrowser117b,respectively; and hosts130 includeweb server119.
• As depicted inFIG. 1, in the illustrated embodiment, PNSS hosts130 includeweb server119, Place Metadata Service (PMDS)module131, Permanent Place identifier (ID) Service (PPIDS)module133, Place Resources Service (PRS)module135, and Global Place Name Service (GPNS)module136, all described above. One or more of these modules access a place metadata data structure, such asplace metadata database137. The place metadata data structure includes aplace entry139 for every different place registered with the PNSS. In an illustrated embodiment, PPIDS, PMDS and PRS are web services that provide an HTTP based application programming interface (API) that follows the design principles for RESTful web services. In some embodiments, such services are accessed by a browser117 with a human operator providing manual input required by the API. Currently, no standard browser directly supports the HTTP-PUT operation or is capable of directly creating XML messages, so in such embodiments, the service is accessed with the help of a JavaScript based browser extension. Alternatively, a special place building client process, e.g.,PNSS client121, can automatically provide some or all of the input required by the API using one or more HTTP messages. It is expected that the number of places that are going to be managed might one day extend the capabilities of a single host. Therefore in some embodimentsmultiple hosts130 are deployed acrossnetwork105, each host responsible for a specific “area” of the world
• In the illustrated embodiment, the modules of PNSS hosts130 are the centralized services invoked by a community of place builders distributed acrossnetwork105, such as an operator ofmobile terminal120 orother host140.Mobile terminal120 includes aPNSS client121a,andother host140 includesPNSS client121b,collectively referenced hereinafter asPNSS client121. ThePNSS client121 interacts with one or more modules on PNSS hosts130 to allow a user to submit place metadata for registration with the PNSS and obtain the unique place ID for the place indicated by the metadata.
• According to the illustrated embodiment, armed with the place ID for a place, a user can identify aparticular place resource103 where information and service about that place are located on thenetwork105, such as by the URL for a webpage of links to descriptions and services for that place. Such a webpage can be accessed by the browser117 on the user's node based on that URL in some embodiments. In other embodiments,separate place resources105 are not used.
• Although a particular set of nodes, processes, and data structures are shown inFIG. 1 for purposes of illustration, in various other embodiments more or fewer nodes, processes and data structures are involved. Furthermore, although processes and data structures are depicted as particular blocks in a particular arrangement for purposes of illustration, in other embodiments each process or data structure, or portions thereof, may be separated or combined or arranged in some other fashion. For example, in some embodiments, thePRS135 andGPNS136 are included inPMDS131 andPPIDS133, respectively; andPPIDS133 is embedded in aweb server119; and thePNSS client121 includes a browser117.
• FIG. 2A is a diagram of anentry201 for a place metadata data structure, according to one embodiment. Theentry201 embodies a model for place metadata that allows the detection of duplicates. The placedata structure entry201 includes aplace ID field203, aplace URL field205, mergedplace IDs field207, place category fields211,place names field221, place location fields231 and place contact fields241. Example values for some of these fields are presented inFIG. 2B,FIG. 2C andFIG. 2D, described in more detail below.
• In some embodiments, place metadata is transferred from one node to another in one or more HTTP messages. One manner for transporting place metadata in an HTTP message is to include the place metadata in an extended markup language (XML) document. XML documents allow values for any of one or more predefined parameters in a dictionary to be exchanged among nodes that have access to that dictionary. XML parameters can be nested and, for any level of nesting, can be listed in any order.FIG. 2C andFIG. 2D illustrate an example XML document holding example place metadata; according to one embodiment. As is well known in the art, an XML parameter value is given between a parameter start indicator <name> and a parameter end indicator </name> where name represents the parameter name. This example document does not include a mergedplace IDs field207 orother contact field249.
• In the illustrated embodiment, the place ID field holds data that indicates the unique identifier for a particular place. In some embodiments, theplace URL field205 holds data that indicates aprimary place resource103 on the network for obtaining information and services related to the place. Links to multiple other resources, if any, related to that place are found at the primary place resource.
• In some embodiments, the primary place resource is a web page hosted by the organization that registered the place and named using the place ID. For example, inFIG. 2C, the place ID is 184385761, and the place resource is a web page (using HTTP) named 184385761 in directory homePlace at domain organization.com as given by the value of the URL in the start indicator for the place parameter. The URL included in the xml-place representation is the URL to the PMDS-instance that did provide the place metadata representation (a kind of self reference). This becomes especially important in case the PMDS is regionally partitioned across multiple hosts as described above. In some embodiments, place resources are managed independently from the core attributes in the PRS. In these embodiments, the shared element between PMDS and PRS is the placeID.
• The mergedplace IDs field207 holds data indicating the place IDs, if any, for metadata entries that were originally distinct but were subsequently identified as the same place as the place described inentry201. In other embodiments, when a place gets merged, data indicating the target place with which the current place is merged is indicated in thefield207, i.e., a forward reference, linking to the target place which will be the remaining place. Any attempt to a “merged” place will result in an immediate redirect to the target place. That way the placeID remains usable, but only the target placeID is returned.
• In the illustrated embodiment, the categories fields211 include managedcategories field213, free-form categories field215 and free-form language field217. In the illustrated embodiment, PNSS introduces a very small core category tree that is centrally managed to support distinction of places that share the same address (e.g. a hotel that resides in a famous building; restaurant within a hotel) when the names might not allow a comparison due to different languages or entries by different users at different times. Every core category is maintained in a category data structure and contains a unique identifier, a semantic description and a list of tags that name the categories in various languages. Published category systems (e.g. EuroStat, GNS Feature Codes) that are centrally managed are mapped to the PNSS core categories. Each such extended category belongs to a single category system that is managed by a single provider. The semantic concepts that define a category are collected in a dictionary. Every place is associated with at least one of these core categories, as indicated by a category ID in the managedcategory field213.FIG. 2B illustrates example core categories, according to one embodiment. For example, inFIG. 2C, the categories are “Bar” and “Restaurant” but should also include the core category “dining” fromFIG. 2B.
• In the illustrated embodiment, PNSS allows assigning arbitrary category tags (a free text keyword and its language) to a place. PNSS users are free to assign their own categories through tags to a place. Translations of concepts associated with a category are stored as tags. These arbitrary tags and their associated languages are indicated by the data in the free-form categories field215 and free-form language field217. The Bar and Restaurant categories can be treated as arbitrary tags depicted inFIG. 2C.
• In the illustrated embodiment, the names fields221 hold data that indicates a name of the place and zero or more alternatives, and includesdefault language field223,default name field225 and alternative names/languages field227. Thedefault language field223 holds data that indicates the default language used for the names and address of the place. For example, the default language is the predominant language spoken at the location of the place. In some embodiments the default language is another choice, such as English, which is widely spoken throughout the world. InFIG. 2C, the default language is German (Deutsch, represented by the abbreviation “de”) in the start indicator for the defaultName parameter. Thedefault name field225 holds data that indicates the default name for the place in the default language. InFIG. 2C, the default name is “Türkische Kneipe” (which means Turkish Restaurant in the default language, German).
• In the illustrated embodiment, the alternative names/languages field227 holds data that indicates other names for the place and the associated language. Thus a different alphabet/character associated with the different language can also be used to name and therefore subsequently identify the place. Similarly, different names in the same language can be indicated infield227. InFIG. 2C, the alternative names include the English name “Turkish Restaurant” in English, represented by the abbreviation “en.” Two German language alternative names for the restaurant are also indicated inFIG. 2C.
• In the illustrated embodiment, the location fields231 hold data that indicates a geographic location of the place, and includesaddress field233, exonyms for address elements field235 (where exonyms refer to names in different languages) andgeographic coordinates field237. Theaddress field233 holds data that indicates the postal address of a place in the default language. For example, inFIG. 2D, the German language address is “12 Invalidenstr. Berlin 72145 Del.” as indicated in separate XML parameters for houseNumber, street, city, region, zipCode, and country.
• In the illustrated embodiment, the exonyms for address elements field235 holds data that indicates names for address elements in different languages than the default or local language. The exonym field also indicates the language, such as by the abbreviation “en” for English. For example, inFIG. 2D, the English language street name is “Invaliden Street” as indicated by the data in the XML exonyms parameter.
• In the illustrated embodiment, thegeographic coordinates field237 holds data that indicates the geographic position of the place, such as Global Positioning System (GPS) coordinates or latitude and longitude values with sufficient precision. For example, in FIG2D, the latitude is 15.22122 degrees (positive degrees signify North) and the longitude is 17.33333 degrees (positive degrees signify East), as indicated by values in separate XML parameters.
• In the illustrated embodiment, the contact fields241 hold data that indicates non-postal addresses for contacting one or more organizations or persons associated with a place. Contact information infields241 provides a useful way to distinguish among entities with similar names at the same location, such as related businesses in the same office building. The contact fields241 includephone field243,email field245,website field247 andother field249. Thephone field233 holds data that indicates one or more telephone numbers associated with a place. Similarly theemail field245,website field247 andother field249, hold data that indicates one or more email addresses, website URLs, and other contact data, respectively, associated with the place, if any. For example, inFIG. 2D, the contact addresses are as indicated by values in separate XML parameters.
• While the depicted fields inFIG. 2A are shown as integral blocks of data in a particular order in a record in a single structure for purposes of illustration, in other embodiments one or more fields, or portions thereof, are arranged in a different order on one or more records in one or more data structures on one or more nodes connected to a communications network, e.g.,network105. In some other embodiments, one or more depicted fields or portions thereof are omitted, or additional fields are included.
• As described in more detail below with reference toFIG. 6A throughFIG. 6E, in the illustrated embodiments, a browser or PNSS client process interacts with the PNSS by exchanging messages, such as HTTP messages, with the PNSS modules. As an early step, the user sends a registration message to attempt to register a place with the PNSS. The message must include enough information to determine a degree of match with predetermined places in a metadata data structure. According to the example PNSS API, the message to register a place must contain some place metadata and the name of the provider of the place metadata. The place metadata must include at least a proposed core category, a proposed default name and language, and either an address or a geographic coordinate. All other metadata that the user knows for the place should also be included in order to fill the metadata fields of a new entry in the data structure or to update the metadata in a pre-existing entry.
• FIG. 3A is a diagram of aplace registration message301, according to one embodiment. The place registration message includes acategory field311, aname field317, alocation field323 and aprovider ID field327. Although the depicted fields inFIG. 3A are shown as integral blocks of data in a particular order in a single message for purposes of illustration, in other embodiments one or more fields, or portions thereof, are arranged in a different order in one or more messages among two or more processes. In some other embodiments, one or more depicted fields or portions thereof are omitted, or additional fields are included.
• In the illustrated embodiment, thecategory field311 includes a managedcategory field313 and an optional categories field315 for carrying data that indicates one or more core categories and one or more free-form tags, respectively, as described above. Thename field317 includes alanguage field319 and aname field321 for carrying data that indicates the proposed default language and the default name in that language, respectively.
• In the illustrated embodiment, thelocation field323 includesfield325 for carrying data that indicates either or both of a postal address in the default langue or the geographic coordinates, as described above, or both.
• In the illustrated embodiment, the provider identifier (ID)field327 carries data that indicates the organization or person who is attempting to add or otherwise register the place to the community's shared places.
• According to an example embodiment, the PNSS API provides forplace registration message301 to be an XML document in the body of an HTTP POST message. The same XML parameter dictionary is used as used for the XML document illustrated inFIG. 2C andFIG. 2D.
• FIG. 3B is a diagram of aplace response message303 with a single place identifier, according to one embodiment. A message of this type is returned when the registration metadata exactly matches the corresponding metadata of a place already in the place metadata data structure, or when the registration metadata indicates a new place not already in the metadata data structure.Place response message303 includes aplace ID field331 and aplace URL field333. The place ID holds data indicating the unique place ID of the new or existing place that matches exactly the registration metadata. Theplace URL field333 field holds data that indicates the web page where links to the description or services related to the place should be added and where links to existing descriptions and services, if any, can be found. In some embodiments, theplace URL field333 just links to the PMDS's entry for that place. It's just a second way to provide the value of the location header described next for an environment where there might be a problem accessing/displaying http-headers.
• According to an example embodiment, the PNSS API provides forresponse message303 to be an XML document in the body of an HTTP message, using the XML parameters illustrated inFIG. 2C andFIG. 2D. In case of a perfect match to a preexisting place the response will returnstatus code303. When a new place is created the response will returnstatus code201. The HTTP header “Location” will contain the URL linking to the place's metadata in the PMDS. The response body will include the XML representation of the place ID.
• FIG. 3C is a diagram of a placeresponse error message305, according to one embodiment. A message of this type is returned when the registration metadata causes a problem for the PNSS.Place response message305 includes anerror description field351 that carries data that indicates the type of error. According to an example embodiment, the PNSS API provides forresponse message305 to be an XML document in the body of an HTTP message. In case the registration metadata does not pass validation performed by the PNSS, theresponse message305 returns status code400. The response body contains an XML representation, e.g., “Error! Reference source not found” Example errors are: “Invalid data,” if the place is missing any required attributes; “Invalid address,” if the address data is invalid or not correct (e.g., the address is not recognized or the geographical coordinates are incorrect).
• FIG. 3D is a diagram of aplace response message307 with one or more candidate places, according to one embodiment. A message of this type is returned when the registration metadata is a partial match for one or more new or predetermined places.Place response message307 includes one or more candidate fields, e.g.,candidate field371a,candidate field371b,and candidate field371c,collectively referenced hereinafter as candidate fields371. Each candidate field371 includes amatch quality field373, an extant/new indicator field375, acategory field377, anames field381, alocation field391 and atoken field397, as depicted forcandidate field371a.
• In the illustrated embodiment, thematch quality field373 holds data that indicates a degree of match between the registration metadata and the metadata of the candidate place. The degree of match is less than a perfect match and greater than a predetermined threshold value for the degree of match. Any method may be used to express the degree of match, e.g., a decimal value between 0.0 for no match and 1.0 for perfect match, or an integer between 0 for no match and 255 for a perfect match. Any measure of similarity may be used to generate the degree of match. In the illustrated embodiment, fuzzy logic is used to simultaneously consider and properly weight similarities in category, name, location and contact information in the place metadata. In some embodiments, one or more properties of the fuzzy logic algorithm are learned based on differences between registration metadata and the metadata of candidates selected by previous users of the PNSS.
• In the illustrated embodiment, the extant/new indicator flag375 holds data that indicates whether the candidate is a new place with valid metadata or an extant place already in the place metadata data structure.
• In the illustrated embodiment, thecategory field377 includes a managedcategories field379 that holds data that indicates the managed categories of the candidate place. Similarly, thename field381 includes adefault language field383 that holds data that indicates the default language of the candidate place, and adefault name field385 that holds data that indicates the name of the candidate place in the default language. Thelocation field391 includes anaddress field393 that holds data that indicates the address in the default language of the candidate place, and ageographic coordinates field395 that holds data that indicates the geographic coordinates of the candidate place.
• In the illustrated embodiment, thetoken field397 holds data that indicates the differences between the candidate metadata and the registration metadata. The data in thetoken field397 is used to efficiently indicate a candidate selected by the user and reconstruct the candidate metadata from the registration metadata.
• According to an example embodiment, the PNSS API provides forresponse message307 to be an XML document in the body of an HTTP message, using the XML parameters illustrated inFIG. 2C andFIG. 2D, with the addition of an XML parameter token. When one or more possible candidates are available but there is no perfect match, the response will return status code300. The response body contains an XML representation with a list of candidates. A user can choose one of these candidates and receive the place ID for that candidate through the select candidate resource of the API.
• FIG. 4A is a diagram of amessage401 for selecting a candidate, according to one embodiment. Themessage401 includes a selected candidatetoken field403 that carries data that indicates the token provided inmessage307 for the one candidate that is selected. The selected candidate is one that the PNSS user understands is the place the user meant to register. If no candidate describes the place the user intended, then the user must review and revise the original registration metadata, and submit the revised metadata in a new registration message.
• According to an example embodiment, the PNSS API provides for a select candidate request that allows the PNSS user to choose one of the proposed candidates of a previous POST operation. This operation can be used for either selecting a preexisting place with slightly different metadata or creating a new place that has slightly different metadata, e.g., because it includes some corrected or enhanced metadata. The message body includes an XML document with a value in an XML token parameter for the candidate token of the selected candidate out of the response body of the previous POST operation. In response, the PNSS client receives the candidate place ID, e.g., inplace response message303, described above.
• FIG. 4B is a diagram of amessage411 for requesting a place resource, according to one embodiment. This request is directed to thePMDS131 and includes aplace ID field413. The place ID field holds data that indicates a value for the unique place identifier. In response, the PNSS client receives the metadata for the place, including the place resource where links to existing description and services related to the place can be obtained, and where links to new descriptions and services can be added.
• According to an example embodiment, the PNSS API provides for the place metadata service (PMDS) to allow a PNSS user to read and manage the core metadata of a place. Therefore, every place is modeled as a resource indicated by the URL returned infield333 ofmessage303. The resource provides a set of operations and sub-resources. An HTTP GET message returns the metadata of the place with the place ID as specified by the last URL segment. The HTTP response message includes a Status Code. When a place with a place ID matching the last URL segment exists, the response will return status code200. The response body will contain the XML representation of the place as depicted inFIG. 2C andFIG. 2D. When no place with a place ID that matches the last URL segment exists, then the response will return status code404.
• According to an example embodiment, the PNSS services are divided among multiple modules. In the following description, the processes at the place metadata service (PMDS)module131 and the Permanent Place ID Service (PPIDS)module133 are described with reference toFIG. 5A andFIG. 5B, respectively. In other embodiments, two or more of these modules are combined into a single module that performs the steps of both processes.
• FIG. 5A is a flowchart of aprocess500 at a place metadata service (PMDS), according to one embodiment. Although steps inFIG. 5A and subsequent flow chartFIG. 5B are show in a particular order for purposes of illustration, in other embodiments, one or more steps may be performed in a different order or overlapping in time, in series or in parallel, or one or more steps may be omitted or added, or changed in some combination of ways.
• In the illustrated embodiment, instep501, a message is received, such as an XML document in the body of an HTTP message. Instep503 it is determined whether the message indicates place metadata for a new place to be created.
• If so, then in step505 a next place ID is determined in the illustrated embodiment. Any method may be used to determine the next place ID. In some embodiments, the next available place ID is generated by incrementing the last place ID; in some embodiments the place ID is determined by a hash function. In some embodiments, the next place ID is determined by sending a request message for the next place ID to a Global Place Name Server (GPNS)136. In step507 a new entry is added to a place metadata data structure with the new place ID. The values of the metadata received in the create message are stored in the new entry fields, as depicted inFIG. 2A. Instep509, the new place ID and associated place resource are returned to the module that sent the create message.
• If the message does not indicate a new place is to be created, then instep511 in the illustrated embodiment, it is determined whether the message indicates to retrieve place metadata based on a place ID provided in the message. If so, then in step513 the place metadata for the given place ID is returned to the module that sent the message, e.g., in an XML document like that depicted inFIG. 2C andFIG. 2D in the body of an HTTP message. However, if such a place ID is not valid, then an error message is returned, e.g., like message306, with a description of the error, or with an error code.
• If the message received is not a request to retrieve metadata based on a place ID, then instep515, in the illustrated embodiment, it is determined whether the message is a request to retrieve a place ID based on metadata included in the message. If not, then the message is further reviewed instep535, described below. If so, then instep517 the next entry in the place metadata data structure is retrieved. In some embodiments the next entry retrieved is the next entry within a vicinity of a location indicated in the metadata provided in the received message.
• In the illustrated embodiment, n step519 a quality of match is determined between the metadata in the message received (message metadata) and the metadata in the data structure entry (entry metadata). Any method may be used to determine the quality of match. In some embodiments, the quality is computed as a degree of match determined using a fuzzy logic algorithm that takes account of location identification, category definition, name resolution, vicinity detection, and previous selection tracking, as described above. In other embodiemtns, the fuzzy logic is left to the PPIDS, and the match quality determined in the PMDS merely indicates one of three levels of matching: a first level for no match of any metadata except category, a second level for complete match of all metadata, and a third level for match of at least one metadata parameter other than category.
• Instep521, in the illustrated embodiment, it is determined whether there is a perfect match of all metadata in the message with the corresponding metadata in the entry. If so, then instep521, the place ID of the entry is returned as an extant place ID, and processing of the received message is complete.
• If there is not a perfect match, then instep525, in the illustrated embodiment, it is determined whether the degree of match exceeds a predetermined threshold or falls into the third category of match quality. If so, then there is a partial match and the place ID of the entry is returned along with the value of the match quality level.
• Instep529, in the illustrated embodiment, it is determined if the entry just examined is the last entry in the vicinity. If not, then the next entry is selected instep517. If so, then it is determined instep531 whether any partial matches were obtained (e.g., whetherstep527 was executed at least once). If so, then the processing of the message is complete and the process ends. If not, then a message is returned indicating no match for the message metadata.
• Instep535, in the illustrated embodiment, it is determined if the message received is to update the metadata at an existing entry. If not, then the message is ignored and the process ends. If so, then instep537, the metadata of an existing entry is updated. For example, new metadata is added to blank fields, metadata in a field is replaced, metadata in a field is deleted, or the entry is deleted, or merged with a different entry. An entry is merged, for example, by indicating one entry as the dominant entry, using metadata from the subordinate entry only in blank fields in the dominant entry, deleting the subordinate entry and including the place ID of the subordinate entry in the mergedplace IDs field207 of the dominant entry. The process then ends.
• As a result ofmethod500 any node can determine the metadata associated with a place ID or find a place ID for a place with metadata that exactly or partially matches the metadata on hand. According to some embodiments, these processes atPMDS131 are utilized by aPPIDS133 to quality control metadata registered for the metadata database and substantially reduce duplicate entries. To prevent malicious creation of new entries, messages to create a new place or update an entry are accepted only from trusted sources, likePPIDS133.
• FIG. 5B is a flowchart of aprocess550 at a permanent place ID service (PPIDS), according to one embodiment. Instep551, a metadata data structure is seeded with multiple entries. In some embodiments,step551 is performed by a different process. In step553 a request for the PPIDS web page is received and the web page is sent in one or more HTTP messages. The web page provides active areas and forms that a PNSS user can manipulate to perform PNSS functions. Instep555 an HTTP message is received from the user's browser. In some embodiments,step553 is omitted and the message received instep555 is sent by aPNSS client121, e.g., as an HTTP message.
• Instep557, in the illustrated embodiment, it is determined whether the message is a registration message, e.g.,place registration message301. If so, then instep559 it is determined if the registration metadata is valid. Any method may be used to determine if the metadata is valid. For example, in some embodiments, the validity of a postal address is determined based on the commercial LRO services available from NAVTEQ. For example the LRO service can indicate if a given street name does not exist in a given city or within a given postal code, or whether a given house number does not exist for the given street name. Latitude values must lie between 90 degrees South and 90 degrees North; longitude values between 180 degrees West and 180 degrees East.
• If the registration metadata is not valid, then instep561, in the illustrated embodiment, it is determined if the registration metadata can be corrected. If not, an error message, such aserror message305 is returned to the client process instep563. If the registration metadata can be corrected, such as for misspellings, transposed numeral and missing postal codes or cities, then, instep565, the registration metadata is corrected to produce valid, corrected registration metadata. In some embodiments, the corrected registration metadata is used instep567.
• Instep567, in the illustrated embodiment, a list of one or more candidate places is generated, with tokens as described above, including a candidate based on corrected registration metadata, if any. In step569 a place response message with candidates, such asmessage307, is returned to the client process. Control then passes to step555, to receive the next message from the client (e.g.,PNSS client121 or browser117)
• If the metadata is found valid instep559, or, in some embodiments, corrected instep565, then, instep571, the place ID for the valid registration metadata is obtained. For example, a request message with valid registration metadata is sent to thePMDS331 for processing as described above with reference toFIG. 5A.
• Instep573, in the illustrated embodiment, it is determined if the PMDS returns only partial matches, e.g., returns at least one message with a match quality at the third level, but returns no message for a place ID of a perfect match. If so, then a list of candidates is built instep567 based on those partial matches. In some embodiments all the partial matches are included in the list of candidates. In some embodiments, further processing is performed to determine which, if any, of the partial matches to include in the list of candidates. For example, in some embodiments the fuzzy logic algorithm is applied based on past learning from past selections of candidates. In these embodiments, for example, a place having a partial match with a degree of match rarely selected by a user, is not included in the list of candidates, unless it is the best match. A token is determined for each place included in the list of candidate places. The place response with candidates message is returned instep569, as described above.
• Instep575, in the illustrated embodiment, it is determined if the PMDS returns a perfect match. If so, then the place ID of the place that perfectly matches the valid registration metadata is returned, along with the place resource, e.g., inplace response message303. The process is then complete until the next message is received instep553 orstep555.
• If no perfect match or partial matches are returned, then, in the illustrated embodiment, PMDS returns a message that there is no match for the valid registration metadata. Instep579, the valid registration metadata is sent to the PMDS in a message for creating a new place. The PMDS gets the next place ID and adds a new entry to the place metadata data structure and returns the new place ID., as described above with reference to step505 throughstep509 ofFIG. 5A. Instep581 the new place ID is received from the PMDS, and is returned to the client process. The process is then complete until the next message is received instep553 orstep555.
• If the message received is not a registration message, then, in the illustrated embodiment, instep583, it is determined if the message received is a select candidate message, e.g.,message401. If not, the process is complete until the next appropriate message is received instep555. If so, then instep585, the metadata from the selected candidate is reconstructed based on the valid registration data and the token. Furthermore, metrics, for determining which places should be offered as candidates from the set of returned places with partial matches, are reviewed and updated as advantageous. Control then passes to step587 and following steps to determine if the selected candidate token represents an extant place or a new place, and respond accordingly. If the token refers to an extant place, control passes back to step577, described above. If the token refers to a new place, then control passes to step579 and following to create the metadata and return the placeID for the new place.
• FIG. 6A is a time sequence diagram that illustrates a sequence of messages and processes600 for accessing place metadata, according to one embodiment. Time increases downward in this and following time sequence diagrams. A network process on the network is represented by a vertical bar. A message passed from one process to another is represented by horizontal arrows. A step performed by a process is indicated by a box or looping arrow overlapping the process at a time sequence indicated by the vertical position of the box or looping arrow.
• The network processes represented in the illustrated embodiment ofFIG. 6A are a PNSS user, such asPNSS client process121, the Permanent Place ID service (PPIDS)133, and the Place metadata Service (PMDS)131.
• In the illustrated embodiment,The Place Meta Data Service manages metadata of all registered places. Access to the meta data requires place ID for the place.Message611, getPlace(placeID), is an example of arequest place message411.Message613, result:place Metadata, is an example of an HTTP message with place metadata as depicted inFIG. 2A,FIG. 2C andFIG. 2D.
• FIG. 6B is a time sequence diagram that illustrates a sequence of messages and processes620 for registering a valid new place, according to one embodiment. The network processes represented inFIG. 6B are the same as depicted inFIG. 6A.
• ThePPIDS133 manages the registration of new places, in the illustrated embodiment. Therefore thePNSS user121 has to provide the metadata of the place to the PPIDS in a registration message621 (e.g., message301). PPIDS validates the data inprocess623. If the data is correct, the PPIDS searches for matching places by sendingmessage625 to thePMDS131. If no matching place is available, as indicated inmessage627 from the PMDS, PPIDS creates a new place in the PMDS by sendingmessage629. The new place ID returned by the PDMS to the PPIDS inmessage631 is returned to thePNSS user121 inmessage633.
• FIG. 6C is a time sequence diagram that illustrates a sequence of messages and processes640 for registering a matched place, according to one embodiment. The network processes represented inFIG. 6C are the same as depicted inFIG. 6A.
• Registering a place that matches perfectly to a preexisting place begins as registering a new place inFIG. 6B, but the lookup in the PMDS will return a perfect matching place inmessage647, in the illustrated embodiment. The PPIDS directly returns inmessage649 the place ID of the matching place.
• FIG. 6D is a time sequence diagram that illustrates a sequence of messages and processes650 for registering a partially matched place, according to one embodiment. The network processes represented inFIG. 6D are the same as depicted inFIG. 6A.
• In case the provided metadata matches only partially to one (or multiple) places inmessages657, PPIDS creates a list of all matching candidates together with a “quality of match” value inprocess659, in the illustrated embodiment,. The list is sent in message661 (e.g., inmessage307 ofFIG. 3D). The user can then select one of these candidates by sending back the selection as a token in message665 (e.g., inmessage401 ofFIG. 4A). Based on the selected candidate, the PPIDS reconstructs the candidate metadata from the registration metadata and the token inprocess667. The PPIDS sends the registration metadata to the PMDS in anupdate place message669 to update the metadata of the selected place based on the registration metadata. The PDMS updates the selected place and sends the place ID of the updated but extant place inmessage671. The place ID may have changed if the original partial matched place was merged with another place as a result of the updates. The PPIDS returns inmessage673 the place ID of the extant place.
• If the user doesn't agree with any of the candidates, the user has to correct the metadata manually and rerun the registration with the new metadata, in the illustrated embodiment.
• FIG. 6E is a time sequence diagram that illustrates a sequence of messages and processes680 for registering a partially valid place, according to one embodiment. The network processes represented inFIG. 6E are the same as depicted inFIG. 6A.
• During validation inprocess683, in the illustrated embodiment, PPIDS can automatically fix some issues in the registration metadata received inmessage681, such as fixing misspellings and adding Zip code. The PPIDS proceeds as if the corrected data would have been directly provided, e.g., by sendingmessage685 searching for matching places. Even if no matches are found, as indicated inmessage687, PPIDS gives the user the chance to accept the fixes in an additional selection step. Therefore the PPIDS creates a candidate based on the corrected metadata inprocess689 and send this together with a “selectToken” object inmessage690. If the user agrees with the fixes, the user sends the selectToken object in aselectCandidate request message691 to the PPIDS. The PPIDS proceeds as if the user would have initially provided the corrected data. If no match is found, as shown inFIG. 6E, PPIDS creates a new place by reconstructing the fixed metadata from the registered metadata and the token inprocess693. The reconstructed metadata is used to create the new place by sending it in acreat place message695. Aresult message697 is received with the new place ID, and returned to thePNSS user121 inmessage699.
• If a match had been found, then the PPIDS returns the place ID of a matching preexisting place, in the illustrated embodiment, If the user doesn't agree to the fixes, the user he has to modify the registration metadata manually and rerun the registration with the modified meta data
• The processes described herein for tracking and sharing content playback may be implemented via software, hardware (e.g., general processor, Digital Signal Processing (DSP) chip, an Application Specific Integrated Circuit (ASIC), Field Programmable Gate Arrays (FPGAs), etc.), firmware or a combination thereof. Such example hardware for performing the described functions is detailed below.
• FIG. 7 illustrates acomputer system700 upon which an embodiment of the invention may be implemented.Computer system700 includes a communication mechanism such as abus710 for passing information between other internal and external components of thecomputer system700. Information (also called data) is represented as a physical expression of a measurable phenomenon, typically electric voltages, but including, in other embodiments, such phenomena as magnetic, electromagnetic, pressure, chemical, biological, molecular, atomic, sub-atomic and quantum interactions. For example, north and south magnetic fields, or a zero and non-zero electric voltage, represent two states (0, 1) of a binary digit (bit). Other phenomena can represent digits of a higher base. A superposition of multiple simultaneous quantum states before measurement represents a quantum bit (qubit). A sequence of one or more digits constitutes digital data that is used to represent a number or code for a character. In some embodiments, information called analog data is represented by a near continuum of measurable values within a particular range.
• Abus710 includes one or more parallel conductors of information so that information is transferred quickly among devices coupled to thebus710. One ormore processors702 for processing information are coupled with thebus710.
• Aprocessor702 performs a set of operations on information. The set of operations include bringing information in from thebus710 and placing information on thebus710. The set of operations also typically include comparing two or more units of information, shifting positions of units of information, and combining two or more units of information, such as by addition or multiplication or logical operations like OR, exclusive OR (XOR), and AND. Each operation of the set of operations that can be performed by the processor is represented to the processor by information called instructions, such as an operation code of one or more digits. A sequence of operations to be executed by theprocessor702, such as a sequence of operation codes, constitute processor instructions, also called computer system instructions or, simply, computer instructions. Processors may be implemented as mechanical, electrical, magnetic, optical, chemical or quantum components, among others, alone or in combination.
• Computer system700 also includes amemory704 coupled tobus710. Thememory704, such as a random access memory (RAM) or other dynamic storage device, stores information including processor instructions. Dynamic memory allows information stored therein to be changed by thecomputer system700. RAM allows a unit of information stored at a location called a memory address to be stored and retrieved independently of information at neighboring addresses. Thememory704 is also used by theprocessor702 to store temporary values during execution of processor instructions. Thecomputer system700 also includes a read only memory (ROM)706 or other static storage device coupled to thebus710 for storing static information, including instructions, that is not changed by thecomputer system700. Some memory is composed of volatile storage that loses the information stored thereon when power is lost. Also coupled tobus710 is a non-volatile (persistent)storage device708, such as a magnetic disk, optical disk or flash card, for storing information, including instructions, that persists even when thecomputer system700 is turned off or otherwise loses power.
• Information, including instructions, is provided to thebus710 for use by the processor from anexternal input device712, such as a keyboard containing alphanumeric keys operated by a human user, or a sensor. A sensor detects conditions in its vicinity and transforms those detections into physical expression compatible with the measurable phenomenon used to represent information incomputer system700. Other external devices coupled tobus710, used primarily for interacting with humans, include adisplay device714, such as a cathode ray tube (CRT) or a liquid crystal display (LCD), or plasma screen or printer for presenting text or images, and apointing device716, such as a mouse or a trackball or cursor direction keys, or motion sensor, for controlling a position of a small cursor image presented on thedisplay714 and issuing commands associated with graphical elements presented on thedisplay714. In some embodiments, for example, in embodiments in which thecomputer system700 performs all functions automatically without human input, one or more ofexternal input device712,display device714 andpointing device716 is omitted.
• In the illustrated embodiment, special purpose hardware, such as an application specific integrated circuit (ASIC)720, is coupled tobus710. The special purpose hardware is configured to perform operations not performed byprocessor702 quickly enough for special purposes. Examples of application specific ICs include graphics accelerator cards for generating images fordisplay714, cryptographic boards for encrypting and decrypting messages sent over a network, speech recognition, and interfaces to special external devices, such as robotic arms and medical scanning equipment that repeatedly perform some complex sequence of operations that are more efficiently implemented in hardware.
• Computer system700 also includes one or more instances of acommunications interface770 coupled tobus710.Communication interface770 provides a one-way or two-way communication coupling to a variety of external devices that operate with their own processors, such as printers, scanners and external disks. In general the coupling is with anetwork link778 that is connected to alocal network780 to which a variety of external devices with their own processors are connected. For example,communication interface770 may be a parallel port or a serial port or a universal serial bus (USB) port on a personal computer. In some embodiments,communications interface770 is an integrated services digital network (ISDN) card or a digital subscriber line (DSL) card or a telephone modem that provides an information communication connection to a corresponding type of telephone line. In some embodiments, acommunication interface770 is a cable modem that converts signals onbus710 into signals for a communication connection over a coaxial cable or into optical signals for a communication connection over a fiber optic cable. As another example,communications interface770 may be a local area network (LAN) card to provide a data communication connection to a compatible LAN, such as Ethernet. Wireless links may also be implemented. For wireless links, thecommunications interface770 sends or receives or both sends and receives electrical, acoustic or electromagnetic signals, including infrared and optical signals, that carry information streams, such as digital data. For example, in wireless handheld devices, such as mobile telephones like cell phones, thecommunications interface770 includes a radio band electromagnetic transmitter and receiver called a radio transceiver.
• The term computer-readable medium is used herein to refer to any medium that participates in providing information toprocessor702, including instructions for execution. Such a medium may take many forms, including, but not limited to, non-volatile media, volatile media and transmission media. Non-volatile media include, for example, optical or magnetic disks, such asstorage device708. Volatile media include, for example,dynamic memory704. Transmission media include, for example, coaxial cables, copper wire, fiber optic cables, and carrier waves that travel through space without wires or cables, such as acoustic waves and electromagnetic waves, including radio, optical and infrared waves. Signals include man-made transient variations in amplitude, frequency, phase, polarization or other physical properties transmitted through the transmission media.
• Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, a hard disk, a magnetic tape, or any other magnetic medium, a compact disk ROM (CD-ROM), a digital video disk (DVD) or any other optical medium, punch cards, paper tape, or any other physical medium with patterns of holes, a RAM, a programmable ROM (PROM), an erasable PROM (EPROM), a FLASH-EPROM, or any other memory chip or cartridge, a transmission medium such as a cable or carrier wave, or any other medium from which a computer can read. Information read by a computer from computer-readable media are variations in physical expression of a measurable phenomenon on the computer readable medium. Computer-readable storage medium is a subset of computer-readable medium which excludes transmission media that carry transient man-made signals.
• Logic encoded in one or more tangible media includes one or both of processor instructions on a computer-readable storage media and special purpose hardware, such asASIC720.
• Network link778 typically provides information communication using transmission media through one or more networks to other devices that use or process the information. For example,network link778 may provide a connection throughlocal network780 to ahost computer782 or toequipment784 operated by an Internet Service Provider (ISP).ISP equipment784 in turn provides data communication services through the public, world-wide packet-switching communication network of networks now commonly referred to as theInternet790. A computer called aserver host792 connected to the Internet hosts a process that provides a service in response to information received over the Internet. For example,server host792 hosts a process that provides information representing video data for presentation atdisplay714.
• At least some embodiments of the invention are related to the use ofcomputer system700 for implementing some or all of the techniques described herein. According to one embodiment of the invention, those techniques are performed bycomputer system700 in response toprocessor702 executing one or more sequences of one or more processor instructions contained inmemory704. Such instructions, also called computer instructions, software and program code, may be read intomemory704 from another computer-readable medium such asstorage device708 ornetwork link778. Execution of the sequences of instructions contained inmemory704 causesprocessor702 to perform one or more of the method steps described herein. In alternative embodiments, hardware, such asASIC720, may be used in place of or in combination with software to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware and software, unless otherwise explicitly stated herein.
• The signals transmitted overnetwork link778 and other networks throughcommunications interface770, carry information to and fromcomputer system700.Computer system700 can send and receive information, including program code, through thenetworks780,790 among others, throughnetwork link778 andcommunications interface770. In an example using theInternet790, aserver host792 transmits program code for a particular application, requested by a message sent fromcomputer700, throughInternet790,ISP equipment784,local network780 andcommunications interface770. The received code may be executed byprocessor702 as it is received, or may be stored inmemory704 or instorage device708 or other non-volatile storage for later execution, or both. In this manner,computer system700 may obtain application program code in the form of signals on a carrier wave.
• Various forms of computer readable media may be involved in carrying one or more sequence of instructions or data or both toprocessor702 for execution. For example, instructions and data may initially be carried on a magnetic disk of a remote computer such ashost782. The remote computer loads the instructions and data into its dynamic memory and sends the instructions and data over a telephone line using a modem. A modem local to thecomputer system700 receives the instructions and data on a telephone line and uses an infra-red transmitter to convert the instructions and data to a signal on an infra-red carrier wave serving as thenetwork link778. An infrared detector serving as communications interface770 receives the instructions and data carried in the infrared signal and places information representing the instructions and data ontobus710.Bus710 carries the information tomemory704 from whichprocessor702 retrieves and executes the instructions using some of the data sent with the instructions. The instructions and data received inmemory704 may optionally be stored onstorage device708, either before or after execution by theprocessor702.
• FIG. 8 illustrates achip set800 upon which an embodiment of the invention may be implemented. Chip set800 is programmed to carry out the inventive functions described herein and includes, for instance, the processor and memory components described with respect toFIG. 8 incorporated in one or more physical packages. By way of example, a physical package includes an arrangement of one or more materials, components, and/or wires on a structural assembly (e.g., a baseboard) to provide one or more characteristics such as physical strength, conservation of size, and/or limitation of electrical interaction.
• In one embodiment, the chip set800 includes a communication mechanism such as a bus801 for passing information among the components of the chip set800. Aprocessor803 has connectivity to the bus801 to execute instructions and process information stored in, for example, amemory805. Theprocessor803 may include one or more processing cores with each core configured to perform independently. A multi-core processor enables multiprocessing within a single physical package. Examples of a multi-core processor include two, four, eight, or greater numbers of processing cores. Alternatively or in addition, theprocessor803 may include one or more microprocessors configured in tandem via the bus801 to enable independent execution of instructions, pipelining, and multithreading. Theprocessor803 may also be accompanied with one or more specialized components to perform certain processing functions and tasks such as one or more digital signal processors (DSP)807, or one or more application-specific integrated circuits (ASIC)809. ADSP807 typically is configured to process real-word signals (e.g., sound) in real time independently of theprocessor803. Similarly, anASIC809 can be configured to performed specialized functions not easily performed by a general purposed processor. Other specialized components to aid in performing the inventive functions described herein include one or more field programmable gate arrays (FPGA) (not shown), one or more controllers (not shown), or one or more other special-purpose computer chips.
• Theprocessor803 and accompanying components have connectivity to thememory805 via the bus801. Thememory805 includes both dynamic memory (e.g., RAM, magnetic disk, writable optical disk, etc.) and static memory (e.g., ROM, CD-ROM, etc.) for storing executable instructions that when executed perform the inventive steps described herein. Thememory805 also stores the data associated with or generated by the execution of the inventive steps.
• FIG. 9 is a diagram of example components of a mobile station (e.g., handset) capable of operating in the system ofFIG. 1, according to one embodiment. Generally, a radio receiver is often defined in terms of front-end and back-end characteristics. The front-end of the receiver encompasses all of the Radio Frequency (RF) circuitry whereas the back-end encompasses all of the base-band processing circuitry. Pertinent internal components of the station include a Main Control Unit (MCU)903, a Digital Signal Processor (DSP)905, and a receiver/transmitter unit including a microphone gain control unit and a speaker gain control unit. Amain display unit907 provides a display to the user in support of various applications and mobile station functions. Anaudio function circuitry909 includes a microphone911 and microphone amplifier that amplifies the speech signal output from the microphone911. The amplified speech signal output from the microphone911 is fed to a coder/decoder (CODEC)913.
• Aradio section915 amplifies power and converts frequency in order to communicate with a base station, which is included in a mobile communication system, viaantenna917. The power amplifier (PA)919 and the transmitter/modulation circuitry are operationally responsive to theMCU903, with an output from thePA919 coupled to theduplexer921 or circulator or antenna switch, as known in the art. ThePA919 also couples to a battery interface andpower control unit920.
• In use, a user ofmobile station901 speaks into the microphone911 and his or her voice along with any detected background noise is converted into an analog voltage. The analog voltage is then converted into a digital signal through the Analog to Digital Converter (ADC)923. Thecontrol unit903 routes the digital signal into theDSP905 for processing therein, such as speech encoding, channel encoding, encrypting, and interleaving. In the example embodiment, the processed voice signals are encoded, by units not separately shown, using a cellular transmission protocol such as global evolution (EDGE), general packet radio service (GPRS), global system for mobile communications (GSM), Internet protocol multimedia subsystem (IMS), universal mobile telecommunications system (UMTS), etc., as well as any other suitable wireless medium, e.g., microwave access (WiMAX), Long Term Evolution (LTE) networks, code division multiple access (CDMA), wireless fidelity (WiFi), satellite, and the like.
• The encoded signals are then routed to anequalizer925 for compensation of any frequency-dependent impairments that occur during transmission though the air such as phase and amplitude distortion. After equalizing the bit stream, themodulator927 combines the signal with a RF signal generated in theRF interface929. Themodulator927 generates a sine wave by way of frequency or phase modulation. In order to prepare the signal for transmission, an up-converter931 combines the sine wave output from themodulator927 with another sine wave generated by asynthesizer933 to achieve the desired frequency of transmission. The signal is then sent through aPA919 to increase the signal to an appropriate power level. In practical systems, thePA919 acts as a variable gain amplifier whose gain is controlled by theDSP905 from information received from a network base station. The signal is then filtered within theduplexer921 and optionally sent to anantenna coupler935 to match impedances to provide maximum power transfer. Finally, the signal is transmitted viaantenna917 to a local base station. An automatic gain control (AGC) can be supplied to control the gain of the final stages of the receiver. The signals may be forwarded from there to a remote telephone which may be another cellular telephone, other mobile phone or a land-line connected to a Public Switched Telephone Network (PSTN), or other telephony networks.
• Voice signals transmitted to themobile station901 are received viaantenna917 and immediately amplified by a low noise amplifier (LNA)937. A down-converter939 lowers the carrier frequency while the demodulator941 strips away the RF leaving only a digital bit stream. The signal then goes through theequalizer925 and is processed by theDSP905. A Digital to Analog Converter (DAC)943 converts the signal and the resulting output is transmitted to the user through the speaker945, all under control of a Main Control Unit (MCU)903—which can be implemented as a Central Processing Unit (CPU) (not shown).
• TheMCU903 receives various signals including input signals from thekeyboard947. TheMCU903 delivers a display command and a switch command to thedisplay907 and to the speech output switching controller, respectively. Further, theMCU903 exchanges information with theDSP905 and can access an optionally incorporatedSIM card949 and amemory951. In addition, theMCU903 executes various control functions required of the station. TheDSP905 may, depending upon the implementation, perform any of a variety of conventional digital processing functions on the voice signals. Additionally,DSP905 determines the background noise level of the local environment from the signals detected by microphone911 and sets the gain of microphone911 to a level selected to compensate for the natural tendency of the user of themobile station901.
• The CODEC913 includes theADC923 andDAC943. Thememory951 stores various data including call incoming tone data and is capable of storing other data including music data received via, e.g., the global Internet. The software module could reside in RAM memory, flash memory, registers, or any other form of writable storage medium known in the art. Thememory device951 may be, but not limited to, a single memory, CD, DVD, ROM, RAM, EEPROM, optical storage, or any other non-volatile storage medium capable of storing digital data.
• An optionally incorporatedSIM card949 carries, for instance, important information, such as the cellular phone number, the carrier supplying service, subscription details, and security information. TheSIM card949 serves primarily to identify themobile station901 on a radio network. Thecard949 also contains a memory for storing a personal telephone number registry, text messages, and user specific mobile station settings.
• While the invention has been described in connection with a number of embodiments and implementations, the invention is not so limited but covers various obvious modifications and equivalent arrangements, which fall within the purview of the appended claims. Although features of the invention are expressed in certain combinations among the claims, it is contemplated that these features can be arranged in any combination and order.

Claims (20)

1. A computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to perform at least the following:

receiving registration data that indicates one or more values for a corresponding one or more attributes that describe a place that is associated with a geographic location; and

initiating providing indication of a match between the registration data and metadata for a predetermined place.

2. A computer-readable storage medium ofclaim 1, wherein the apparatus is caused to further perform:

validating the registration data; and

generating a new entry for predetermined places based on the validation of the registration data and a negligible degree of match.

3. A computer-readable storage medium ofclaim 2, wherein the indication of the match further indicates a unique identifier for the place, the unique identifier corresponding to the new entry of the place within a data structure, the predetermined places having been assigned respectively a plurality of unique identifiers within the data structure.

4. A computer-readable storage medium ofclaim 1, wherein the apparatus is caused to further perform determining a degree of match using a fuzzy matching algorithm that applies place category matching, place name matching, nearby matching, previous selection matching, or a combination thereof.

5. A computer-readable storage medium ofclaim 2, wherein the indication of the match further indicates a candidate place of one or more predetermined places based on the validation of the registration data and determining that the registration data matches the candidate place to a predetermined degree.

6. A computer-readable storage medium ofclaim 1, wherein:

the apparatus is caused to further perform building a token for a candidate place if the registration data matches the candidate place to a predetermined degree;

the token includes data that indicates a difference between the registration data and the candidate place; and

the indication of the match further includes the token for the candidate place.

7. A computer-readable storage medium ofclaim 6, wherein the token includes a unique identifier for the candidate place if the candidate place is one of predetermined places.

8. A computer-readable storage medium ofclaim 6, wherein the apparatus is caused to further perform:

receiving a candidate selection message that indicates a single token selected by a user; and

initiating updating of a set of predetermined places for the candidate place based on the single token.

9. A computer-readable storage medium ofclaim 6, wherein building the token for the candidate place further comprises generating the candidate place by automatically correcting the registration data.

10. A computer-readable storage medium ofclaim 6, wherein the indication of the match includes a plurality of tokens for a plurality of candidate places.

11. A computer-readable storage medium ofclaim 1, wherein the apparatus is caused to further perform initiating sending an error message if the registration data omits a value for a place name attribute or a place category attribute or a geographic location attribute.

12. A computer-readable storage medium ofclaim 8, wherein initiating updating of the set of predetermined places for the candidate place based on the single token further comprises initiating deleting or merging one of the predetermined places.

13. A computer-readable storage medium ofclaim 8, wherein the apparatus is caused to further perform learning a heuristic for selecting a candidate based on the single token selected by the user.

14. An apparatus comprising a processor and a memory storing executable instructions that if executed cause the apparatus to perform at least the following:

receive registration data that indicates one or more values for a corresponding one or more attributes that describe a place that is associated with a geographic location; and

initiate providing an indication of a match between the registration data and metadata for a predetermined place.

15. An apparatus ofclaim 14, wherein the apparatus is further configured to:

validate the registration data; and

create a new entry for predetermined places based on the validation of the registration data and a negligible degree of match.

16. An apparatus ofclaim 15, wherein the indication of the match further indicates a unique identifier for the place, the unique identifier corresponding to the new entry of the place within a data structure, a set of predetermined places having been assigned respectively a plurality of unique identifiers within the data structure.

17. An apparatus ofclaim 14, wherein the apparatus is further configured to determine a degree of match using a fuzzy matching algorithm that applies place category matching, place name matching, nearby matching, previous selection matching, or a combination thereof.

18. An apparatus ofclaim 14, wherein:

the apparatus is further configured to build a token for a candidate place if the registration data matches the candidate place to a predetermined degree;

the token includes data that indicates a difference between the registration data and the candidate place; and

the response data further includes the token for the candidate place.

19. A system including the apparatus ofclaim 14, the system further comprising a place-building client configured to send the registration data.

20. A method comprising:

receiving registration data that indicates a value for a subset of place metadata that includes a plurality of attributes that describe a place that is associated with a geographic location; and

providing an indication of match between the registration data and metadata for a predetermined place.

Images