FIELD

The field relates generally to information processing techniques, and more particularly, to the processing of multisets of data.

BACKGROUND

One common search query in a security analytics scenario involves identifying the users that were connected to particular devices at a given point in time (e.g., which systems a given user was connected to at a given time; where the information is often derived from log data that includes connectivity information). This particular problem comes up, for example, in the context of user and entity behavioral analytics. To be able to answer this query efficiently, and in near-real-time, appropriate data structures and algorithms are needed. In particular, it is often important to store for each user and time value, a multiset representing, for example, which devices a given user was logged into at a given time.

Tracking this type of multiset, however, can become expensive from a storage perspective. In addition, being able to maintain multisets efficiently is desirable (e.g., permitting efficient insertion of entities into multisets and removal of entities from multisets). A need therefore exists for techniques for encoding and evaluating multiset data. A further need exists for techniques for efficient storage and maintenance of multiset data.

SUMMARY

In one embodiment, a method comprises encoding a multiset comprised of entities, over time, as a product of a prime number assigned to each of the entities in the multiset to obtain an integer representation of the multiset; adding a first entity to the multiset at a first time by multiplying the integer representation of the multiset at the first time by the prime number assigned to the first entity, wherein the first entity is permitted to appear multiple times in the multiset; removing a second entity from the multiset at a second time by dividing the integer representation of the multiset at the second time by the prime number assigned to the second entity; and identifying the entities in the multiset at a given time by decomposing the integer representation of the multiset at the given time into a product of the prime numbers assigned to each of the entities in the multiset at the given time.

In some embodiments, the repeated appearance of the first entity in the multiset is represented using the prime number assigned to the first entity with an indication of the number of times that the first entity appears in the multiset.

In one or more embodiments, the obtaining the multiset comprises ingesting network connectivity log data, and wherein identifying the entities in the multiset at the given time comprises one or more of: (i) identifying devices that a given user was connected to at the given time; and (ii) identifying a plurality of users connected to a given device at the given time. A mapping can be maintained between: (i) an identifier of each of the entities and the corresponding prime number; and/or (ii) each prime number and an identifier of the corresponding entity.

Other illustrative embodiments include, without limitation, apparatus, systems, methods and computer program products comprising processor-readable storage media.

