HK1178629A - Ranking of entity properties and relationship - Google Patents

Description

Ordering of entity attributes and relationships

Background

For purposes of this specification, an entity refers to a concept, thing, or event. For example, Seattle, Tom Hanx, Microsoft corporation, gulf war, and cosmos grand explosion theories, Washington, are all examples of entities. An entity may have an attribute. The attributes reflect any aspect of or information about the given entity. Examples of entity attributes include the date and name of birth of a person, geographic coordinates of a place, and revenue for a company. Entities may also share relationships with other entities. For example, the entity "tomhank" has a "spouse" relationship with another entity "litawilson", the entity "tomhank" has an "evolution" relationship with the entity "saving the soldier ryan", and the entity "microsoft" has a "CEO" relationship with the entity "stev pall mer". As a rule of thumb, attributes of an entity represent aspects of the form of a string, text, or other information, while relationships of an entity relate to other entities.

It is often useful to order entity attributes and relationships. Consider the information provided by wikipedia for entity/movie "saving soldier ryan". The entry lists the director, four producers, the drama, four directors, the distributor, the release date, the title length, the country, the language, the budget, and the total revenue. Each of these is an attribute of an entity, some attributes having multiple property values. In some situations or applications, there may only be space to display five attributes of the entity "save soldier ryan" rather than all attributes. Which five will be selected is a function of the attribute and relationship ordering. Several real world applications have limited display fields (e.g., mobile phones, web page toolbars, kiosks, etc.) to display information. It is not generally feasible to display all the features that an entity data source can provide. In addition, people/information consumers have a limited span of attention, so that it is often helpful to display information structured in a way that conveys the most relevant information in limited space and time.

An entity is described by the sum of its attributes, relationships, and their background. Currently, the order in which these characteristics are displayed is often left to the application receiving this information. For example, a mobile application for displaying a list of movies may hard-code which movie features it will display and where/how it will display them. In many cases, the data source may want some impact on the data, but this is not possible or difficult in current systems. For example, a data source may want to reveal new or unique information about an entity. The dependency on applications for ranking also implies that new entity types cannot be displayed by any ranking until the application developer spends time building a custom application to do so. Thus, new types of information may be built up in the data source for a period of time before an application for effectively viewing the information is available. It is common to see that a new web site or other application appears well after needing to view a particular type of information. For example, an Internet Movie Database (IMDB) website provides movie information that is available long before the site exists, but that is difficult to view or access in any structured way.

Disclosure of Invention

An entity ordering system is described herein that provides an input signal of ordering characteristics between a data source and an entity viewing application. By providing an input signal of ordered nature, the data source can influence the way these applications use (consume) the attributes and relationships of these entities. The more efficient ordering provided by the system allows new information to be presented in a "most relevant first" manner and may also provide a cut-off in situations of limited space. The entity ranking system scans attribute types and their ranges of values (spectra) for a given entity type among the various types, identifies the diversity of each characteristic/value, and computes a ranking based on a plurality of distance measures. Most search engines today index information in the form of one or more keywords associated with a Uniform Resource Locator (URL) where content related to the keywords can be found. A more useful way of indexing the information is to form a list of one or more attributes associated with the entity. Entities will form the basis for more useful search results, and ranking entity attributes and relationships is a major part of providing an entity-based search experience. Thus, the entity ranking system provides ranking information from the data sources to describe how to rank the entity attributes so that applications can be written more generally to cope with many types of entities while still displaying the most relevant entity information.

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

Drawings

FIG. 1 is a block diagram that illustrates components of the entity ordering system in one embodiment.

FIG. 2 is a flow diagram illustrating processing of an entity ranking system to process a ranking attribute query associated with a particular entity in one embodiment.

FIG. 3 is a flow diagram that illustrates the processing of the entity ranking system to determine a property ranking score for a given entity in one embodiment.

Detailed Description

An entity ordering system is described herein that provides an input signal of ordering characteristics between a data source and an entity viewing application. By providing an input signal of ordering characteristics, the data source can influence the way these applications use these entity attributes and relationships. The more efficient ordering provided by the system allows new information to be presented in a "most relevant first" manner and may also provide a cut-off in situations of limited space. The entity ranking system scans the attribute types and their value ranges for a given entity type among the various types, identifies the diversity of each characteristic/value, and computes a ranking based on a plurality of distance measures. One application of entity ranking is in the field of search engines. The search engine may be viewed as a general-purpose entity display application. It is common in the sense that a user can invoke a search engine to find information about a movie, book, restaurant, task, topic, news, or any other type of entity. It is not feasible for a search engine to know how to display relevant information, particularly for each of these types, so common mechanisms are often used, such as keyword analysis or asking web page authors to provide content summaries.

