IP Library › Granted Patent US 11,475,014

Granted Patent B2

US 11,475,014 · App. 16/721,745 · Granted Oct 18, 2022

Updating a toplist for a continuous data stream

Inventor: Antonín K{hacek over (r)}í{hacek over (z)} (Prachatice, CZ)

Assignee: Avast Software s.r.o.

G06F16/24568 G06F7/08 G06F16/2255 G06F16/2379

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 11,475,014
App. No.: 16/721,745
Granted: Oct 18, 2022
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

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.

Claims (67)

1. A system comprising:

one or more processors;

at least one non-transitory machine-readable medium configured to store a sliding window comprising a fixed number of data elements and a toplist;

a data element counter comprising instructions executable by the one or more processors, the instructions to cause the one or more processors to:

receive a new data element of a data stream from a data source,

in response to a determination that an identifier for the new data element matches an identifier for a data element in the toplist, updating a counter for the data element in the toplist, and

in response to a determination that the identifier for the new data element does not match any identifier for data elements in the toplist,

determine if a counter for the new data element is larger than a counter for a current smallest data element for the toplist, wherein the current smallest data element for the toplist is maintained in a data structure that is separate from the toplist,

remove from the toplist the identifier for the current smallest data element in response to a determination that the counter for the new data element is larger than the counter for the current smallest data element, and

add an identifier of the new data element and the counter for the new data element to the toplist.

2. The system of claim 1 , wherein the data element counter further includes instructions to cause the one or more processors to:

in response to a determination that the identifier for the new data element matches the identifier for the data element in the toplist and that the identifier for the new data element matches the identifier for the current smallest data element:

scan the toplist to determine a data element having the smallest counter value for data elements in the toplist; and

reset the counter value for the current smallest data element counter to the counter value of the data element having the smallest counter value for data elements in the toplist, and

reset the identifier for the current smallest data element to the identifier of the data element having the smallest counter value for data elements in the toplist.

3. The system of claim 1 , wherein the size of the toplist is smaller than the size of the sliding window.

4. The system of claim 1 , wherein the size of the toplist is at least an order of magnitude smaller than the size of the sliding window.

5. The system of claim 1 , wherein the sliding window comprises a first hashmap and the toplist comprises a second hashmap.

6. The system of claim 1 , wherein the data element counter further includes instructions to cause the one or more processors to, further in response to the determination that the identifier for the new data element does not match any identifier for the data elements in the toplist:

in response to a determination that the current minimum data element is nil:

scan the toplist to determine a data element having the smallest counter value for data elements in the toplist; and

reset the counter value for the current smallest data element counter to the counter value of the data element having the smallest counter value for data elements in the toplist, and reset the identifier for the current smallest data element to the identifier of the data element having the smallest counter value for data elements in the toplist.

7. The system of claim 6 , wherein the determination that the current minimum data element is nil comprises a determination that a counter for the current minimum data element has a zero value.

8. The system of claim 1 , wherein the data element counter further includes instructions to cause the one or more processors to:

in response to a determination that the sliding window is full, remove a data element from the sliding window;

wherein a data element having the identifier of the data element removed from the sliding window is not removed from the toplist.

9. The system of claim 1 , wherein the data stream comprises a continuous data stream.

10. A method for maintaining a toplist for a sliding window comprising a fixed number of data elements, the method comprising:

receiving a new data element from a data stream;

in response to determining that an identifier for the new data element matches an identifier for a data element in the toplist, updating a counter for the data element in the toplist; and

in response to determining that the identifier for the new data element does not match any identifier for data elements in the toplist,

determining if a counter for the new data element is larger than a counter for a current smallest data element for the toplist, wherein the current smallest data element for the toplist is maintained in a data structure that is separate from the toplist,

removing from the toplist the identifier for the current smallest data element in response to determining that the counter for the new data element is larger than the counter for the current smallest data element, and

adding an identifier of the new data element and the counter for the new data element to the toplist.

11. The method of claim 10 , wherein further in response to determining that the identifier for the new data element matches the identifier for the data element in the toplist:

in response to determining that the identifier for the new data element matches the identifier for the current smallest data element:

scanning the toplist to determine a data element having the smallest counter value for data elements in the toplist; and

resetting the counter value for the current smallest data element counter to the counter value of the data element having the smallest counter value for data elements in the toplist, and resetting the identifier for the current smallest data element to the identifier of the data element having the smallest counter value for data elements in the toplist.

12. The method of claim 10 , wherein the size of the toplist is at least an order of magnitude smaller than the size of the sliding window.

13. The method of claim 10 , wherein the sliding window comprises a first hashmap and the toplist comprises a second hashmap.

14. The method of claim 10 , wherein further in response to determining that the identifier for the new data element does not match any identifier for the data elements in the toplist:

in response to determining that the current minimum data element is set to nil:

scanning the toplist to determine a data element having the smallest counter value for data elements in the toplist; and

15. The method of claim 10 , further comprising:

in response to determining that the sliding window is full, removing a data element from the sliding window;

wherein a data element of the toplist having the identifier of the data element removed from the sliding window is not removed from the toplist.

16. The method of claim 10 , wherein the counter has an associated time value corresponding to a last update time, and wherein the method further comprises adjusting the counter downward based on the last update time.

17. A machine-readable medium having stored thereon machine-executable instructions to cause one or more processors to:

receive a new data element from a data stream;

store to a non-transitory machine-readable medium a sliding window comprising a fixed number of data elements and a toplist;

in response to a determination that an identifier for the new data element matches an identifier for a data element in the toplist, update a counter for the data element in the toplist; and

in response to a determination that the identifier for the new data element does not match any identifier for data elements in the toplist,

add an identifier of the new data element and the counter for the new data element to the toplist.

18. The machine-readable medium of claim 17 , wherein the machine-executable instructions include instructions to cause the one or more processors to, further in response to the determination that the identifier for the new data element matches the identifier for the data element in the toplist:

in response to a determination that the identifier for the new data element matches the identifier for the current smallest data element:

scan the toplist to determine a data element having the smallest counter value for data elements in the toplist; and

19. The machine-readable medium of claim 17 , wherein the machine executable instructions further include instructions to cause the one or more processors to, further in response to determining that the identifier for the new data element does not match any identifier for the data elements in the toplist:

in response to a determination that the current minimum data element is set to nil:

scan the toplist to determine a data element having the smallest counter value for data elements in the toplist; and

20. The machine-readable medium of claim 17 , wherein the machine-executable instructions further comprise instructions to cause the one or more processors to:

in response to a determination that the sliding window is full, remove a data element from the sliding window;

wherein a data element of the toplist having the identifier of the data element removed from the sliding window is not removed from the toplist.

Assignments (5)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 30, 2025

From: GEN DIGITAL AMERICAS S.R.O.

To: GEN DIGITAL INC.

Reel/Frame 071771/0767 →

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 30, 2025

From: AVAST SOFTWARE S.R.O.

To: GEN DIGITAL AMERICAS S.R.O.

Reel/Frame 071777/0341 →

RELEASE OF SECURITY INTEREST Recorded Mar 26, 2021