BitTorrent for geodata was big in 2005

Big in 2005…

Today I’m trying to find out whether BitTorrent + geodata is a “thing”. I have found out that it WAS a thing… in 2005! Just like Coldplay, Gorillaz, Eminem, 50 cents, James Blunt, Green Day… but it never really took off.

  • In 2006 Chris Holmes had a blog post titled Distribution of Geodata, where he said stuff like «What is needed is a standard, so that clients tile up the earth in the same way and make the same requests.» and «instead of asking the server to return a set of tiles that represents an area, it could ask a p2p network»
  • In 2005 Ed Parsons has a blog post titled Peer to Peer Geodata anyone ?, where he said stuff like «The idea of distributing large geodata datasets as small chucks is quite appealing and I have no doubt that when open geodata becomes more mature – this will be the obvious mechanism of supply» and «peer to peer means piracy in many minds, an unfortunate perception».
  • He and others mention GeoTorrent.org, a site offering geographical datasets via bittorrent.
  • In 2008 people ask: What happened to geotorrent.org?
  • In 2011, I’m asking the same thing: What is going on with P2P and geodata? Either I’m hopelessly old school, or a good idea simply went missing without a trace…

Ok, so people are still talking about P2P+geodata in 2006, 2007 and 2008, but the fact is that it has not seen a wide breakthrough in 2011. Or am I missing something?

GeoTorrent.org no longer answers HTTP requests, but it is still registered. GeoTorrent.org was run by ERMapper, who was bought by Leica Geosystems, who merged with Erdas, according to some person in 2008. It was a site devoted to offering geodata via bittorrent. Richard Orchard was one of the people behind GeoTorrent.org. Maybe he knows what happened to geotorrent.org?

Using the keywords “P2P” and “geodata” I went looking on scholar.google.com. I did not find that much, and nothing that has been generally adopted (see some of the hits in the Links section below).

What am I looking for in 2011?

What I’m looking for is something like a plugin for GeoServer, or a web-gis framework that fetches tiles via P2P, or something like GeoNode with a P2P twist. Actually GeoNode could be it… is GeoNode it?

Conclusion: Some pros and cons of P2P geodata

  • In 2009 a guy on a mailing list said: «Pure P2P solutions are great for exchanging large files, but typically have too much latency to be practical»
  • In 2010 some chinese guys said: «P2P technology offered a novel solution to spatial information online service and a good platform for sharing mass spatial data, it can avoid “single point of failure”and “hot spots bottleneck” problem»
  • In 2007 some austrians said: «As disaster management inherently happens in highly dynamic environments, these applications suffer from deficiencies with respect to maintaining connections to the server representing their sole source of information. We propose to exploit peer-to-peer networks to interconnect field workers.»
  • They also said: «P2P oriented raster geo-data online services have been widely applied, whereas vector geo-data online services still have many issues that can′t be handled, such as vector geo-data organization pattern, segmentation, lossless reconstruction etc»
  • In 2006 Chris Holmes said: «The damn brilliant thing about using an architecture of participation for geospatial data information is that as a layer gets more popular it scales perfectly, since more people downloading and checking out the layer means that more people are serving it up to others.»

If «P2P oriented raster geo-data online services have been widely applied», then where has it gone now? I’d like to find out…

Links

How translate.google.com works

Actually, this is not about how translate.google.com works. It’s about loading HTML from a random URL, adding some extra Javascript and CSS and redisplaying the page on a different domain.

A simple test page

I’ve made a simple test web page:

1
2
3
4
5
6
7
<html>
  <head></head>
  <body>
    <h1>Hello world</h1>
    <img src="world.jpg" />
  </body>
</html>

Let’s translate it with Google Translate.

The translation page has two iframes (details omitted):

<html>
<head>
<title>Google Translate</title>
</head>
<frameset>
	<frame src="/translate_n?...">
	<frame src="/translate_p?...">
</frameset>
</html>

Let’s look at the second iframe, the one which begins with ...src="/translate_p?.... This is the actual translated page.

