in reply to Re: An optimal solution to finding weights for a weighted sum signature.
in thread An optimal solution to finding weights for a weighted sum signature.

Is there some reason you don't want to use an existing algorithm like CRC or MD5?

Yes. Whilst in my examples I'm using strings of letters for simplicity and conciseness; the actual collection could be pretty much anything. Eg. Instead of letters in a word; in might be the existence of and ordering of words in a sentence, or the existence of phrases, regardless of ordering in a document; or literally any other combinatorial subset of attributes of some datasets.

In order to use crc or MD5 for these other kinds of subset collections, it would require two passes: one to encode (say hash lookup mapping) the collection subset into a 'string' digestible by those algorithms; and a second pass over that string to arrive at the signature.

If I can accumulate the signature whilst iterating the first pass, I can save a substantial amount of time. In a previous attempt at a similar problem I came up with an algorithm -- very specific to the data being processed -- that proved to be almost 50 times faster than first stringifying then MD5. With a dataset measured in terabytes, that was a substantial saving.

To keep from overflowing, you can choose a big modulus $M.

That's a good suggestion, but there is a problem with it. With a pure (non-modulo) arithmetic signature, the values tend to group like-near-like in a nearly continuous ordering. It isn't a collating order that anyone would recognise, but similar subsets tend to be collate close to each other and transition gradually from one end of the spectrum to the other.

However, once you start wrapping the signatures back on themselves using modulo arithmetic, that useful artifact of the non-modulo arithmetic disappears. It's not always needed or useful, but if I can avoid it, it might allow a more generic solution with additional useful properties.

It is certainly something for me to keep in mind if another solution doesn't present itself. Thankyou.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
In the absence of evidence, opinion is indistinguishable from prejudice.
  • Comment on Re^2: An optimal solution to finding weights for a weighted sum signature.

Replies are listed 'Best First'.
Re^3: An optimal solution to finding weights for a weighted sum signature.
by Anonymous Monk on Nov 04, 2016 at 18:26 UTC

    Actually, both CRC and MD5 can be calculated incrementally without having to stringify the entire dataset at once. That's what the MD5 context object is for. I don't know of a CRC module that provides that functionality, but it's easy to implement.

    But yeah, coming up with a function that has the "nonrandom" behavior you're looking for is going to be very tricky and data-dependent.

[reply]
      Actually, both CRC and MD5 can be calculated incrementally without having to stringify the entire dataset at once.

      You misunderstand what I meant by stringification; or rather, I didn't make myself clear enough.

      Each item in a collection could be a single character; or it could be an entire data structure representing anything. Each item might for instance be:

      • An entire 19x19 array representing a position in a game of go;

        with a subset of items being a sequence of moves within a game.

      • Each a known marker sequence -- variable length sequence of ACGT;

        with a subset of items being a DNA fragment.

      • It could be a frequency spectrum derived by Fourier Analysis representing one instant in a piece of music or voice recording;

        with the subset representing a few bars of the tune or a phoneme of the speech.

      • each could be a snapshot of stock prices or movements at a given moment of the trading day;

        with the subset representing elapsed time periods.

      • Many other things; simple or complex.

      The signature has to capture both the individual items and their ordering. It is easy to demonstrate that if you run MD5 over the subset of items simply concatenated data, a single combined sequence, two or more quite different subsets can easily result in the same signature. Eg.

      Take the simply concatenated subset of DNA markers CTCGGTGCGACGGTCTGCCAAGATCGCGTT. That could have been formed from any of these subsets:

      1. CTC GGTGCGAC GGTCTG CCAAGAT CGCGTT
      2. CTCGG TGC GACGGTC TGC CAAGA TCG CGTT
      3. CTCGGTGCGACGG TCTGCCAAGATCGCGTT

      And many others, but the resultant MD5 would be the same for all of them. Of course you can prevent that by adding (say) nulls between items in the concatenation; but then think about how you would deal with the same problem with the audio samples; or video or ...

      The classic way of dealing with this problem is that instead of concatenating the raw data, you assign each item in the collection a unique letter or number, and you run the MD5 on the concatenation of those; by doing a hash mapping of individual items to unique placeholders; concatenating them, and the MD5ing those. This is what I meant by two passes.

      By using a mathematical algorithm to combine the placeholder numbers as they are looked up, a second pass is avoided; and the item to unique number mapping process results in a consistent output regardless of the type of raw input processing, all down-stream processing ccan be applied to any type of input data.

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
[select]

        No need for stringification. It's all numbers (or bits). MD5, for example, processes 512 bits of input at a time. That's 8 64 bit integers or 16 32 bit integers (or 128 8 bit characters). Just concatenate your numbers to get 512 bit chunks of input.

        If you go with CRC, then use a polynomial for the number of bits per integer you want to use: CRC-32 takes 32 bit integers as input. CRC-64 takes 64 bit integers.

        I don't know what level of integrity checking you need, but you said "signature". So maybe you should consider one of the SHA-2 algorithms. as I interpret the descriptions, the 256 variant takes 512 bit inputs while the 512 variant takes 1024 bit inputs.

[reply]

In Section Seekers of Perl Wisdom