Patent Document ID: 20080114722
Application ID: 11816890
Patent Status: 0

Claim One:
1. A method of mapping a first d-bit input string to a first output string, the method comprising: a) setting the first output string equal to the first input string if d is below a threshold, otherwise performing steps b) through h); b) partitioning the first input string into several contiguous blocks of length L; c) performing steps d) through g) on each block for each whole number j from zero to n where n is the largest number such that (log d) n+1 is less than or equal to L, creating a z-string for each such performance of steps d) through g); d) defining a plurality of shifted substrings by taking a sliding window of the block having length L−(log d) j for each whole number from zero to (log d) j ; e) recursively mapping each shifted substring to a corresponding mapped substring, the recursive mapping comprising performing steps a) through h) using the shifted substring being mapped as the first input string; f) picking k independent uniformly randomly distributed samples of b bit positions of each of the mapped substrings, picking the same b bit positions from each mapped substring within each sample, where k is chosen to reflect a probability of success, and b is dependent on d and j; g) constructing the z-string, by concatenating a mini z-string for each of the k samples, each mini z-string created by: 1) initially setting each position in the mini z-string to a value of 0; 2) constructing a corresponding sampled substring for each of the mapped substrings by concatenating the bits from the b picked bit positions of the corresponding mapped substring; and 3) performing a hash function on each of the sampled substrings, each time calculating a position within the mini z-string and then incrementing the value at the calculated position by 1; and h) scaling each of the z-strings constructed, then concatenating the scaled z-strings to create a concatenated z-string and converting the concatenated z-string to a bit string using unary notation to form the first output string.