Efficient evaluation of XML queries entails fast finding all the occurrences of a twig pattern, a subgraph of treestructured XML documents. One approach models the pattern as a query tree directly, and associates a cursor and a stack to each tree node for coordinated sequential access and partial match tally of all the XML elements. Even if pre-built indices on the elements can facilitate skipping mismatches, this approach works well only when the pattern purely involves ancestor-descendent edges. Another strategy first transforms XML data and query trees one-to-one into sequences. Then, string indices are used for subsequence matching to achieve equivalent skips in transform domain. This strategy performs better when the twig contains ordered parent-child edges and nodes with their own selection predicates. This paper proposes to replace the stacks used in the first approach by simple pipes (double-ended queues) to queue too inner entries of index trees accessed by level-order traversal. Our design permits the cross-verification among queued entries subject to the twig pattern. Early filtration at the inner level of index trees is thus achievable to further expedite processing. Joint with the leaf entries having full specifications of query elements, our design can also suppress any subgraph that violates parent-child edges and selection predicates at query tree nodes. Intensive experimental results also demonstrate such superiority over the second strategy.

Digital pollution is emerging as an overwhelming threat to the Internet, whose ubiquitous connectivity conversely cultivates the widespread outbreaks of such dirt. Considerable amount of human efforts and network resources are wasted at a little cost of the few polluters. To prevent flooding of the contamination, classical string matching schemes and their variants can be used to detect these patterns for removal. The speed of detection is crucial to this application. In this paper, we propose a novel pattern detection technique based on the decision tree induction to seek for significant improvement over the classical schemes. According to the intrinsic of the pattern, the tree is sprouted adaptively to minimize the number of symbols in the data stream needs to be examined. This allows a unique order to inspect the symbols in a strategic way optimized contextually, as opposed to the fixed order followed by the other schemes. Performance study indicates our approach achieves the speed-up of five or more over the best competitors.

Efficient similarity search in large string databases requires effective index support. Since long strings have each numerous substrings of arbitrary length, the effective index designs are of great challenge. The existing solution, namely MRS [T. Kahveci et al., (2001)], employs a low-cost lower bound function to sieve out the most similar candidates from the majority of unlikely database substrings. Therefore, only very small portions of string databases require the expensive true edit distance computation to finalize the query. A significant savings in overall query processing cost can be realized by the filtration feature of lower bound functions. In this paper, we seek to improve MRS to its full potential. Specifically, we propose a very simple method that exchanges the roles of database strings and query string in the original MRS design. Despite simplicity, our solution can further improve the query performance by 10 times in terms of disk page accesses while using only half of the original index's size.

Video-cassette-recorder-like (VCR) capabilities such as jumping to a specific frame or fast forwarding a video are becoming essential services in video-on-demand (VOD) applications. To provide VCR functionalities in a broadcast environment, current techniques depend on data prefetching. However, a fast-forward or a fast-backward of a video for several seconds would certainly exhaust the prefetch buffer because the prefetching rate cannot sustain typical speeds. In this paper we address this practical problem where each video and its interactive version are broadcast repeatedly on the network. For example, interactive versions might contain only every fifth frame in the original videos. We propose a new technique that leverages these "interactive" broadcasts to provide better VCR service.

Various approaches have been proposed to discover patterns from system call trails of UNIX processes to better model application behavior. However, these techniques only consider the relationship between system calls (or system audit events). We first refine the definition of maximal patterns given in (Wespi et al., 2000) and provide a pattern extraction algorithm to identify such maximal patterns. We then add one additional dimension to the problem domain by also taking into consideration the overlap relationship between patterns. We argue that an execution path of an application is usually not an arbitrary combination of various patterns; but rather, they overlap each other in some specific order. Such overlap relationship characterizes the normal behavior of the application. Finally, a novel pattern matching module is proposed to detect intrusions based on both intra-pattern and inter-pattern anomalies. We test this idea using the data sets obtained from the University of New Mexico. The experimental results indicate that our scheme detects significantly more anomalies than the scheme presented in (Wespi et al., 2000) while maintaining a very low false alarm rate.

