First Research Paper

Hi all, Long time no content. Anyway, I've been fighting through my first quarter in grad school and all I have to show for it is a crummy research paper. Anyway, if you're interested, here's a link to it:

http://www.scribd.com/doc/8096612/CBIR-Research-Paper?secret_password=22uh3l6h29p36v34eg5l

It's on CBIR (Content Based Image Retrieval) or being able to search images based on image content, not needing image tags or other meta data.

Enjoy

Reducing the search space

For a class I'm taking, we're looking at Constraint Satisfaction Problems or CSPs. For a homework assignment we're looking at different methods of solving these CSPs. One way to do this is to create a tree of the possible variables in the CSP and at each level assign values. One obvious optimization is to reduce the assigned values at each level to only those that meet the constraints. According to the text this reduces the search space from n!*d^n to d^n where d is the size of the domain and n is the number of variables in the CSP.

As much as I'm interested in theory, practice is very helpful in explanation. One problem is the following:

  TWO
+ TWO
------
  FOUR

This is a crypt-arithmetic puzzle where a unique value is assigned to each letter, and no word can have leading 0's. To see this for myself I quickly implemented this in ruby to see the difference between constraining the search at each level and not. Results?

Unconstrained search (should be n!*d^n):

real 0m44.690s
user 0m42.769s
sys  0m0.315s

Constrained Search (should be reduced to d^n)

real 0m0.049s
user 0m0.037s
sys  0m0.005s

As you can see, a huge difference. Even though I fully understood the math, I was surprised how much of a difference it made by reducing the search space (even though it involved more checks at each level).

In summary... reduce

Had a really fun evening...

Had a really fun evening tonight and went to the George Eastman house and then to Charlie's Frog Pond

Powered by Jott

kitty.cat

wow... this is really cute.

source: http://kitty.cat/

Jott from www.jott.com....

Jott from www.jott.com. I believe it's my new best friend.

Powered by Jott

IPC

At work the other day I had to come up with a creative solution to a linking problem. I had a library from a 3rd party vendor that used one set of C++ libraries, and I had our code that used another set of C++ libraries. Unfortunately these libraries are incompatible with each other. This is because they both define the same (or at least some of the same) symbols. i.e. they both define std::string, std::cout, std::map and so on. The problem is that they do not have the same feature set (they can't be blindly interchanged) so we can't just recompile with the other library set and vice versa. 

Either way, my managers just wanted it done. They wanted us to use theses libraries, no matter what, A.S.A.P. The only way I knew of to compile anything with those shared libraries was to have another heavy weight process. This was surprisingly much easier than I originally imagined. 

My original intent was to develop our code as if we could use their library without any problems. Then, create functions that resolve all the symbols that are "missing" when I try to compile. These functions will use one form or another of IPC to make the function calls to the other heavy weight process to do what we originally intended. Here's an example of how I did it.

The main process defines all the missing symbols as functions with the exact same signature.
I define an enumerated type with the names (Almost) of all the functions that can be called.

enum messageNames { fun1, fun2, fun3 };

I define some shared data types (structures) that will be passed between the sender and receiver. These types will be based on the passed data types to be sent between the function calls. i.e. 

typedef struct _my_sending_data_ {
messageNames message;
char key[100];
int index;
float some_data[50];
...
} MySendingData;

Now, do the same thing for data that will be returned from the functions

typedef struct _my_receiving_data_ {
char value[100];
int error_code;
float ret_float;
...
} MyReceivingData;

Now, when we define these functions in the main program side, all we do is take the passed in parameters and fill a MySendingData structure with the values that need to be sent to the function. Also we fill in the message field with the name of the function that we are calling (using the enumerated type).

Finally we write this structure to the stream that we are using for IPC (pipe, socket, etc..) and then block on a read from the stream waiting to get back a MyReceivingData structure.

The other heavy weight process will be compiled with the real versions of these functions. That process just sits in a while loop, blocking on a read, waiting for a MySendingData typed block to appear in the stream. Then it does a switch on the data.message field to see what function was meant to be called. It then calls the message, with the parameters that are inside the sent data structure, fills a MyReceivingData structure with the return values and writes that across the IPC stream.

Of course there are some more details, but they are specific to the implementation. The basic idea was to be the simplest way to get past a shared library that wouldn't compile. This is not intended to be a long term way to do message passing over IPC, but works well given the application.

Probability of being right

Truth according to GraphJam

Individually Wrapped Lemon Slices

Just so that everyone knows, I am aware of the health risks associated with unwashed hands and how hands play a major part in spreading diseases, but sometimes too much is too much. See exhibit a:

Individually wrapped lemons slices.

I'm not even sure I want to know who's job it is to cut up lemons and then put what looks like a scrub cap on them one at a time.

Mind you, this was at the Riverside Convention Center

I was there for a Microsoft Launch Event (mostly for the free swag)

small bird

Phone Bunny

Last night we went for a walk and were able to get really close to a bunny near our townhouse. I didn't have a real camera, so I took a couple of pictures of him with my phone.

More bacon...

Oddly enough, another bacon related post:

Thank you xkcd

Monkey's and Bacon

Andy Inhatko has the greatest quote I've seen today. In blogging about the new iPhone SDK he mentions the following:

Monkeys are like bacon. They improve just about anything.

Here's the article:

http://ihnatko.com/index.php/2008/03/06/apples-special-iphone-press-eventmy-liveblog/

(yes, I like monkeys and bacon)