US 8,234,285 B1Grant

Context-dependent similarity measurements

Issue Date:2012-07-31

•18 Claims

•6 Drawing Sheets

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for determining similarity measures for objects in a dataset that include contextual associations of the objects with contexts. In one aspect, a method includes calculating a similarity measure for any two objects that include a common feature f based, in part, on the likelihood that the two object representations in the dataset that both include f will we associated with distinct contexts, and the likelihood that the two objects in the dataset that both include f will be associated with the same context.

Metadata

Assignee

Google Inc.

Inventor

William W. Cohen

Application Information

Application Number:US 12/506,685

Filing Date:2009-07-21

Priority Date:2009-07-10

Art Unit:2165

Classifications

IPC:

G06F7/00G06F17/30

Patent Drawings (6 sheets)

Description

Cross-Reference to Related Applications

[0001] This application claims the benefit under 35 U.S.C. §119(e) of U.S. Patent Application No. 61/224,757, titled “Context-Dependent Similarity Measurements,” filed Jul. 10, 2009, which is incorporated herein by reference.

Background

[0002] This specification relates to measuring the similarity of objects stored in datasets.

[0003] Heterogeneous datasets are datasets from several sources, each storing data representing objects. Each dataset includes an object identifier that identifies an object, a context value that identifies a context of the object, and a set of feature values that identify features of the object. The number of features and values often differ between each dataset, and within a dataset. Examples of such datasets are inventory catalog data from merchants, patient record data from hospitals, and technical paper data from publishers. For example, for inventory catalog data, an object identifier identifies a particular merchandise item, a context identifier identifies a particular vendor, and the set of feature values are words and numbers that describe the merchandise item.

[0004] Heterogeneous datasets are often integrated for data management, searching, and archiving operations. A common step in integrating heterogeneous datasets is determining a mapping between objects from one dataset and objects from another dataset. This step is often referred to as record linkage, matching, and/or de-duping. One useful matching strategy is to use a threshold similarity function that generates a similarity score from the feature values and identifies objects as identical if the similarity score exceeds a threshold value.

[0005] One widely-used similarity function is term frequency-inverse document frequency (TF-IDF) similarity. This similarity function identifies objects as similar if they are associated with a sufficient number of identical “terms”. TF-IDF processing works well in many situations, and the resulting statistics can be stored in compact form. TF-IDF processing also facilitates parallelization, and thus can be efficiently scaled. Other similarity processes that are used include edit distance processes, Jaccard distance processes, and token-based processes.

[0006] However, these processes do not take into account the context of the objects. This can cause, is some situations, skewing of similarity measures. One example situation is when a particular context in a dataset includes many of the same feature values, e.g., the merchant's store name. The store name is not highly indicative of object similarity, as the merchant may sell a number of different products. However, the presence of the store name as a feature in the dataset for many objects in a particular context can increase a similarity measure for any two of those objects.

Summary

[0007] This document describes processes for determining similarity measures for objects in a dataset that include contextual associations of the objects with contexts. A similarity measure for any two objects that include a common feature f is based, in part, on the likelihood that the two object representations in the dataset that both include the feature f will be associated with distinct contexts, and the likelihood that the two objects in the dataset that both include the feature f will be associated with the same context.

[0008] In general, one innovative aspect of the subject matter described in this specification can be embodied in methods that include the actions of selecting, by a data processing apparatus, object representations from a dataset storing a plurality of object representations, each object representation being an association of a object identifier that identifies an object instance in the dataset and corresponds to an object, a context value that identifies a context of the object, and a set of feature values that identify features of the object, and wherein each object identifier is unique in the dataset, and each context value is associated with one or more object identifiers; for each feature value, determining an inter-context score that is proportional to the number of different context values in the dataset that are associated with the feature value and determining an intra-context score that proportional to the number of times the feature value is associated with each context value; and for a selected pair of object representations, determining a similarity score based on an inter-context score and an intra-context score of a matching feature value in the set of features for the pair of object representations, the similarity score being a measure of the similarity of the object representations in the pair of object representations. Other embodiments of this aspect include corresponding systems, apparatus, and computer programs, configured to perform the actions of the methods, encoded on computer storage devices.

[0009] Another innovative aspect of the subject matter described in this specification can be embodied in methods that include the actions of selecting, by a data processing apparatus, object representations from a dataset storing a plurality of object representations, each object representation being an association of, a object identifier that identifies an object instance in the dataset and corresponds to an object; a context value that identifies a context of the object, and a set of feature values that identify features of the object, wherein each object identifier is unique in the dataset, and each context value is associated with one or more object identifiers; and generating feature weights and associating the feature weights with the feature values in the sets of features in the dataset, each feature weight for a feature value being proportional to the frequency of co-occurrence of the feature value with different context values in the dataset. Other embodiments of this aspect include corresponding systems, apparatus, and computer programs, configured to perform the actions of the methods, encoded on computer storage devices.

[0010] The details of one or more embodiments of the subject matter described in this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.

Brief Description of the Drawings

[0011] FIG. 1 is a block diagram of an example system for generating context-dependent similarity metrics.

[0012] FIG. 2 is a flow diagram of an example process for generating context-dependent feature weights.

[0013] FIG. 3 is a flow diagram of an example process for generating a context-dependent similarity measure from feature weight vectors.

[0014] FIG. 4 is a block diagram illustrating an example process for generating context histograms.

[0015] FIG. 5 is a flow diagram of an example process for generating context-dependent similarity measures from context histograms.

[0016] FIG. 6 is a flow diagram of an example process for generating context-dependent similarity measures with empirical priors.

[0017] FIG. 7 is a block diagram of a programmable processing system.

[0018] Like reference numbers and designations in the various drawings indicate like elements.

Detailed Description

1.0 Context-Dependent Similarity System Overview

[0019] FIG. 1 is a block diagram of an example system 100 for generating context-dependent similarity metrics. The system 100 can, for example, be in data communication with a computer network 102, such as a local area network (LAN), wide area network (WAN), the Internet, or a combination thereof. Data providers 104-1 . . . n can provide constituent datasets 105-1 . . . n to an aggregator 110. Example constituent datasets include inventory catalog data from merchants, patient record data from hospitals, and technical paper data from publishers, to name just a few. The aggregator 110 stores the received constituent datasets in a consolidated dataset 120. For clarity, the consolidated dataset will simply be referred to as dataset 120.

