laziness, impatience, and hubris PerlMonks

### Re: Choosing a data structure for AI applications

by rjray (Chaplain)
 on Jul 16, 2002 at 06:20 UTC ( #182009=note: print w/ replies, xml ) Need Help??

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

Comment on Re: Choosing a data structure for AI applications
Replies are listed 'Best First'.
Re: Re: Choosing a data structure for AI applications
by Ovid (Cardinal) on Jul 16, 2002 at 16:01 UTC

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(|V2|)). 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.

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

Create A New User
Node Status?
node history
Node Type: note [id://182009]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (14)
As of 2015-08-31 18:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?