Twig Pattern Search in XML Database
Metadata
Show full item recordAuthor
Zou, Leping
Date
2011-03-03Citation
Zou, Leping. Twig Pattern Search in XML Database; A thesis submitted to the Department of Applied Computer Science in conformity with the requirements for the degree of Master of Science, University of Winnipeg. Winnipeg, December 2010.
Abstract
For current search engine, we got results ranked by popularity. However, the most popular topics are not always I want. Millions people have millions different favors. So, the main challenge is how to dig the information up from the tremendous database of Internet according to different people's favor.
In computer science, "favor" is pattern. We call it "Twig Pattern Search". Unlike index methods that split a query into several sub-queries, and then stick the results together to provide the final answers, twig pattern search uses tree structures as the master unit of query to avoid expensive join operations.
We present an efficient algorithm for tree mapping problem in XML database. Given a target tree T and a pattern tree Q, the algorithm can find all the embeddings of Q in T in O (|D||Q|) time, where D is the largest data stream associated with a node of Q.