[0020] In some implementations, the datasets 105 can be web-based resources, and the data providers 104 can be web sites. Each web site 104 is one or more resources 105 associated with a domain name, and one or more servers host each web site, and each resource 105 is any data that can be provided by the web site 104 over the network 102 and that is associated with a resource address. Examples of resources include HTML pages, word processing documents, portable document format (PDF) documents, images, video, and feed sources, to name just a few. In these implementations, the aggregator 110 can crawl the websites and store the received resources in the dataset 120.

[0021] The dataset 120 is a collection of object representations x_i. Each object representation x_irepresents some object, e.g., a book, a merchandise item, a technical paper. Each object representation includes an object identifier id(x_i), e.g., ID₁, ID₂. . . ID_mfor i=1 . . . m; a context value c(x_i), e.g., c₁. . . c_k, and a set of feature values F(x_i), e.g., f₁, f₂. . . f_n.

[0022] Each object identifier is unique in the dataset, and each context value is associated with one or more object identifiers. For example, the object identifiers ID₁and ID₂are associated with the context c₁. Assuming the object identifiers ID₁and ID₂correspond to two different products, and the context c₁is a merchant name, then the two objects represented by the first and second object instances are provided by the same merchant. The set of features might be the words in the name of the product and copy describing the product.

[0023] A contextual similarity engine 112 accesses the dataset 120 and generates similarity data 122 that include similarity scores sim_m,n. Each similarity score sim_m,nis a measure of the similarity of two object representations in a pair of object representations.

[0024] In some implementations, the contextual similarity engine 112 uses a modified TF-IDF process that accounts for the contexts of the object instances in the dataset 120. Let V_Dbe the vocabulary associated with the dataset 120, i.e.,

[0025]

V_{D} \equiv ⋃_{x_{i} \in D} F (x_{i})

The elements of V_Dare all features f₁, . . . f_|_D_|.

[0026] Any set of feature values F_ithat are a subset of V_Dcan also be represented as the vector v(x_i), also written as v_i:
v_i= custom character

a₁, . . . a_|V_D_| custom character

where the k-th component a_kis 1 if f_kis in the set of feature values F_i, and 0 if f_kis not within the set of feature values F_i.

[0027] The contextual similarity engine 112 generates the feature vectors v, and uses the feature vectors to determine the document frequency of the feature values f_kwith respect to the dataset 120. In particular, with D being the dataset 120 of object instances x₁, . . . x_n, the document frequency of a feature value f with respect to the dataset 120 (“D”) is defined as the number of object instances that include the feature f, i.e.,
DF_D(f){x_iεD:fεF(x_i)}|
and the inverse frequency of the feature with respect to the dataset 120 is defined as:

[0028]

{IDF}_{D} (f) \equiv \log (\frac{\langle D \rangle}{{DF}_{D} (f)})

The inverse frequency values of the feature values are used to generate an inverse frequency weighted vector w_i, i.e.,
w(x_i)= custom character

b₁, . . . , b_|V_D_| custom character

where the k-th component b_kof w_iis a_k·IDF_D(f_k).

[0029] For each feature f_k, contextual similarity engine 112 determines a context similarity value CX(f_k), the details of which are described below. The contextual similarity engine 112 combines the frequency weighted vector w_iwith the context similarity values to generate a context-dependent inverse frequency weighted vector z₁, i.e.,
z(x_i)= custom character

d₁, . . . , d_|V_D| custom character

where the k-th component d_kZ_iis b_k·CX(f_k)=a_k·IDF_D(f_k)·CX(f_k). In some implementations, the characteristics of the context similarity value are such that the magnitude is of the context similarity value is approximately proportional to the ratio of an estimated probability that two object instances in the dataset 120 that both include a feature value f_kwill be associated with distinct context values to the estimated probability that the two objects in the dataset 120 will be associated with the same context values.

[0030] The contextual similarity engine 112 can select any two object representations and determine a similarity score for the object representations from the context-dependent inverse frequency weighted vectors. In some implementations, the similarity score is cosine similarity score (also referred to as a TF-IDF similarity score), and is generated according to the equation:

[0031]

{sim}_{CX \cdot IDF} (x_{i}, x_{j}) \equiv \frac{z_{i} \cdot z_{j}}{ z_{i}  \cdot  z_{j} }

where the numerator is the inner product of the two vectors z_iand z_j.

[0032] The contextual similarity engine 112 associates the similarity scores for the pairs of object representations in similarity data 122. The similarity data 122 can be used, for example, by another application engine 130 to perform one or more data processing operations. For example, the application engine 130 can be a clustering engine that can generate cluster data representing object clusters. Alternatively, the application engine 130 can be a search engine that ranks object representations stored in the dataset 120 by relevance scores that measure the relevance of the object representations to a search query. The search engine can use the similarity data to, for example, identify duplicate object representations, web pages, etc., and either promote or demote the identified duplicates according to one or more search processing algorithms. Many other data processing operations that operate on the dataset 120 can also use the similarity data 122 as input.

2.0 Context-Dependent Similarity Measurements

[0033] As described above, the context-dependent similarity measurement is substantially proportional to the frequency of co-occurrence of the feature value with different context values in the dataset 120, and can be further inversely proportional to the frequency of occurrence of the feature value for each context value. In some implementations, the context-dependent similarity measurements are based on an inter-context score and an intra-context score associated with each feature value. In particular, the contextual similarity engine 112 determines, for each feature value, an inter-context score that is proportional to the number of different context values in the dataset that are associated with the feature value, and an intra-context score that proportional to the number of times the feature value is associated with each context value.

[0034] In some implementations, the inter-context score is a probability, Pr^INTER, that a random pair of object representations that each include a particular feature value are each associated with different context values, i.e., the probability that two object representations selected uniformly at random and that include the feature f are associated with different context values. Conversely, the intra-context score is a probability, Pr^INTRA, that a random pair of object representations that each include the particular feature value are each associated with the same context value, i.e., the probability that two object representations selected uniformly at random and that include the feature f are associated with same context value.

