Efficient data search and synchronization for tree-structured data on mobile devices

We consider two methods about operating data for tree-structured data sets. The first method is to search particular data items and still retains all the important metadata information; the second method is to allow the data synchronization between two tree-structured files. Both of the methods are based on a special data structure we proposed, called Bloom Filter Tree. It is to compute a bloom filter for each interior node of the tree, essentially building a co-existing BF-tree to enhance the original data tree in order to allow more operations. Using the BF-tree, these two processes become faster by pruning out entire subtrees from being searched and precisely locate the parts we are looking for. Experiments are performed to verify the efficiency of each method. What’s more, we deploy the search method as an android application for practical purposes on mobile devices. We focus on a particular tree-structured dataset, DBLP, and select hundreds of records from it and enrich it as a neat XML file for parsing. With hundreds of records, more than 35,000 nodes in the tree structure, our method responds accurately and efficiently.

Name thesis:degree_name

Master of Science (MSc)

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Ontario Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Wang, Mengyu

Advisor dc:contributor.advisor

• Zhu, Ying

• Bloom filters
• Tree-structured data
• Data search
• Data synchronization
• Mobile devices

Language dc:language.iso

en

Handle dc:identifier.uri

https://hdl.handle.net/10155/605

OAI identifier oai:identifier

oai:ontariotechu.scholaris.ca:10155/605