Re: 'Most used' queue - C# Discussion Boards

Re: 'Most used' queue [modified]

15-Jun-08 5:12

I'm looking for an implementation or example or even just the logic for what must be an extremely common scenario:

Suppose we have N objects (where N is large). These objects are being accessed over time, but the pattern of access changes. Some are more popular at one time of the day, another i more popular at another time.

I would like to have a list of the top M (M << N) most requested objects for the last T minutes.

Keeping a log of all requests for all objects for the last T minutes is inpractical. Even keeping a list M items long in memory is stretching the friendship. It needs to be fast and efficient.

It doesn't need to be 100% accurate. Just close.

I've got something close based on rolling averages but it's not quite right. I know as soon as the answer is given I'll go 'Why didn't I think of that' but my brain is stuck, possibly because of the Adam Sandler movie I watched last night.

cheers,
Chris Maunder

CodeProject.com : C++ MVP

User 665815-Jun-08 5:43

User 6658

15-Jun-08 5:43

Sounds like you need a Priority Queue[^] (Wikipedia Link[^]), as used in many scheduling algorithms (process creation and much more). Each access to an object in the queue should increase the object's priority (could be a property, like a time stamp).

Or did I misunderstand your problem?

regards

modified on Sunday, June 15, 2008 11:50 AM

modified 12-Sep-18 21:01pm.

Eslam Afifi15-Jun-08 6:07

Eslam Afifi

15-Jun-08 6:07

I don't have much experience and this is primitive and slow and it’s certainly not what you’re looking for but here are my thoughts anyway. You have N objects and you want to get the top M of N each T period. I think you would associate an integer with each object and keep them in a list or something. Each time an object is accessed you increase the integer. Each T period you sort them and get the top M instead of maintaining them in a sorted structure.

About the rolling averages, this is the first time I hear about this and I don’t understand it. Doesn’t it depend on storing the last average and calculating a new average based on the current one? It’d be great if you explain it a little. Thank you.

Eslam Afifi

Robert.C.Cartaino15-Jun-08 7:13

Robert.C.Cartaino

15-Jun-08 7:13

A moving average (or rolling average) is used when you are accumulating data and you take an average of the short-term data rather than averaging all the data you accumulated. It's a way of "smoothing out" data that can fluctuate wildly when all you really want to know is the short-term trend of the data. There are various ways to approximate and weight the average of the data as it comes in rather than actually re-calculating all the data as it changes.

I've done this a lot when writing stock analysis software. Here[^] is a graph of the last six months of eBay stock values (in blue) with a "10-day moving average" (in red). See how it smooths out the data to show the short term trends?

For the original poster's application, I guess you could use a rolling average if you don't want a particular entry shooting right to the top if you suddenly start using a bunch of times but rather have it slowly drift towards the top if you continue to use it over a period of time.

If you don't like the results your rolling average is giving you, maybe you can try one of the variations like a weighted moving average or an exponential moving average. Try Wikipedia[^]for some of the theory/math.

Eslam Afifi15-Jun-08 7:32

Eslam Afifi

15-Jun-08 7:32

Thank you for the reply. The chart of eBay is about days (the set of object) and a value for each day (the blue line) and the 10-day MA (the red line); despite I don't know how it's calculated, I can't see the relation between the average and getting the top M number of days N according to the values Confused | :confused:

Or do I get it wrong?

Eslam Afifi

Chris Maunder15-Jun-08 14:46

15-Jun-08 14:46

Eslam Afifi wrote:
I think you would associate an integer with each object

This requires an entry for every object. What if I have, say, 4 billion objects?

Eslam Afifi wrote:
Each T period you sort them and get the top M instead of maintaining them in a sorted structure

Unfortunately this means that your list is, by definition, always out of date (by anything between 0 and T minutes)

cheers,
Chris Maunder

CodeProject.com : C++ MVP

Eslam Afifi15-Jun-08 20:38

Eslam Afifi

15-Jun-08 20:38

Chris Maunder wrote:
This requires an entry for every object. What if I have, say, 4 billion objects?

I didn't realize that N is that big. But like I said, I don't have much experience, but I think you will keep track of how many times an object has been accessed in the past T period. I don't know about rolling average and it'd be great if you point out the relation between it and what you're trying to accomplish.

Chris Maunder wrote:
Unfortunately this means that your list is, by definition, always out of date (by anything between 0 and T minutes)

Then I guess you'll keep them in a SortedList or something.

Eslam Afifi

Pete O'Hanlon16-Jun-08 8:37

16-Jun-08 8:37

Chris - there is a way that you can do this, but it's going to rely on using some technology hacks. Let's assume that each object has a unique identifier. Now, every time the object is accessed, write the id and date/time that the object has been accessed to a message queue. Next, read from the message queue and update a database server based on these values.

Periodically, prune and summarise the values in the database - so, every N minutes, you'll pick the top M objects and write a summary of this information to a table - then delete the old entries. The beauty of this approach is that you can spread the load of this processing.

Deja View - the feeling that you've seen this post before.

Chris Maunder16-Jun-08 8:39

16-Jun-08 8:39

I thought about this but I want it in-memory. The load on the database will be way too high.

cheers,
Chris Maunder

CodeProject.com : C++ MVP

Pete O'Hanlon16-Jun-08 8:46

16-Jun-08 8:46

It really depends how many objects you are talking about - if it's the billions mentioned above, then you've no chance. You would have to track every one to see if there are multiple accesses - even if 99.99999999% are only accessed once, you still have to track them.

BTW - the reason for using the messagequeue is that you can control/throttle how much throughput you want in there, so you could load data in bursts.

Deja View - the feeling that you've seen this post before.

Pete O'Hanlon16-Jun-08 9:12

16-Jun-08 9:12

Never mind - I need to get my brain back into gear here. Basically, what you have is an optimisation problem - effectively you've got a matrix MxN, where M represents the number of objects and N represents the accesses. What you could do is create a sparse matrix, whereby you would put the value in and the time you last access time for each accessed object. Now, every so often you will want to iterate over this list and remove those objects that haven't been accessed since the last collection. At this point, you have a sparse matrix.

Deja View - the feeling that you've seen this post before.

Chris Maunder16-Jun-08 9:18

16-Jun-08 9:18

Bingo

[Except I just thought of a way, way faster way of doing it using some stats we keep elsewhere. I know - unfair posing a problem and not telling you about the ace up my sleeve Wink | ;)

]

cheers,
Chris Maunder

CodeProject.com : C++ MVP

Pete O'Hanlon16-Jun-08 9:22

16-Jun-08 9:22

Chris Maunder wrote:
I know - unfair posing a problem and not telling you about the ace up my sleeve

Never mind - I got to dust off some of my old optimisation skills, back from my life writing realtime optimizers.

Deja View - the feeling that you've seen this post before.