[0035] The contextual similarity engine 112 determines the inter-context scores and the intra-context scores for each feature according to the following formulas:

[0036]

\begin{matrix} \begin{matrix} \Pr^{INTER} (f) \equiv \Pr (c_{i} \neq c_{j} ❘ x_{i} ~ D_{f} and x_{i} ~ D_{f} and x_{i} \neq x_{j}) \\ = \sum_{c \in C_{D}} \Pr (c_{i} = c ❘ x_{i} ~ D_{f}) \cdot \Pr (c_{j} \neq c ❘ x_{j} ~ D_{f} - {x_{i}}) \\ = \sum_{c \in C_{D}} \frac{n_{c, f}}{n_{f}} \cdot \frac{n_{f} - n_{c, f}}{n_{f} - 1} \end{matrix} & (1) \\ \begin{matrix} \Pr^{INTRA} (f) \equiv \Pr (c_{i} = c_{j} ❘ x_{i} ~ D_{f} and x_{i} ~ D_{f} and x_{i} \neq x_{j}) \\ = \sum_{c \in C_{D}} \Pr (c_{i} = c ❘ x_{i} ~ D_{f}) \cdot \Pr (c_{j} = c ❘ x_{j} ~ D_{f} - {x_{i}}) \\ = \sum_{c \in C_{D}} \frac{n_{c, f}}{n_{f}} \cdot \frac{n_{c, f} - 1}{n_{f} - 1} \end{matrix} & (2) \end{matrix}

where:
n is the number of object representations in the dataset 120, i.e.,
n≡|D|
C_Dis the set of contexts in the dataset, i.e.,
C_D≡{c(x_i):x_iεD}
n_cis the number of object representations in the dataset associated with the context value c, i.e.,
n_c≡|{x_iεD:c_i=c}|
n_fis the number of object representations in the dataset that include the feature value f, i.e.,
n_f≡DF_D(f)≡{x_iεD:fεF_i}|
n_c,fis the number of instances in the dataset that include the feature value f and are associated with the context value c, i.e.,
n_c,f≡|{x_iεD:fεF_iand c_i=c}|
D_fis the instances in the dataset 120 (D) that include the feature f, i.e.,
D_f≡{x_iεD:fεF_i}
and x˜D_fdenotes selecting the object representation x uniformly from D_f.

[0037] In some implementations, the contextual similarity engine 112 determines the context similarity value according to the following formula:

[0038]

\begin{matrix} CX (f) \equiv \log \frac{\Pr^{INTER} (f)}{\Pr^{INTRA} (f)} & (3) \end{matrix}

[0039] In some implementations, the contextual similarity engine 112 implements one or more smoothing or bounding operations when determining the inter-context and intra-context scores. The bounding and smoothing operations address the rare cases in which n_f=1 or Pr^INTRA(f)=0. In the former case, CX(f)=1 if n_f=1, which leaves the original feature weight unchanged. For the latter case, the estimates for Pr^INTRAand Pr^INTERare smoothed away from extreme values of 0 and 1. Example smoothing and bounding processes are described in section 5 below.

2.1 Example Contextual Similarity Processing of a Dataset

[0040] Consider the example dataset of Table 1 below. In Table 1, each object representation (row) corresponds to a product, and is identified by an identifier id_i. The feature set F_iincludes words in the name of the product and description of the product, and the context value c_iidentifies a merchant offering the product.

[0041]

TABLE 1

id_i	C_i	F_i

us:gh1	ToyCoUS	guitar, hero, IIIx, controller, from, ToyCoUS
us:gh2	ToyCoUS	guitar, hero, for, gameboy, from, ToyCoUS
us:b14	ToyCoUS	lego, bionicle, kit, x14, from, lego
us:b23	ToyCoUS	lego, bionicle, kit, x23, from, lego
us:b37	ToyCoUS	lego, bionicle, model, x37, from, lego
bb:gh2	ToyCoBB	guitar, hero, IIIx, for, gameboy
bb:b14	ToyCoBB	lego, bionicle, x14, truck, kit
bb:b23	ToyCoBB	lego, bionicle, x23, zombie, kit
bb:b37	ToyCoBB	lego, bionicle, x37, watermelon, kit
cc:gh2	ToyCoCC	guitar, hero, IIIx, for, gameboy
cc:b14	ToyCoCC	lego, bionicle, x14, truck, kit
cc:b23	ToyCoCC	lego, bionicle, x23, zombie, kit
cc:b37	ToyCoCC	lego, bionicle, x37, watermelon, kit

[0042] For the dataset of Table 1, the feature weights (IDF_D(f)) for each feature are provided in Table 2:

[0043]

	TABLE 2

	Feature f	IDF_D(f)

	IIIx	1.466
	bionicle	0.368
	controller	2.565
	for	1.467
	from	0.956
	gameboy	1.467
	guitar	1.179
	hero	1.179
	kit	0.486
	lego	0.368
	model	2.565
	ToyCoUS	1.872
	truck	1.872
	watermelon	1.872
	x14	1.467
	x23	1.467
	x37	1.467
	zombie	1.872

[0044] As the dataset of Table 1 is a product listing for merchants, any two object representations for the same context (i.e., any two products for the same merchant) are unlikely to be identical, as this would indicate a duplication of a product listing within a single merchant's dataset. Such duplications have been found to be unlikely. Additionally, many of the weights of Table 2 correlate to the intuitive notion of “importance” of the IDF function. For example, the features “from”, “lego” and “bionicle” have relative low feature weights, as they are shared by many pairs of object representations. Conversely, the features “IIIx”, “x14” and “x37” have higher weights, and appear in object representations that represent the same item offered by different merchants.

[0045] Note, however, the feature weight for ToyCoUS is larger than the feature weights of IIIx, x14 and x37. Additionally, the features IIIx, x14 and x37 co-occur with each context ToyCoUS, ToyCoBB, and ToyCoCC, and occur only once for each context. Conversely, the feature ToyCoUS occurs twice in the context of ToyCoUS, and does not occur in any other context. Thus, the context similarity values CX(ToyCoUS), CX(IIIx), CX(x14) and CX(x37) result in the feature weight of the feature ToyCoUS being less than the feature weights of the features IIIx, x14 and x37.

