Composing text and structured databases

[0001] This application claims priority under the benefit of 35 U.S.C. §119(e) to Provisional Patent Application No. 61/623,809, filed Apr. 13, 2012. This provisional patent application is hereby expressly incorporated by reference herein in its entirety.

[0002] It has become common for users of computer-type devices to connect to the World Wide Web (the “web”) and employ web browsers and search engines to locate web pages (or “documents”) having specific content of interest to them (the users). As a result, an ever-increasing amount of data is becoming accessible online, and today the web already contains tens of billions of web pages. Many structured repositories for these web pages are also widely available, and it is useful to link information available in these various data sources. To this end, there are initiatives aimed at providing specifications for linking data objects from disparate data sources, and the corresponding research on composing information from multiple sources is already quite extensive. However, automating the task of linking information from various data sources is problematic largely because this abundance of data is being created in an ever-growing variety of forms and formats.

[0003] Current solutions to composing data from multiple sources include identifying similar structured records, linking text documents, and matching structured records to text data. Some of these solutions may also employ techniques to identify the object that is the topic of a review and then hypothesize a language model underlying the creation of reviews which is then used for finding the object (or objects) most likely to match the topic of a review. To improve results, such solution are often generalized to allow for attributes in structured records to have different weights and admit semantic translations of values, but such approaches are highly dependent upon good pre-categorization of documents and the structured records pertaining to same. Meanwhile, current work to linking text documents has focused on identifying mentions of phrases representing concepts (i.e., “named entities”) in one document and linking them to other documents that have in-depth information about those concepts. For such approaches, concept phrases are identified and disambiguated using rules, machine learning, or other information extraction techniques. As for matching text to structured records, most known approaches generally involve extracting structured data from text and then matching these structured records.

[0004] The foregoing techniques have been widely used often to algorithmically build structured databases, but methods for later extracting information from these structured databases often provide only limited accuracy unless also coupled with a substantial labeling effort. One proposed solution is to match concise text snippets to structured records, where the text snippets correspond to brief descriptions of merchant offers that need to be matched to the structured specifications in a product catalog, and thereby identify pieces of text that are identical to values in structured records and tag those records with the corresponding property names. The text is thus reduced to tuples of pairs, each pair comprising a value and a set of plausible property names, and a match between this representation of a text and a structured record is then scored by choosing the optimal property name for each value and checking whether the values are the same or different for identical property names of the two. However, these proposals tacitly assume that the text and structured records have been accurately classified in accordance with some taxonomy, and building good taxonomies and accurate classifiers is very difficult to achieve in practice.

[0005] Various implementations disclosed herein are directed to a framework for composing texts about objects with structured information pertaining to those objects. The framework utilizes the concept of a “trait” which herein is defined as a set of characteristics that can serve as the proxy for the identity of an object and that, in contrast to database keys for example, are instance-based rather than schema-based. Thus the various implementations employ specific techniques for computing traits, mapping structured records and text documents to these traits, and then joining information about the same object from two different data sources (or “repositories”).

[0006] Certain implementations disclosed herein associate records in a structured database with text documents in a corpus, such that records and documents are paired if they refer to the same object (e.g., a person, business, product, etc.) while no assumptions are made regarding the structure of the two data sources. For such implementations, each text document is processed as a bag of words having no categorization or structure to identify the objects being discussed, while each structured record is viewed as a set of key-value pairs (e.g., <color, blue>) that serve to describe various characteristics pertaining to an object. For several such implementations, knowledge of the significance of the characteristics or their role in distinguishing objects within a domain is not required and, as a result, such implementations are not restricted to or specialized for any particular domain.

[0007] Several implementations disclosed herein are also directed to linking information from at least two data sources—including a first data source comprising a plurality of documents comprising text pertaining to at least one object, and a second data source comprising a plurality of structured records comprising at least one characteristic of the at least one object—utilizing a processor for determining an instance-based trait for the at least one object and for associating at least one record in the second data source with the at least one document from the first data source that refers to the at least one object.

[0008] 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.

[0027] In considering the general problem of automating the linking of information from various data sources, it should be noted that many text documents and structured records often contain information about some specific “object,” that is, an entity of interest such as a person, place, product, event, and so forth. For example, data sources containing text documents written in a natural language often discuss some aspects of one or a small number of objects, although there are no markings or structure in any of the documents that explicitly identifies the objects that the document is about. Thus each text document may be viewed as a bag of words. In contrast, data sources that comprise a collection of structured records contain information in each record about some of the characteristics of some object, and each characteristic in turn may comprise a property name and a corresponding value for that property name, although such records would not explicitly contain the identity of objects to which the record pertains.

[0028] For the various implementations discussed herein, a universe of objects is postulated in which each object is described by a set of characteristics. Such objects have an implicit unique identity such that different objects may include one or more of the same characteristics but necessarily differ in at least one characteristic. For these various implementations, a framework for composing texts about the objects and structured information pertaining to the same is based on the concept of an instance-based “trait” comprising a set of characteristics that can serve as the proxy for the identity of an object. As such, the various implementations disclosed herein are directed to computing traits, mapping structured records and text documents to traits, and/or joining information about the same object from at least two repositories.

[0029] Several such implementations may have broad application to the area of web search where the web pages (as documents) are each endowed with at least one object corresponding to the web page content. This, in turn, will enable a search engine to exploit structure present in the document to answer queries based not just on matching keywords but also by taking into account semantics of the queries to match structured values. Consequently, web pages may be augmented with information having structured data to enable the web page to better “surface” in search results even when the queried words are not present in the web pages (which would normally preclude it from search results) because its corresponding structured source comprises the corresponding relevant information to the query and helps identify the web page as highly relevant to the query.

