WiFi is not always best

I own a Nexus 4. Aside from a few niggles with the camera and distinctly average battery life, my phone is great. Particularly as someone who uses Google services, the user experience is pleasant and if feels like everything is working for you.

Well, almost everything. I find myself constantly fighting the phone over network connections – specifically when the phone should connect to available WiFi networks. The switch to WiFi appears extremely aggressive: as soon as a known network is within reach the phone automatically connects, regardless of the strength of the connection, the availability of internet access from the network, or – and here’s the kicker – what I’m currently doing.

Often I will be walking around Bristol, chatting with friends and family on WhatsApp or Google Hangouts whilst using mobile internet. I’ll walk past a cafe I’ve visited before and my phone switches to its WiFi network, stopping that message I was about to send. I swipe down and turn off WiFi. Later on, I’ll be home checking Facebook/Reddit/Hacker News/Any Other Time Sink and be frustrated that all these images are loading so slowly – I need to see that cute kitten now damnit – until I realise WiFi is still off. So I swipe down and re-enable.

Why is this so frustrating? Well, firstly because it is so common: it probably happens multiple times a day. Secondly, it all feels very preventable:

• My phone is aware I’m moving(1)This doesn’t even require high battery GPS; the constant change of networks is sufficient. Why jump on a new WiFi network that is likely to drop out of range?
• Instant messaging is a very low bandwidth activity. I really don’t care about saving my data allowance. I’m with giffgaff and have a generous data plan(2)My allowance is 3GB/month. I used to be on an unlimited data plan but I don’t mind the new cap. I rarely hit 1GB and a limited data plan allows me to tether, which is occasionally useful to me
• Surely the phone could at least test that WiFi network actually provides internet access before connecting? Many networks are unprotected but require a login after connection. This is particularly true of the large, national networks with many hotspots around a city. Inevitably, these are the biggest problem.

Although the phone provides an option to ‘avoid poor connections’, this doesn’t seem to help much(3)If anything, it just makes thigns worse. It feels like another setting to fight with: there’s been too many times when I have wanted to connect to a network with a weak signal.. Perhaps I could use one of these apps that only enables WiFi at home and and work? Maybe, but this is definitely not tackling the problem and only fixes some of the symptoms. When I visit my friends or parents, I want to use their WiFi network. When I’m actually in a cafe, I might want to use their network. And particularly at work, which for me is actually an entire university campus, WiFi may not be providing me with a good internet connection at any given time. For me, the fix is this:

Use mobile internet unless there is a real reason not to

Where reasons include:

• The user has indicated that they much prefer WiFi networks, e.g. because they have a small data plan
• There is a stable connection to a known network that also actually provides a better internet connection
• The activity I want to perform is high bandwidth. This is the time for my phone to say “hey, there’s a connection that might work, but you’ll need to log in”
• Mobile internet coverage or speeds become poor

Doing this requires the phone to take account of how I’m currently using my phone – Am I moving? What’s my network usage look like at the moment? – as well as testing a WiFi connection before switching to that. Is that really so hard?

[ + ]

 1 ↑ This doesn’t even require high battery GPS; the constant change of networks is sufficient 2 ↑ My allowance is 3GB/month. I used to be on an unlimited data plan but I don’t mind the new cap. I rarely hit 1GB and a limited data plan allows me to tether, which is occasionally useful to me 3 ↑ If anything, it just makes thigns worse. It feels like another setting to fight with: there’s been too many times when I have wanted to connect to a network with a weak signal.

My running progress over the last year

I started running again just over a year ago and have been using RunKeeper for all of that time. I find it pretty motivating to track activities and compare with previous runs. However, RunKeeper doesn’t make it so easy to track your progress over time – at least not in the free version*

While RunKeeper allows you to export your data, they also have an API – so I knocked together a graph (using Flot) of my running history that will automatically update as I do more exercise. Perhaps I’ll write about how I made this in a later blog post and share the code. The graph below shows distance and pace for my running activities – either as raw data, averaged by month or a moving average

Data type:
Show distance as:

When I first made this, I’d run just shy of 200km in 40 running sessions. I’m pretty happy with that! What’s particularly pleasing is that I’ve been managing to run consistently – apart from a blip in January. Over the last few years, I’ve often tried to get back into running but usually had niggly knee issues. It seems that reasonably regular gym sessions have helped to keep other muscles strong – though I should also get back to yoga