[0046] The effect of the feature weight adjustments are shown in Table 3 below, which lists the similarity measures for some of the pairs of object representations in the dataset of Table 1. The pairs that are below the line refer to different products, while the pairs that are above the line refer to the same product. The similarity measures in the column sim_IDF(x_i, x_j) are calculated using the inverse frequency weighted vector w. The similarity measures in the column sim_CX·IDF(x_i, x_j) are calculated using the inverse frequency weighted vector z that, in turn, is calculated from the vector w and smoothed values of CX(f).

[0047]

TABLE 3

Pair id_i, id_j	sim_IDF(x_i, x_j)	sim_CX.IDF(x_i, x_j)

bb:b14, cc:b14	1.00	1.00
bb:b23, cc:b23	1.00	1.00
bb:b37, cc:b37	1.00	1.00
bb:gh2, cc:gh2	1.00	1.00
bb:b23, us:b23	0.86	0.99
cc:b23, us:b23	0.86	0.99
bb:gh2, us:gh2	0.82	0.84
cc:gh2, us:gh2	0.82	0.84
cc:b14, us:b14	0.57	0.88
bb:b14, us:b14	0.57	0.88
bb:b37, us:b37	0.31	0.85
cc:b37, us:b37	0.31	0.85
us:gh1, us:gh2	0.53	0.19
bb:gh2, us:gh1	0.46	0.62
cc:gh2, us:gh1	0.46	0.62

[0048] As shown in Table 3, the similarity measures sim_CX·IDF(x_i, x_j) take into account the contexts of the features.

3.0 Example Contextual Similarity Processes

[0049] FIG. 2 is a flow diagram of an example process 200 for generating context-dependent feature weights. The process 200 can be implemented in the contextual similarity engine 112.

[0050] The process 200 selects a dataset storing object representations (202). For example, the contextual similarity engine 112 can select the dataset 120. The dataset 120 includes a plurality of object representations, each object representation being an association of an object identifier that identifies an object instance in a dataset and corresponds to an object, a context value that identifies a context of the object, and a set of feature values that identify features of the object.

[0051] For each feature value, the process 200 determines a frequency of co-occurrence of the feature value with different context values in the dataset (204). For example, the contextual similarity engine 112 can determine the number of context values with which a feature value is associated.

[0052] For each feature value, the process 200 determines a frequency of occurrence of the feature value for each context value (206). For example, the contextual similarity engine 112 can determine, for each context value, the number of object representations that include the frequency value.

[0053] For each feature value, the process 200 determines a feature weight based on the frequency of co-occurrence and the frequency of occurrence (208). For example, the contextual similarity engine 112 can multiply an inverse frequency value for the feature value by another value that is proportional to the ratio of the frequency of co-occurrence to the frequency of occurrence.

[0054] FIG. 3 is a flow diagram of an example process 300 for generating a context-dependent similarity measure from feature weight vectors. The process 300 can be implemented in the contextual similarity engine 112.

[0055] The process 300 determines a probability that a random pair of object representations that each include a feature value f are each associated with different context values (302). For example, the contextual similarity engine 112 can determine the value Pr^INTER(f).

[0056] The process 300 determines a probability that a random pair of object representations that each include the feature value are each associated with the same context value (304). For example, the contextual similarity engine 112 can determine the value Pr^INTRA(f).

[0057] The process 300 generates a weighted vector including the feature weights for corresponding feature values, the feature weights being proportional to a ratio of the inter-context score of the feature value to the intra-context score of the feature value (306). For example, the contextual similarity engine 112 can generate the vector w and multiply the feature weights of the vector by corresponding context similarity values CX to generate the vector z.

[0058] The process 300 determines a cosine similarity value from the weighted vectors. For example, the contextual similarity engine 112 can determine the value sim_CX·IDF(x_i, x_j).

4.0 Example Process for Computing Context-Dependent IDF Similarity

[0059] FIG. 4 is a block diagram illustrating an example process 400 for generating context histograms. The process 400 facilitates parallelization among multiple computers in a data processing apparatus, e.g., distributing processing of the contextual similarity engine 112 over multiple computers.

[0060] The process 400 performs an initial pass over the dataset 120 to determine the frequencies of contexts (n_c) in the dataset 120 (402). Typically, there are only a few thousand distinct contexts, even for a very large dataset 120, and thus storing this information is not expensive.

[0061] Thereafter, the process 400 generates feature value and context value vector pairs (404). The feature value and context value vector pairs are of the form
(f, custom character

c₁, . . . , c_n custom character

)
where f is a feature and c₁, . . . , c_nis a sorted list of all context values that co-occur with that feature.

[0062] The process 400 then generates context histograms for each feature f (406). The context histograms are of the form
(f, custom character

(c₁,n_f,c₁), . . . , (c_n,n_f,c_n) custom character

)
where the pair (c_i, n_f,ci) contains a context and the number of times the context was duplicated for that feature. Because the feature weight CX(f)·IDF(f) for a feature f depends only on the context histogram off, the process 400 can be readily parallelized. For example, a first processor can be tasked with determining the feature weights for a particular context histogram for a first feature f₁, and a second processor can be tasked with determining the feature weights for a particular context histogram for a second feature f₂.

[0063] FIG. 5 is a flow diagram of an example process 500 for generating context-dependent similarity measures from context histograms. The process 500 can be implemented by the contextual similarity engine 112 operating in a parallelized environment.

[0064] The process 500 counts frequencies of context (n_c) in a dataset (502). For example, the contextual similarity engine 112 can, for each context c, initialize a context counter n_cto 0, and set another context independent counter n to 0. For each object representation in the dataset, a context counter corresponding to the context value of the object representation is incremented. Additionally, the counter n is incremented for each object representation in the dataset.

[0065] The process 500 initializes a map list (504), and for each feature value in each object representation, adds a feature value and context value pair to the map list (506). For example, the contextual similarity engine 112 can initialize the map list and append the feature value and context value pairs (f, c_i) to the map list.

[0066] The process 500 sorts the map list (508). For example, the contextual similarity engine 112 can sort the map list lexicographically.

