Archive for October, 2008

Easy Green PC

Tuesday, October 28th, 2008

My former roommate had the idea a few months ago to build a ‘green’ PC, which would be very low power, easy for anyone to use for things such as email and office applications, and (of course, the clincher) cheap. So he went ahead and did it… it worked out quite well. Its a shiny lil box, actually. The performance isn’t that bad either, and it is in fact power efficient.

Its running Ubuntu on it (of course, its supposed to be cheap!), and he mentioned some plans to research patches and tweaks to make the Linux kernel more power efficient, and include other peoples power-related patches and such in there as well.

Anyways, visit his site, it doesn’t have a whole lot of content there yet but he was planning on adding some more…

Power efficient ‘green’ linux-based PC

Best Election Twist *ever*

Monday, October 27th, 2008

Best election twist *ever*:

Wargames III: The Obama Code: The mysterious hacking of Joe the Plumber’s motor vehicle records was America’s only warning of Barack Obama’s secret past as “The0n3,” a founding member of the 1980’s hacker group Legion of Doom. Once in office, Obama reassembles the now-middle-aged cyberpunk gang for “the l33test Cabinet ever,” and new defense secretary “NinjaBoy” promptly declares cyberwar on China, Russia and, oddly, Canada (“I always hated that poser Mafiaboy.”) Cyber Armageddon seems inevitable until rival hackers from MOD change all the White House phone lines into pay phones. (by Threat Level)

R* Tree Implementation for C++

Saturday, October 4th, 2008

So a few weeks ago I finished preliminary work on an R* Tree implementation in C++. My goal for this implementation is as follows:

  • Simple API – Most existing implementations I’ve seen are far from simple
  • Generic enough to use with most types, with low overhead
  • N dimensions for bounding boxes
  • Easy to integrate and use for Roadnav
  • Take advantage of modern C++ features to get decent performance

This is a header-only implementation of an R tree with an R* index, and makes heavy use of templates, STL, and STL-style functors; but it should work in any relatively modern C++ compiler. To do searching for nodes, this implementation uses the Visitor pattern via functors — there are examples and documentation in RStarVisitor.h.

If you use this, *please* let me know, I’m very interested to see what bugs may come up, and possible performance problems. Unfortunately, I haven’t gotten around to writing any comprehensive tests for it (but given the tests I’ve run so far, I’m reasonably sure the implementation is mostly correct), but I expect that once I get it integrated into Roadnav that this will follow shortly after. Also, integration of the R* tree into Roadnav will make a lot of potential errors pop out. Look for this in the near future.

Additionally, I am thinking about some of the following ideas too:

  • Adding the ability to work with extra-large datasets by saving/loading to/from disk (after all, that is the point of R trees…)
  • Adding a bulk insert function — there is pseudocode already for this, but I haven’t actually written an implementation for this yet. Also, a more efficient bulk delete function
  • Trying to implement it as a Boost intrusive container. I’ve been playing with some Boost stuff lately at work, and theres a lot of neat things there.

I’ll also use this opportunity to put in a plug for Roadnav — if you’re looking to work on an open source project, theres a bunch of (mostly) interesting stuff that I’m working on/planning for Roadnav. What I’m working on right now is totally removing US-specific stuff from Roadnav, and moving to an OpenStreetMap-only implementation. Theres a number of features that are getting thrown away, but I think that the dynamic community that OSM opens up to Roadnav will be well worth it.

Note: I’ve updated this quite a bit (though, remove functionality has been removed and it no longer uses the visitor pattern for data access), and its currently a part of libsdbx. Libsdbx can be found in Roadnav SVN at https://roadnav.svn.sourceforge.net/svnroot/roadnav/libsdbx/trunk/. I’ll write about this soon.. but its pretty neat. It supports R* and modified B+ trees, in memory or on disk. Check it out.

Note II: I’ve pushed the source code to github at https://github.com/virtuald/r-star-tree

Download the sourcecode here