[0030] Several such implementations may also have broad application to verticals such as online shopping searches where, in addition to retrieving structured records for the products, the vertical may also retrieve relevant web pages about the products being queried since an implementation can identify the relevant products (or more generally objects) among such web pages. Of course, shopping is just one of many verticals to which the various implementations herein disclosed may apply, and these various implementations may be applied to other verticals as well, and these innumerable other applications will be readily evident to skilled artisans.

[0031] As such, a framework (representative of several implementations disclosed herein) is provided for composing texts about objects with structured information about these objects, and thus disclosed are methodologies for linking information from at least two data sources—one comprising a plurality of documents comprising text pertaining to at least one object, and one comprising a plurality of structured records comprising at least one characteristic of the at least one object, each characteristic comprising one property name and an associated property value corresponding to the property name for the at least one object—by determining one or more instance-based traits for each object in both data sources and associating at least one record with at least one document that refers to each object, each trait comprising one or more characteristics that identifiably distinguish each object from all other objects.

[0032] Part I: Overview of Various Implementations

[0033] Various implementations disclosed herein utilize a text document and a structured database. A text document may be a bag of words that does have any categorization of objects within its text according to any taxonomy. A structured database may be an arbitrary collection of records obtained from multiple sources—for example, in a product catalog the product specifications might have been obtained from multiple data providers—wherein the records are sets of pairs of property names and values. To describe the various implementations disclosed herein, assume a universe of objects (Ö) where each object is represented by a collection of characteristics, and each characteristic is a property <name, value> pair (that is, a property name and an associated property value corresponding to the property name for that object).

[0034] FIG. 1 is a table 100 representing four objects 102 (one per row) and a subset of characteristics 104 (organized in columns) associated with each object in accordance with various implementations disclosed herein. As illustrated in this figure, the table 100 illustrates perfect and complete information regarding the four objects 102 with regard to their corresponding characteristics 104. Of course, access to perfect and complete information of any kind is atypical in the real world, and perfect and complete information of Ö is rarely (if ever) achievable. Instead, at most one has access to a subset of objects in Ö as a collection of records, and this collection of records ({hacek over (R)}) may have only a random subset of characteristics that are relevant to its subset of objects from Ö.

[0035] FIG. 2 is a table 120 representing records 122 (one per row) corresponding to as subset of objects 102 and known characteristics 124 from FIG. 1. The known characteristics 124 are organized in columns according to the various characteristics 104 possible, and empty characteristic blocks represent unknown information with regard to the records 122 listed in the table 120.

[0036] FIG. 3 illustrates an example text document 140 (here a product web page) comprising data 142 that happens to correspond to the first record 122a of FIG. 2 (as well as the first object 102a of FIG. 1) representative of several implementation herein disclosed. In other words, based on the data 142, this text document 140—which is just one text document from the subset of accessible text documents ({hacek over (D)}) from the universe of all documents ()—can be identified as a text document containing information about one or more objects, in this case, object 102a corresponding to record 122a.

[0037] With regard to FIGS. 1-3, several implementations disclosed herein are directed to composing records in {hacek over (R)} with text from {hacek over (D)}. Conceptually, the records in {hacek over (R)} and text from {hacek over (D)} are mapped to object identifiers before {hacek over (R)} is composed with {hacek over (D)}; however, in some implementations, there are no explicit identifiers for all of the objects in Ö, and thus a surrogate for a subset of the explicit identifiers for Ö is used. For these several implementations, a distinct combination of characteristics pertaining to each object serves as a proxy for a distinguishable identifier for that object. More specifically, each object has multiple distinguishing sets of characteristics (e.g., traits) that may be used in turn to identifiably distinguish each object from the other objects. In FIG. 1, this distinguishing combination of traits for each object 102 (and on a row-by-row basis) is indicated using shaded boxes 106 (i.e., the shaded boxes in the same row as the object correspond to that object). As shown, for certain object (e.g., object 102a) a single characteristic (e.g., Model=SD1300IS) may alone completely distinguish one camera object from all others, while other objects may use two or more characteristics (e.g., Model=A400 and rand=Fuji) to uniquely identify and thereby distinguish an object from the other objects. It is also possible (and often the case) that an object may have more than one trait (i.e., combination of characteristics) that identifiably distinguishes (i.e., that uniquely identifies) the object from among the other objects.

[0038] In this manner, traits may serve as “signatures” of sorts for objects in O. Therefore, identifying these traits in {hacek over (R)} and {hacek over (D)} allows them to be associated with the objects to subsequently perform composition using the mapped set of traits. As such, the mapping function amounts to mapping records in {hacek over (R)} and text documents in {hacek over (D)} to a predetermined set of traits. For example, and referring again to FIG. 2, certain records for which the traits can be identified, and hence associated, have traits that are shown with shaded boxes 124. It should be noted that the third record (having Record ID 4300) may also have one of two traits, either (a) A400 and Powershot or (b) A400 and 5.8 oz, although neither trait has been specifically indicated in the figure. FIG. 3, on the other hand, shows that trait 142 has been identified in the document and that this trait 142 corresponds to Model=SD1300IS.

