Easy product or class rating system

So you've got a lovely little ratings system going on your site. All of a sudden though you get slashdotted, dugg or just your marketing starts working and you have thousands of users all rating your products / services / systems / posts / videos etc and your pages start to creak.

"It's the shared web space you're on," say your techies, "it can't handle the users" and duly bounce you to a better hosting environment at triple the cost along with the migration charges.

From time to time I come across this problem when I've either picked up code from someone else or else a techie asks me how to optimise a page that's running really slowly. In this particular instance it was caused by a ratings system in the style of Amazon or YouTube - basically a user is displayed a product and then people rate it as to whether it's any good. The real problem came when they had a list of products, each of which had it's individual ratings displayed.

The cause of this very slow page however had nothing to do with shared hosting or otherwise or direct server load - it was all down to some naive coding executing what my old CS lecturer would call an O(n)² process.

What the coder had done was get a list of products, then for each product gone back to the database and got a list of all the rankings ever made and then averaged them out. Nice and simple but frightfully inefficient and that which caused the problem I've highlighted.

This isn't the first time I've seen this and I've been asked how to build them numerous times as well so here's a well optimised method of doing it in general terms.

Consider first that calculating the average when you insert into the database is going to be computationally less expensive than calculating it every time you perform a select when a user hits the page. This sounds obvious but it's stunning how often it's overlooked.

Make two extra fields for your product table, one called average and the other called user_count or something. On your insert of the rating into the ratings table, run a trigger or else add some code that will update the product table with the updated count and a new average calculated from the ratings info.

Now when you select the product data you pull down the average and user count as part of that select and they are just simple static fields, thus adding no more computational load than the original select or view does already.

This gives you a nice little rating system that's not heavy in terms of processor load. However we can improve things once step further if you aren't interested in the data.

The option I'm providing below is good if you are just after a running average and don't care about the individual ratings being kept. I did a project recently where we weren't worried about keeping individual ratings data because the site wasn't going to be up for very long and it didn't add anything to our system to have it.

This option uses a running weighted average in order to just update the data in the product table without requiring a ratings table at all.

Some useful background maths though:

If I have a set {3, 4, 4} and take it's average I need to add the numbers and divide by the number of entries. Thus this set's average is (3+4+4)/3 = 3.67

Now suppose I've precalculated this average as I've suggested above and stored it without the individual ratings, I now want to add another rating, 2 to the set.

Intuition says to do something like this: (2 + 3.67)/2 = 2.83 which is actually wrong. Looking at the set {3, 4, 4, 2} we can guestimate that the average is going to be somewhere more between 3 and 4 than it is 2 and 3 as we've calculated above.

Thankfully a technique from statistics gives us an option here which is to use a weighted average instead. This is useful for adding sets together that have different numbers of elements within them but maintain the averages by skewing the data using proportional averages (or a weighted average).

The general formula for this is:

Avg_w = (Avg₁ * (n₁ / (n₁+n₂))) + (Avg₂ * (n₂/ (n₁+n₂)))

Where:

Avg₁ is the average of the first set
Avg₂ is the average of the second set
n₁ is the number of elements in the first set
n₂ is the number of elements in the second set

In our example this simplifies even further because our second set is actuall only one item. So let's work this through:

Avg_w = (3.67 * (3/(3+1))) + (2 * (1/(3+1)))

= (3.67 * 3/4) + (2 * 1/4)

= 2.75 + 0.5

= 3.25

Which is the answer we're after for our average.

As we know all the base line average data in the product table and we know the value of the rating we're tracking, it's a very simple function to update this instead of doing another insert into a ratings table and we just keep on doing it for every rating that has been added.

Computationally this is a very inexpensive process and whilst I'm more than happy to be shown otherwise I think this is about as good as it gets in terms of optimisation.

The key thing is we've now reduced an O(n)² operation to O(n) which is a drastic improvement as n tends towards infinity.

Fuzzy logic could book more flights

I've talked about fuzzy logic for use by the retail sector in the past and the project I'm involved in there is maturing nicely. This week I've really realised how as software engineers we need to grasp the nettle and move a lot of service based software toward fuzzy systems for usability reasons.

Nearly everyone these days has booked a flight online and when it came time to booking a holiday to Australia this winter, the first thing I did was fire up a browser and head to expedia and travelocity.

