Jaccard similarity estimation of weighted samples: scaling and randomized rounding sample selection with circular smearing

A tangible non-transitory computer readable storage medium that stores program instructions that, when executed, cause a computer to implement a method for pre-calculation, per object, of object feature bin values for identifying close matches between objects that have numerous weighted features, the method including:

• during min-hashing of an expanded set of weighted features into a predetermined number of feature bins, circularly smearing a feature that qualifies to be inserted by min-hashing into a particular feature bin across successive feature bins,
• using a processor and memory coupled to the processor, the memory holding objects, sets of weighted features of the objects, and values placed in the feature bins by min-hashing,
• for initial weighted features of an object and a predetermined number of the feature bins used to receive the values produced by the min-hashing of the weighted features, as part of calculating an estimated Jaccard similarity index among objects:
• scaling initial weights to produce scaled-weighted features, using scaling factors automatically selected based on a sum of the initial weights divided by a number of features in a feature set, applying two or more of the selected scaling factors to scale the initial weights for min-hashing into one set of feature bins per scaling factor;
• expanding the scaled-weighted features into two or more expanded sets of weighted features of the object, wherein each expanded set includes at least as many weighted features as the predetermined number of feature bins;
• wherein expanding a particular scaled-weighted feature produces multiple instances of feature samples in proportion to respective scaled weight of the particular scaled-weighted feature;
• and
• min-hashing the expanded sets, with circularly smearing incremented fractional parts of a min-hashed value under consideration, so that the incremented fractional part of the min-hashed value is considered as a candidate to be inserted into at least one successive bin after insertion into an initial min-hash selected bin;
• and
• saving completed sets of the feature bins for each scaling of weights of the object together with a scaling factor or sum of feature weights for use in comparing sampled features of the object with sampled features of other objects by calculating an estimated Jaccard similarity index.

A method of pre-calculation, per object, of object feature bin values for identifying close matches between objects that have numerous weighted features, the method including:

• during min-hashing of a down-scaled set of weighted features into a predetermined number of feature bins, circularly smearing a feature that qualifies to be inserted by min-hashing into a particular feature bin across successive feature bins,
• using a processor and memory coupled to the processor, the memory holding objects, sets of weighted features of the objects, and values placed in the feature bins by min-hashing,
• for initial weighted features of an object and a predetermined number of the feature bins used to receive the values produced by the min-hashing of the weighted features, as part of calculating an estimated Jaccard similarity index among objects:
• scaling initial weights to produce scaled-weighted features, using scaling factors automatically selected based on a sum of the initial weights divided by a number of features in a feature set, applying two or more of the selected scaling factors to scale the initial weights for min-hashing into one set of feature bins per scaling factor;
• applying randomized rounding selection to the scaled-weighted features to select contracted sets of weighted features of the object, wherein each contracted set includes one to eight times as many weighted features as the predetermined number of feature bins;
• min-hashing the expanded sets, with circularly smearing incremented fractional parts of a min-hashed value under consideration, so that the incremented fractional part of the min-hashed value is considered as a candidate to be inserted into at least one successive bin after insertion into an initial min-hash selected bin;
• and
• saving completed sets of the feature bins for each of scaling weights of the object together with a scaling factor or sum of feature weights for use in comparing sampled features of the object with sampled features of other objects by calculating an estimated Jaccard similarity index.

A tangible non-transitory computer readable storage medium that stores program instructions that, when executed, cause a computer to implement a method for pre-calculation, per object, of object feature bin values for identifying close matches between objects that have numerous weighted features, the method including:

• during min-hashing of a down-scaled set of weighted features into a predetermined number of feature bins, circularly smearing a feature that qualifies to be inserted by min-hashing into a particular feature bin across successive feature bins,
• using a processor and memory coupled to the processor, the memory holding objects, sets of weighted features of the objects, and values placed in the feature bins by min-hashing,
• for initial weighted features of an object and a predetermined number of the feature bins used to receive the values produced by the min-hashing of the weighted features, as part of calculating an estimated Jaccard similarity index among objects:
• scaling initial weights to produce scaled-weighted features, using scaling factors automatically selected based on a sum of the initial weights divided by a number of features in a feature set, applying two or more of the selected scaling factors to scale the initial weights for min-hashing into one set of feature bins per scaling factor;
• applying randomized rounding selection to the scaled-weighted features to select contracted sets of weighted features of the object, wherein each contracted set includes at least as many weighted features as the predetermined number of feature bins;
• min-hashing the expanded sets, with circularly smearing incremented fractional parts of a min-hashed value under consideration, so that the incremented fractional part of the min-hashed value is considered as a candidate to be inserted into at least one successive bin after insertion into an initial min-hash selected bin;
• and
• saving completed sets of the feature bins for each of scaling weights of the object together with a scaling factor or sum of feature weights for use in comparing sampled features of the object with sampled features of other objects by calculating an estimated Jaccard similarity index.