Compare source code of the original page with the translated page. It’s been buffed up considerably.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
<html>
<head>
<script>
	(function() {
		function ti_a(b) {
			this.t = {};
			this.tick = function(c, d, a) {
				a = a ? a : (new Date).getTime();
				this.t[c] = [ a, d ]
			};
			this.tick("start", null, b)
		}
		var ti_b = new ti_a;
		window.jstiming = {
			Timer : ti_a,
			load : ti_b
		};
		try {
			var ti_ = null;
			if (window.chrome && window.chrome.csi)
				ti_ = Math.floor(window.chrome.csi().pageT);
			if (ti_ == null)
				if (window.gtbExternal)
					ti_ = window.gtbExternal.pageT();
			if (ti_ == null)
				if (window.external)
					ti_ = window.external.pageT;
			if (ti_)
				window.jstiming.pt = ti_
		} catch (ti_c) {
		}
		;
	})()
</script>
<script
	src="http://translate.googleusercontent.com/translate/static/biEfM_qFbxU/js/translate_c.js"></script>
<script>
	_infowindowVersion = 1;
	_intlStrings._originalText = "Original English text:";
	_intlStrings._interfaceDirection = "ltr";
	_intlStrings._interfaceAlign = "left";
	_intlStrings._langpair = "en|da";
	_intlStrings._feedbackUrl = "http://translate.google.com/translate_suggestion";
	_intlStrings._currentBy = "Current translation on %1$s by %2$s";
	_intlStrings._unknown = "unknown";
	_intlStrings._suggestTranslation = "Contribute a better translation";
	_intlStrings._submit = "Contribute";
	_intlStrings._suggestThanks = "Thank you for contributing your translation suggestion to Google Translate.";
	_intlStrings._reverse = false;
</script>
<style type="text/css">
.google-src-text {
	display: none !important
}
 
.google-src-active-text {
	display: block !important;
	color: black !important;
	font-size: 12px !important;
	font-family: arial, sans-serif !important
}
 
.google-src-active-text a {
	font-size: 12px !important
}
 
.google-src-active-text a:link {
	color: #00c !important;
	text-decoration: underline !important
}
 
.google-src-active-text a:visited {
	color: purple !important;
	text-decoration: underline !important
}
 
.google-src-active-text a:active {
	color: red !important;
	text-decoration: underline !important
}
</style>
<meta http-equiv="X-Translated-By" content="Google">
<base href=http://skipperkongen.dk/tmp/test.html />
</head>
<body>
<iframe
	src="http://translate.google.com/translate_un?hl=en&ie=UTF-8&sl=en&tl=da&u=http://skipperkongen.dk/tmp/test.html&prev=_t&rurl=translate.google.com&twu=1&lang=en&usg=ALkJrhhpCjCAYEWwbQX9TROT-522jGdGEw"
	width=0 height=0 frameborder=0
	style="width: 0px; height: 0px; border: 0px;"></iframe>
<h1><span onmouseover=
	_tipon(this);
onmouseout=
	_tipoff();
>
<span class="google-src-text" style="direction: ltr; text-align: left">Hello
world</span> Hej verden </span></h1>
<img src=world.jpg />
</body>
<script>
	_addload(function() {
		_setupIW();
		_csi('en', 'da', 'http://skipperkongen.dk/tmp/test.html');
	});
</script>
</html>

Leaving only the really important stuff:

1
2
3
4
5
6
7
8
<head>
	<script src="http://translate.googleusercontent.com/translate/static/biEfM_qFbxU/js/translate_c.js"></script>
	<base href=http://skipperkongen.dk/tmp/test.html />
</head>
<body>
	<h1>Hej verden</h1>
	<img src=world.jpg />
</body>

Two notable things have changed from the original. The head section has extra script tags and a base tag. The body section the phrase Hello World has been translated into danish.

Summary of modifications to original page

In summary Google translate has done the following to the original page:

  1. Added script tags
  2. Added a style tag
  3. Added a base tag
  4. Added an iframe tag
  5. Replaced content text with translated version
  6. Marked up content with some span tags, for a fancy tooltip

What does the script tags do?

This is the most complex part. I’m not done analysing this yet.

What does the style tag do?

This is simply to provide some styling of the fancy tooltip added with the span tags.

What does the iframe tag do?

In short I don’t know yet.

What does the base tag do?

