My first suggestion: you could give modperl a try.
With modperl you are able to parse the xml file once, when apache starts up,
and store the results in a persistent data structure,
accessible to all threads/processes which handle the cgi requests.

If that's not what you are looking for,
There would also be the possiblity of using a xml database.

some readings..
http://www.xml.com/pub/a/2000/12/13/perlxmldb.html,
http://www.xml.com/pub/a/2003/05/07/bdb.html