In video-on-demand (VOD) applications, it is desirable to provide the user with the video-cassette-recorder-like (VCR) capabilities such as fast-forwarding a video or jumping to a specific frame. We address this issue in the broadcast framework, where each video is broadcast repeatedly on the network. Existing techniques rely on data prefetching as the mechanism to provide this functionality. This approach provides limited usability since the prefetching rate cannot keep up with typical fast-forward speeds. Fast-forwarding a video for several seconds would inevitably exhaust the prefetch buffer. We address this practical problem in this paper by repeatedly broadcasting the interactive versions of the videos. For instance, an interactive version might contain only every fifth frame in the original video. Our client software leverages these "interactive" broadcasts to provide better VCR service. We formally prove the correctness of this approach, and compare its performance to a prefetch method, called active buffer management. This scheme has been shown to offer, in the broadcast environment, the best performance to date. Our simulation results indicate that the new technique is superior in handling long-duration VCR actions.

Several periodic broadcasting schemes have been shown to be very effective in addressing the bandwidth limitation in multimedia servers. Since this approach allows many users to share a server stream, its bandwidth requirement is independent of the number of users the system is designed to support. Existing broadcasting schemes use two or less download channels at the client end to receive data. We discuss the drawbacks of this approach, and propose a new technique which allows a video session to download data through several client channels. The number of channels which can be used simultaneously is limited only by the communication capability of the client system. We prove the correctness of this client-centric approach, and provide analytical evaluations to show that it has significantly better performance than skyscraper broadcasting technique which has been shown to offer the best performance to date.

Until now, true video-on-demand can only be achieved using a dedicated data flow for each sen-ice request. This brute- force approach is prohibitively expensive. Using multicast can significantly reduce the system cost. This solution, however, must delay services in order to serve many requests as a batch. In this paper, we consider a third alternative called Patching. In our technique, an existing multicast can expand dynamically to serve new clients. Allowing new clients to join an existing multicast improves the efficiency of the multicast. Furthermore, since all requests can be served im-mediately, the clients experience no service delay and true video-on-demand can be achieved. A significant contribution of this work, is making multicast work for true video- on-demand services. In feet, we are able to eliminate the service latency and improve the efficiency of multicast at the same time. To assess the benefit of this scheme, we perform simulations to compare its performance with that of standard multicast. Our simulation results indicate convincingly that- Patching offers substantially better performance. © 1998 ACM.

The two main operating constraints of today's multimedia servers are the I/O bandwidth and communication bandwidth limitations. Both of these problems are addressed in this paper using a novel technique called Earthworm. In this scheme, the network memory is used as a huge cache for buffering multimedia data. Dramatic reduction in the demand on the I/O bandwidth, therefore, can be achieved. This scheme also chains display stations to allow them to forward video streams. This strategy eliminates the congestion at the communication port of the server. Removing this bottleneck allows our technique to operate on the vast aggregate bandwidth of the WAN rather than being constrained by the very limited local bandwidth available to the server. A unique feature of the Earthworm approach is that every display station using the server attempts to make some contribution to the caching space and communication bandwidth. The arrival of a new request, therefore, can be seen as a contributor, rather than just a burden to the server. This characteristic ensures the scalability of our design to support very large multimedia applications.

We present a technique, called bidirectional highly optimized pipelining (BiHOP), for managing disks as a buffer for the tertiary storage of a multimedia server. We implement a simulator to compare its performance to that of a recently proposed scheme called SEP. The results show that BiHOP performs significantly better. Its superior performance is attributed to a novel caching approach, which caches every other data fragment of the multimedia file, rather than caches consecutive fragments as in traditional practice. This new approach allows us to use tiny staging buffers for pipelining, which can be implemented in the memory to conserve disk bandwidth. Furthermore, the whole disk space can be dedicated for caching purposes to improve hit ratio. Another important advantage of BiHOP is its ability to pipeline in either forward or reverse direction with the same efficiency. This unique feature, not possible with existing schemes, makes it natural for implementing VCR functions.

We investigate a novel multicast technique, called Skyscraper Broadcasting (SB), for video-on-demand applications. We discuss the data fragmentation technique, the broadcasting strategy, and the client design. We also show the correctness of our technique, and derive mathematical equations to analyze its storage requirement. To assess its performance, we compare it to the latest designs known as Pyramid Broadcasting (PB) and Permutation-Based Pyramid Broadcasting (PPB). Our study indicates that PB offers excellent access latency. However, it requires very large storage space and disk bandwidth at the receiving end. PPB is able to address these problems. However, this is accomplished at the expense of a larger access latency and more complex synchronization. With SB, we are able to achieve the low latency of PB while using only 20% of the buffer space required by PPB.