Author |
Topic: Ranking streaming items (Read 1374 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print