Approximation in the Web World

In a recent Coding Horror article on the Wide-Finder 2 project, it dawned on me that there is Another Way to solve I/O-limited Top 10 URL problems and generate a faster log analyzer: approximate.

As a Physicist, I know that not only is an approximation frequently perfectly adequate, in many scenarios is it more valuable to have a good, quick answer than a perfect, slow one. Imagine if Google really searched the whole of its multi Petabyte index just for your lolcats query.

The Wide Finder 2 problem is that you have a very large dataset, out of which you want to retrieve the top 10 URLs. Most of the discussion seems to centre on which language to use, and how to parallelise the code.

A fast start
Suppose you've created something clever that uses:

• a thread to read in the dataset and pile it sequentially into chunks of N megs of memory
• a batch of threads that do an initial match but not perfectly - making an unsorted statistic for each chunk, idling if there is nothing to process
  
• a third batch that sorts these chunks and atomically integrates the result into a main list

Then you tidy up at the end.

But the problem will still be I/O-limited. This is what happens with supercomputers - you just convert a compute-limited problem into an I/O-limited one.

A clever approximation
Although it's not in the spirit of the original project (it doesn't 'mimic' the original script), in many ways adding an approximation speedup is exactly what people need here. It makes the resulting numbers slightly worse in order to make the speed a lot better. No, I know, speed isn't the most important thing when processing log files. But this is a project centred on speed, so adding this dimension might make people think a bit harder. So what's the idea?

Skip most of the data.


The statistics (think pareto, normal distribution, etc) will tell you that for a popular site, a small proportion of the articles will absorb most of the hits. Hence the top 10 list. So we can make use of that by reading a sequential chunk of data, then skipping a big chunk, and repeating. If we simply modify that first thread in this way, we can (with a bit of experimentation) skip a large proportion of the file. The only requirement is that the statistics on the combined selection we do read give the same top 10 as the dataset as a whole.

Monte Carlo log file analysis
If we take the Monte Carlo approach, and randomly decide how much of the file to skip, we can simply keep reading chunks of the file (scanning back to the beginning if necessary) until the top 10 list stops changing. Note that we may be encountering new files, we may be adding more to the statistics of the top ten, but all we need are the right 10 in the right order.

One of the beauties of Monte Carlo methods is that they parallelize superbly. By throwing determinism out the window and letting the sizes of the chunks we read, the sizes of the sections we skip and the decision to quit probabilistic, each thread can run independently. I run until I stop seeing changes, then I decide to quit. The only inter-thread communication becomes getting the data to process. We can use multi-core friendly while loops rather than incrementing shared integers, or waiting a number of steps to read/quit.

Outro
So there you go. Physics methods applied to log file analysis; approximation in the Web World. Remember, Google are smart, and they give you approximate answers: "Results 1 - 10 of about 26,900,000 for kittens".

Ethical/green driving lessons

The Pitch
I haven't covered many straightforward business ideas here, but let's start with some bandwagon jumping: Green driving lessons.

The differences:

• The instructor's car is a hybrid of some kind, or perhaps a hydrogen/electric car eventually.
  
• Lessons are on driving an automatic. All hybrids and electric cars are automatic or paddle-shift, because the standard gearing system and technique is designed to give a petrol engine mid-range revs where the it has its best torque output. I think.
  
• It should help shelter the instructor from the rising price of fuel
• But above all it's got that warm, fuzzy, superiority of doing something normal in a green way.

Did you wonder why 'ethical' sits pressed against the 'green' in the title? Ethically, you'd be better off feeding the starving than saving the environment, in my view. So perhaps the fuel money saved (significant - learners spend even more time at low speeds) could go to aid charities, or at least give the student the choice of adding a pound to their lesson price to go straight to a particular charity. They'd go for it, they're paying for green lessons.

Business Sense
There is good business sense behind all this:

Target demographic: younger females.
Most learners are teenagers. Most teenagers are still quite left-wing, liberal, eco-friendly, moral, etc. They're not bitter yet. So to many of them, particularly those who aspire to driving hybrids later on, green driving lessons would make perfect sense. Admittedly, a more female demographic, and some of the boys will baulk at the automatic-only nature of the deal and the girly image. So consider this a niche market. A niche 50%.

Marketing message: aspirational.
Most marketing, and generally the most manipulative marketing, is aspirational. And here you're certainly trading on that: if you want to be green, you'll have eco-friendly lessons.

