Re: Choosing a data structure for AI applications

[rjray]

This isn't a fully-thought-out, comprehensive solution, but rather something that occurred to me while reading your examples. So there may be better arguments for or against this approach...

What strikes me most about the predicates you describe is that they seem to lend themselves to a matrix-like structure. Granted, in your examples you are using names/strings rather than numbers, but that is a minor detail, comparitively speaking. If you can handle converting queries to and from matrix indices (or vector extractions, or vector operations, etc.) then you may find that PDL may be a great boon to your efforts. As an added plus, it handles sparse matrices, which I seem to remember being a key implementation component of matrix-based AI.

But it's been 13 years since I took an AI class, or even really read up on the topic. This is just a thought.

--rjray

[Ovid]

I don't claim to understand matrices very well, but they seem like a bad solution for this. My understanding is that a matrix will require two bits per connection between two vertices (O(|V²|)). That's for all possible connections. If I have a modest size database of 20,000 facts with an average of 5 vertices per fact, that's 100,000 bits squared. That works out to around 1192 megs of data to store the matrix. If the number of edges (|E|) is extremely large, than matrices start being more attractive, but I suspect that graph representations of AI systems are going to be rather sparse (someone feel free to contradict me on this) which suggests that adjacency lists are preferable).

If I go with adjacency lists, the memory consumption is O(|V|+|E|). This will scale much better.

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

[rjray]

This is why I made reference to PDL's support of sparse matrices. The in-memory storage is much more manageable, while still being able to do all the other operations you need.

--rjray