[0039] For several implementations, the mapping function may independently associate traits to records and text documents, and it should be noted each document may contain multiple traits corresponding to different objects. For example, consider a text document that reviews a product object by contrasting it with another product object. In this document, the traits for both of these products may be identified. Therefore, to facilitate the composition between a record and text, these several implementation may use a scoring function that utilizes additional characteristics (in addition to traits) present on the text document and in the records in order to score that particular text document's relevancy to a record that shares at least one of the traits in the document. As such, these implementations may use trait computations to identify signatures of objects, mapping functions to map traits to records and documents, and the composition function to compose the documents into the subset of relevant records out of the records that share at least one trait with the document. These elements are discussed in greater detail herein.

[0040] Text documents generally contain a larger number of property values corresponding to more relevant objects than less relevant objects, and such text documents also mention the more relevant objects with much higher frequency. As such, text documents have two highly-relevant features: (1) the fraction of distinct property names corresponding to property values found in the joining structured record and the text document that overlap, and (2) the weighted fraction of property values that overlap, where the weight is determined through the relative frequency of the corresponding property name and property value pairings. Moreover, when a small number of features are used, there is no need for a large amount of training data.

[0041] Part II: Associating Structured Records to Text Documents

[0042] Various implementations disclosed herein employ techniques for associating corresponding structured records to text documents. For several such implementations, these techniques are described in the context of two independently created data sources, the first of which contains text documents each discussing one or more (but generally a small number of) objects, and the second being a collection of structured records each containing information about the characteristics of some objects.

[0043] In order to associate a document to its relevant objects, it suffices to look at the object traits (T) that appear in the document. Again, traits are sets of attribute value pairs that serve to distinguish objects from each other and are computed directly from the structured database. For example, it may be determined from the structured database that the single attribute value pair T=<model, SD1300IS> is distinguishing enough to uniquely identify that a particular record is about the camera “Canon SD1300IS”. Although traits bear some resemblance to “keys” used in relational databases, it should be noted that traits are fundamentally different because traits are instance-based rather than schema-based (as is the case for relationship database keys). For example, and referring again to FIGS. 1 and 2, the “Fuji FinePix A400” camera may need to use the longer trait {<model, A400>, <brand, Fuji>} than just the simpler <model, A400> because the latter identifier is insufficient to distinguish the “Fuji FinePix A400” from the “Canon Powershot A400”.

[0044] The implementation framework for several implementations disclosed herein uses a trait generation algorithm that draws upon a connection of the problem with that of finding infrequent item sets while also using a graphical model to identify unsafe attribute value pairs that can lead to an invalid trait. Consider the following example: There is a camera called “Olympus Stylus 600” and {<brand, Olympus>, <model, 600>} might appear to be a reasonable trait computed from the database. However, the term “600” may appear in many documents for reasons unrelated to a model number (e.g., a price of 600 dollars). Thus, such a trait could lead to associating wrong documents to the Olympus camera. However, there may still be other traits—better traits—that could instead be used for mapping such as, in the foregoing example, {<brand, Olympus>, <line, Stylus>, <resolution, 6 mp>}.

[0045] The presence of a particular trait in a document is a strong indicator that the document refers to the object that the trait represents. However, a document may contain traits corresponding to multiple objects, with different degrees of importance of the document to them. To handle this, the framework also includes a machine-learned scoring function that provides a probabilistic score of agreement between matched documents and objects by leveraging the attribute-value pairs present in them. It should be kept in mind that the mere occurrence of a trait value does not imply that the document is about an object in the database.

[0046] This framework may be applied to a number of applications including web search, for example, by augmenting the web index with structured data for improving relevance and enriching search snippets.

[0047] Part III: Additional Details for the Conceptual Framework

[0048] Review of Context of Operation

[0049] If one postulates a universe of objects Ö, then each object OεÖ may be described by a set of characteristics. A characteristic X comprises a property name N and its value V, i.e., X←(N,V) (or equivalently (N=V)), and O←{X}. As such, property names and values may be arbitrary strings. Herein is denoted by {umlaut over (X)} the set of all characteristics, by Ñ the set of all property names, and by {tilde over (V)} the set of all property values. Different objects may have many of the same characteristics, but they differ at least in one characteristic, and thus every object can be thought of as having an implicit unique identity (although the object identity is not itself manifest).

[0050] For various implementations disclosed herein, a structured repository {hacek over (R)} and a text repository {hacek over (D)} are provided. The structured repository {hacek over (R)} contains the representations of objects from Ö, called records. Records comprise a set of characteristics (pairs of property names and their values) from objects, and there are no duplicates (identical records) in {hacek over (R)}. An object may be underrepresented in {hacek over (R)}; that is, property names in a record may only be a proper subset of property names in the object.

[0051] Records do not have primary keys, and thus an object may have multiple representations in {hacek over (R)} such that there may be more than one record, say R₁ and R₂, corresponding to the same object O but each having a different set of property names. Since records are in general an under-representation (or subset) of objects (i.e., all objects in Ö), it is possible that a record may represent more than one object.

[0052] The text repository {hacek over (D)} comprises text documents containing information about the objects in Ö where the text document is treated as a bag of words. As such, the text does not contain any explicit markings that can be used to identify the objects that the text is about; however the text may contain some of the property names and values that pertain to the objects described in the text. In addition, a text may contain information about objects for which there is no representation in {hacek over (R)} and, conversely, there may not be any text in {hacek over (D)} for a particular object, although this object still has a representation in {hacek over (R)}.