The base tag is there to make sure that relative paths like the image path works, even if the HTML is loaded from a different domain than the original skipperkongen.dk domain.

This:

3
	<base href=http://skipperkongen.dk/tmp/test.html />

Makes this work:

7
	<img src="world.jpg" />

Would this work with AJAX?

Many pages use Ajax to load content. I’m expecting Google Translate to not work in this case, because of cross site scripting restrictions. In theory it could be done by creating a dynamic service proxy on the google domain, not taking authentication issues into account.

Let’s try with a page that replaces the header text with AJAX.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<html>
	<head>
	<script src="http://code.jquery.com/jquery-1.5.min.js" type="text/javascript"></script>
	<script type="text/javascript">
		$(function() {
			$.get('message.txt', function(data) {
				$('h1').text(data);	
				})
 
			})
	</script>
	</head>
	<body>
		<h1>...</h1>
	</body>
</html>

When loading via http://skipperkongen.dk/tmp/test2.html, the page look like this:

Hello World

When loading via Google Translate, the page looks like this:

...

So the conclusion is that Google does not do anything about data fetched via AJAX.

Building osm2pgsql on Mac OS X using homebrew

General instructions are here: http://wiki.openstreetmap.org/wiki/Osm2pgsql#Mac_OS_X

Note: I’m running Snow Leopard (10.6.6 )

1. Install homebrew

Check that you don’t have it already:

$ which brew

If you don’t have homebrew install it from here:

E.g. like this:

$ ruby -e "$(curl -fsSLk https://gist.github.com/raw/323731/install_homebrew.rb)"

2. Install proj

$ brew install proj
$ which proj
/usr/local/bin/proj

3. Install geos

$ brew install geos

4. Install osm2pgsql

First add pg_config to the path, then install osm2pgsql:

$ PATH=$PATH:/Library/PostgreSQL/9.0/bin/
$ brew install osm2pgsql
$ which osm2pgsql
/usr/local/bin/osm2pgsql

You should now have osm2pgsql installed.

Import OSM data into PostgreSQL

I did the following to import OSM data into PostgreSQL.

# create a user for the osm database
createuser -U postgres osm-user
# create the osm database
createdb -U postgres -E utf8 -O osm-user osm
# download som osm data from cloudmade.com, I chose Copenhagen, Denmark.
wget http://downloads.cloudmade.com/europe/northern_europe/denmark/copenhagen/copenhagen.osm.bz2
# unzip it
bzip2 -d copenhagen.osm.bz2
# install the mercator projection 900913 on the database
wget http://svn.openstreetmap.org/applications/utils/export/osm2pgsql/900913.sql
psql -U postgres -d osm -f 900913.sql
# install PostGIS on database
psql -U postgres -d osm -f /Library/PostgreSQL/9.0/share/postgresql/contrib/postgis.sql
# find the style to use with osm2pgsql 
brew list osm2pgsql # list locations installed by homebrew, including location of the default style
 
# Ready to import! use -s if you chose a large OSM dataset, this keeps RAM usage down.
# Use location of style file found with brew list osm2pgsql
osm2pgsql -d osm -U postgres -S /usr/local/Cellar/osm2pgsql/HEAD/share/osm2pgsql/default.style copenhagen.osm

You should now have some OSM data in your PostgreSQL database.

Using SQLite databases on different machines as a single virtual database

You can use separate SQLite database on different machines as a single virtual database by using the attach command in SQLite.

I read about the technique here: http://souptonuts.sourceforge.net/readme_sqlite_tutorial.html

For this example let’s use the simplest possible database. A contact database containing nothing but email addresses.

1. Create SQL script for a simple contacts database

File createcontacts.sql:

CREATE TABLE contacts (
id INTEGER PRIMARY KEY,
email VARCHAR(64));

2. Create two databases

Create the databases:

$ sqlite3 contacts1.db < createcontacts.sql
$ sqlite3 contacts2.db < createcontacts.sql

Notice: I'm using SQLite on Mac OS X, which comes preinstalled with /usr/bin/sqlite3.

Insert one contact in each database:

$ sqlite3 contacts1.db "insert into contacts (email) values ('john@example.com');"
$ sqlite3 contacts2.db "insert into contacts (email) values ('jane@example.com');"

