Encoding semi-structured data for efficient search and browsing

1. A method for transforming an XML data input to enable search over the XML data input or components thereof, the method comprising:

a. transforming said XML data input into a logical tree in which tags or attributes of said XML data input are nodes of the logical tree, each of said nodes representing non-structural or structural information from said XML data input;

b. labeling each of said nodes of said logical tree with tokens from a token table, the token table including tokens and matching tags or attributes being tags or attributes of said XML data input, thereby obtaining labeled nodes; and

c. creating an index from said tokens to facilitate efficient search of data in said logical tree, said index representing paths of labeled nodes in said logical tree whereas the indexing process includes transforming said paths into keys to be indexed, the keys being indexed being strings of arbitrary length that each includes both: non-structural and structural information from said XML data input,

wherein one portion of the key comprising of tokens representing structural information and second portion of the key comprising non-structural information,

wherein the structural information is a representation of the structural markup and attributes of said XML data input, and the non-structural information represents content from the XML data input.

2. The method of claim 1 , wherein said index represents the structural information, said structural information being the relationships between data items, the relationships between data items consisting of parent-child or sibling relationship.

3. The method of claim 1 , wherein said index is a designated index.

4. The method of claim 1 , wherein said index is a layered index.

5. The method of claim 1 , wherein said index is based on a Patricia Trie.