[0053] Data Model

[0054] If Ĩ represents the set of (hypothetical) object identities corresponding to objects in Ö, then the function RI: {hacek over (R)}→(Ĩ) results where P(Ĩ) represents the powerset of identities in Ĩ. Given a record Rε{hacek over (R)}, RI (R) yields the set of object identities {I}, where every I in this set corresponds to an object OεÖthat R represents. Similarly, the function DI: {hacek over (D)}→P(I) is such that DI(D) yields the set of identities of the objects that the text D is about.

[0055] Given these mapping functions, a result is defined by the following composition (given in pseudo-SQL syntax):

[0056]

	select R, D
	from {hacek over (R)} R, {hacek over (D)} D
	where ∃ IR ∈ RI(R)   ∃ ID ∈ DI (D)   IR = ID

[0057] With this in mind, presented below are algorithms for implementing the above composition. It should be noted, however, that the objects in the example framework do not have manifest identities, and therefore the computation methodology does not provide explicit implementation of RI or DI but instead aims to obtain the result of the prescribed composition.

[0058] Algorithm

[0059] FIG. 4 is a process flow diagram 200 illustrating an exemplary method for composing text and structured databases representative of various implementations disclosed herein. At 210, a set of traits are identified from the records in {hacek over (R)}. At 212, the records in {hacek over (R)} and the documents in {hacek over (D)} are mapped to these traits. At 214, a composition is performed between the records in {hacek over (R)} and the documents in {hacek over (D)} using the mapped set of traits. As previously mentioned earlier herein, ideally records and text would be mapped to object identifiers before {hacek over (R)} is composed with {hacek over (D)}; however, objects in Ö do not have explicit identifiers. Therefore, objects may instead be defined and distinguished by their characteristics, and thus various implementations disclosed herein search for distinct characteristics that can proxy as object identifiers and are referred to herein as traits. Thus, given a set of traits for Ö, if those traits can be identified in {hacek over (R)} and {hacek over (D)}, then the composition can be correctly effected. The mapping functions in the framework are then tantamount to mapping records in {hacek over (R)} and documents in {hacek over (D)} to a predetermined set of traits, and the composition is then performed over these mapped sets of traits. Traits are presented in more detail later herein.

[0060] System Architecture

[0061] FIGS. 5-12 together illustrate aspects of an exemplary system architecture for various implementations disclosed herein. FIG. 5 is a block diagram of an exemplary system architecture 400 for composing text and structured databases corresponding to one or more implementations disclosed herein. FIG. 6 is a table representing records 402′ (in rows) corresponding to an object database 402 illustrated in FIG. 5. FIG. 7 is a table representing traits 404′ (with rows organized by trait ID) that are determined for each object in the object database 402 by the trait generation 404 illustrated in FIG. 5. FIG. 8 is a table representing traits 406′ listed by trait ID derived by the trait generation 404 and filtered by the filtering module (or filter) 406 illustrated in FIG. 5. FIG. 9 is a table representing attributes 412′ and values corresponding to documents from among the web documents 410 tokenized by the document tokenization 412 illustrated in FIG. 5. FIG. 10 is a table representing a mapping 414′ of trait IDs to document IDs produced by the mapping module 414 illustrated in FIG. 5. FIG. 11 is a table representing the joined data 416′ from the resulting table 406′ from the filtering module 406 and the mapping 414′ from the mapping module 414 produced by the joiner module 416 illustrated in FIG. 5. FIG. 12 is a table 418′ representing the document/object pairs 420 scored by the scoring component 418 illustrated in FIG. 5.