[0067] The process 500 collects sequences of adjacent feature and context value pairs with the same feature value and replaces them with a feature value and context value vector pair (510). For example, the contextual similarity engine 112 can collect sequences of adjacent pairs (f, c₁) . . . (f, c_n) with the same feature and replace them with a feature value and context value vector pair (f, <c₁, . . . c_n>).

[0068] The process 500, for each feature value and context vector value pair, determines the number of object representations that include the feature value (n_f) and, for each context value, determines the number of object representations that include the feature value and are associated with the context value (n_c,f) (512). For example, the contextual similarity engine 112 can, from the list <c₁, . . . c_n>, computer the feature value n_fand the context value n_c,ffor each feature.

[0069] The process 500 determines, for each feature value, a context similarity value using n_fand n_c,f(514). For example, the contextual similarity engine 112 can determine the values CX(f) using equations (1)-(3) above. Alternatively, if smoothing is implemented, the contextual similarity engine 112 can determine the values CX(f) using equation (3) above and equations (4) and (5) below.

[0070] The process 500 determines, for each feature value, an inverse frequency value of the feature value with respect to the dataset (516). For example, the contextual similarity engine 112 can determine the values of IDF(f), e.g., log(n/n_f).

[0071] The process 500 generates, for each feature value, a feature value and feature weight pair (f, FW) and adds the feature value and feature weight pair to a feature weight list (518). For example, the contextual similarity engine 112 can generate the pair of values (f, CX(f)·IDF(f)) for each feature f and add the pair to a feature weight list.

[0072] The process 500 generates, for each feature value, a feature value and context similarity value pair (f, CX(f)) and adds the feature value and context similarity value pair to a context similarity list. For example, the contextual similarity engine 112 can generate the feature value and context similarity value pair (f, CX(f)) and add each pair to the context similarity list.

[0073] The data generated by the process 500 can be stored as the similarity data 122 and associated with the dataset 120.

5.0 Example Smoothing and Bounding Processes

[0074] As described above, the definitions of Pr^INTRA(f) and Pr^INTER(f) are maximum likelihood estimates, and it is possible for Pr^INTRA(f) to have a value of 0, resulting in an indeterminate value for CX(f). If the system has prior knowledge of the importance of a feature f, this prior knowledge can be incorporated by smoothing the estimate toward these values. In general, if a quantity is estimated to be p₁based on m₁examples and the system is provided two values p₀, m₀representing a prior probability p₀and a “strength” (expressed in number of equivalent examples) m₀, then a Dirichlet-smoothed estimate of the following form can be used:

[0075]

\hat{p} = p_{1} \cdot \frac{m_{1}}{m_{1} + m_{0}} + p_{0} \cdot \frac{m_{0}}{m_{1} + m_{0}} = \frac{p_{1} m_{1} + p_{0} m_{0}}{m_{1} + m_{0}}

[0076] In some implementations, p₀is set to 0.5 and m₀is set to 1.

[0077] In some implementations, the feature values of the dataset 120 are divided into disjoint sets V₁. . . V_m. Each disjoint set includes different types of features that are expected to have different levels of importance. For example, for a dataset related to movies, a first disjoint set of features can be from movie titles; a second disjoint set of features can be from director names; a third disjoint set of features can be from cast names; and a fourth disjoint set of features can be from movie summaries.

[0078] The CX(f) values are computed for each feature using the default priors, over each subset of features belonging to each disjoint set V_l, and the mean μ₁and standard deviation σ₁for the values of CX(f) are determined. From these mean and standard deviation values, a prior value p₁and a strength value m₁are determined. In some implementations, the prior p₁, m₁for features f that are in the disjoint set V_lare set as:

[0079]