The are now two databases, each with a row of data:

$ ls
contacts1.db	contacts1.sql	contacts2.db	contacts2.sql
$ sqlite3 contacts1.db 'select * from contacts;'
1|john@example.com
$ sqlite3 contacts2.db 'select * from contacts;'
1|jane@example.com

Next, we'll combine the databases using the SQLite command attach.

3. Create a single virtual database

First, enter the sqlite3 console:

$ sqlite3 
SQLite version 3.6.12
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> 

Then, attach the two databases:

sqlite> attach database 'contacts1.db' as c1;
sqlite> attach database 'contacts2.db' as c2;

Check that it went well with the .databases command:

sqlite> .databases
seq  name             file                                                      
---  ---------------  ----------------------------------------------------------
0    main                                                                       
2    c1               /Users/kostas/Documents/Dev/SqliteExp/attach/contacts1.db 
3    c2               /Users/kostas/Documents/Dev/SqliteExp/attach/contacts2.db 

Finally, select email addresses simultaneously from contacts1.db and contacts2.db:

sqlite> select 'c1',* from c1.contacts union select 'c2',* from c2.contacts;
c1|1|john@example.com
c1|2|janet@example.com
c1|3|joe@example.com
c2|1|jane@example.com

This demonstrates how one can select rows from multiple databases at once, using the attach command in SQLite. Imagine that the databases are actually on separate machines and accessed via e.g. NFS mounts.

Next, I'll look at spatial data in SQLite.

How to import OpenStreetMap data into PostgreSQL

1. Download data and software

The instructions are fairly generic, so should work for both Windows, Linux and Mac OS X. I wrote them for Windows, but I’ve since then switched to Mac OS X.

PostgreSQL+PostGIS

I assume that you do not already have Postgres/PostGIS installed on your system.

Download PostgreSQL+PostGIS for all platforms here: http://www.postgresql.org/download/

Follow the instructions provided to install the database software.

OSM data

Download OpenStreetMap data (.osm file):
downloads.cloudmade.com

I chose europe -> denmark.

osm2pgsql

Download the version for your platform (Windows, Linux, Mac OS X etc):
wiki.openstreetmap.org/wiki/Osm2pgsql

2. Create and prepare database

If you add the PostgreSQL bin folder to your path, you’ll have access to commands like createuser and createdb in your shell.

Create a user (after running command, answer ‘y’ to superuser):

createuser -U postgres <enter your username, I entered kostas>

Create the database (should be called ‘gis’):

createdb -U postgres -E UTF8 -O kostas gis

Install language plpgsql (on my system this was already installed):

createlang -U postgres plpgsql gis

Add PostGIS functionality to database (you should get pages of output as functions etc are created):

psql -U postgres -d gis -f PATH_TO_POSTGRES/share/contrib/postgis-1.5/postgis.sql

Download the file 900913.sql. The following will add spherical mercator projection to the database:

psql -U postgres -d gis -f PATH_TO_FILE/900913.sql

3. Add OSM data to database

Change directory to where you unzipped osm2pgsql:

cd PATH_TO_OSM2PGSQL

Import OSM data:

osm2pgsql -U postgres -s -S ./default.style PATH_TO_OSM_FILE/denmark.osm

Options for osm2pgsql:

  • -U postgres
    Run program with the PostgreSQL admin user
  • -s
    Run in “slim” mode, which means running the program not in RAM, which is necessary on my system
  • -S ./default.style
    On windows (maybe also Linux and other OS) you must specify path to style file. Use default which comes with osm2pgsql.

That’s it! You now have a database full of street data.

4. Testing the database

This is where I live:

select name, astext(way) from planet_osm_line where name='Anders Henriksens Gade'

Which gives the name of the road plus a WKT representation of the geometry:

Anders Henriksens Gade

LINESTRING(1402528.63 7491973.55,1402602.4 7491829.85)

Conclusion

It works, but tables are created in the ‘public’ schema of the ‘gis’ database. This is not so nice. I’d prefer that tables were created e.g. in ‘osm’ schema. When I’ve looked into how this is done, I’ll update this post.

I’d like to write a howto that uses Osmosis to continuously update the local OSM data with diffs from OSM.

SOLR with JSONP with JQUERY