It’s also nice to see that my distance has generally been increasing and pace has improved a little. Here’s to the next 200km!

*I suppose the Pro version (which is crazy expensive, but that’s another matter) might have support for this. Since I’m just using this for my own personal data, I don’t think I’m doing against their terms

Back to blogging

I have never really got into blogging. The last blog posts I wrote are now over four years old and were just to document a summer research project.

I’ve decided to try now though, for a few reasons:

• Presenting some of my PhD work in a more accessible way is a valuable skill
• It will hopefully encourage me to work on side projects in my spare time

A quick overhaul of this old WordPress had the lower barrier to entry. A new theme (Decemberable – slightly customised, without the mug shot it seems a little impersonal) makes things look more modern. I was surprised by the number of ‘popular’ WordPress themes that weren’t responsive; looking OK on mobile/tablet is really a must these days. Maybe in the future I’ll look at different blog software or roll something custom though.

Final Report Plus Code Library

I’ve now completed my final report for this project, which can be found here.

There’s also a release of all the code, which should be quite friendly to use here.

Apart from some work still to do at StringPedia, that’s pretty much we done for this project. It’s generally been a good experience and I’ve enjoyed it. I’m now looking forward to a little bit of a break before university starts again in October.

Positive Results At Last

Until now I’d not run any tests comparing the two methods that can report the hamming distance at all alignments of text and pattern (A special case of k-mismatches where k >= m). The methods are the naive $O(nm)$ approach and the algorithm of Abrahamson/Kosaraju which runs in $O(n\sqrt{m \log{m} })$. Early results are quite pleasing though! The following shows a graph of run-times for varying pattern sizes with a text size of 4,345,138 (the full length of the source). The text and pattern were taken from an English text sourced from Project Gutenberg:

It’s a little hard to see down at the lower pattern sizes (in fact it’s pretty hard to see at all unless you click for a larger version!), but the Abrahamson/Kosaraju method is faster right down to pattern sizes of about 5! It’s interesting to see that there are some slight bumps in the run time of the algorithm; though this can be attributed to the number of “frequent” characters — for each frequent character matching is done using FFTs, which adds some overhead. It’s further complicated by the fact that a character which occurs only just enough times to be considered frequent will have more relative overhead than a character which is far above the “frequent threshold” — in each case we’ll do the same amount of work, but in the latter case, we should see less use of the “counting” part of the algorithm.

I’ll run some tests on larger text sizes over night and also use some different sources; it’ll be interesting to see how it fares with a smaller alphabet size, perhaps using the  DNA corpus from Pizza and Chili

Working, but slow

After some work, I’ve now got the new library working — I’m using LCA queries on the suffix tree in order to calculate pattern-pattern LCEs. In addition, I’ve now converted the p-representation generated to work with the new library.

After all that, I was a bit disappointed to find out that new library isn’t performing so well; the old library builds the suffix tree quite a bit faster and is much much faster at creating the p-representations of the text. Things aren’t quite as bad as I first found: it turns out that the new library is affected quite heavily by optimization levels (perhaps unsurprising, since it’s OO and C++ so inlining, unrolling etc are going to be needed for speed) and also that I was using the slower of the two suffix tree methods. I’m currently investigating ways of making if faster : for example, it provides various implementations of suffix arrays, one of which is uncompressed, so I believe should be faster than the default, compressed array. I’m also expecting an update on the library from the author, who tells me that the latest version is faster than the one I’m currently using.

In general, I think it may always be a little slower than the old library: it provides more functionality and focuses on size as well, but I’m still surprised at how much slower it is. The best I’ve seen from it is still 6-7x slower at generating suffix trees and the p-representation generated is even worse.

Let’s hope I can fix this otherwise the best I’ll be able to do is to use the old library to create the p-representations and the new library for LCE calculations. That would involve creating two suffix trees though, so it seems a bit pointless!

Finally getting somewhere (maybe)

For the last few days I’ve been fiddling around trying to get this library working. It supports LCA queries on suffix trees, which is quite nice. However, it’s been a bit of a pain to compile and it’s also written in C++ which I have no experience with and have to make work with my existing C code. Oh, and Valgrind doesn’t seem to like it too much (but only if I compile it; the examples compiled with the supplied Makefile run fine through Valgrind — odd) but I’ve emailed the developer about this.

But no matter, I think I’m getting there with actually performing LCE queries with it; certainly I’ve managed LCE queries on a few simple strings. A few bugs have come up trying to integrate it into the rest of my work, but lets hope (and pray) they’re easy to fix.