Lower overheads = wider profit margins
One of the largest overheads for any driving instructor is the fuel. As the price of petrol rises with the price of oil and tax increases, the instructor's profit margin is squeezed. On the other hand, as this pushes up the average price of driving lessons, a green driving instructor would see their profit margin increase as the extra money mostly went into their pocket.

The Hypocrisy and the Pragmatism
There is hypocrisy (no, not irony) in eco-friendly driving lessons. The best lesson is to simply get a bus instead. But there is pragmatism at work - if kids are going to learn to drive, teach them how to do it with good fuel economy. The clutch/accelerator games disappear in an automatic, so there isn't the tradeoff that lower revs means more stalling. And they'd be geniunely interested in learning. Smooth driving is generally safer anyway.

The Final Kicker: Parents as a new (niche) market
With high petrol prices, inevitably the parents could benefit from learning greener driving, which opens a new market: Parents that take a few lessons on green driving technique. Inevitably, you don't have to be a parent to do it, but parents are the most immediate choice: you already have the customer relationship in teaching their child to drive. So it shouldn't be too difficult to add a few hours on for Mum to learn smoother driving and up her fuel economy. Inevitably, a fair proportion of the time would be spent teaching them to drive more carefully and ironing out bad habits, but that can only be a good thing.

You can always earn commission on referring them to your nearest hybrid dealership.

Daily exercise for your creative muscles

Create a flow gadget or RSS feed or other auto-updating thing to give people a short and straightforward creative exercise to do, up to twice a day. In the style of OneWord as an iGoogle gadget, for example.

Could make it social with games like these:
* Write oneword type paragraph, then provide a (related) word for the next person. Show your previous posts in the string.
* Web 2 whispers - you write for an unknown random number of seconds, then the text is snatched away for the next person to continue - they get as many seconds as you had to read it, then a random number to write.

But really, variety would be a great thing. Get people doing word association, describing a day as an X, relating two words, perhaps even writing for the length of a particular song, taking a phone photo of some interesting bit of ceiling, writing a haiku, chewing an interesting shape, drawing on a banana, following on from a randomly chosen sentence, following on from other people's following on sentences, taking a photo of two and a half things, explaining their choice of colour for 'think', imagining the world without an X, thinking up new ideas about a randomly chosen product, venting their spleen, getting angry, sending an extract from a receipt in their pocket, drawing a both-ways-up face, designing a tshirt, spilling some water (intentionally) and giving it a caption, "You are a dog, what do you think of fridges?", asking any of a thousand useful (and perhaps user contributed) questions - what would make a train journey better?, things to do with paperclips/cds/receipts/short pencils/unwanted cushions, invent a new magazine.

How would it work? Just provide a stimulus for the first few people, and occasionally drop in the question: what would you ask of people?

Setup: Blog-style post-and-reply would work well, but the replies must become the centre stage, rather than the post, and it must allow for more complicated supply and reply mechanisms for many of the above games.

Ah! How about a dynamically generated RSS feed unique to each user, supplying a reply-type link for the responses, which updates to show the state of the game when they're finished.

Further rumination, generalising yet further: make the whole thing a game. Let people cluster towards fellow users who supply their kind of game or stimulus, allow them to form their own mini communities. I don't want to say 'Facebook app', but...

Dealing with long words

In his blog entry Injecting Word Breaks With Javascript, John Resig suggests using javascript to insert word-break positions in long words, solving long-word-broke-my-page-layout problems. The hyphenation problem has been around a long time, and in decent typesetting systems like LaTeX, libraries do the job for you, breaking in the right places to maintain the flow of a sentence and not leave you on a new line starting with a spare letter. One comment relays a story of their own algorithm which ran each time, breaking up words too long for the lines, but that it grew too computationally expensive. That implies it was being done every time the page was loaded.

As far as I can see, there are two different challenges here: dealing with long words and dealing with URLs. My comments:

Long words
Given that the best length of a line for legibility is somewhere in the 20-40em range, very few normal words will break your layout. Perhaps just process it when you are about to insert the text into the database - use a proper hyphenation script to insert zero width spaces or wprs or whatever. You can always replace them all later. This way each chunk of text gets hyphenated properly once, instead of badly repeatedly.

URLs
Unless you maintain a site dedicated to long strings of text, livingwithspacebarphobia or organic chemistry, URLs are the vast majority of long strings. Why treat them differently? Because they are not expected to be shown in their raw form; most people would prefer the long URL to be hidden behind the usual linktext.

