I have a function that is receiving messages with the following pattern:

Example of accumulating strings

(In this picture, "string" and "message" are synonymous.)

I'm only interested in the largest messages, such as these:

Largest filtered accumulated strings

over a particular window.

Is there an algorithm that can appropriately filter the messages in the desired manner over a specified window?

  • $\begingroup$ The examples do not show how to handle m1, m1´ and, later on, m1, m1´´ ("forks"). Is the CorrelationId part of the messages received? $\endgroup$ – greybeard Dec 3 '19 at 7:27
  • $\begingroup$ m1, m1' would be dropped/removed. m1, m1'' is not a valid case. It would just be m1, m1'. The correlationId can be included in each message, or it can be outside each message in an envelope that would be discarded prior to the filtering algorithm. Does that answer the question? $\endgroup$ – devinbost Dec 3 '19 at 20:09
  • $\begingroup$ The statements about example messages m1 to m1, m1'' escape me. (When m1, m1'' is not valid after m1, m1', shouldn't m1, m1'' be dropped? How come that after dropping m1, m1' It would just be m1, m1'?) The alternatives given for *CorrelationId * answer the explicit question in my comment above. Please edit additional information you think helpful for answering your question into the question body, if any. $\endgroup$ – greybeard Dec 3 '19 at 22:07
  • 1
    $\begingroup$ From how I currently read the question: put the messages in a prefix tree. $\endgroup$ – greybeard Dec 3 '19 at 22:19

Store them in a heap or priority queue, keyed on the size of the message. This way, if you want the $k$ largest messages, you can keep track of that as each message arrives. This will require $O(k)$ space to keep track of the $k$ largest messages at each step, and $O(\log k)$ time per message that arrives, so it should be pretty efficient.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.