[0062] As illustrated in FIG. 5, and with regard to FIGS. 6-12 described above, data from an object database 402 (represented by the table of FIG. 6) is utilized by a trait generator (shown as trait generation 404) to generate traits (represented by the tables of FIG. 7 and FIG. 8) that are then, in turn, filtered by a “distinguishing value” filter (shown as dist. value filtering 406) which, for certain implementations, may use an N-Gram Service component 408 (discussed further with regard to FIG. 14 and FIG. 15). Separately, data from web documents 410 is processed by a component for document tokenization 412 to identify characteristics (represented by the table of FIG. 9). Once the characteristics have been identified in the documents, the mapping module 414 (a.k.a., the mapping function) maps the documents to the set of traits previously computed and filtered (at 404 and 406 respectively) using the resulting tables 412′ and 406′. This mapping function essentially relies on matching characteristics found in the documents with those present in the traits. The traits from the filtering module 406 and mapping module 414 are then joined in a joiner module 416 to determine traits overlapping both the web documents 410 and the records in the object database 402—that is, the joiner module 416 joins the tables 414′ with 406′ to form table 416′ (of FIG. 11). This information is then scored (discussed later herein with regard to FIG. 13) user a scoring component 418 (a.k.a., the scoring function) from which final traits comprising document/object pairs with scores 420 (thereby yielding table 418′ of FIG. 12 from table '416) are determined and stored.

[0063] As will be readily appreciated by skilled artisans, the various modules and components (or functions) herein described—including but not limited to one or more of the trait generation 404, filtering 406, N-Gram service component 408, document tokenization 412, mapping module 414, joiner module 416, and scoring component 418—may be implemented in hardware and software using, for example, a computer processor such as the computer processor referred to in FIG. 17. Likewise, the object database 402, web documents 410, and the document/object pairs with scores 420 may be maintained in memory or other computer-readable media also referred to with regard to FIG. 17.

[0064] Utilizing the aforementioned system described in FIG. 5, various implementations disclosed herein are thereby able to link information from at least two data sources—including a first data source comprising documents comprising text pertaining to at least one object, and a second data source comprising structured records comprising at least one characteristic of the at least one object, each characteristic comprising at least one property name and an associated property value corresponding to the property name for the at least one object—and utilizing a processor (and/or other operational modules and components) for determining one or more instance-based traits for each object and for associating at least one record in the second data source with the at least one document from the first data source that refers to each object, each trait comprising one or more characteristics that identifiably distinguish each object from among all other objects in the plurality of documents. Several implementations are also directed to methods for linking information from at least two data sources by describing a plurality of objects using a set of characteristics wherein each object comprising the plurality of objects is identifiably distinguishable by one or more characteristics from among the plurality of characteristics, and then using at least one additional characteristic that does not comprise the set of characteristics to score a document's relevancy to a record from a first data source that shares at least one of the characteristics of a document from a second data source, wherein the additional characteristic is from the document. Yet other implementations are also directed to computer-readable instructions that cause a processor to map a plurality of documents in a first data source to a plurality of traits in a second data source, and then score the relevancy of a document from among the plurality of documents to at least one record from the second data source based on at least one of the characteristics of the document.

[0065] Traits

[0066] Since there is no access to Ö, various implementation disclosed herein generate traits from the only concrete representation of Ö available—namely {hacek over (R)}. Moreover, these traits are instance-based rather than schema-based and thus different objects may have traits comprised of different characteristics, and it is also possible for objects to have more than one trait.

[0067] To more formally define what constitutes a trait and a computation procedure for that trait, various implementations disclosed herein begin with a record Rε{hacek over (R)} that exhibits a characteristic (N,V) iff (N,V)εR. For a given integer ρ, a set of characteristics T constitute a ρ-trait of {hacek over (R)} (or simply trait, when ρ is clear from the context) iff {hacek over (R)} contains at least one and at most ρ records each of which exhibits every characteristic in T and no proper non-empty subset of T constitutes a trait. As used herein, {hacek over (T)} denotes the set of all traits of {hacek over (R)}. Because {hacek over (R)} is an imperfect representation of Ö, the definition of a trait deliberately allows for values of ρ to be greater than one (to accommodate the possibility of objects having multiple representations in {hacek over (R)}), although the degree of this “relaxation” (i.e., how much higher than one β is permitted to be) depends on the expected multiplicity of representations in {hacek over (R)}. For example, if {hacek over (R)} has been created from n data providers who have overlapping content, setting ρ←n would be reasonable. Of course, the flip side of “relaxation” is that a trait may now represent multiple objects (and unnecessarily so). At the time of composition, therefore, certain such implementations may use additional information present in the records and text documents to alleviate this ambiguity.

[0068] Computing Traits

[0069] For various implementations disclosed herein, it is recognized that there is a connection between the problem of finding traits and the problem of finding infrequent itemsets. In a database of records comprising items, a set of items is referred to as a ρ-frequent itemset if all these items are present in at least ρ records. Correspondingly, an itemset is ρ-infrequent if it is present in fewer than ρ records. Subsets of frequent itemsets are also frequent and supersets of infrequent itemsets are also infrequent. A minimal ρ-infrequent itemset is one which is ρ-infrequent but each of its proper subsets is ρ-frequent. Thus, the problem of computing all ρ-traits is same as the problem of computing all minimal (ρ+1)-infrequent itemsets.

[0070] As known and appreciated by skilled artisans, all minimal ρ-infrequent itemsets can be found in output quasi-polynomial time, i.e., time which is bounded by a quasi-polynomial in total number of minimal ρ-infrequent itemsets. Depth-first recursive algorithms for computing a given number of them are also known to skilled artisans. To generate all traits up to a certain maximum cardinality, a breadth-first algorithm may be used for trait generation that is suitable for implementation over data using database primitives.

[0071] Recalling that a trait T←F {X}, where Xε{umlaut over (X)} and {umlaut over (X)} denotes the set of all characteristics exhibited in {hacek over (R)}, and where Tⁱ is used herein to denote the set of all traits such that each trait has a cardinality of i, then for a given ρ the following “TraitGen” Algorithm 1 (employed by several implementations herein) will produce all ρ-traits of cardinality up to i_max, or in other words, the following “TraitGen” Algorithm 1 will correctly compute all ρ-traits of R for the specified values of ρ and imax:

[0072]

Algorithm 1: TraitGen algorithm for mining ρ-traits
Input: Structure Database {hacek over (R)}, Largest cardinality of desired traits imax,
Parameter ρ
Output: ∪j=0imax {hacek over (T)}j
1: {hacek over (T)}0 ← Ø
2: for i ∈ 1..imax do
3:	Ci ← {Xi ∈ P({umlaut over (X)}) | |{Xi ∈ R | R ∈ {hacek over (R)}}| ≦ ρ}
4:	Fi ← {Ti ∈ Ci | ∃ T ∈ P(Ti) s.t. T ∈ ∪j=0imax {hacek over (T)}j
5:	Ti ← Ci − Fi
6: Output ∪j=0imax {hacek over (T)}j

[0073] Because {hacek over (R)} is an imperfect representation of Ö, particular attention is given to how traits are generated. For example, simply using any original combination of characteristics in {hacek over (R)} as originally found in {hacek over (R)} can result in sparsity and duplicity of object representations. Therefore, in order to have effective traits, certain implementations disclosed herein operate such that every trait contains at least one “anchor property” that may be thought of as endowing pseudo-keys to the data. By analogy, just as names are a useful but imperfect method for distinguishing people, and phone numbers do a fairly good job of distinguishing businesses, anchor properties are those that have a large number of non-repetitive values that are well-distributed amongst records in the database.

[0074] FIG. 13 is a process flow diagram 230 representing a method for algorithmically determining anchor properties for several implementations. At 240, an anchor score is computed for every property name where a property's anchor score is the normalized entropy computed over all the values for that property. For example, let {umlaut over (N)} represent all the property names present in {hacek over (R)}. Using {{ . . . }} to denote a bag, compute the anchor score of every property name NεÑ as follows:

[0075]

		{tilde over (V)}′ ← {{V | (N,V) ∈ R   R ∈ {hacek over (R)}}}	(1)
		{tilde over (V)} ← {V | (N,V) ∈ R   R ∈ {hacek over (R)}}
		Anchor Score ← Entropy ({tilde over (V)})/log |{tilde over (V)}|

[0076] At 242, the property names are sorted in the decreasing order of their anchor score. At 244, the top k of the properties having the highest anchor scores are designated as anchor properties. Generally there is a sudden steep fall off in anchor scores, and methods for determining k are known to skilled artisans.

[0077] Intuitively, an anchor score indicates the distinctiveness of values for the corresponding property name, and it is generally beneficial to have traits comprising distinctive properties. It should also be noted that the choice of k influences the choice of i_max in Algorithm 1, as a trait comprised entirely of anchors would be a powerful trait. As such, it would make sense to set i_max≧k in Algorithm 1, and it may also be beneficial for the results of Algorithm 1 to be adapted (or possibly restricted) to ensure that every trait is anchored.

[0078] Mapping Records to Traits

[0079] When the trait set {hacek over (T)} to which records of {hacek over (R)} need to be mapped has been generated from {hacek over (R)} itself, the TraitGen Algorithm 1 for certain alternate implementations may be modified to concurrently enumerate and persist the {hacek over (R)}→{hacek over (T)}mappings while generating traits. On the other hand, a trait set may also have been obtained from an independent source such as, for example, a manually curated set. In such instances where every record Rε{hacek over (R)} has an internal identifier—referred to herein as R.rid, which uniquely designates R—the mappings from records to their traits may be kept in a table (RT) with entries in the form (R.rid,R.trait). Given such a trait set {hacek over (T)}, then RT←{(R.rid,T)|Tε{hacek over (T)}∃R s.t. T⊂R} will bind all the records in {hacek over (R)} to their traits.

[0080] Mapping Documents to Traits

[0081] Mapping a given document to traits from a given trait set is more challenging than just employing fast data structures for locating relevant traits within the document because the vocabulary used in the documents might be different than found in the structured data. However, this difficulty is ameliorated by certain implementations by using semantic translations of the values present in trait.

[0082] Another challenge is preventing distinguishing values within the structured database from being ambiguous in the text corpus. For example, both “LunarFly+” and “Free” are lines of Nike running shoes that might find their way into the trait set generated from a product database, but while the former trait is quite distinguishing the latter may be significantly ambiguous in many text corpora. Therefore, various implementations may preclude trait sets that include words that may be significantly ambiguous in view of at least the specific text corpus being utilized—that is, precluding at least one characteristic that is deemed to be too ambiguous in view of the content of text document data source.

[0083] Similarly, it is beneficial to prevent attributes of any specific text corpus from creeping into the trait generation process despite the temptation to do so with the intent of creating broadly applicable traits as introducing this kind of generality is often not necessary when mapping documents from a certain text corpus into traits and typically only serves to diminish the efficiency and effectiveness of the results. On the other hand, information may be used from a particular corpus to filter out traits containing commonly found values, and a method employed by certain implementations herein may utilize a probabilistic model as described in the next section.

[0084] Identifying Valid Values for Traits

[0085] For implementations where removing traits containing values that are common in the context of the text repository on which composition is performed may be beneficial, such implementations may utilize statistics of words (in particular, probability of occurrence) in the text repository to compare to occurrences in the structured repository {hacek over (R)}. The comparison may be performed for each property name and their corresponding values. For these implementations, the methodology addresses the challenge of identifying valid values as probabilistic inference in a generative model for values generated from the values present in {hacek over (R)} for the corresponding property name and/or from a background text corpus.

[0086] FIG. 14 is a process flow diagram 260 representing a method for filtering out traits containing commonly found values in a particular corpus that may be utilized by certain implementations disclosed herein. At 270, the model is trained using an unsupervised learning algorithm that does not require manually labeled input. Then, once the model is learned, at 272 an inference may be performed on the model to obtain the probability of a value being explained using {hacek over (R)}. At 274, those values with inferred probabilities in {hacek over (R)} below a threshold value (z) are identified as ambiguous (and hence invalid) values and, at 276, those traits that contain invalid property name/value combinations are pruned or eliminated as invalid.

[0087] In the context of the text corpus, and for some implementations, an N-gram computation (performing an N-Gram analysis) derived from the web corpus may be used to identify invalid values when the text documents are from the general pool of web pages. These values then become identifiers for use in subsequently identifying and removing (or “pruning”) such traits because these traits are deemed invalid for associating the records to the text documents. In this regard, {hacek over (R)}^N=RN={v₁, . . . , v_K} are the values for the property name N and correspond to K records in {hacek over (R)} (where herein {hacek over (R)}^N=RN are used interchangeably). It should be noted that v_i=v_j when the records i and j share the same value for the property name N.

[0088] FIG. 15 is a block diagram illustrating a generative model 300 for finding invalid trait values that may be utilized by some implementations disclosed herein. As illustrated in the figure, a generative model 300 comprises a value 308 that is present in the background corpus 302 and is also a value 304 for the property name N in {hacek over (R)} and related to the binary selection variable s 306. The binary selection variable s 306 is discussed in more detail below with regard to FIG. 16.

[0089] FIG. 16 is a table 320 representing examples of valid and invalid trait values detected by the generative model 300 of FIG. 15 (with invalid values 322 and 324 denoted by shaded rows). In operation, the binary selection variable s (306 in FIG. 15), along with prior p(s), defines which of the two sources is responsible for generating the value v. Hence, s takes two values, db and bg, corresponding to whether the value is generated from RN or from the background corpus respectively. Thus the probability of generating a value is defined by the choice of s and is given by p(v|s) as follows:

[0090] $\begin{array}{cc}p\left(v|s\right)=\{\begin{array}{cc}p\left(v|\mathrm{bg}\right)& \mathrm{if}s=\mathrm{bg}\\ p\left(v|\mathrm{RN}\right)& \mathrm{if}s=\mathrm{db}\end{array}& \left(2\right)\end{array}$

[0091] In equation (2), p(v|bg) and p(v|RN) are probabilities of observing the value in the background corpus and in RN. The joint probability p(v,s) is given by p(v,s)=p(s)p(v|s). When the text documents that correspond to web pages are considered, a corpus of web pages may be used to build the background model and, in particular, a web N-gram service may be used to estimate p(v|bg).

[0092] Given an observed value v=v*, various such implementations determine probabilistic inference by computing the posterior distribution over the unknown variables in the model. This amounts to inferring p(s=s*|v=v*), where s*ε{bg, db}. This, in turn, enables the performance of probabilistic inference by applying the Bayes rule:

[0093] $\begin{array}{cc}p\left(s=s^{*}|v=v^{*}\right)=\frac{p\left(v=v^{*}|s=s^{*}\right)p\left(s=s^{*}\right)}{\sum _{s=\left\{\mathrm{bg},\mathrm{db}\right\}}p\left(v=v^{*}|s\right)p\left(s\right)}& \left(3\right)\end{array}$

[0094] While p(v|RN), on the other hand, may be approximated by some such implementations using relative frequency counts of values in RN, other such implementations may instead learn these parameters such that those values that are more fully explained using the background model are down-weighted in the p(v|RN) calculation. For learning p(v|RN), in turn, training data may comprise only of those values, {vk}, currently present in RN. Then, assuming each value in RN is independent and identically distributed, an estimate θ*=p(v|RN) can be obtained by maximizing p(RN) as follows:

[0095] $\begin{array}{cc}{\theta }^{*}=\underset{\theta }{\arg \max }p\left(\mathrm{RN}\right)=\underset{\theta }{\arg \max }\prod _{k}p\left(v_k\right)=\underset{\theta }{\arg \max }\log \prod _{k}p\left(v_k\right)=\underset{\theta }{\arg \max }\sum _k\log \sum _{s_k}p\left(v_k,s_k\right)=\underset{\theta }{\arg \max }\sum _k\sum _{s_k}p\left(s_k|v_k\right)\log \frac{p\left(v_k|s_k\right)p\left(s_k\right)}{p\left(s_k|p_k\right)}& \left(4\right)\end{array}$

[0096] These implementations then solve for θ* by maximizing the observation probability using the iterative Expectation Maximization algorithm wherein there is iteration between the Expectation(E-) step and the Maximization(M-) step. Starting with the initial close to uniform probabilities over values, in the E-step, these implementations perform probabilistic inference using equation (3) to obtain p(sk|vk) for each data point. In the M-step, these implementations then use the following distribution to fill-in for the unobserved s_k to compute the current estimates for θ:

[0097] $\begin{array}{cc}p\left(v=v^{\prime }|\mathrm{RN}\right)=\frac{\sum _{k}p\left(s_k=\mathrm{db}|v_k=v^{\prime }\right)I\left(v_k=v^{\prime }\right)}{\sum _{k}p\left(s_k=\mathrm{db}|v_k=v^{\prime }\right)}& \left(5\right)\end{array}$

[0098] In this equation (5), I(vk=v′) is the indicator function that evaluates to one (1) when vk=v′. This equation can be derived from equation (4) by taking derivatives with respect to p(v=v|RN).

[0099] After learning the parameters of the model, and for each value in the database, these implementations perform inference using equation (3) to find the probability of the value being explained by the database and then prune traits that contain common values that do not meet a chosen threshold on this probability. FIG. 13 shows examples of property <name,value> pairs that are identified as valid (or invalid) to be present in the traits (as discussed earlier herein).

[0100] Composition

[0101] With mappings obtained from structured records as well as text documents to the same set of traits, various implementations may compose information about the same objects from the two repositories by doing a natural join on traits (e.g., by composing information pertaining to a set of objects common to the two data sources based on set the characteristics). However, since traits are computed from an imprecise representation of Ö, several such implementations use a function that provides a probabilistic score of agreement between matched documents and structured records.

[0102] For these implementations, the scorer is defined using binary logistic regression based on a set of features that measure the similarity between a text D and a record R. Given matched and mismatched training pairs, {F, Y}={(f₁,y₁), (f_T,y_T)} is the set of feature vectors along with their corresponding binary labels. Logistic regression maximizes the conditional log-likelihood of the training data: arg max log P (Y|F,w)≡arg max_w Σ_i=1^T log P (y_i|f_i,w), where w is the weight vector wherein each component w_j measures the relative importance of the feature f_j for predicting the label y, and P (y=1|f,w)←1/(1+exp(−(b+f^Tw))).

[0103] Since text documents generally contain larger number of property values corresponding to more relevant objects than less relevant ones and, in addition, also mention the more relevant objects with a much higher repetition frequency, two features that can be determined from the text document include: (1) a fraction of distinct property names corresponding to property values found in the joining structured record and the text document that overlap, and (2) a weighted fraction of property values that overlap, where the weight is determined through the relative frequency of the corresponding property name, property value pairs. For these features, and because a small number of features is used, there is no need for a large amount of training data.

[0104] Various implementations disclosed herein, and generally outlined in FIG. 5, address the problem of composing structured and text databases about objects in a very general setting, making minimal assumptions. Structured databases contain partial and possibly multiple representations of objects comprising property name and value pairs. Texts are bags of words devoid of any markings or structure that explicitly identifies the objects that the document is about. The notion of a trait is postulated herein as a set of characteristics that can serve as the proxy for the identity of an object, and techniques are presented herein for algorithmically computing traits, mapping structured records and text documents to traits, and using traits for joining information about the same object from two repositories.

[0105] FIG. 17 is a block diagram of an example computing environment that may be used in conjunction with example implementations and aspects. The computing system environment is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality.

[0106] Numerous other general purpose or special purpose computing system environments or configurations may be used. Examples of well known computing systems, environments, and/or configurations that may be suitable for use include, but are not limited to, personal computers (PCs), server computers, handheld or laptop devices, multiprocessor systems, microprocessor-based systems, network PCs, minicomputers, mainframe computers, embedded systems, distributed computing environments that include any of the above systems or devices, and the like.

[0107] Computer-executable instructions, such as program modules, being executed by a computer may be used. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Distributed computing environments may be used where tasks are performed by remote processing devices that are linked through a communications network or other data transmission medium. In a distributed computing environment, program modules and other data may be located in both local and remote computer storage media including memory storage devices.

[0108] With reference to FIG. 17, an exemplary system for implementing aspects described herein includes a computing device, such as computing device 500. In its most basic configuration, computing device 500 typically includes at least one processing unit 502 and memory 504. Depending on the exact configuration and type of computing device, memory 504 may be volatile (such as random access memory (RAM)), non-volatile (such as read-only memory (ROM), flash memory, etc.), or some combination of the two. This most basic configuration is illustrated in FIG. 17 by dashed line 506.

[0109] Computing device 500 may have additional features/functionality. For example, computing device 500 may include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated in FIG. 17 by removable storage 508 and non-removable storage 510.

[0110] Computing device 500 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by device 500 and include both volatile and non-volatile media, and removable and non-removable media.

[0111] Computer storage media include volatile and non-volatile, and removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Memory 504, removable storage 508, and non-removable storage 510 are all examples of computer storage media. Computer storage media include, but are not limited to, RAM, ROM, electrically erasable program read-only memory (EEPROM), flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the information and which can be accessed by computing device 500. Any such computer storage media may be part of computing device 500.

[0112] Computing device 500 may contain communication connection(s) 512 that allow the device to communicate with other devices. Computing device 500 may also have input device(s) 514 such as a keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s) 516 such as a display, speakers, printer, etc. may also be included. All these devices are well known in the art and need not be discussed at length here.

[0113] Computing device 500 may be one of a plurality of computing devices 500 inter-connected by a network. As may be appreciated, the network may be any appropriate network, each computing device 500 may be connected thereto by way of communication connection(s) 512 in any appropriate manner, and each computing device 500 may communicate with one or more of the other computing devices 500 in the network in any appropriate manner. For example, the network may be a wired or wireless network within an organization or home or the like, and may include a direct or indirect coupling to an external network such as the Internet or the like.

[0114] It should be understood that the various techniques described herein may be implemented in connection with hardware or software or, where appropriate, with a combination of both. Thus, the processes and apparatus of the presently disclosed subject matter, or certain aspects or portions thereof, may take the form of program code (i.e., instructions) embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium where, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the presently disclosed subject matter.

[0115] In the case of program code execution on programmable computers, the computing device generally includes a processor, a storage medium readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and at least one output device. One or more programs may implement or utilize the processes described in connection with the presently disclosed subject matter, e.g., through the use of an API, reusable controls, or the like. Such programs may be implemented in a high level procedural or object-oriented programming language to communicate with a computer system. However, the program(s) can be implemented in assembly or machine language. In any case, the language may be a compiled or interpreted language and it may be combined with hardware implementations.

[0116] Although exemplary implementations may refer to utilizing aspects of the presently disclosed subject matter in the context of one or more stand-alone computer systems, the subject matter is not so limited, but rather may be implemented in connection with any computing environment, such as a network or distributed computing environment. Still further, aspects of the presently disclosed subject matter may be implemented in or across a plurality of processing chips or devices, and storage may similarly be affected across a plurality of devices. Such devices might include PCs, network servers, and handheld devices, for example.

[0117] Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.