Avast Software S.r.o.

Antonín Kríz

Libor Morkovský

Systems and methods maintain a toplist associated with a sliding window having m elements. The toplist can include the top k elements of the sliding window, where k is less than m (typically an order of magnitude or more less than m). As new elements are received from a data stream, a counter associated with the new element is updated and the new element is inserted into the sliding window. If the toplist has less than k elements, the new element is added. Otherwise, if the new element is already in the toplist, its counter value is updated with the new value. Otherwise, if the new element's counter is smaller than the smallest element in toplist, then do nothing. If the new element counter is larger than the smallest counter in the toplist, the smallest element is discarded from the toplist and the new element is inserted.

Updating a toplist for a continuous data stream

Systems and methods perform various optimizations of an LLCS algorithm for use in determining if a set of input sequences are similar to a query sequence. The optimizations include filtering out sequence from the set of input sequences where the estimated similarity of the sequence with the query sequence is below a threshold value. The remaining sequences can then be provided to an LLCS algorithm where the output of the LLCS algorithm is used in a similarity function to determine an actual similarity of an input sequence with a query sequence.

Length of the longest common subsequence algorithm optimization

Systems and methods create an inverted index for a set of documents utilizing a heap data structure. The documents can be divided into a series of n-grams. The n-grams can be hashed, producing hashed n-gram values. A first hashed n-gram value can be placed into the heap data structure. Operations performed using the heap data structure obtain document identifiers that are associated with documents that include a hashed n-gram value that matches the top n-gram value in the heap.

Constructing an inverted index

A similarity fingerprint for a data object such as a file can be automatically determined using one or more anchor values. The one or more anchor values can be provided or determined. For each anchor value, a set of distances between each instance of the anchor value in the data object is determined. The set of distances for the instance of the anchor value is aggregated into a single value. The single value is added as a component of the similarity fingerprint. Thus, if there are N anchor values, there can be N components of the similarity fingerprint. The similarity fingerprints of different data objects can be compared and the results of the comparison can be used to determine how similar the data objects are.

Methods of determining a file similarity fingerprint

A system and method for prefix fingerprints for a first file or a first data object. A prefix fingerprint comprises a plurality of hash values. The hash values of the prefix fingerprints are typically generated starting at the same offset within the file or data object, but are generated based on different data sizes. Later, a second file or second data object can be compared with the first file or first data object to determine if the second file or data object is a prefix of the first file or data object. A hash value is selected from the previously determined prefix fingerprint of the first file based on the size of the second file. A hash is generated for the second file using the same offset value and size as was used to generate the selected hash value from the prefix fingerprint. The hash values are then compared.

Growing community of inventors

Prachatice, Czechia

Antonín Kríz