A Time/Space Efficient XML Filtering System for Mobile Environment

Existing XML filtering approaches suffer from excessive overheads incurred in matching time and the storage/memory space needed during the matching process. This makes them unsuitable in mobile computing environment, where computing resources are extremely scarce. Hence there is a need to formulate a filtering mechanism that optimizes the computation and space constraints in performing XML filtering across a distributed environment. In our experiments, we found that the time imposed on parsing is a dominant factor of the total matching time cost, and the space needed is largely dependent on the structural representation. Motivated by these insights, we developed a highly compact structure representation using bloom filter, which also provides an easy solution for separation of the parsing process from the matching process so as to relief the burden of parsing from the matching. In general, our proposed method includes a preprocessing component, where the incoming documents/subscriptions are parsed and fed into the bloom-filter creator, and a matching component, where the bloom-filter will be used for evaluation. Experiments show that, by our approach, the matching time is significantly reduced due to the separation of parsing and matching, and the space for indexing structure is tremendously reduced due to the compactness of bloom filter. Although the bloom filter introduced false positive errors in the matching results, it can be controlled to a selectable and reasonable range. Importantly, considering the significant speedup and performance gain, our approach represents a viable solution when time/space efficiency is paramount.