Algorithms for searching through an XML stream

I'm looking for suggestions on algorithms / techniques for breadth first searching through an a streaming XML document.

<foo>
   <bar name="aaa" >
       <grah name="aab" />
        ..
   </bar>
   <bar name="bbb" />
   <bar name="ccc" />
   <bar name="ddd" />
   <bar name="eee" />
... up to 10,000 entries
</foo>

The number of 1st level elements is out of my control. The use of xml is also out of my control. I can pre-process the xml, i can index the xml but i can not (for the forseeable future) load the entire xml document into memory on a per request basis.

I'm currently searching sequentially using libxml's stream reading capability to perform this task. It consumes a more or less fixed amount of RAM / request and is very responsive generally for anything less than 3k rows, and caching the most popu开发者_如何学运维lar results helps but almost every top level element is hit at some stage.

Recently we have had to deal with a number of really large files where the level 1 elements have been up to 10,000 elements in size and a match closer to the end is unacceptable in regards to server response.

So far I've seen Introselect and Quickselect which may reduce the search space, to something reasonable. I thought i would see if there any other ideas or algorithms which I have overlooked before I started to write some code.

You don't explain in detail what the search requirements are or what the text that will be searched looks like. I assume the XML in itself isn't of interest and that the stream parsing you're doing with libxml can be made to continually build objects where the data from the XML has been refined and made more easily searchable.

You can of course just jam the XML document into an XML database like eXist. That is very flexible if you want to preserve the original XML, but if you can throw that away, I would look for other means of storing just the essence of the XML document; the data that is to be searched for.

Since you write that the XML can be pre-processes, I also assume that the XML doesn't change very often. If these assumptions are correct, you can index the text you want to be searched in a search-focused database like Lucene. You can of course create the search algorithm yourself, but since there are open source solutions that does this (with query caching and whatnot in place), I recommend you to look at some of the existing solutions.

If the searches themselves don't vary much, you can also create JSON objects from the data in the XML and store them in a document database (like MongoDB or CouchDB) with pre-defined indexes that pretty much contains the answer to the searches you want to perform in-memory.

Which solution you should go for is a bit difficult to give any clear recommendations on since I don't know all of your requirements, but these are at least some ideas you can explore.