Most search engines today index information in the form of one or more keywords associated with a Uniform Resource Locator (URL) where content related to the keyword can be found. A more useful way of indexing the information is to form a list of one or more attributes associated with the entity. In searching for restaurants, for example, a user would prefer to receive a list of restaurants and related information (e.g., menus, duration, addresses, or phone numbers) rather than a list of links to documents about the restaurants, such as what is provided today. Entities will form the basis for more useful search results, and ordering entity attributes and relationships is a major part of providing an entity-based search experience. Thus, the entity ranking system provides ranking information from the data sources to describe how to rank the entity attributes so that applications can be written more generally to cope with many types of entities while still displaying the most relevant entity information.

Many signals represent a correlation of information conveyed through attributes or relationships with respect to a given entity. The entity ranking system combines these signals to arrive at an overall ranking score. The combinations themselves can be customized to reflect different application goals. One class of signals includes those based on classification. Taxonomy classifies information specific to a particular field or subject area. Taxonomy-based ranking scores are useful because they allow field experts to capture their expertise in the score and influence the final ranking. For example, a movie specialist may want to indicate that "lead practice" and "lead actor" are the two most relevant characteristics of an entity of type "movie". This score mimics the behavior of a traditional website, where editorial picks a property to show for a given entity.

Another way to capture the relative importance of entity attributes and relationships is by looking at search engine query logs and finding the frequency of occurrence of patterns in the form of [ entity ] [ attribute/relationship name ] or [ attribute/relationship name ] [ entity ] and the like. For example, if many people search for "the first house of england", "the first prefecture of france", "the population of mexico", "the population of russia", etc., one can conclude that "the first" and "the population" are more relevant characteristics of entities of the type "country" than other attributes such as "area" or "HDI" (human developmental index) with low search frequency.

Another signal that can be used to infer the relative importance of a relationship is the importance of the entity to which another entity is being related. For example, for the entity "michel obama," the relationship "spouse" related to "balaclavam" is more relevant than the "spouse" relationship for entities such as "tomhan", for example. This signal allows the system to dynamically order entities and show different attributes of different entities potentially belonging to the same "type", which reflects the importance of the attributes of each particular entity.

In some embodiments, news may affect entity ranking. The relative importance of the relationships can be expanded to incorporate news items and dynamic ordering of relationships that depend on recent news. For example, for the entity "tagwood," the relationship "crown army" may be more relevant during the golf season, while "spouse" is more relevant during the morning of 2010.

In the case where there is a query and the user specifically requires a certain set of characteristics, the overall ordering of the characteristics can be influenced by their relevance to the query. For example, for the query "save soldier ryan statistics", attributes such as "budget", "title", "release date", "income", etc. would be ranked higher than "director", "lead actor", etc. The query term "statistics" signals the particular type of information the searcher is looking for, and the system uses this information to provide input query-specific rankings.

Several of the signals discussed above may be combined to calculate a final ranking score. The direct way to do this is a linear weighted combination of the scores of each signal:

wherein the content of the first and second substances,an ordering score representing the attribute/relationship 'i'. TheRepresents the weight of the signal type's', anda score representing the attribute/relationship 'i' of the signal's'. The weighting scheme W allows the system to have different weights for different application scenarios. For example, relevance and news based importance metrics are more useful for search engine application scenarios, while taxonomy based importance metrics are more useful in portable application scenarios.

FIG. 1 is a block diagram that illustrates components of the entity ordering system in one embodiment. The system 100 includes an application request component 110, a taxonomy signal component 120, a query log signal component 130, a dynamic signal component 140, an entity-specific ranking component 150, a context input component 160, a score determination component 170, and a ranked output component 180. Each of these components is described in more detail herein.

The application request component 110 receives a request from one or more applications to return an ordered list of entities and their attributes. The component 110 may receive the request via a web page, a web service, an Application Programming Interface (API), or any other interface for receiving a request to obtain data. The request may include contextual information such as the purpose of the request, one or more keywords related to the request, weights or relative relevance of various signals affecting the ranking, and the like. The request may also identify the particular entity or type of entity that returned the attribute in response to the request. The applications may include search engines, entity viewing applications, or any other type of application that uses any type of entity or entity data. The application may also provide requested restrictions, such as restrictions on the properties that the application may display.

