Compact probabilistic data structure for storing log data

Abstract

A computer-implemented method is presented for storing log data generated in a distributed computing environment. The method includes: receiving a log line from a given storage entity; applying a first tokenization rule to create a plurality of base tokens; applying a second tokenization rule to create a plurality of combination tokens; applying a third tokenization rule to create a plurality of n-gram tokens; combining the plurality of tokens into a set of tokens; for each token in the set of tokens, storing a given token by applying a hash function to the given token to generate a hash value, where the given token is associated with the given storage entity containing the log line; updating a listing of entities with the given storage entity, where entries in the listing of entities are configured to identify more than one storage entity and each entry in the listing of entities specifies a unique set of storage entities; and storing the hash value, along with an address, in a token map table of a probabilistic data structure, where the address maps the hash value to an entry in the listing of entities.