If I was planning to fly on specific dates I would be well catered for and I could get a list of prices and book a flight in a few easy steps.

I wasn't planning on flying on a specific date though. I work for myself so can take time off whenever I want in a general sense. Really what I wanted was the cheapest flight from London to Sydney in December.

After typing a few different dates in manually I did the sensible thing and called a human travel agent who was very helpful. Unfortunately, as helpful as she was, she only had access to the same systems I did so couldn't tell me the info I needed to know. Mentioning this to friends had the usual "you can't do that" response. Can't do it?! I'm the customer I can book when I want.

All airlines operate through the SABRE booking network which is basically a masive database of flights from point to point with availability and prices per leg on it. It sits on top of a nice mature API which makes it easy to program against and so that's where the developers leave it.

But as a customer this doesn't fulfill my requirements and this is where engineers need to spend more time thinking fuzzy.

In these days of multi-processor and multi-threaded OSes it is not that difficult to build offline agents that could go and find this information out for a customer and then email it back to them. Indeed I wouldn't mind registering to use this sort of service so now the company has my personal details and they can market to me.

The agent wouldn't even need to respond with all the availability. It could just give me the cheapest 10 or 20, all from a specific operator etc or those flights routing through Hong Kong as a stop over for example. It also doesn't need to be fast. A deprioritised thread could take a day to get this sort of information and if I'm being that vague then time is hardly an issue.

If someone reads this from the travel industry please ask your techies to build this feature. If you are a venture capitalist then give me a call and we can revolutionise the online travel sector!

The web has brought us an always on, on-demand, serviced-based method of interacting with our information but the casuality of this has been flexibility. The days of fuzzification are soon to be upon us and coupled with automated agents some amazing new systems will become available that will give us back our flexibility.

Fuzzy's where it's at... or will be eventually

I'm working on a project at the moment that took a remarkable turn recently. Most clients we work on are fairly staid in their use of technology - which suits our company as we are firm believers of the Keep It Simple Stupid methodology of programming.

I was in a meeting with a client who is a large retailer and we were talking about "filters" for being able to reduce sets of data returned from the database. Things like "style", "size", "price" etc - not dissimilar to Dabs or any one of a thousand other online retailers. Off the cuff I just said "wouldn't it be good to use fuzzy logic on the filters so instead of black and white result you get the shades of grey as well". To be honest I'm not even sure why I mentioned it...

Imagine my surprise when the client said "Show me"... Out came the pen and paper and 15 minutes later he was sold on the idea and I was left to code and example.

Fuzzy logic is a funny old beast - it is based around this notion that instead of black and white you deal in shades of grey - black and white are just extreme examples of the shades of gray. So black might equal 0 and white might be 1 but in between we can have 0.5 or even 0.3218956 if you so desire... everything belongs to every group at least in part - even if that part is tiny, or even 0.

I love fuzzy logic - I played with it a lot at Uni when I was studying Neural Networks - but it has never made it into mainstream web use - mostly because it is so difficult to implement with a database unless you do a lot of extra background work. Background work most clients won't pay for.

It does make a big difference though - take this as an example:

Say you have two products, Product A is £295 and Product B is £305.

Now suppose you have a filter, or a search query that says "Give me everything less than £300"

Obviously Product A gets returned but Product B wont if you are using discrete maths as it isn't 100% lower than £300.

In the fuzzy view of the world though we can say "Give me everything approximately less than £300". Now depending on your exact specification of what "approximately" means Product B may well be returned. Indeed most people prepared to spend £300 will probably spend £320 so we could say Product B has a 95% fit for this result. As we get closer to £320 the relevance gets less so it is less likely to be returned.

Ahh, I hear you say, I can do this by just pushing my filter up. Yes you can but then £321 is left out altogether again. Maybe £321 is not as relevant as £305 but it is more or less as relevant as £320 on this scale.

Fuzzy logic has made huge strides in engineering particularly with control systems for things like washing machines [if a load is heavy use more water, if light use less] and airconditioning units [if it is hot turn on harder than if I am more or less where I need to be] but it has never caught on big time on the web.

I think that now that fundamental systems are starting to get in place [e-commerce etc is no where near as difficult as it used to be] then we will start seeing clients and programmers starting to use their brains a bit more and looking at how we can deliver the best experience for our customers.