Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: Re: Choosing a data structure for AI applications

by Ovid (Cardinal)
on Jul 16, 2002 at 16:01 UTC ( #182128=note: print w/ replies, xml ) Need Help??


in reply to Re: Choosing a data structure for AI applications
in thread Choosing a data structure for AI applications

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.


Comment on Re: Re: Choosing a data structure for AI applications
Re: Re: Re: Choosing a data structure for AI applications
by rjray (Chaplain) on Jul 17, 2002 at 09:41 UTC

    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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://182128]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (10)
As of 2014-10-01 21:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (38 votes), past polls