Name
Abstract | ||
|---|---|---|
We consider two problems in the context of tree-structured data sets (e.g., XML): (1) searching for a data element, (2) synchronizing two data trees (replicas) stored at remote locations. We propose to compute bloom filters for the interior tree nodes, this bloom filter tree is used for both data search and synchronization. It is more efficient than tree traversal since it prunes out entire subtrees, while still retaining the important metadata (in the interior nodes) that cannot be achieved by any linear list search of leaf nodes. We present a theroetical analysis of the search complexity of selective placement of bloom filters in the tree leading to an optimal placement strategy. We implement the classic rsync algorithm for comparison and verify the efficiency of our method in terms of lower network overhead and faster runtime. We also implement our bloom filter search method as an Android application on the mobile device, tested its performance on the real DBLP data set and verified its efficiency. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/IRI.2016.60 | 2016 IEEE 17th International Conference on Information Reuse and Integration (IRI) |
Keywords | Field | DocType |
data search,data synchronization,tree-structured data,mobile device | Data mining,Bloom filter,Metadata,Synchronization,Data set,Tree traversal,XML,Computer science,Data element,Search tree | Conference |
ISBN | Citations | PageRank |
978-1-5090-3208-2 | 0 | 0.34 |
References | Authors | |
13 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mengyu Wang | 1 | 0 | 0.34 |
| Ying Zhu | 2 | 0 | 0.34 |