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

Date

2015-11-01

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.

Description

Keywords

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

Citation