Update: The previous version of this howto was a bit unclear or even erroneous, and some people had problems getting it to work. I have now rewritten it and testet it with SOLR 3.5.0 and jQuery 1.7.1.

Making SOLR return results suitable for consumption using JSONP is very easy!

Calling SOLR in JSONP style

Enter the following into your browser to see an example of how this works (change values for ‘yoursolrserver.com’ and ‘yoursearchgoeshere’):

  • http://yoursolrserver.com/solr/select/?q=yoursearchgoeshere&wt=json&json.wrf=callback

Looking at the structure of the JSON will give you an idea about how to process it in the following code.

The important two parameters in the URL are wt=json and json.wrf=callback. Of course callback can be anything (it’s just the name of the callback to call), so json.wrf=foo works as well. jQuery will autogenerate a name for you, so you don’t need to worry about it.

To perform the above call with jQuery in a JSONP style, use the following code snippet, and process the data result in the success function.

$.ajax({
  'url': 'http://yoursolrserver.com/solr/select',
  'data': {'wt':'json', 'q':'your search goes here'},
  'success': function(data) { /* process e.g. data.response.docs... */ },
  'dataType': 'jsonp',
  'jsonp': 'json.wrf'
});

Google fusion tables cheat sheet

See below for commands using the Fusion Tables API. Example table is the oldschool message wall public table. Note that examples are shown first without the required url-encoding.

Authenticating: Getting the auth token

To authenticate you may use the following test account myjdoe.

  • account: myjdoe@gmail.com
  • password: JoesSecret

Response:

SID=DQAAAHcAAAD90F7mQKULu7fY44z-maGyaTBElaKsaBvypHqU88b7mqVU93Lyf_1sr7ZbxSosjx2e6dT4LSOswAYG3fzAFVjQ-Z8VBS7-oloLNfNZF3A9qMhhI-cpDxoUe_3SUfdUsTfmk34a4wnkok4im77J-vBM5OqmMxLTE8JaDlylHgG2RA
LSID=DQAAAHoAAADkmXi_iKlUyVI_tuZ7n__6R9PkF3jIior9YnbO5a6lYFtNXxez2Ymw3sXbHKU48IwWhztVfDVUBF4UcCuH2rs3v6s5M1-duCG8gXaJph0oJByr3_Rj9olzm9Zlo5JKgcOiSNN38PY0jnONuuqR2G22KT-meIls05soufg8GEX-Xg
Auth=DQAAAHoAAAA3fDq7sZbeekb_x96Z7icle8VzWyucA50O2HnzUxbG_Y_PfaLfv5HmljUvNJoN1Owrgei796p-LGX-3l1KDRacWF_QhhSpAusdAVgSvxVlqrsJAc52Wu0CFb60_m19AwbbnLjd-CvIy-A-gwBI2Oi0O29lEU0qeL-JMOmiq_UtuQ

Auth is the token.

To make an authenticated POST request use the following header: Authorization: GoogleLogin auth=DQAAAHoAAA... which includes the token.

Query with SELECT

Querying data is done with HTTP GET and the SELECT command. Does not require authentication for public, exportable tables like the oldschool message wall public table.

Select all rows

http://www.google.com/fusiontables/api/query?sql=SELECT * FROM 380584

Try it.

Select rows with WHERE clause

http://www.google.com/fusiontables/api/query?sql=SELECT Message FROM 380584 WHERE User='Kostas'

Try it.

Select rows with spatial clause

http://www.google.com/fusiontables/api/query?sql=SELECT * FROM 380584 WHERE ST_INTERSECTS(Geo, CIRCLE(LATLNG(55.67892,12.58338),5000))

Try it.

Add data with INSERT

Adding rows of data is done with HTTP POST and the INSERT command. Requires authentication.

Notice we are using the token retrieved in the authentication step.

Response:

rowid
401

Get column names with DESCRIBE

Discovering column names is done with HTTP POST and the DESCRIBE command. Requires authentication.

Notice we are using the token retrieved in the authentication step.

Response:

column id,name,type
col0,User,string
col4,Message,string
col5,Geo,location

Client libraries by Google

To help create the API calls, you can use the client libraries developed and shared by Google instead of curl.