The taxonomy signal component 120 provides an ordering signal based on the taxonomies associated with a particular subject area. The taxonomy-based signals may be automatically determined or provided by one or more editors that classify the subject area. Classification policies define which attributes of a particular entity type or a particular entity are most relevant. The taxonomy may include various contexts such that different attributes are considered most relevant under different circumstances or based on different application requirements. The taxonomy signal can be particularly useful for portable-type applications that want to display a taxonomy list of subject areas or entity attributes.

The query log signal component 130 provides a ranking signal based on web query logs that indicate how often search queries include particular entity attributes. The component 130 provides analysis of past user queries and may include keyword proximity, keyword frequency, and other elements to provide ranking signals. For example, if the user frequently searches for "capitalization in italy," the component 130 may provide a strong signal for the attribute "capitalization" related to queries of the entity type "country. The proximity of keywords in the query log and the frequency of occurrence of such queries provide hints as to the relative relevance of various attributes. In some cases, the system 100 may apply normalization to prevent over-emphasis of the stream row attributes. For example, an attribute such as "age" may be common in a search of a particular name of a person, but may not be relevant for display in an application as the frequency of searches would indicate. The normalization can be adjusted for any exceptional case.

The dynamic signal component 140 provides a dynamically changing ordering signal that adaptively adjusts the ordering of entity attributes based on recent information. For example, the signal may incorporate news and other quick change information into the ranking of the entities. As an example, consider a popular celebrity that has recently gone. In normal situations, the cause or date of death may not be attributes that are highly relevant in relation to the human entity, but on the days after death of the human, these attributes are very relevant and frequently requested. Thus, the system 100 may evaluate such attributes higher for a period of time after such an event. As another example, a rumor or disaster may cause a particular attribute to be more relevant for a particular entity. For example, information about japan that one requested changes from the type of information requested previously in 2011 after tsunami and the resulting nuclear reactor damage. This type of information may affect the ordering produced by the system 100.

The entity-specific ranking component 150 provides ranking signals based on exceptional relevance of particular entities and particular attributes of those entities. For example, users are often interested in different information for the american president than for others. While the spouse of most people may not be well known, the spouse of the president is often very relevant and well known. Celebrities may also change the relevance of information about other people, places, or things. For example, people may request different information about a business leader or a venue where a significant event occurred than people do for an ordinary person or venue. This component 150 provides a signal incorporating any exceptions to a particular entity that would suggest a different ordering than the default (generated by other signals) for the entity.

The context input component 160 receives context information related to the request and provides a ranking signal indicating the relevance of a particular entity attribute to the request. For example, a request for "movie statistics" indicates that the user is more interested in attributes such as "total revenue" and "cost of production" for the movie than who is featured in the movie or what genre the movie belongs to. The request may provide keywords, specific attributes of interest, and other information that suggests a ranking that is different than what the system 100 would otherwise produce. The system 100 incorporates this type of information into the ranking process through the context input component 160 to affect the ranking for a particular context. This makes the resulting ordering highly relevant to the nature of the received request.

The score determination component 170 combines the signals to produce a ranking score that ranks the attributes of the entities. The component 170 may apply weights to each score and combine the scores in any number of ways. For example, in some embodiments, component 170 may add each of the weighted scores to produce a linear combination. In some embodiments, the system may utilize a complex algorithm that applies application-specific criteria to rank attribute relevance (leverage). The system 100 can provide an API through which an application can specify the weights of particular signals to be used, functions to be used to combine signals, or other inputs that influence how the score determination component 170 derives a final score to order entity attributes. This allows both the data source and the requesting application to influence the way the entity attributes are ordered, and to set this balance differently for different purposes. For example, a particular application may prefer a certain set of signals for known entity types, but may be more compliant with the data source for new or unknown entity types.

The sort output component 180 sends a response to the received application request that includes a sorted set of entity attributes based on the sort score. The ranking output component 180 may provide visual responses (e.g., through a web page or mobile application), programmatic responses (e.g., through an API or event interface), or other output that may be used by the requesting application. The response may include the attribute values or just a determined ordering of the attributes. Based on the response, the application may request attribute data for a certain number of ordered attributes or may display the data provided directly in the response. Those of ordinary skill in the art will recognize numerous variations and optimizations based on performance and other goals without departing from the scope and intent of the system 100 described herein.

A computing device implementing the entity ordering system may include a central processing unit, memory, input devices (e.g., keyboard and pointing devices), output devices (e.g., display devices), and storage devices (e.g., disk drives or other non-volatile storage media). The memory and storage devices are computer-readable storage media that may be encoded with computer-executable instructions (e.g., software) that implement or realize the system. In addition, the data structures and message structures may be stored on a computer readable storage medium. Any computer readable media claimed herein includes only those media that fall within the statutory patentable category. The system may also include one or more communication links over which data may be transmitted. Various communication links may be used, such as the Internet, a local area network, a wide area network, a point-to-point dial-up connection, a cellular telephone network, and so forth.