On a side note, I’m going to have to do a little more work on the rest of the $O(n \sqrt{k} \log{m})$ method anyway. I’ve been able to generate inputs that have the same text and pattern lengths and the same k but fall into different cases becase one has more frequent symbols than the other and, excluding pre-processing time, case 1 has been up to 10x as slow as case 2! Whether or not it’s worth trying to reduce the time complexity to $O(n \sqrt{k \log{k}})$ or it would be better to simply change the maximum number of frequent symbols allowed for case 1 to be used (I would assume that changing it from $2\sqrt{k}$ to some fraction of that wouldn’t affect the time complexity, but I’ll need to check) I don’t know.

Food for thought I guess.

Randomised Results

I’ve been meaning to get around to benchmarking a couple of implementations that solve the “matching with don’t cares” problem by using some randomisation. This reduces the number of convolutions we need at the sacrifice of the small chance of a false-positive. More specifically, we can reduce the number of convolutions from 3 to 2, or even 1 if we consider the case where wild-cards are only allowed in the pattern.

The implementation allowing wild-cards in either follows straight from Adam Kalai’s paper; the method only allowing wild-cards in the pattern is a little different though follows the same broad idea. If I get time I guess I should probably implement Kalai’s method for this for completeness.

Anywho, onto the results which are quite pleasing:

• In both cases, the point at which the algorithms become faster than the naive method is somewhere between a half and two thirds of the deterministic equivalent. This follows nicely from the reduction in the number of convolutions.
• With wild cards in the text and pattern, this is a reduction from around 80 to 45-50.
• With no wild cards in the text, we get a reduction from about 50 to 25.

You can see some graphs of this either in SVG format or in PNG format.

These results were repeats for a few different text sizes in the range of 1-4 million; I might repeat it overnight with a larger text size but I don’t expect to see any difference. You can read more about the testing and results over at the page on StringPedia.

A Day Of Frustrating Edge Cases

So I’ve spent most of the day fixing a few bugs and dealing with some edge cases. That’s the nice thing about theory: you can ignore all the slight caveats and small problems. The two problems today have been: 1.) rounding of the values of $\sqrt{k}$ — I ran into a problem because I was rounding down, resulting in it not being possible to find enough matches for a given alignment to surpass the threshold at which potential mis-matches are verified with LCEs and 2.) producing p-representations when not all of the characters in the text are in the pattern — to deal with this we change the last character of the pattern to some special character and set all characters that don’t occur in the pattern to this character as well. You have to be careful if the only occurrence of a character in the pattern is the last character though!

On a more positive note, some tests that enforce the worst case for the naive method (text and pattern are both mostly a’s with the necessary number of b’s at the end to ensure a k-mismatch only occurs right at the end) have shown that all the methods are faster even for pretty small pattern sizes. With a text size of 1,000,000, the $O(n\sqrt{m\log{m}})$ method is faster from pattern sizes greater than 30 or so. Interestingly, at these small pattern sizes the $O(n\sqrt{k}\log{m})$ is running at least 1.5x as slow as this, even if we exclude the pre-processing time and use a very small k. This contradicts what I was looking at yesterday, though I suspect those times may be have been a bit skewed by a couple of bugs.

Perhaps for larger pattern sizes we’ll see the latter method performing better.

First Results For K-mismatches

I’ve just finished putting together something to time a few of the different methods for solving the k-mismatches problem. It looks like the results could be quite interesting. There’s quite a few variables and it will be interesting to see how that affects the relative performance of the methods. It’s already looking like that, for randomly generated texts and patterns, the naive method might be hard to beat. I guess this was also the case for the “exact matching with don’t cares problem”, though I’ve not really run any proper tests with randomized inputs for that.

It may be worthwhile putting more effort into the LCE generation. At the moment the pre-processing time is $O(n + m^2)$ and so is taking a fair while. But I’m seeing results that show that, if I exclude the pre-processing from the timing, the $O(n\sqrt{k}\log{m})$ method is running quite a lot faster than the $O(n\sqrt{m\log{m}})$ algorithm with $k=1$. I guess I should wait till morning and see more results before drawing too many conclusions though! In any case, it will be interesting to time the creation of the suffix tree; in particular I’ll be interested to see how the creation of a suffix tree for text and pattern compares with just creating the suffix free for the pattern and using the “p-representation” for the text.