Voting and ratings

[he_who_journals]

I've been thinking about rating systems. Some sites have simple up/down systems where you can vote a link up one point or down one point; and if you think it's high enough already, you can leave it. Many websites use averages of votes on a scale; the problem here is that when you have enough people voting, it's always in your favor to vote 1 or

Comments

Implementation

[he_who_journals]

Let me stress how cheap this is computationally with buckets. Use b+1 buckets B_0 ... B_b, with bucket i receiving B_i votes. The diagonal function is D(n); for a straight line with u users you can use D(n)=floor(n*(u/b)). In the diagram b=u=9 and D(n)=n. The squares below the graph are the buckets; their contents are the B_n.

Start with n=b, acc=0. REPEAT: acc=acc+B_n. if acc>D(n), stop with victor=n. otherwise :REPEAT

This is O(b), which is not bad at all. The sort is O(u) (not really sorting in the general sense, but it's all we need). In practice b will be fixed, so the entire process is O(u). That entire cost can be distributed over long periods of time (as the votes are cast). It should be obvious that the constants are small, too.

Taking a mean is also O(u), and the constants are comparable. A median can be found the same as in this method but with D(n) a constant u/2.