Embodiments of the system may be implemented in a variety of operating environments, including: personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, digital cameras, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, set top boxes, systems on a chip (SOCs), and the like. The computer system may be a cellular telephone, personal digital assistant, smart phone, personal computer, programmable consumer electronics, digital camera, and the like.

The system may be described in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments.

FIG. 2 is a flow diagram illustrating processing of an entity ranking system to process a ranking attribute query associated with a particular entity in one embodiment. Beginning in block 210, the system receives a request from an application to order attributes of a specified entity or entity type. For example, a web application may call an API that stores entity information or a web-based data source. The API may receive information such as entities or entity types, contextual information about requests that may affect the resulting ordering, and the like. For example, the context information may include one or more keywords or entity attributes that are particularly relevant to the request. The system may receive requests from multiple types of applications for various purposes. The applications may include general applications such as search engines, or specific applications such as movie information viewing applications that request entity information.

Continuing in block 220, the system identifies the requesting entity or entity type for which the ranked attribute information is requested. The request may name the particular entity (e.g., movie "Hunt October Red") or entity type (e.g., movie) for which the application is requesting information. In some cases, the request does not specify the entity itself, but rather information related to the entity (e.g., "the chief role in Jurassic park"). This allows users to connect with the information they seek using the information they know.

Continuing in block 230, the system identifies attributes and attribute values associated with the specified entity. For example, the system may access a data source associated with a specified entity and enumerate attribute information stored within the data source. The system includes a data source, which may include one or more files, file systems, hard drives, databases, cloud-based storage services, or other facilities for storing data. The data source includes a plurality of entities and a plurality of attributes for each entity. The system accesses this information to generate an attribute ordering in response to the received request.

Continuing in block 240, the system determines a diversity of each of the identified attributes and attribute values. Diversity includes one or more distance measures indicating how each attribute relates to a received request. Diversity helps the system generate ranking scores for ranking entity attributes.

Continuing in block 250, the system determines a ranking score for each attribute. The rank score may be determined from various weighted signals that each provide some information regarding the relevance of a particular attribute to the currently received request. The process of determining the rank score is further described with reference to FIG. 3.

Continuing in block 260, the system provides a response to the received request that includes a ranking attribute based on the determined ranking score. The ordering attribute provides the following information from the data source to the requesting application: the information informs the requesting application how to display the entities and which attributes are likely to be most relevant to the application. By providing information about the destination of the information to the data source, the application receives information from the data source that the application can use to display relevant entity information, even for entities of a type that the application does not specifically predict or program. After block 260, these steps conclude.

FIG. 3 is a flow diagram that illustrates the processing of the entity ranking system to determine a property ranking score for a given entity in one embodiment. Beginning in block 310, the system selects a first attribute of an entity to determine a ranking score that indicates the relevance of the attribute relative to other attributes of the entity. The relevance of any particular request may vary as described herein and depends on the context information specific to the particular request.

Continuing in block 320, the system determines the request type to determine one or more signal weights for weighting the various signal type correlations. The type of request and the context affect how the different signals are weighted. For example, a request from a portable application to display general information about an entity type may suggest a different signal weight than a query request to obtain a particular type of information about the entity. As an example, a request to display a listing of movies released in 2010 may suggest displaying different attributes (e.g., title, rating, commentary) than a request to display movie statistics (e.g., budget, total revenue, show).

Continuing in block 330, the system determines a plurality of available signals that provide ranking information related to attributes of the selected entity. The signal may include various types of information, such as taxonomy information, query log information, dynamic information, entity-specific information, information related to the context of the ordering request, and so forth. Different signals may be available to some entities but not to others. The system determines the signals available to the ranked entities. For example, an expert may have provided a taxonomy to categorize information for one type of entity, but other types of entities may not have available taxonomies.

Continuing in block 340, the system sets signal weights appropriate for the current sort request, where the weights affect the relative impact of each signal on the resulting sort score. The system may set the weights received from the requesting application based on preconfigured weights specific to the purpose of the request, based on administrator configuration data, or based on any other content. In some cases, the operator of a particular data source may provide and adjust the weights based on the set-up experience that yields good results. In other cases, the requesting application may rely more heavily on certain signal types and may assign higher weights to such signals.