Options:

• Replace the linktext with a shortened form - keep some of the beginning (so we can see the domain) and perhaps the text between the last slash and the following dot (the page name), to make something like 'slashdot.org/.../index...'
  
• Steal the title text of the linked page - in processing the form data, follow each link and get hold of the page title, and use that (or, again, a shortened form) as the link text.
  

The overriding principle? Sanitize user input. Even when all they are doing is typing in words and pasting in URLs, users can cause unexpected problems. And do the sanitizing on input, not as a reformatting exercise on output - the input processing happens once and the result is served up many times.

Social side of bookshops

Bookshops are a hallowed ground on the high street, or on campus. They have the high spending per square metre of a shop, but the quietness and sensible nature of a library. No pumping music, no anorexia-inducing models on display - unlike the rest of retail, the focus is on knowledge and choosing the right product. It is generally a solitary activity, even if you're there with a friend or spouse.

Yet those that frequent a bookshop are more united than most other shoppers. If I stand in front of the Computing section and leaf through Agile Methods books or Web Site Zen, I am united with the other browsers of the section. The basic elements for a classic community are there - geography (we're in the same bookshop, in the same town), commonality of interest (the section we're browsing) and probably social status (although that shouldn't separate us, really).

A golden opportunity.

The web two-point-oh 'revolution' is about interaction and user-generated content. But that's just community with shiny buttons. The internet has always been about information, porn and community. Assuming we've grown out of the second, much of the latest stuff has just been usable combinations of information and community. And if I'm in community with my fellow information seekers in a bookshop, we've shortcircuited the painful path to video-based social networking websites dedicated to specific groups.

The idea is this: have book nights for given subjects. Get an author or other 'name' in, provide coffee/beer and have a short talk and a Q&A. Let people ask questions about which books are actually useful, or whatever they like related to the subject. An example: "Computing book night, with the author of Agile Methods. Bring an inquisitive mind and questions about Agile methods."

There's some truth in the stereotype that geeks lack social skills, yet everyone needs community. I suspect that for many subjects of these book nights, if you build it they will come. But tell tem it's for their education, and let the social side accidentally happen.

Here's the stimulus; my suggestion for a campus bookshop which also sells snacks and drinks:
"It's summer, so let's have an al-fresco reading area outside - provide some cheap novels, expect people to buy their books first. Nice comfy sofas from the union communal area should work.

That should get people to come to the bookshop, and consuming more snacks."

Legible Web

Everyone talks about the symantic web, AJAX, Content Management Systems, Flash, and various other ways to fancy-up your website. And developers are told time and again about avoiding things that take away from the simple usability (and legibility) of the sites they create. But not everyone listens, and a significant proportion of the web is just illegible. These websites are designed for a different device, screen size, browser, or just not designed properly at all (animated background gifs, anyone?). So we end up trying to read things that are too small, too wide, illegible against the background or in a stupid font like Comic Sans.

So how about a browser extension that allowed you to choose to make that body of text legible? One that used all the well-researched legibility advice as defaults (alphabet and a half width, ragged right, larger fonts, better contrast) and allow users to tweak their settings.

The interface could be fairly simple - an inoffensive button similar to that in AdBlock, which would toggle the functionality for specific boxes, and the option to have it globally on. Functionality would revolve around undoing a lot of the things designers do (mess up fonts, colours, link underlining, silly backgrounds, etc) and set things that designers are unaware of (better line lengths of 30-50 characters, left justified text, paragraph indenting, greater leading, black on cream text).

Some users need even greater legibility through vision loss, so for them a mode with a different set of default values would be worthwhile. If everything is customisable, then few will find it doesn't help them in some way, but having the best set of defaults would be key.

Some pages that give legibility information: Web Style Guide, Wikipedia. As a side note, it seems that readability means something else - the complexity of the text itself, rather than its presentation.

Improving browsers

The Mighty Webpage: Still a Document
The humble webpage has been through many reformations, survived the attack of technologies that sought to remake it in their own image; flash, dynamic HTML, page transitions, animated gifs, the list is unlikely to end. All these have improved the basic webpage, but only slightly. The underlying formula has remained. It has been pointed out that nobody uses the navigation systems employed by websites, however pretty or inviting. We hunt for the piece of information we desire, and if it's not in the main body of text we look for an obvious link in the right direction. If we find neither, we hit Back and try the next path.

Many expected websites to become more complex, for the browser to fade away. That has always been Microsoft's expectation - that websites would evolve into applications, and that the browser would evolve into a programming platform. In some ways it has. Javascript/AJAX, for example is one of the supposed hallmarks of a modern website of the new (2.0) era. Yet Firefox came to the fore not just for its speed (an attempt to get out of the way) but for its features. Tabs, extensions, a search box, ad killers, alternate stylesheets. Dynamic and clever it may be, but the web page is still a document. Ish.

So where are our tools to use and manipulate it as a document? When you work with a photocopy, you highlight bits, tear bits out, underline things. You make lasting changes to it. An application is not meant to be messed about with. For that you buy the new version. Here are a few thoughts on enabling webpages to be treated more like documents:

1. Staples
Despite treating and viewing websites as a kind of interactive document, we don't have the tools to treat it like one. The favoured method of sharing a website with someone else is to send them a link. But in this you face the CMS systems that need cookies or session keys, which make it necessary to explain how to get to the page (the anithesis of the hyperlink), and the fact that no page lives forever on the web. The closest you get is the Wayback machine.

A solution? Staples. A web page now consists of a lot of files. Can't it all be packaged together, so that I can send it to someone? I had a set of search results from a travel company giving flight details, and the easiest thing to do was print to pdf and attach it. So at a first guess, let people Send As PDF, or Save/Send Zipped (a zipped folder with the site files in). A standardised way of saving within a zipped HTML document the origin of the page such that on opening it one could go to the live version, if it exists, would calm the critics saying we're sliding backwards technologically.

Highlighters and red ink
Often we want to annotate a page, or highlight bits of it. Currently, you need a specific extension for your browser to do it, and there is no interoperability enabling you to do the most basic thing in the paper world - highlight the interesting bit, scribble "How about this, Fred?" and give it to a colleague. This goes hand in hand with the above Staples - once annotated, you need a packaged way to keep it or send it.

• How about a changes-based solution? Much like word-processor documents can have a history of changes, do the same for HTML.


• Create a simple class of DIV tag for comments that marks a position on the page and contains a description - "This image is funny!", "What's this paragraph doing on our website?", etc.


• Provide tools for highlighting, grouping etc. Google's terms highlighting in search results is the right kind of effect.

It's gone off the screen again
Possibly one of the most irritating things when viewing a website is when the page is too wide. For whatever reason, the choice of font, column width and window size conspire to make you use the dreaded horizontal scrollbar. Although web designers are supposed to make pages that avoid these things, it does happen, and annoyingly often. So let people move things or resize the boxes.

This is really a call for easy ways to transparently edit the page CSS (or table properties), mostly centring on readability and accessibility. Whether it's an editing mode, or better a way to select and change an element (think marquee selection tools in graphics apps, and resizing in the same). Obviously, that works best in the changes-based, wrappable environment mentioned above.

Reapply Changes
The fundamental difference between a website and a printed document is what they are made out of. A webpage is just information, and so a set of changes is still just information. So if I have done something to one page, perhaps I can redo it to a different page, or a new version of the page.

A redo, or reapply changes, function would be the icing on the cake. This is possibly the most difficult to implement, but there are smart people out there. To be able to apply a saved set of changes to a site would enable people to change (for example) The Register's index page, and keep it 'changed' when they revisit it, even though the page itself has been updated.

Extending further, it enables the user to entirely redesign a site to make it more readable. By viewing the unformatted page (as is already possible in Firefox et al), and editing it in various ways, the page is remade as the user wants it.

Defense
Consider a very common everyday experience: Junior staffer finds something on a website. She prints it off, highlights the relevant paragraphs, and leaves it on her manager's desk. Said manager photocopies it, writes a note on it and gives it to another colleague. That entire process in electronic form would require one of those hellish Copy-Paste-into-Word moments where nothing looks right, emailing, opening, annotating or more likely maulishly editing, resaving and resending. Web pages are just not portable, editable or an improvement on paper. In the new version, you'd look at the page, email it off to your manager, he'd look at it (or click to view the live site version), edit it in-place, send it on. The paper office hasn't happened because paper is easier. There are financial (and increasingly ecological) incentives to move to a paperless office, but it hasn't happened because it's not easier yet.

So, browser-makers, let HTML be a document format on top of its other expanding functionality. Whether you like the suggestions or not, let's have html documents as documents, and save the planet.