p_{l} \equiv \frac{p_{0} m_{0} + p_{l}^{'} m_{l}^{'}}{m_{0} + m_{l}^{'}}

m_{l} \equiv m_{0} + m_{l}^{'}

where p₀, m₀are initial values (e.g., 0.5 and 1) and:

[0080]

p_{l}^{'} = μ_{l}

m_{l}^{'} = \frac{μ_{l} (1 - μ_{l})}{σ_{l}^{2}}

[0081] Once p₁and m₁are determined, the CX(f) values are re-computed using the revised priors. This process is described in more detail with respect to FIG. 6 below.

[0082] The values of Pr^INTER(f) and Pr^INTRA(f) are smoothed towards p₀and m₀:

[0083]

\begin{matrix} \begin{matrix} \Pr^{INTER} (f) \equiv \Pr (c_{i} \neq c_{j} ❘ x_{i} ~ D_{f} and x_{i} ~ D_{f} and x_{i} \neq x_{j}) \\ = \sum_{c \in C_{D}} \Pr (c_{i} = c ❘ x_{i} ~ D_{f}) \cdot \Pr (c_{j} \neq c ❘ x_{j} ~ D_{f} - {x_{i}}) \\ \approx \sum_{c \in C_{D}} \frac{n_{c, f} + p_{0} m_{0}}{n_{f} + m_{0}} \cdot \frac{n_{f} - n_{c, f} + p_{0} m_{0}}{n_{f} - 1 + m_{0}} \end{matrix} & (4) \\ \begin{matrix} \Pr^{INTRA} (f) \equiv \Pr (c_{i} = c_{j} ❘ x_{i} ~ D_{f} and x_{i} ~ D_{f} and x_{i} \neq x_{j}) \\ = \sum_{c \in C_{D}} \Pr (c_{i} = c ❘ x_{i} ~ D_{f}) \cdot \Pr (c_{j} = c ❘ x_{j} ~ D_{f} - {x_{i}}) \\ \approx \sum_{c \in C_{D}} \frac{n_{c, f} + p_{0} m_{0}}{n_{f} + m_{0}} \cdot \frac{n_{c, f} - 1 + p_{0} m_{0}}{n_{f} - 1 + m_{0}} \end{matrix} & (5) \end{matrix}

[0084] In a first variant of this implementation, the values of p₀and m₀are set to 0.5 and 1.0 and are not adjusted, i.e., the values of Pr^INTERand Pr^INTRAare calculated using these initial values of p₀and m₀. This variant is also referred to as a “Laplace-corrected” variant, and the resulting values of CX(f) are minimally smoothed away from extreme values.

[0085] In a second variant of this implementation, the CX(f) values are calculated using the Laplace-corrected variant, and then process 600 of FIG. 6 is used to calculate empirical priors. The equations (4) and (5) above are then adjusted for the empirical priors and the adjusted equations (4) and (5) are used for generating the smoothed CX(f) values.

[0086] In some implementations, the similarity function sim_CX·IDFcan be bounded away from unity. This is accomplished by adding to every set of feature values a unique feature value that is included only in that set of feature values. The unique feature value has an associated feature weight γ in a corresponding weighted vector that causes the resulting similarity score (e.g., cosine similarity value) to be less than one. In some implementations, the definition of the inner product and ∥v∥ can be modified to implement the bounding by the unique feature γ. Let z_i,fbe the component of z_ithat corresponds to the feature f, and similarly for z_j,f. Then:

[0087]

\begin{matrix} {sim}_{CX \cdot IDF} (x_{i}, x_{j}) \equiv \frac{z_{i} \cdot z_{j}}{ z_{i}  \cdot  z_{j} } \\ = \frac{\sum_{f}^{} z_{i, f} \cdot z_{j, k}}{\sqrt{\sum_{f}^{} z_{i, f}^{2}} \sqrt{\sum_{f}^{} z_{j, f}^{2}}} \\ \approx \frac{\sum_{f}^{} z_{i, f} \cdot z_{j, k}}{\sqrt{γ + \sum_{f}^{} z_{i, f}^{2}} \sqrt{γ + \sum_{f}^{} z_{j, f}^{2}}} \end{matrix}

[0088] The value of γ can vary. In some implementations, the values can range from 0 (no bounding) to 10.

[0089] FIG. 6 is a flow diagram of an example process for generating context-dependent similarity measures with empirical priors. The process 600 can be implemented in the contextual similarity engine 112.

[0090] For each feature type 1, the process initializes counters a, b and c (602). For example, the contextual similarity engine 112 can initialize counters for each disjoint set of feature values. If there are no disjoint sets, i.e., the same smoothing values are used for all features, then only one set of counters are initialized.

[0091] For each feature value and context similarity value pair in the context similarity list generated by the process 400, the process 600 increments counter a by CX, increments counter b by CX², and increments counter c by 1 (604). For example, the contextual similarity engine 112 can increment the counters for each (f, CX) pair.

[0092] The process 600 determines prior adjustments p′₁and m′₁to priors p₀and m₀(606) For example, the contextual similarity engine 112 can perform the following calculations:
p′_l=a_l/c_l
σ′_l=√{square root over (b_l/c_l−(p′—l)²)}
m′_l=(p′_l(1−p′_l)σ²)
The process 600 determines the priors p_iand m_ifrom the prior adjustments (608). For example, the contextual similarity engine 112 can perform the following calculations:

[0093]

m_{l} = m_{0} + m_{l}^{'}

p_{l} = \frac{p_{l}^{'} m_{l}^{'} + p_{0} m_{0}}{m_{0} + m_{l}^{'}}

[0094] The process 600 generates new feature weights for the feature values for the features of type l using the priors p_land m_l(610). For example, the contextual similarity engine 112 can re-execute the process 400 using equation (3) and the Dirichlet-smoothed versions of equations (1) and (2) (i.e., equations (4) and (5)) wherein the priors are m_land p₁, and where l is the type of feature f.

[0095] Although a Dirichlet smoothing scheme has been described, other smoothing schemes can also be used.

6.0 Inverse Similarity Score Classification

[0096] A variant of CX context similarity values can be used for classification instead of similarity matching. Assuming that each class is represented by a different c. The inverse frequency weighted vector w_ican be divided dividing the CX(f) weights, rather than multiplying it by the CX(f) weights. The CX(f) context similarity values increase the importance of features that are distributed across many contexts, and decrease the importance of features that are concentrated in a single context. Thus, for classification, the reverse can be accomplished by dividing the vector w_iby corresponding CX(f) weights.

[0097] Embodiments of the subject matter and the operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described in this specification can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions, encoded on computer storage medium for execution by, or to control the operation of, data processing apparatus. Alternatively or in addition, the program instructions can be encoded on an artificially-generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. A computer storage medium can be, or be included in, a computer-readable storage device, a computer-readable storage substrate, a random or serial access memory array or device, or a combination of one or more of them. Moreover, while a computer storage medium is not a propagated signal, a computer storage medium can be a source or destination of computer program instructions encoded in an artificially-generated propagated signal. The computer storage medium can also be, or be included in, one or more separate physical components or media (e.g., multiple CDs, disks, or other storage devices).

[0098] The operations described in this specification can be implemented as operations performed by a data processing apparatus on data stored on one or more computer-readable storage devices or received from other sources.

[0099] The term “data processing apparatus” encompasses all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, a system on a chip, or multiple ones, or combinations, of the foregoing. The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, a cross-platform runtime environment, a virtual machine, or a combination of one or more of them. The apparatus and execution environment can realize various different computing model infrastructures, such as web services, distributed computing and grid computing infrastructures.

[0100] A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, declarative or procedural languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, object, or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub-programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

[0101] The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform actions by operating on input data and generating output. The processes and logic flows can also be performed by, and an apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

[0102] Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for performing actions in accordance with instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto-optical disks, or optical disks. However, a computer need not have such devices.

[0103] Devices suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

[0104] To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user's client device in response to requests received from the web browser.

[0105] Embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back-end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front-end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back-end, middleware, or front-end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), an inter-network (e.g., the Internet), and peer-to-peer networks (e.g., ad hoc peer-to-peer networks).

[0106] The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other. In some embodiments, a server transmits data (e.g., an HTML page) to a client device (e.g., for purposes of displaying data and receiving user input from a user interacting with the client device). Data generated at the client device (e.g., a result of the user interaction) can be received from the client device at the server.

[0107] An example of one such type of computer is shown in FIG. 7, which shows a block diagram of a programmable processing system (system). The system 700 that can be utilized to implement the systems and methods described herein. The architecture of the system 700 can, for example, be used to implement a computer client, a computer server, or some other computer device.

[0108] The system 700 includes a processor 710, a memory 720, a storage device 730, and an input/output device 740. Each of the components 710, 720, 730, and 740 can, for example, be interconnected using a system bus 750. The processor 710 is capable of processing instructions for execution within the system 700. In one implementation, the processor 710 is a single-threaded processor. In another implementation, the processor 710 is a multi-threaded processor. The processor 710 is capable of processing instructions stored in the memory 720 or on the storage device 730.

[0109] The memory 720 stores information within the system 700. In one implementation, the memory 720 is a computer-readable medium. In one implementation, the memory 720 is a volatile memory unit. In another implementation, the memory 720 is a non-volatile memory unit.

[0110] The storage device 730 is capable of providing mass storage for the system 700. In one implementation, the storage device 730 is a computer-readable medium. In various different implementations, the storage device 730 can, for example, include a hard disk device, an optical disk device, or some other large capacity storage device.

[0111] The input/output device 740 provides input/output operations for the system 700. In one implementation, the input/output device 740 can include one or more of a network interface device, e.g., an Ethernet card, a serial communication device, e.g., and RS-232 port, and/or a wireless interface device, e.g., an 802.11 card. In another implementation, the input/output device can include driver devices configured to receive input data and send output data to other input/output devices, e.g., keyboard, printer and display devices 760.

[0112] While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any inventions or of what may be claimed, but rather as descriptions of features specific to particular embodiments of particular inventions. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination.

[0113] Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.

[0114] Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

[0115] Thus, particular embodiments of the subject matter have been described. Other embodiments are within the scope of the following claims. In some cases, the actions recited in the claims can be performed in a different order and still achieve desirable results. In addition, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In certain implementations, multitasking and parallel processing may be advantageous.

Claims

Certificate of Correction present

The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.

What is claimed is:

1. A method performed by a data processing apparatus, the method comprising:

selecting, by the data processing apparatus, object representations from a dataset storing a plurality of object representations, each object representation being an association of:

an object identifier that identifies an object instance in a dataset and corresponds to an object;

a context value that identifies a context of the object; and

a set of feature values that identify features of the object;

wherein each object identifier is unique in the dataset, and each context value is associated with one or more object identifiers;

for each feature value:

determining an inter-context score that is proportional to the number of different context values in the dataset that are associated with the feature value, wherein the inter-context score is based on a probability that a pair of object representations that each include a particular feature value are each associated with different context values; and

determining an intra-context score that proportional to the number of times the feature value is associated with each context value, wherein the intra-context score is based on a probability that a pair of object representations that each include the particular feature value are each associated with the same context value; and

for a selected pair of object representations, determining a similarity score based on a respective inter-context score and a respective intra-context score of each matching feature value in the set of features for the pair of object representations, the similarity score being a measure of the similarity of the object representations in the pair of object representations, the determining comprising, for each feature value, determining a feature weight for the feature value, the feature weight being based on a ratio of the inter-context score of the feature value to the intra-context score of the feature value.

2. The method of claim 1, wherein:

determining a similarity score comprises:

generating a weighted vector for each set of features of the selected pair of object representations, each weighted vector having, for each feature value, a corresponding feature weight determined for the feature value; and

determining a cosine similarity value from the weighted vectors.

3. The method of claim 2, wherein generating a weighted vector for each set of features of the selected pair of object representations comprises, for each feature value in the set of features of the selected pair of object representations:

determining an inverse frequency value of the feature value with respect to the dataset; and

multiplying the inverse frequency value by a logarithmic ratio of the inter-context score of the feature value to the intra-context score of the feature value.

4. The method of claim 3, further comprising, for each set of feature values in the dataset, adding a unique feature value to the set of feature values and that is included only in that set of feature values, the unique feature value having an associated feature weight in a corresponding weighted vector that causes the cosine similarity value to be less than one.

5. The method of claim 1, wherein determining the inter-context score and intra-context score comprises for each feature value in the sets of features in the dataset comprises:

determining a number of object representations in the dataset that include the feature value;

for each context value in the dataset, determining a number nc of objet representations including the context value;

for each context value in the dataset, determining a number nc,f of object representations including the context value and including the feature value;

determining the inter-context score based on a summing over each context value in the dataset values proportional to:

(nc,f*(nf−nc,f))/(nf*(nf−1)); and

determining the intra-context score based on a summing over each context value in the dataset values proportional to:

(nc,f*(nf−1))/(nf*(nf−1)).

6. The method of claim 5, further comprising smoothing the inter-context scores and intra-context scores by a first value p and a second value m so that determining the inter-context score is based on a summing over each context value in the dataset values equal to:

((n_c,f+p*m)*(n_f−n_c,f+p*m))/((n_f+m)*(n_f−1+m)); and

determining the intra-context score based on a summing over each context value in the dataset values equal to:

((n_c,f+p*m)*(n_f−1+p*m))/((n_f+m)*(n_f−1+m)).

7. The method of claim 6, further comprising:

grouping the feature values into disjoint sets of feature values; and

determining, for each disjoint set of feature values, a corresponding first value p and a correspond second value m;

wherein the first values p differ for at least two disjoint sets of feature values, and the second values m differ for at least two disjoint sets of feature values.

8. The method of claim 1, further comprising:

generating a context histogram for each feature value in the sets of feature values, the context histogram defining the number of times the feature value co-occurs with each context value in the dataset; and

determining the feature weight for each feature value comprises determining the feature weight based on the context histogram of the feature value.

9. The method of claim 8, wherein generating a feature weight for each feature value based on the context histogram of the feature value comprises:

providing a first set of context histograms to a first computer in the data processing apparatus;

providing a second set of context histograms to a second computer in the data processing apparatus, the first and second sets of context histograms being disjoint sets; and

determining, at the first and second computers, the respective feature weights of the feature values from the respective first and second sets of context histograms.

10. The method of claim 1, wherein the objects are products offered by merchants, and wherein the context values are the identifiers of the merchants.

11. A method performed by a data processing apparatus, the method comprising:

selecting, by the data processing apparatus, object representations from a dataset storing a plurality of object representations, each object representation being an association of:

an object identifier that identifies an object instance in a dataset and corresponds to an object;

a context value that identifies a context of the object; and

a set of feature values that identify features of the object;

wherein each object identifier is unique in the dataset, and each context value is associated with one or more object identifiers; and

generating feature weights and associating the feature weights with the feature values in the sets of features in the dataset, the generating of feature weights comprising, for each feature value:

determining a feature weight for the feature value, the feature weight being based on a ratio of the inter-context score of the feature value to the intra-context score of the feature value.

12. The method of claim 11, further comprising:

selecting a pair of object representations from the dataset; and

determining a similarity score that measures the similarity of the pair of object representations, the similarity score determined from the feature weights associated with the feature values in the set of features of each object representation in the pair of object representations.

13. The method of claim 12, wherein:

further comprising:

generating a weighted vector for each set of features of the selected pair of object representations, each weighted vector including the feature weights for corresponding feature values; and

determining a cosine similarity value from the weighted vectors.

14. The method of claim 13, wherein generating a weighted vector for each set of features of the selected pair of object representations comprises, for each feature value in the set of features of the selected pair of object representations:

determining an inverse frequency value of the feature with respect to the dataset; and

multiplying the inverse frequency value by a logarithmic ratio of the inter-context score of the feature value to the intra-context score of the feature value.

15. The method of claim 14, further comprising, for each set of feature values in the dataset, adding a unique feature value to the set of feature values and that is included only in one set of feature values, the unique feature value having an associated weight in a corresponding weighted vector that causes the cosine similar value to be less than one.

16. A system, comprising:

a data processing apparatus in data communication with resource index data store, the resource index data indexing data of the resources and resource locators addressing the resources;

a data storage apparatus in data communication with the data processing apparatus and storing instructions executable by the data processing apparatus and upon execution by the data processing apparatus cause the data processing apparatus to perform operations comprising:

a object identifier that identifies an object instance in a dataset and corresponds to an object;

a context value that identifies a context of the object; and

a set of feature values that identify features of the object;

wherein each object identifier is unique in the dataset, and each context value is associated with one or more object identifiers;

for each feature value:

for a selected pair of object representations, determining a similarity score based on a respective inter-context score and a respective intra-context score of each matching feature value in the set of features for the pair of object representations, the similarity score being a measure of the similarity of the object representations in the pair of object representations, the determining comprising, for each feature value, determining a feature weight for the feature value based on a ratio of the inter-context score of the feature value to the intra-context score of the feature value.

17. A system, comprising:

a data processing apparatus in data communication with resource index data store, the resource index data indexing data of the resources and resource locators addressing the resources;

selecting object representations from a dataset storing a plurality of object representations, each object representation being an association of:

an object identifier that identifies an object instance in a dataset and corresponds to an object;

a context value that identifies a context of the object; and

a set of feature values that identify features of the object;

wherein each object identifier is unique in the dataset, and each context value is associated with one or more object identifiers; and

generating feature weights and associating the feature weights with the feature values in the sets of features in the dataset the generating of feature weights comprising, for each feature value:

determining a feature weight for the feature value based on a ratio of the inter-context score of the feature value to the intra-context score of the feature value.

18. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

selecting object representations from a dataset storing a plurality of object representations, each object representation being an association of:

an object identifier that identifies an object instance in a dataset and corresponds to an object;

a context value that identifies a context of the object; and

a set of feature values that identify features of the object;

wherein each object identifier is unique in the dataset, and each context value is associated with one or more object identifiers; and

generating feature weights and associating the feature weights with the feature values in the sets of features in the dataset, the generating of feature weights comprising, for each feature value:

determining a feature weight for the feature value based on a ratio of the inter-context score of the feature value to the intra-context score of the feature value.

Patent Citations (4)

Patent	Date	Inventor	Cited By
US6738759(B1)	2004-05-01	Wheeler et al.	Examiner
US7890514(B1)	2011-02-01	Mohan et al.	Examiner
US2011/0087680(A1)	2011-04-01	Murdock et al.	Examiner
US2011/0106821(A1)	2011-05-01	Hassanzadeh et al.	Examiner

Non-Patent Literature (13)

Hernandez et al., “Modeling Context Through Domain Ontologies”, Inf Retrieval vol. 10, pp. 143-172, 2007, Springer.Examiner
Yang et al., “ContextSeer: Context Search and Tecommendation at Query Time for Shared Consumer Products”, MM'08, pp. 199-208, 2008, ACM.Examiner
Li et al., “Video Search in Concept Subspace: A Text-Like Paradigm”, CIVR'07, pp. 603-610, 2007, ACM.Examiner
Aizawa, “An Information-Theoretic Perspective of TF-IDF Measures”, Information Processing and Management vol. 39, pp. 45-65, 2003, Elsevier Science Ltd.Examiner
Basu et al., “Constrained Clustering: Advances in Algorithms, Theory, and Applications.” Chapman & Hall/CRC Press, pp. 1-462, 2008.Applicant
Bilenko et al., “Adaptive Name Matching in Information Integration.” IEEE Intelligent Systems, 18(5): 16-23, Sep./Oct. 2003.Applicant
Cohen, “Data Integration Using Similarity Joins and a Word-Based Information Representation Language.” ACM Transactions on Information Systems, 18(3):288-321, Jul. 2000.Applicant
Cohen and Hirsh, “Joins that Generalize: Text Classification Using WHIRL.” in Proceedings of the Fourth International Conference on Knowledge Discovery and Data Minings, pp. 169-173, 1998.Applicant
Cohen et al., “A Comparison of String Distance Metrics for Name-Matching Tasks,” in Proceedings of the IJACI-2003 Workshop on Information Integration on the Web (IIWeb-03), 2003 (6 pages).Applicant
Dean & Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters.” in OSDI'04: Sixth Symposium on Operating System Design and Implementation, pp. 1-13, 2004.Applicant
Oyama and Tanaka, “Distance Metric Learning from Cannot-be-Linked Example Pairs, With Application to Name Disambiguation.” in Constrained Clustering: Advances in Algorithms, Theory, and Applications, Chapman & Hall/CRC Press, pp. 357-374 2008.Applicant
Salton, “Automatic Text Processing.” Addison Welsley, pp. 1-563, 1989.Applicant
Wagstaff and Cardie, “Clustering With Instance-Level Constraints.” in Proceedings of the International Conference on Machine Learning (ICML), pp. 1103-1110, 2000.Applicant

Abstract