Continuing in block 350, the system normalizes the signal information for one or more attributes to avoid over-emphasis of popular attributes. Normalization avoids anomalies where a particular signal (e.g., a web query log) excessively skews the ordering of a particular attribute of an entity. Normalization explains other reasons for the popularity of certain attributes that do not necessarily relate to attribute ordering.

Continuing in block 360, the system accumulates the weighted signals to produce a ranked score. The ranking score combines information from the multiple signals to produce a score that indicates how relevant the currently selected attribute is to other attributes that identify the entity. The system may sort the attributes according to the scores to provide an ordered list of attributes to the requesting application. In some cases, the system caches the ordering information to more efficiently handle subsequent requests.

Continuing in decision block 370, if the system determines that more entity attributes are available for sorting, the system loops to block 310 to select the next attributes of the entity, else the system ends. While shown as occurring serially for ease of illustration, one of ordinary skill in the art will recognize that scores for attributes of entities may be determined in parallel for more efficient operation of the system or to address other objectives of a particular implementation of the system. After block 370, these steps conclude.

From the foregoing, it will be appreciated that specific embodiments of the entity ordering system have been described herein for purposes of illustration, but that various modifications may be made without deviating from the spirit and scope of the invention. Accordingly, the invention is not limited except as by the appended claims.

Claims (15)

1. A computer-implemented method to process queries for ranking attributes associated with one or more entities, the method comprising:

receiving (210) a request from an application to order attributes of a specified entity or entity type;

identifying (220) a requesting entity or entity type for which the ordered attribute information is requested;

identifying (230) attributes and attribute values associated with a specified entity;

determining (240) a diversity of each identifying attribute and attribute value;

determining (250) a ranking score for each attribute; and

providing (260) a response to the received request, the response including a ranking attribute based on the determined ranking score,

wherein the previous steps are performed by at least one processor.

2. The method of claim 1, wherein receiving the request comprises: an Application Programming Interface (API) between a web-based application displaying entity information and a web-based data source storing the entity information is invoked.

3. The method of claim 1, wherein receiving the request comprises: context information related to the request that affects the resulting ranking is received.

4. The method of claim 1, wherein identifying a requesting entity comprises: an indication is received from an application user identifying a particular entity.

5. The method of claim 1, wherein identifying attributes comprises: a data source associated with the specified entity is accessed and attribute information stored within the data source is enumerated.

6. The method of claim 1, wherein determining diversity comprises: one or more distance measurements are performed indicating how each attribute relates to the received request.

7. The method of claim 1, wherein determining diversity facilitates the system to generate ranking scores to rank the entity attributes.

8. The method of claim 1, wherein determining diversity provides one or more ranking signals for each attribute relevance indication to a received requesting application.

9. The method of claim 1, wherein determining a ranking score comprises: the plurality of weighted ranking signals are accumulated to produce a cumulative ranking score reflecting the relative relevance of each attribute to the received request.

10. The method of claim 1, wherein the ordering attribute in the response provides information from the data source to the requesting application informing the requesting application of how to display the entity and which attributes are most relevant to the application.

11. A computer system for ordering of entity attributes and relationships, the system comprising:

a processor and memory configured to execute software instructions implemented within the following components;

an application request component 110 that receives requests from one or more applications to return an ordered list of entities and entity attributes;

a taxonomy signal component 120 that provides a ranking signal based on a taxonomy associated with a particular subject area;

a query log signal component 130 that provides a ranking signal based on web query logs that indicate how frequently search queries include particular entity attributes;

a dynamic signal component 140 that provides a dynamically changing ordering signal that adaptively adjusts the ordering of entity attributes based on recent information;

an entity-specific ranking component 150 that provides ranking signals based on exceptional relevance of particular entities and particular attributes of those entities;

a context input component 160 that receives context information related to a request and provides a ranking signal indicating a relevance of a particular entity attribute to the request;

a score determination component 170 that combines the signals to produce a ranking score that ranks the attributes of the entities; and

a ranking output component 180 for sending a response to the received application request, the response comprising a ranked set of entity attributes based on the ranking score.

12. The system of claim 11, wherein the taxonomy signal component automatically classifies the entity information to generate a taxonomy for the attributes of the at least one entity.

13. The system of claim 11, wherein the query log signal component provides an analysis of past user queries, including keyword proximity and keyword frequency, to determine relative importance of entity attributes.

14. The system of claim 11, wherein the dynamic signal component provides a signal based on news related to the entity.

15. The system of claim 11, wherein the contextual input component receives one or more keywords in the request and determines one or more attributes of the entity related to the received keywords.