18283115
Mining Maximal Frequently Changing Subtree Patterns from XML Documents
Due to the dynamic nature of online information, XML documents typically evolve over time. The change of the data values or structures of an XML document may exhibit some particular patterns. In this paper, we focus on the sequence of changes to the structures of an XML document to find out which subtrees in the XML structure frequently change together, which we call Frequently Changing Subtree Patterns (FCSP). In order to keep the discovered patterns more concise, we further define the problem of mining maximal FCSPs. An algorithm derived from the FP-growth is developed to mine the set of maximal FCSPs. Experiment results show that our algorithm is substantially faster than the naive algorithm and it scales well with respect to the size of the XML structure.
13928372
VRules: an effective association-based classifier for videos
Video classification is an important step towards multimedia understanding. Most state-of-the-art approaches which apply HMM to capture the temporal information of videos have the limitation by assuming that the current state of a video depends only on the immediate previous state. Nevertheless, this assumption may not hold for videos of various categories. In this paper, we present an effective video classifier which employs the association rule mining technique to discover the actual dependence relationship between video states. The discriminatory state transition patterns mined from different video categories are then used to perform classification. Besides capturing the association between states in the time space, we also capture the association between low-level features in spatial dimension to further distinguish the semantics of videos. Experimental results show that the performance of our association rule based classifier is quite promising.
6316461
Partitioned optimization algorithms for multiple sequence alignment
Multiple sequence alignment is an important and difficult problem in molecular biology and bioinformatics. In this paper, we propose a partitioning approach that significantly improves the solution time and quality by utilizing the locality structure of the problem. The algorithm solves the multiple sequence alignment in three stages. First, an automated and suboptimal partitioning strategy is used to divide the set of sequences into several subsections. Then a multiple sequence alignment algorithm based on ant colony optimization is used to align the sequences of each subsection. Finally, the alignment of original sequences can be obtained by assembling the result of each subsection. The ant colony algorithm is highly optimized in order to avoid local optimal traps and converge to global optimal efficiently. Experimental results show that the algorithm can significantly reduce the running time and improve the solution quality on large-scale multiple sequence alignment benchmarks.
1912999
Improving wireless link throughput via interleaved FEC
Wireless communication is inherently vulnerable to errors from the dynamic wireless environment. Link layer packets discarded due to these errors impose a serious limitation on the maximum achievable throughput in the wireless channel. To enhance the overall throughput of wireless communication, it is necessary to have a link layer transmission scheme that is robust to the errors intrinsic to the wireless channel. To this end, we present interleaved-forward error correction (I-FEC), a clever link layer coding scheme that protects link layer data against random and busty errors. We examine the level of data protection provided by I-FEC against other popular schemes. We also simulate I-FEC in Bluetooth, and compare the TCP throughput result with Bluetooth's integrated FEC coding feature. We show that I-FEC consistently and significantly outperforms other link layer coding schemes by providing an impressive amount of protection against heavy channel burst errors.
206977606
Priority Based Overlay Multicast for Distributed Interactive Applications
Distributed Interactive Applications (DIAs) is different with other network-based applications, since the data should be delivered to the receiver node according to its priority. Among the existing overlay multicast protocols the "priority-based directed minimum spanning tree" (PST) is designed for DIAs. But in PST the available bandwidth (avail-bw) is used inefficiently and the system becomes unstable when its scale increases. This paper proposed a novel overlay multicast protocol named Priority Based Overlay Multicast (POM), which uses the entities’ priority, links’ delay and node’s avail-bw to build multicast tree. By using POM the nodes with high priority receive the data in short delay, while the nodes with low priority tolerate a long delay in order to balance the available bandwidth usage among the nodes. The simulation results show that POM uses the avail-bw efficiently and keeps the system stable when its scale increases. Keywords: DIAs; Priority; Available bandwidth.
4775385
A fine-grained replacement strategy for XML query cache
Caching popular queries and reusing results of previously computed queries is one important query optimization technique, especially in modern distributed environments such as the WWW. Based on the recent proliferation of XML data and the emergence of the XQuery language, we are thus developing a query- based caching system for XQuery queries, called ACE-XQ. ACE-XQ applies innovative query containment and rewriting strategies to answer incoming user queries based on the cached XQueries, whenever possible, instead of accessing remote XML data sources.To manage the space of the cache, a straightforward application of traditional replacement strategies would correspond to removing a complete cached query and its derived XML document as a whole when space needs to be freed. This coarse granularity however does not match well with the typical access pattern of web searches where new queries often partially overlap with cached queries.In this paper, we propose a novel replacement strategy appropriate for such query-based XML caching systems. In particular, we collect user access statistics at the granularity of the XML path structure instead of the complete XML query regions. We then apply a more fine-grained replacement strategy that purges XML fragments off a cached region instead of the whole XML document and accordingly adjusts the query descriptor. This may better capture the user access patterns since more frequently used XML document fragments are likely to remain in the cache while other less beneficial parts are purged. This approach has been implemented in our ACE-XQ System. Preliminary experiment results illustrate the performance improvement achievable by our fine-grained replacement strategy over the one which replaces a whole XML view at a time when the cache size is relatively large.
335267
VLSI implementation of shape-adaptive discrete wavelet transform
In this paper, several VLSI architectures and implementations of Shape-Adaptive Discrete Wavelet Transform (SA-DWT) with odd symmetric biorthogonal filters are presented. The hardware implementation issues of SA-DWT algorithm are first addressed, and one lifting scheme together with some appropriate shape information processing units is introduced for the 1-D SA-DWT architectures. These architectures can efficiently perform 1-D length-adaptive DWT on continuous line segments and solve the corresponding boundary extension and subsampling problems without any overhead. In addition to 1-D architectures, two 2-D SA-DWT architectures are also proposed. One is the direct method, which uses the 1-D SA-DWT architectures as basis to extend to 2-D SA-DWT by direct row-column approach. The other is the line-based method, which is an efficient and feasible architecture that uses internal line buffers rather than external frame memory. These two 2-D SA-DWT architectures are both VLSI implemented by using cell-based chip design flow. The Daubechies (9,7) filter is used for the implementation by direct method, and the Daubechies (9,3) filter is used for the line-based implementation. The proposed architectures can be applied both in arbitrarily shaped visual objects coding such as MPEG-4 still texture coding and rectangular region image coding such as JPEG2000 still image coding.