wu :: forums « wu :: forums - Ranking streaming items » Welcome, Guest. Please Login or Register. May 19th, 2024, 9:57am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: towr, SMQ, ThudnBlunder, Eigenray, Icarus, william wu, Grimbal)    Ranking streaming items « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Ranking streaming items  (Read 1381 times)
TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 1001
 Ranking streaming items   « on: Nov 1st, 2017, 9:52am » Quote Modify

N videos are streamed to you. Your goal is to rank the N videos. A simple way to do that is just give some score to each video and finally sort the videos by score to get the ranking.

Now there are constraints:
1. The videos are streamed to you one-by-one and it is just single pass
2. You have to provide positive integer scores
3. Once you have given score to an item, it cannot be changed

Note that, you know N upfront.

Given the constraints, how would you score the items so that you are able to score each video appropriately and the final ranking obtained is the one you wished for after going through the videos. Also, if r_i is the score given to ith ranked video. We would also like to minimize sum_i |r_i - r_(i+1)|.

---
I came up with this problem myself (based on some real world problem). By the way, I tried to make the problem as concise as possible above, I hope there is no confusion. I have some ideas on how to proceed to solve this, but thought it might be interesting to the group here.
 IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ranking streaming items   « Reply #1 on: Nov 1st, 2017, 1:57pm » Quote Modify

Is the goal a perfect ranking, or a "good enough" ranking?
Because to get a perfect ranking I think you need 2N-1 possible scores, just so you can always insert a score between two existing ones. But if "good enough" is good enough, you could use a probabilistic approach to reduce that significantly.
 « Last Edit: Nov 1st, 2017, 1:58pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 1001
 Re: Ranking streaming items   « Reply #2 on: Nov 5th, 2017, 6:51am » Quote Modify

That's pretty much what I had as well. A probabilistic approach would be interesting to explore too!
 IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ranking streaming items   « Reply #3 on: Nov 5th, 2017, 7:48am » Quote Modify

I think the biggest issue with a probabilistic approach is probably how you want to weigh the range of scores against the number of ranking mistakes (like duplicate scores, but not necessarily limited to those)

You could just pick a small fixed range of scores (say 100, or proportional to N), and try to insert videos as best you can (with possibly lots of duplicate scores). Most sites that rank things have a 5 star system, possibly with a decimal (so 41 scores if you start at 1 and end at 5 with increments of .1)

Whether you can estimate relative goodness of videos will also have a big effect. Say you've already seen a video with a score of 1 and one with a score of 100, then if you see a video that falls in between, can you tell (approximately) <i>where</i> in between? Is it more like a 30 or 70?
In this case an approach like library-sort might work: reserve some constant factor * N as space and insert videos as best you can, the extra space leaves you some wiggle room to insert videos that unexpectedly fall in between two previous videos. But there's still a risk of duplicate scores once there's no room left between two videos.

The quality of videos will probably follow a normal distribution, and even if we're limited to integers, you can use a logistic function to map one to the other (i.e. use more scores to represent the bulge). The more videos you see the better you'll be able to characterize the distribution and insert videos at the correct score.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: Ranking streaming items   « Reply #4 on: Nov 6th, 2017, 3:45am » Quote Modify

You could rank the videos relative to all the videos you have seen in the past, yielding a percentile.  That should give a score with a good distribution.  That is assuming the new videos follow the same distribution as what you used to see.  And that you have seen your share.

If you still get two equal scores, they are probably indistinguishable in quality.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: Ranking streaming items   « Reply #5 on: Feb 14th, 2018, 10:05am » Quote Modify

on Nov 1st, 2017, 9:52am, TenaliRaman wrote:
 Also, if r_i is the score given to ith ranked video. We would also like to minimize sum_i |r_i - r_(i+1)|.

That means minimize (r_1 - r_N).  Doesn't it?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ranking streaming items   « Reply #6 on: Feb 14th, 2018, 10:52am » Quote Modify

Yeah, considering you sorted on r.

If you want to penalize large differences between adjacent items, we could change it to sum of squares, instead of sum of absolute difference.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »