On Tuesday night my friend Brian and I tried out a new restaurant in Tokyo. An Izakaya is a tiny bar that also serves food, popular with Salarymen. Usually the food is huddled way over on the unhealthy end of the spectrum, but we found a macrobiotic one with good reviews. We sat there bemoaning how difficult it is to find places in Tokyo. Streets don't have names and the address system is a bit confusing. The conversation moved on to talking about how difficult it is to express a location to someone. GPS coordinates are awkward, google maps links can't be sent by SMS or over the phone, and not everywhere has an address. Even some addresses are confusing enough that they get miscommunicated. And how do you concisely give someone the exact location for "that bridge in the middle of the park"?
Is there a better way, we wondered? Could a location be expressed in just a short string of characters?
As I walked home, my mind was churning trying to figure out just how short of a string I could pack any location on earth into. As soon as I got home I visited wolframalpha.com, using it for a legitimate purpose for the very first time.
Consumer GPS devices have a resolution of about one square meter, which seemed to be the appropriate range to aim for. I was tempted to go for ten meters to make the string shorter, but decided it would be too inexact.
So, into Wolfram I put in "Surface area of planet earth in square meters". That gave me a fifteen digit long number, meaning that if I wanted to stick to just decimals, the new notation would have to be fifteen characters long. Too long.
I took that number (5100000000000000) and put into Wolfram "5100000000000000 in Base 36", which represents how long the string would be if I used all of the letters and numbers. That gave me a ten digit number, which was still longer than I wanted.
I changed base 36 to base 62, which represents all of the upper (26) and lowercase (26) letters as well as numbers (10). That gave me nine digits, but the first one was a two, meaning that it was just barely over twice as many locations as I'd need to get down to eight. I decided to split the globe in half and add a plus or minus to the beginning.
That brought me down to just about 20% more locations than I would need for eight digits. To bridge the gap I cut off everything above and below the northernmost and southernmost cities with 1000 residents respectively. I also had to stretch the map just slightly (4%), which resulted in a slight decrease in accuracy, but I thought it worth it for a shorter string.
The biggest technical problem followed. Although there were enough locations in my narrowed-down field, there wasn't an easy way to use them all. That's because the maximum latitude or longitude that a four character alphanumeric string could hold was about 167.00000. I needed 179.99999 for the latitude, but only around 126.00000 for the longitude. In other words, I couldn't just have a pair of four character strings; I needed to "borrow" the extra space from the longitude and use it for the latitude. This took me a full twenty-four hours to figure out, and by figure out, I really just mean that I posted it to quora.com and a really nice guy told me how to do it.
Hey, it's not all glory.
The next two days were spent learning how to use the Google Maps API and throw the whole thing together in a usable fashion. It could still use a bit of work, my code desperately needs to be cleaned up, and I need to make a mobile version for phones / Kindle, but enough functionality is there that I think people will find it a useful service.
To check it out, go to ToFind.Me and search for an address in the search box. You can also click the map to "unfreeze" the findme code and it will update as you move the mouse around until you click again.
I'd love to hear your feedback... is this useful to you? Could I change it to be more useful to you? Do you want to make an iPhone or Android app for it?
If you're in Tokyo, check out the cool bar/restaurant in the basement here: http://ToFind.Me/+remkjuka. It's built out like a cave. I didn't eat there, but my friends did and they really liked it.
Since photos of me slumped in a couch eating mikan oranges while programming aren't exciting, here's a picture Todd took when we were on the roof of this building.
I don't have a picture yet, but I got to visit NHK (like the BBC of Japan) because my friend Miwa works there. It was really fun playing with the weather green screen and sitting in the anchor's chair.
Cool thought exercise, Ty. I definitely agree with the suggestions to eliminate or otherwise compress the oceans.
Here's another suggestion for optimization: you don't need the same accuracy in wide-open spaces that you do in dense, urban ones. While it might be useful to locate someone within a meter in New York, Toyko, or Beijing, there are vast areas of the globe, including the oceans, Saskatchewan, the Arctic circles, Mongolia/Siberia, to name a few, where you don't need that level of precision. A square kilometer (one millionth the precision) or even 10 square kilometers (one ten-millionth) might be sufficient. Maybe there's a way to model a grid that is denser in populated areas than in unpopulated ones? This may make the translation to GPS a bit more complicated but might save you quite a bit of information storage.
Signal processing and data compression is fun and fascinating stuff - I have a BBN/Harvard/MIT friend who does this for a living -- I'll ask her to take a look at this article.
* By the way, the link took me to Saskatchewan too.
I could be missing the point here, but I just used http://is.gd to compress my location as grabbed from Google Maps and am getting very, very tiny URLs, even shorter than tofind.me does. As an exercise in "how would I do this" it is an interesting project, but for the end-user point of view, being able to make a url that is readable over the phone (or turned into a tiny QR code for a business card?), I wonder a bit if this isn't a solution in search of a problem.
Your website, encoding San Francisco, CA
URL shortening of standard Google Map URL, exact same address
But, in the spirit of thinking about the problem, I think if we look at the characters as raw strings of bits, we'll find we can encode quite a lot for a table look up in a database using just a few characters. A pre-built table could likely contain even shorter URLs, as we are concerned with only one domain of data: geo coordinates.
However, even just thinking about a one-for-one encoding of latitude and longitude, if we consider that 4 bits can hold the entire 10 digit space (plus extra... perhaps that space could be used for something), we can imagine that a single UTF-16 character could hold a 4 digit number, more than enough for a latitude plus .1 precision. Add a second character and with 32 bits we can encode xxx.xxxxx precision in two characters. Do that for both lat and longitude and we get 4 characters encoding any point on the globe with 5 decimal point precision. Add one more character and allow the lat and long to share some bit space within a single character and you'll gain 7 decimal precision.
With UTF-8 encoding, we have to be more sly in thinking about how best to maximize the bit usage. Still though, a single 8-bit ASCII character would effectively hold two digits of information, so if Wolfram Alpha gave you a base 62 digit that was 9 digits long and each digit can be represented by 4 bits, then at 5 characters we still have the possibility to encode every square meter on the planet. Going back to the UTF-16 character set, we could get it down to three characters... two if we are willing to lose precision... but there's still no guarantee those characters would be human readable.
Im not sure if you made some changes recently or not but the links to map locations you have there are somewhere in northern Canada. Also, when I try and go directly to the website without a /something at the end, nothing loads but a grey box and a green box. However, when I follow your link everything loads just fine.
Interesting solution to common problem. This is a problem that my friend and I set out to solve also. We took a somewhat different approach and enabled real-time tracking of friends also using google maps api. Check it out at mobileply.com. This is a little more robust and has some of the features I think you were looking to implement. I do love the simplicity of your idea though.
Cool idea! I just tried it and +remkjuka, it tell me is closest to Bylot Island, Baffin, Unorganized, NU, Canada.
And no map is showing. Tried it both in Chrome and Firefox on Ubuntu 10.
Saw this a few days ago and thought it was cool.
Was just browsing the internet and saw the following links:
The first one is more of a call for help (get in touch?!). Georef seems to be very similar to your proposal!
Angela - I missed it too at first, but it's in the fact that the URL is shortened to a point where you can easily communicate it.
Pretty awesome idea. Like the first commenter said though, the problem is getting people to ultimately adopt GPS. Till then, the nearest address is a nice workaround, if it is in fact accurate for the most part - it would be helpful to list the distance of the nearest address to your exact GPS coordinates, by measuring the distance between the two GPS coordinates
The blog started right after we got to our first stop here in Panama, but the dream and the planning of going nomadic began about six months prior.
I think Todd's reasons for going are similar to mine, but I'll speak for myself for now.
Traveling has always been one of my favorite things. Ever since I was fortunate enough to go to Taiwan when I was 13 (Thanks Charlie!), I had the bug. Not only to travel, but to go off the beaten path. Honduras is more appealing than San Francisco.
I feel that I'm kinda getting sense of the PL course. Which helps me gain confidence about studying here. It seems not to be a problem to follow up with both Algorithm and PL during lecture for now. But the really hard part is assignments I think. After all, we've got only less than 3 hours per week for listening to class but we are expected to spend at least 10 hours on assignments each course per week. So it's really important that I try my best doing all the assignments.
So, let's talk about assignment. Right now the assignments for PL seems not to be overwhelming, but I think things are going to be complicated as this course going. If we're going to construct a whole new programming language, then the workload should be hard. So I'd better pack myself and prepare for it.
As for Algorithm, it's really a course that provokes a lot of thinking. And the mechanism of pair assignment is very helpful. I learned a lot during my first assignment working with Michael. And he's only an undergrad! So it really makes me stressful that undergrads here are very creative and outstanding- they even take more classes per semester than I do!
Also, during working for the assignment, Michael have some ideas that is really cool. I never thought of making the string reverse for Problem 3. But it's really what we ought to think- the sub-string must look the same backwards and forwards, so when in original order, we're looking at the string forwards. How to look the string backwards- just reverse the string, right? Pretty simple if you get here. But I was kinda fall into a hole and couldn't notice the whole outside world. And I have a feeling that I've seen some problem like this before, but I still can't remember how to do it this time. This is a little bit sad for me.
Another problem is that I easily fall into the misunderstanding of sub-sequence. I was just thinking that sub-sequence is the same as sub-string but actually they have radically difference! This also leaded me to thinking the Problem 3 wrongly. A little bit more sad~!