Libraries exist for the following languages:

Client libraries
Java gdata-java-client
Javascript gdata-javascript-client
.NET google-gdata
PHP Distributed as part of zend.
Python gdata-python-client
Objective C gdata-objectivec-client

How to load Javascript dependencies dynamically

Loading jQuery using plain Javascript::

// inject e.g. jQuery into a webpage
var thescript =  'http://code.jquery.com/jquery-latest.min.js';
var newscript = document.createElement( 'script' );
newscript.setAttribute( 'src', thescript );
newscript.setAttribute( 'type', 'text/javascript' );
var head = document.getElementsByTagName("head")[0];
head.appendChild(newscript);

To call this from your script with a test to see if jQuery is loaded:

// Test if jQuery is loaded 
if( typeof(jQuery) == 'undefined') 
{
  // code from previous listing
}

Turning big hard problems into smaller, less hard problems.

Here I have captured a thought process I had while reading about algorithms for hard graph problems. The thoughts are inspired by MapReduce, distributed merge sort and the more colorful newspapers of the world.

Summary of thoughts

Given an instance of an problem (think Max Clique, Traveling Salesman or another hard graph problem)…

Thought 1:

Compute an  instance that is “easier” but has the same optimal solution. This is done by a “reducer algorithm”.

Thought 2:

Reducer algorithms may run in parallel.

Thought 3:

Reducer algorithms may be different.

Thought 4:

Reducer algorithms can “gossip” with each other during execution. Gossip helps an algorithm by yielding new information about the problem being solved.

Thought 5:

Gossip is either a suboptimal solution or a reduced problem instance. This information can be used as a lower bound, or in other ways.

Thought 6:

“Merger algorithms” can combine problem instances from different reducer algorithms into one.

A full example of reducing and merging: Maximum Clique Problem.

Here is an instance of the Maximum Clique Problem, in this case a non-planar graph. By the way, planar graphs are boring because they can only contain cliques of size 4 or smaller.

graph
A graph that contains cliques of different sizes.

Let’s see what could happen when running two different reducers (reducer 1 and reducer 2) on this problem instance, and then merging the returned instances.

Reducer 1 works by randomly finding a clique in the graph, and repeatedly deleting nodes that have degree less than the size of the clique. The clique found is emitted as a gossip message (reducer 2 will use this as a lower bound).

Here is the result of running reducer 1:

Reduced instance
The red nodes is the clique found by reducer 1 and gossiped to reducer 2

Let’s look at reducer 2. While running reducer 2 could receive a gossip message from reducer 1, that a clique of size 4 has been found. Reducer 2 could use this as a lower bound. Reducer 2 targets nodes of degree around the lower bound. It works (slowly) be examining the targeted node to find out if it is part of a clique. If not it is deleted from the graph.

This could be the result of running reducer 2 (and accepting gossip from reducer 1):

Reducer 2 result
After getting a gossip that a 4-clique has been found, reducer 2 targets nodes with degree 4 and removes them if they are not in a clique.

In this madeup example reducer 1 managed to remove more nodes than reducer 2, but the point is that they removed different nodes.

Running the merger (computes the intersection) on the two reduces instances yields this:

Merged graphs
The result of merging the output of reducer 1 and reducer 2

Yay, an even smaller instance. But while we have the reducers up and running, we not restart reducer 1 with this instance as input! Let’s see what we get.

reducer 1 rerun
Feeding the reduced instance into reducer 1 for further reduction eliminates even more nodes

This look pretty good. This graph contains only 23 nodes, which is approximately half of the original graph, and that by discovering a relatively small clique of size 4 (compared to the big one of size 7).

Conclusion and a small disclaimer

Most people who deal with such problems call this sort of thing preprocessing. I call it a “reducer network”, mainly because it sounds cooler, but also because I think there might be a novel idea here. Namely running a host of algorithms in a distributed environment to perform the preprocessing while emitting and accepting gossip. Of course this is very similar to the ideas behind Google MapReduce and similar services, and might be exactly the same thing. I just felt the need to document my though process, and this post was created 🙂

This blog post is based on ideas and thoughts I had while reading “The Algorithm Design Manual” by Skiena (great book). The thougts are just that, thoughts.