I also have thought some on data structures for AI applications, which is why I'm here, reading your post.
I think that humans are incredibly self-referential. for instance, we frequently use terms like 'My car', 'My house', etc... even when we are newly born, it's 'this is how I get nourishment'.
Personally, I'm looking for a data structure that allows n links to a datum that has n links to other datum, where n is an arbitrarily large number. Think of dictionary, in which every word of every definition is linked to the definition of that word.
Oh, I know some would say that's an excess that can't be sustained, but for true intelligence, it's a MUST. consider, for a moment The Fed-X box on the corner of my desk. It's a cube ( What's a cube?) it's interior and exterior dimensions have size (what's interior, exterior?) there's an unknown object inside it ( does interior have the same meaning, in this context, as 'inside'?). And I haven't even looked at surface properties, printed text, closure methods or dimensions.
And this proposed data structure should be able to handle contextual linkages, as well. For instance the phrase 'I feel boxed in' is certainly not refering to the above mentioned Fed-X container.
I also know, that such a data structure, once populated would be arbitrarily large, and the linkages between data might occupy more storage space than the data that's being linked.
I can justify the data structure mentioned above any number of ways. Yet, I feel that such a data structure is required to make a mere program truly intelligent.