Principles of Holism for sequential twig pattern matching
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Periodical |
| Magazine / Source | The VLDB Journal |
| MU Faculty or unit | |
| Citation | |
| Web | http://www.springerlink.com/content/ft6w531puk1xm611/ |
| Field | Informatics |
| Keywords | pattern matching; sequential processing; principles |
| Description | Modern applications face the challenge of dealing with structured and semi-structured data. They have to deal with complex objects, most of them presenting some kind of internal structure, which often forms a hierarchy. Though XML documents are the most known, chemical compounds, CAD drawings, web-sites and many other applications have to deal with similar problems. In such environments, ordered and unordered tree pattern matching are the fundamental search operations. One of the main thrusts of research activities for tree pattern matching is the class of holistic approaches. Their ultimate goal is to evaluate a query twig as a whole by relying on sequential access patterns and non trivial auxiliary storage structures, typically stored in main memory. Based on the pre/post-order ranks of individual tree nodes, we establish strong theoretical bases as a foundation for correct and efficient holistic pattern matching algorithms. |
| Related projects: |