Fingerprinting Ingest Processor

[polyfractal]

A potentially useful processor is one that can generate one or more "fingerprints" from an incoming document. This could aid in finding duplicates, detecting plagarism, or clustering similar documents together.

I think there are two realms of fingerprinting: content fingerprinting and structural fingerprinting.

Content Fingerprinting

Hashes the content of fields to generate a fingerprint-per-field, and optionally, a fingerprint that represents all the fields. Could use simple hashing, or perhaps something more sophisticated like MinHash, SimHash, Winnowing or Probabilistic Fingerprinting.

The API could look something like:

{
  "fingerprint": {
    "type": "content",
    "fields": ["foo", "bar"],
    "hash": "minhash",
    "hash_all": true
  }
}

E.g. specify the type of fingerprinting we want to do (content), a list of fields to hash, the style of hashing and if we should also hash all the hashes together. The output would then be the document + new fingerprint fields:

{
  "foo": "...",
  "bar": "...",
  "fingerprint_foo": 1283891,
  "fingerprint_bar": 8372038,
  "fingerprint_all": 3817273
}

Structural Fingerprinting

The other mode of fingerprinting could be structural in nature (this is the one I'm more interested in, tbh). Instead of fingerprinting the content of fields, we are actually fingerprinting the structure of the document itself. Essentially, we would recursively parse the JSON and hash the keys at each level in the JSON tree. These hashes then become a fingerprint for the structure of the document.

Importantly, this type of fingerprinting ignores the leaf values...we just want to fingerprint the JSON keys themselves.

{
  "fingerprint": {
    "type": "structure",
    "root": ["foo"],
    "recursive": true,
    "hash": "murmur3",
    "hash_all": true
  }
}

• root: defines where to start recursing, in case you only care about a portion of the document. Could be omitted or set to "*" to process the entire document
• recursive if you want the processor to fingerprint all the layers. False if you just want the top-level of keys hashed.
• hash: murmur, minhash, etc
• hash_all: if all the hashes should be hashed together to build a final fingerprint

And the new document:

{
  "foo": {
    "bar": {
      "baz": "buzz"
    },
    "beep": {
      "boop": "bop"
    }
  },
  "fingerprint_level1": 001734,
  "fingerprint_level2": 992727,
  "fingerprint_level3": 110293,
  "fingerprint_all": 235240
}

Instead of a fingerprint-per-field, we now have one per "level".

I can think of a number of objections to both of these, but this should at least kick off the discussion :)

/cc @martijnvg

[dadoonet]

I love this!

[martijnvg]

👍 great idea

[clintongormley]

@polyfractal btw have you seen this? #13325

just waiting to be exposed /cc @markharwood

[polyfractal]

Interesting! I had not seen that. That could potentially cover some of the features needed for content fingerprinting (or could be used as one of the "hashes").

The major downside I see to the FingerprintFilter is that large blocks of text will still generate large numbers of tokens, and for some use-cases you really just want a single fingerprint token to represent the whole thing (like minhash, winnowing, etc)

[markharwood]

The major downside I see to the FingerprintFilter is that large blocks of text will still generate large numbers of tokens,

I was thinking a downstream filter could take care of hashing the stemmed, sorted, deduped etc set of tokens FingerprintFilter and friends produces.
I didn't want to build the hashing into FingerprintFilter because sometimes you might want the readability of the raw tokens.

[polyfractal]

Makes sense. I suppose this goes back to the debate of analyzers vs. ingest pipelines ... e.g how much work should be done by analyzers, vs deferring more complex/expensive computations to dedicated ingest pipelines. Dunno :)

[martijnvg]

analyzers, vs deferring more complex/expensive computations to dedicated ingest pipeline

If fingerprinting can be done on a per field basis then this should be done via analyzers, because that will perform much better. However if fingerprinting requires several fields or the entire document then this should be done via a pipeline, since there all fields are accessible.

[polyfractal]

Ok, so in that case we can probably scratch the entire "content fingerprinting" section. That could be done with FingerprintFilter + various hashes, and if you want a total hash, you can copy_to a new field that is also hashed.

The "structural fingerprinting" stuff would have to be a pipeline, since it requires multiple fields in the doc

[eskibars]

Still, I think there's a lot of value. There's a pretty common use case for multiple-field "document fingerprinting," including in records management and e-mail search use cases. Usually something like the concatenation of to+from+cc+timestamp+subject and then md5/sha1/md5+sha1 hashes used for deduplication. It would be most interesting to make sure some of those hash algorithms were available as they're industry standards for those use cases. I'm a +1 for this overall.

[bleskes]

@polyfractal out of curiosity - which you always manage to trigger in me :) - what use cases do you see for the structural fingerprinting? I'm also asking because I presume it will be more useful in the case where people have many many optional fields , in which case the might want to model their data differently and put the field name as value to avoid mapping explosion. In this case we're back to content fingerprinting?

[polyfractal]

@bleskes For me, the use-case is parsing JSON logs (slow query logs in particular) and fingerprinting that structure. And the situation is a bit unique, since I actually want only the fingerprint and original _source, but skip the actual doc fields.

The root problem (for me) is that fingerprinting the structure of hierarchal json is much more reliable than treating the JSON as textual content and n-gram'ing it. I was hoping this could be massaged into a general purpose feature that is used in other contexts, but I'll be 100% honest and say I dunno what else it can be used for. It may be too special-purpose :)

Since this is essentially locality-sensitive hashing for tree structures, I suppose it could be used to cluster taxonomies, call stacks, lineage trees, etc?

I absolutely see the problem with many fields + mapping explosion. Don't have a good answer to that :/

I suppose this could be re-imagined as a content fingerprint that expects JSON, and loads/hashes that from a single string field?

[bleskes]

For me, the use-case is parsing JSON logs (slow query logs in particular) and fingerprinting that structure.

@polyfractal - I see. So the "document" you are interested in is the query type / combination irrespective of the values. I.e., the tree structure, including node names is the document. Indeed the question becomes - do we see more use cases for that? o.w. we can preprocess the tree into a value (by keeping all node names and {}) and finger print that.

[polyfractal]

Yep, and I'm not sure. It definitely could be too niche. Processing the tree into a text value is doable, but introduces a variety of problems. For example, take this tree:

query:
  match:
    baz: abc,
  bool:
    must:
      match:
        bar: xyz
      match:
        baz: abc

How do you transform that into a textual value? Assuming there is still some kind of processor that understand JSON and can emit node names:

• Go depth-first which maintains subtree structure: match baz bool must match bar match baz.
• Go breadth-first which maintains per-level co-ocurrence: match bool baz must match match bar baz.
• Go depth-first, but generate a value for each "branch" in the tree: ["match baz", "bool must match bar", "bool must match baz"], and then use a bunch of phrase magic to accomplish per-level co-ocurrence.

I dunno, I'll keep playing. Maybe one of those above schemes will work nicely when combined with MinHash/SimHash/Winnowing. I definitely agree it doesn't make sense to have functionality that is special-purpose and not generally useful