People locations bring rich information for a wide spectrum of applications in intelligent video surveillance systems. In addition to localization accuracy, computational efficiency is another significant issue to be highly concerned in people localization. As an essential early stage, people localization has to be accomplished in a very short time, enabling further semantic analysis. However, most state-of-the-art people localization methods pay little attention to computational efficiency. Hence, in this paper we propose an effective and efficient multi-view people localization scheme with several acceleration mechanisms. First, a torso-high reference plane is introduced since in general the torso part (after foreground segmentation) is more intact and stable than the other parts of a human body, and thus can predict potential people locations more reliably. Then, a novel and computationally efficient bitwise-operation scheme is proposed to predict people locations at the intersection regions of foreground line samples from multiple views. After rule-based validation, people locations can be accurately obtained and visualized on a real world plane. Experiments on multi-view surveillance videos not only validate the high accuracy of the proposed method in locating people under crowded scenes with serious occlusions, but also demonstrate an outstanding computational speed.

Traditional video annotation approaches focus on annotating keyframes/shots or whole videos with semantic keywords. However, the extraction processes of keyframes/shots might lack semantic meanings, and it is hard to use a few keywords to describe the content of a long video with multiple topics. In this work, near-scenes, which contain similar concepts, topics, or semantic meanings, are designed for better video content understanding and annotation. We propose a novel framework of hierarchical video-to-near-scene annotation not only to preserve but also to purify the semantic meanings of near-scenes. To detect near-scenes, a pattern-based prefix tree is first constructed to fast retrieve near-duplicate videos. Then, the videos containing similar near-duplicate segments and similar keywords are clustered with consideration of multimodal features including visual and textual features. To enhance the precision of near-scene detection, a pattern-to-intensity-mark (PIM) method is proposed to perform precise frame-level near-duplicate segment alignment. For each near-scene, a video-to-concept distribution model is designed to analyze the representativeness of keywords and discriminations of clusters by the proposed potential term frequency and inverse document frequency and entropy. Tags are ranked according to video-to-concept distribution scores, and the tags with the highest scores are propagated to near-scenes detected. Extensive experiments demonstrate that the proposed PIM outperforms state-of-the-art approaches compared in terms of quality segments and quality frames for near-scene detection. Furthermore, the proposed framework of hierarchical video-to-near-scene annotation can achieve high quality of near-scene annotation in terms of mean average precision.

Sequential pattern mining is an important subfield in data mining. Recently, discovering patterns from interval events has attracted considerable efforts due to its widespread applications. However, due to the complex relation between two intervals, mining interval-based sequences efficiently is a challenging issue. In this paper, we develop a novel algorithm, P-TPMiner, to efficiently discover two types of interval-based sequential patterns. Some pruning techniques are proposed to further reduce the search space of the mining process. Experimental studies show that proposed algorithm is efficient and scalable. Furthermore, we apply proposed method to real datasets to demonstrate the practicability of discussed patterns.

Since a proficient golf swing is a key element in success in golf, golfers always make much effort in improving their swing skills. However, if not under the supervision of a coach, a golfer cannot effectively perceive his/her faults in swings and comprehend how to change the swing mechanics. In this paper, we propose a vision-based golf training system, named "Improve My Golf Swing," which aims at improving the golfer's swing skills using intelligent glasses serving as a wearable displayer. The golfer's posture is analyzed through computation-efficient image processing techniques. Involving professional golf training knowledge, the proposed system automatically generates feature lines to evaluate whether the golfer's body is properly aligned. During a swing, the golfer can watch his/her own posture as well as the augmented feature lines displayed on the intelligent glasses. Instead of quantitative swing analysis, we focus on providing instructions of posture adjustment to the golfer in a more intuitive and unambiguous manner. Different audio alerts will be given to the golfer according to which part of a posture fault is detected. Experiments on different golf swing videos show encouraging results.

Sequential pattern mining is an important subfield in data mining. Recently, applications using time interval-based event data have attracted considerable efforts in discovering patterns from events that persist for some duration. Since the relationship between two intervals is intrinsically complex, how to effectively and efficiently mine interval-based sequences is a challenging issue. In this paper, two novel representations, endpoint representation and endtime representation, are proposed to simplify the processing of complex relationships among event intervals. Based on the proposed representations, three types of interval-based patterns: temporal pattern, occurrence-probabilistic temporal pattern, and duration-probabilistic temporal pattern, are defined. In addition, we develop two novel algorithms, Temporal Pattern Miner (TPMiner) and Probabilistic Temporal Pattern Miner (P-TPMiner), to discover three types of interval-based sequential patterns. We also propose three pruning techniques to further reduce the search space of the mining process. Experimental studies show that both algorithms are able to find three types of patterns efficiently. Furthermore, we apply proposed algorithms to real datasets to demonstrate the effectiveness and validate the practicability of proposed patterns.

With the exponential growth of web multimedia contents, the Internet is rife with near-duplicate videos, the video copies applied with visual/temporal transformations and/or post productions. Two critical issues, copyright infringement and search result redundancy, arise accordingly. To resolve these problems, this paper proposes a spatiotemporal pattern-based approach under the hierarchical filter-and-refine framework for efficient and effective near-duplicate video retrieval and localization . Firstly, non-near-duplicate videos are fast filtered out through a computationally efficient data structure, termed pattern -based index tree (PI-tree). Then, an m- pattern -based dynamic programming (mPDP) algorithm is designed to localize near-duplicate segments and to re-rank the videos retrieved. The influence of time shift misalignment can be alleviated by time-shift m-pattern similarity (TPS) measurement. Comprehensive experiments on the five datasets are conducted to verify the effectiveness, efficiency, robustness, and scalability of the proposed approach. Convincing results demonstrate that our proposed approach outperforms the state-of-the-art approaches in terms of mean average precision (MAP) and normalized detection cost rate (NDCR) on the testing datasets. Furthermore, the proposed approach can achieve high quality of near-duplicate video localization in terms of quality frames (QF) and mean F1.

In several applications, sequence databases generally update incrementally with time. Obviously, it is impractical and inefficient to re-mine sequential patterns from scratch every time a number of new sequences are added into the database. Some recent studies have focused on mining sequential patterns in an incremental manner; however, most of them only considered patterns extracted from time point-based data. In this paper, we proposed an efficient algorithm, Inc_TPMiner, to incrementally mine sequential patterns from interval-based data. We also employ some optimization techniques to reduce the search space effectively. The experimental results indicate that Inc_TPMiner is efficient in execution time and possesses scalability. Finally, we show the practicability of incremental mining of interval-based sequential patterns on real datasets.

With the explosive growth of the social multimedia sharing, copyright protection and search result refinement are always the critical issues for the service operators. To resolve the problems, content-based near-duplicate video retrieval is developed in recent years. In this paper, we construct a condensed Pattern-based Prefix tree (PP-tree) to index the patterns of reference videos for fast retrieval. To calculate how likely a query video and a reference video are near-duplicates, a novel algorithm for discovering the temporal relations among patterns is proposed. Comprehensive experiments on public datasets are conducted to verify the effectiveness and efficiency of the proposed method. Experimental results show that the proposed near-duplicate video retrieval approach outperforms the state-of-the-art approaches in terms of precision, recall, and execution time.

Advanced vehicle safety is a recently emerging issue, appealed from the rapidly explosive population of car owners. Increasing driver assistance systems have been designed for warning drivers of what should be noticed by analyzing surrounding environments with sensors and/or cameras. As one of the hazard road conditions, road bumps not only damage vehicles but also cause serious danger, especially at night or under poor lighting conditions. In this paper we propose a vision-based road bump detection system using a front-mounted car camcorder, which tends to be widespread deployed. First, the input video is transformed into a time-sliced image, which is a condensed video representation. Consequently, we estimate the vertical motion of the vehicle based on the time-sliced image and infer the existence of road bumps. Once a bump is detected, the location fix obtained from GPS is reported to a central server, so that the other vehicles can receive warnings when approaching the detected bumpy regions. Encouraging experimental results show that the proposed system can detect road bumps efficiently and effectively. It can be expected that traffic security will be significantly promoted through the mutually beneficial mechanism that a driver who is willing to report the bumps he/she meets can receive warnings issued from others as well.

Jump actions are typically accompanied by spiking and imply significant events in volleyball matches. In this paper, we propose an effective system capable of jump pattern recognition in player moving trajectories from long broadcast volleyball videos. First, the entire video is segmented into clips of rallies by shot segmentation and whistle detection. Then, camera calibration is adopted to find the correspondence between coordinates in the video frames and real-world coordinates. With the homographic transformation matrix computed, real-world player moving trajectories can be derived by a sequence of tracked player locations in video frames. Jump patterns are recognized from the player moving trajectory by using a sliding window scheme with physics-based validation and context constraint. Finally, the jump locations can be estimated and jump tracks can be separated from the planar moving tracks. The experiments conducted on broadcast volleyball videos show promising results.

Given a social graph, the problem of influence maximization is to determine a set of nodes that maximizes the spread of influences. While some recent research has studied the problem of influence maximization, these works are generally too time consuming for practical use in a large-scale social network. In this article, we develop a new framework, community-based influence maximization (CIM), to tackle the influence maximization problem with an emphasis on the time efficiency issue. Our proposed framework, CIM, comprises three phases: (i) community detection, (ii) candidate generation, and (iii) seed selection. Specifically, phase (i) discovers the community structure of the network; phase (ii) uses the information of communities to narrow down the possible seed candidates; and phase (iii) finalizes the seed nodes from the candidate set. By exploiting the properties of the community structures, we are able to avoid overlapped information and thus efficiently select the number of seeds to maximize information spreads. The experimental results on both synthetic and real datasets show that the proposed CIM algorithm significantly outperforms the state-of-the-art algorithms in terms of efficiency and scalability, with almost no compromise of effectiveness.

With the exponential growth of the web multimedia contents, illegal video copies are widespread and easy to be obtained from search engines and video sharing websites. For video copyright protection, near-duplicate video retrieval becomes more and more important. In this paper, we proposed a Pattern Set based Dynamic Programming (PSDP) algorithm to retrieve near-duplicate videos efficiently and effectively. In addition, the precise positions of the near-duplicate segments in videos can also be located. To better deal with the slow/fast motion and the dropped frame problem, the Time-shift Pattern set Similarity (TPS) is then applied. Two datasets are used to evaluate the effectiveness and efficiency of the proposed method, and the experimental results show that the proposed method outperforms the compared approaches in terms of precision and execution time in both two datasets.

Automatic video editing is receiving increasingly attention as the digital camera technology develops further and social media sites such as YouTube and Flickr become popular. Background music selection is one of the key elements to make the generated video attractive. In this work, we propose a framework for background music recommendation based on multi-modal latent semantic analysis between video and music. The videos and accompanied background music are collected from YouTube, and the videos with low musicality are filtered out by musicality detection algorithm. The co-occurrence relationships between audiovisual features are derived for multi-modal latent semantic analysis. Then, given a video, a ranked list of recommended music can be derived from the correlation model. In addition, we propose an algorithm for music beat and video shot alignment to calculate the alignability of recommended music and video. The final recommendation list is the combined result of both content correlation and alignability. Experiments show that the proposed method achieves a promising result.

Serve receive-to-attack (SR2A) is the most principal way to gain points in volleyball games. In addition, the positions of players on the court reveal informative clues about both offensive and defensive formations. Hence, in this paper, we propose an effective system capable of extracting SR2A periods from long broadcast volleyball videos (taken from a pan-tilt-zoom camera), and then locating the players using a novel histogram-based approach. Enriched visual presentation can be provided to give the audience or professional players/coaches a further sight into the game. The proposed system consists of four major processing modules, including court detection, SR2A period extraction, camera calibration, and histogram-based player localization. The experiments conducted on broadcast volleyball videos show promising results.

In volleyball matches, spiking is the most effective way to gain points, while blocking is the action to prevent the opponents from getting scores by spiking. In this paper, we propose an intelligent system for automatic spiking events detection and blocking pattern classification in real volleyball videos. First, the entire videos are segmented into clips of rallies by whistle detection. Then, we find the court region based on proper camera calibration, and detect the location of the net for judging the positions of spiking and blocking. Via analyzing the changes of moving pixels along the net, we make a bounding box around the blocking location, so as to classify the blocking patterns into two main categories based on the width of bounding box. Finally, two important tactic patterns, delayed spiking and alternate position spiking, are recognized. With the information of spiking events and blocking locations, we can collect the statistical data and make tactics inference easily. To the best of our knowledge, no previous work is focused on spiking or blocking event detection. The experimental results on the videos recorded by a university volleyball team are promising and demonstrate the effectiveness of our proposed scheme.

The mining of closed sequential patterns has attracted researchers for its capability of using compact results to preserve the same expressive power as conventional mining. However, existing studies only focus on time point-based data. Few research efforts have elaborated on discovering closed sequential patterns from time interval-based data, where each data persists for a period of time. Mining closed time interval-based patterns, also called closed temporal patterns, is an arduous problem since the pair wise relationships between two interval-based events are intrinsically complex. In this paper, an efficient algorithm, CEMiner is developed to discover closed temporal patterns from interval-based data. Algorithm CEMiner employs some optimization techniques to effectively reduce the search space. The experimental results on both synthetic and real datasets indicate that CEMiner not only significantly outperforms the prior interval-based mining algorithms in terms of execution time but also possesses graceful scalability. The experiment conducted on real dataset shows the practicability of time interval-based closed pattern mining.

In baseball games, different release points of pitchers form several kinds of pitching styles. Different pitching styles possess individual advantages. This paper presents a novel pitching style recognition approach for automatic generation of game information and video annotation. First, an effective object segmentation algorithm is designed to compute the body contour and extract the pitcher's body. Then, star skeleton is used as the representative descriptor of the pitcher posture for pitching style recognition. The proposed approach has been tested on broadcast baseball video and the promising experimental results validate the robustness and practicability.

Free viewpoint video presentation is a new challenge in multimedia analysis. This paper presents an innovative physics-based scheme to reconstruct the 3D ball trajectory from single-camera volleyball video sequences for free viewpoint virtual replay. The problem of 2D-to-3D inference is arduous due to the loss of 3D information in projection to 2D images. The proposed scheme incorporates the domain knowledge of court specification and the physical characteristics of ball motion to accomplish the 2D-to-3D inference. Motion equations with the parameters are set up to define the 3D trajectories based on physical characteristics. Utilizing the geometric transformation of camera calibration, the 2D ball coordinates extracted over frames are used to approximate the parameters of the 3D motion equations, and finally the 3D ball trajectory can be reconstructed from single-camera sequences. The experiments show promising results. The reconstructed 3D trajectory enables the free viewpoint virtual replay and enriched visual presentation, making game watching a whole new experience.

In basketball games, screen is a blocking move performed by an offensive player, who stands beside or behind a defender, in order to free a teammate to shoot, to receive a pass, or to drive in to score. Screen is the fundamental essence that most offensive tactics are executed with. In this paper, a screen- strategy analysis system is designed, and through combining the identified screens, what tactics are executed in basketball games can be speculated. The proposed system is capable of court region detection, camera calibration and player extraction. Player trajectories are computed by a Kalman filter-based tracking method and mapped to the real-world court coordinates. The player position/trajectory information greatly assists professional-oriented applications such as screen-strategy analysis and tactic inference. The experiments on broadcast basketball videos show encouraging results.

Accurate initial pose is a kind of crucial information when localizing shape features or recognizing car models in a real-time intelligent transportation system. However, obtaining a sufficiently accurate initial pose is generally difficult because very little prior information is available when the vehicle is first time captured by the camera. This paper proposes an algorithm that can provide a sufficiently accurate initial pose estimation without incurring a heavy computation load. This algorithm locates the symmetric center of cars and utilizes it to estimate the initial pose of vehicles. Theoretical analysis and real data experiments confirm that the proposed algorithm provides significantly better accuracy in initial pose estimation than previous pose estimation methods.

Most studies on sequential pattern mining are mainly focused on time point-based event data. Few research efforts have elaborated on mining patterns from time interval-based event data. However, in many real applications, event usually persists for an interval of time. Since the relationships among event time intervals are intrinsically complex, mining time interval-based patterns in large database is really a challenging problem. In this paper, a novel approach, named as incision strategy and a new representation, called coincidence representation are proposed to simplify the processing of complex relations among event intervals. Then, an efficient algorithm, CTMiner (Coincidence Temporal Miner) is developed to discover frequent time-interval based patterns. The algorithm also employs two pruning techniques to reduce the search space effectively. Furthermore, experimental results show that CTMiner is not only efficient and scalable but also outperforms state-of-the-art algorithms.

In baseball, the strike zone plays an important role in each pitch. Pitches which pass through the strike zone count as strikes, three of which strike out the batter. Thus, pitchers should acquire mastery of the strike zone. Moreover, the strike zone also provides the reference for positioning the pitch locations, about which sports fans and professionals have an intense interest in compile statistics. This paper presents a stance-based approach for strike zone shaping and visualization in broadcast baseball video. We design efficient and effective algorithms to detect the home plate, contour the batter, locate the features points on the batter contour, and finally outline the strike zone. The experiments show that the proposed framework is able to shape the strike zone fairly well in various broadcast baseball video sequences, needless of manual operation and additional camera setting.

This paper addresses the problem of adapting overlapped block motion compensation (OBMC) windows for use with variable blocksize motion estimates. We tackle the problem by using a parametric window design, which expresses, based on a statistical motion model, the optimal weights as a function of the distances between the predicted pixel and its nearby block centers. The formula enables both prediction weights and prediction order to be adapted on a pixelbypixel basis. Extensive experiments have been conducted using JM 12.4. Compared with conventional block motion compensation, our scheme shows a bitrate saving of 18% (5% on average) while maintaining the same or even higher PSNR (0.1 dB). It also provides a competitive advantage to variable block size motion compensation. Additionally, a hybrid of the two techniques achieves a further bitrate reduction of 13%. The result, nevertheless, provides only a lower bound on what is achievable since both motion estimation and mode decision were accomplished without considering OBMC. Further improvement is expected by incorporating iterative methods.

Efficient mining of high utility itemsets has become one of the most interesting data mining tasks with broad applications. In this paper, we proposed two efficient one-pass algorithms, MHUI-BIT and MHUI-TID, for mining high utility itemsets from data streams within a transaction-sensitive sliding window. Two effective representations of item information and an extended lexicographical tree-based summary data structure are developed to improve the efficiency of mining high utility itemsets. Experimental results show that the proposed algorithms outperform than the existing algorithms for mining high utility itemsets from data streams.

We address the problem of human action understanding of the upper human body from video sequences. Time-sequential images expressing human actions are transformed to sequences of feature vectors containing the configuration of the human body. A human is modeled as a collection of body parts, linked in a kinematic structure. The relation of the joints is used to estimate the human pose. A proposed layered HMM framework decomposes the human action recognition problem into two layers. The first layer models the actions of two arms individually from low-level features. The second layer models the interrelationship of two arms as an action. Experiments with a set of six types of human actions demonstrate the effectiveness of our proposed scheme, and the comparisons with other HMM systems show the robustness.

Despite a lot of research efforts in baseball video processing, little work has been done in analyzing the detailed process and ball movement of the batting content. This paper proposes a novel system to automatically summarize the progress of each batting in baseball videos. Utilizing the strictly-defined specifications of the baseball field, the system recognizes the spatial patterns in each frame and identifies what region of the baseball field is currently focused. Finally, an annotation string which abstracts the batting content is generated. With the annotation strings, the system is able to make descriptions and provide exploration for baseball videos, so that users can be given a further insight into the game quickly. The experiments on broadcast baseball videos of MLB and JPB show promising results.

Despite a lot of research efforts in sports video processing, little work was done in volleyball video analysis due to the high density of players on the court and the complicated overlapping of player-player or ball-player, which lead to great complexity of object tracking for advanced analysis. For ball detection and trajectory extraction in volleyball videos, this paper presents a physics-based scheme which utilizes the motion characteristics to extract ball trajectory from lots of moving objects. The experiments of ball tracking show encouraging results. Moreover, based on game-specific properties, the ball trajectory can be exploited to recognize set types for tactics inference and to detect basic actions in the volleyball game for close-up presentation.

In this paper, we propose a system that can automatically segment a basketball video into several clips on the basis of a GOP-based scene change detection method. The length of each clip and the number of dominant color pixels of each frame are used to classify shots into close-up view, medium view, and full court view. Full court view shots are chosen to do advanced analyses such as ball tracking and parameter extracting for the transformation from a 3D real-world court to a 2D image. After that, we map points in the 2D image to the corresponding coordinates in a real-world court by some physical properties of the 3D shooting trajectory, and compute the statistics of all shooting positions. Eventually we can obtain the information about the most possible shooting positions of a professional basketball team, which is useful for opponents to adopt appropriate defense tactics.

This paper presents a novel method for reducing a baseball video segment from one batter to next batter into a more compact pitch-by-pitch video by pitching ball trajectory detection. The pitch-by-pitch video shows the complete pitching and batting process and largely reduces the source video data, making pitching analysis of broadcast baseball sequences an easier task. The proposed method has been tested for several long sequences, and promising results are reported.

This paper proposes a music accompaniment system capable of catching the tempo of music. The original signal is first reduced to a detection function revealing the pulses of music. To induce the tempo and locate beats, a Fourier analysis-based algorithm with high practicality and generality is designed that it is robust to beat strength and not restricted to specific music genres. The regularity and periodicity of music beats are extracted and even the missing beats are recovered. The performance is validated using a comprehensive testing data set, and results in both formal objective experiments and subjective listening evaluations show convincible performance. Moreover, an interactive interface is designed that users are allowed to select an instrument to accompany the music based on the obtained tempo.

Mining multimedia data is one of the most important issues in data mining. In this paper, we propose an online one-pass algorithm to mine the set of frequent temporal patterns in online music query streams with a sliding window. An effective bit-sequence representation is used to reduce the processing time and memory needed to slide the windows. Experiments show that the proposed algorithm only needs a half of memory requirement of original music query data, and just scans the data once

In this paper, we propose an efficient algorithm, called MQS-change (changes of music query streams), to detect the changes of maximal melody structures in user-centered music query streams. Two music melody structures (set of chord-sets and string of chord-sets) are maintained and four melody structure changes (positive burst, negative burst, increasing change and decreasing change) are monitored in a new data structure MSC-list (a list of music structure changes). Experiments show that MQS-change algorithm is an online, single-pass approach to detect the changes of music melody structures over continuous music query streams

Online mining of streaming data is one of the most important issues in data mining. In this paper, we proposed an efficient one-pass algorithm, called MFI-TransSW (mining frequent itemsets over a transaction-sensitive sliding window), to mine the set of all frequent itemsets in data streams with a transaction-sensitive sliding window. An effective bit-sequence representation of items is used in the proposed algorithm to reduce the time and memory needed to slide the windows. The experiments show that the proposed algorithm not only attain highly accurate mining results, but also run significant faster and consume less memory than existing algorithms for mining frequent itemsets over recent data streams.

In this paper, we proposed an online algorithm, called FQT-Stream (Frequent Query Trees of Streams), to mine the set of all frequent tree patterns over a continuous XML data stream. A new numbering method is proposed to represent the tree structure of a XML query tree. An effective sub-tree numeration approach is developed to extract the essential information from the XML data stream. The extracted information is stored in an effective summary data structure. Frequent query trees are mined from the current summary data structure by a depth-first-search manner.

Peer-to-Peer (P2P) multimedia application is expected to be one of the most important services supported by the next generation networks. However, how to balance server load in reducing the peak network traffic for a given P2P network is still a challenge. This paper performs dynamic server redirect (DSR) techniques that blocked requests from high load peer can be redirect to the peer which has high available bandwidth and very low request arrival rate. A novel and approximate model for evaluating the relationship between the request blocking probability and increased cost is proposed. Based on the performance analysis of request blocking, the P2P system can dynamically find efficient ways of using available bandwidth within the acceptable increased cost. Numerical results show that the dynamic server redirect scheme significantly reduces request blocking rate.

With the growth of digital music, the development of music recommendation is helpful for users. The existing recommendation approaches are based on the users' preference on music. However, sometimes, recommending music according to the emotion is needed. In this paper, we propose a novel model for emotion-based music recommendation, which is based on the association discovery from film music. We investigated the music feature extraction and modified the affinity graph for association discovery between emotions and music features. Experimental result shows that the proposed approach achieves 85% accuracy in average.

Online, single-pass mining Web click streams poses some interesting computational issues, such as unbounded length of streaming data, possibly very fast arrival rate and just one scan over previously arrived click-sequencer In this paper, we propose a new, single-pass algorithm, called DSM-TKP (data stream mining for top-k path traversal patterns), for mining top-k path traversal patterns, where k is the desired number of path traversal patterns to be mined. An effective summary data structure called TKP-forest (top-k path forest) is used to maintain the essential information about the top-k path traversal patterns of the click-stream so far. Experimental studies show that DSM-TKP algorithm uses stable memory usage and makes only one pass over the streaming data.

We study the problem of mining frequent closed structures in a continuous, infinite-sized, and fast changing music melody stream. By modeling a music melody as a sequence of chord-sets, we propose an efficient algorithm FCS-stream (frequent closed structures of streaming melody sequences) for incremental mining of frequent closed structures in one scan of the continuous stream of chord-set sequences. An extended prefix-tree structure called TCS-tree (temporal closed structure tree) is developed for storing compact, essential information about the frequent closed structures of the stream. Results from our theoretical analysis and experimental studies with synthetic data show that the FCS-stream algorithm satisfies the main performance requirements, namely, single-pass, bounded memory, and real-time, for data stream mining.

Many performance studies have shown that locking based protocols outperform other concurrency control protocols in most database configurations and workloads. However, in mobile environments there are many special characteristics, such as long network delay and the expensive wireless communication. Besides, transactions may be aborted due to forced termination when handoff occurs for the consideration of concurrency control. The performances of concurrency control strategies should be re-evaluated in such environments. In this paper, we develop an analytic model to evaluate the performances of concurrency control strategies. The accuracy of this model is verified by simulation. According to the experimental results we show that the behavior of mobile users and the degree of data contention have a significant impact on the relative performances of the concurrency control strategies. In particular, we point out that the optimistic concurrency control strategy outperforms other strategies over a wide range of system configurations. We also explain why the optimistic algorithm is well suited in mobile environments.

There are more and more information services provided on the wireless network. Due to long network delay of wireless link, the transaction will be a long lived transaction. In such a situation, the occurrence of handoff is inevitable, and thus a wireless link held by the mobile unit crossing the cell boundaries might be forced to terminate. It is undesirable that an active transaction is forced to terminate. We propose two guard channel schemes (GCS), static and dynamic, to reduce the probability of forced termination of transactions. In dynamic GCS, the number of reserved channels of a base station is dynamically assigned according to the number of transaction calls which may handoff to this cell while the number of guard channels is fixed in the static GCS. An analytic model based on Markov chain is derived to evaluate the system performance. The correctness of this model is verified by a simulation program. The experimental results show that a significant improvement is achieved by using the dynamic GCS.

Mining of sequential patterns in a transactional database is time consuming due to its complexity. Maintaining present patterns is a non-trivial task after database update, since appended data sequences may invalidate old patterns and create new ones. In contrast to re-mining, the key to improve mining performance in the proposed incremental update algorithm is to effectively utilize the discovered knowledge. By counting over appended data sequences instead of the entire updated database in most cases, fast filtering of patterns found in last mining and successive reductions in candidate sequences together make efficient update on sequential patterns possible.

Disk arrays have been proposed as a way of improving I/O performance by using parallelism among multiple disks. This paper focuses, however, on improving the performance of disk array systems in the presence of disk failures, which are significant for applications where continuous operation is of concern. Although several approaches have been explored, the goals of achieving high performance and storage efficiency often conflict. In this paper, we propose a new variation of RAID organization, multi-partition RAID (mP-RAID), to improve storage efficiency and reduce performance degradation when disk failures occur. The idea is to recognize that frequently demanded data dominate the degree of the performance degradation when disk failures occur. mP-RAID subdivides a disk array into several partitions associated with different block organizations. Based upon data popularity, we assign data to appropriate partitions so that high performance and better storage efficiency can be achieved simultaneously.

Chinese characters are constructed by basic strokes based on structural rules. In handwritten characters, the shapes of the strokes may vary to some extent, but the spatial relations and geometric configurations of the strokes are usually maintained. Therefore these spatial relations and configurations could be regarded as invariant features and could be used in the recognition of handwritten Chinese characters. In this paper, we investigate the structural knowledge in Chinese characters and propose the stroke spatial relationship representation (SSRR) to describe Chinese characters. An On-Line Chinese Character Recognition (OLCCR) method using the SSRR is also presented. With SSRR, each character is processed and is represented by an attribute graph. The process of character recognition is thereby transformed into a graph matching problem. After careful analysis, the basic spatial relationship between strokes can be characterized into five classes. A bitwise representation is adopted in the design of the data structure to reduce storage requirements and to speed up character matching. The strategy of hierarchical search in the preclassification improves the recognition speed. Basically, the attribute graph model is a generalized character representation that provides a useful and convenient representation for newly added characters in an OLCCR system with automatic learning capability. The significance of the structural approach of character recognition using spatial relationships is analyzed and is proved by experiments. Realistic testing is provided to show the effectiveness of the proposed method.

The task of painting each cel of an animated sequence has always been a tedious work using traditional methods. In order to simplify and speed up the process, the development of an automatic cel painting system is desired. This paper presents a method for assisting the production of cartoon animation using computers in order to reduce the production expense and to improve the overall quality. It signals a great improvement in the working environment where 2-D animation is produced. The basic idea of our automatic cel painting mechanism is to extract both statistical and topological features of regions from input animation drawings, and to search for similar corresponding regions in the previous drawing. If the similarity measures are within the accepted thresholds, the corresponding colour will be inherited. A new integrated labelling algorithm constructing statistical region and topological graph features is proposed. Furthermore, a similarity measure of regions is defined and an algorithm of partial matching of attribute graphs is presented. The experimental result shows the feasibility and practicability of the proposed approach. © 1997 John Wiley & Sons, Ltd.

An on-line signature verification scheme based on linear prediction coding (LPC) cepstrum and neural networks is proposed. Cepstral coefficients derived from linear predictor coefficients of the writing trajectories are calculated as the features of the signatures. These coefficients are used as inputs to the neural networks. A number of single-output multilayer perceptrons (MLPs), as many as the number of words in the signature, are equipped for each registered person to verify the input signature. If the summation of output values of all MLPs is larger than the verification threshold, the input signature is regarded as a genuine signature; otherwise, the input signature is a forgery. Simulations show that this scheme can detect the genuineness of the input signatures from a test database with an error rate as low as 4%

This paper presents a rule-based approach for online Chinese character recognition without writing constraints on both stroke number and order. Stroke correspondence is accomplished based on rules predefined such that combinatorial exhaustion can be avoided for character matching. Stroke correspondence rules contain the basic stroke types and geometric features of strokes. Because rules are constituted by invariant structural features, wide handwriting variations can be accommodated. Utilizing the structural characteristics in Chinese characters, we represent the reference database hierarchically to reduce its data size. It only requires O(n log n) time to accomplish stroke correspondence between a template of n strokes and an input script using the hierarchical reference database. This approach is very suitable for those systems with very limited computing resource.

A locking model adopting a multi-granularity approach is proposed for concurrency control in object-oriented database systems. The model is motivated by a desire to provide high concurrency and low locking overhead in accessing objects. Locking in schemas and locking in instances are developed separately and then are integrated. Schema changes and composite objects are also taken into account. A dual queue scheme for efficient scheduling of lock requests is developed. The model consists of a rich set of lock modes, a compatibility matrix, and a locking protocol. Characteristic query examples on single class, class lattice, and composite objects are used to illustrate the comparison between the ORION model and the proposed model. It is shown that our locking model has indeed made some improvements and is suitable for concurrency control in object-oriented databases.

In this paper, a generic architecture of interactive video databases is proposed.It is a platform for video applications.It consists of six major modules : Video Indexing, Interactive Browser, Object Annotator, Query Processing Tool, Video Management Module and Content Retrieval Module.The considerations and requirements of the video database in the aspects of video data management, annotation capability, content-based query and browsing interfaces are described.This paper also describes a Video Object Description Model (VODM) for annotations.The notion of VODM is based on the Entity-Relationship model for the database conceptual level organization.Unlike keyword or framebased knowledge representation, VODM can record the detail attribute information about video objects, store and retrieve annotations in many different video files.To construct VODM, we give a recursive definition of the video object and describe the operations of annotation storage structures.A two-step query processing method is introduced that can reduce the processing time of each video object query.

In the application of the superimposed coding method to character-based Chinese text retrieval we find two kinds of false hits for a multi-syllabic (multicharacter) query. The first type is a random false hit (RFH) which is due to accidental setting of bits by irrelevant characters in a document signature. The other type is an adjacency false hit (AFH) which is due to the loss of character sequence information in signature creation. Since many query terms are proper nouns and Chinese names which often contain three characters (tri-syllabic), we derive a formula to estimate the RFH for trisyllabic queries. As for the AFH which cannot be reduced by single character (monogram) hashing method, a method which hashes consecutive character pairs (bigram) is designed to reduce both the AFH and the RFH. We find that there exists an optimal weight assignment for a minimal false hit rate in a combined scheme which encodes both monogram and bigram keys in document signatures.

In the domain of multimedia applications, continuous display is an important issue. In this paper, we present a practical method to allocate disk storage for multimedia data so that continuous requirement can be met. This technique explores data-transfer parallelism on a multidisk system. Moreover, in order to ensure that continuous retrieval can be achieved in a multiuser environment, we propose the dynamic scheduling mechanism for real-time object retrieval. It can be seen that, a good scheduling can explore higher access concurrency in display of multimedia applications. Several approaches with different trade-off based upon this mechanism are proposed in this paper, which include delay initiation, read-ahead, migration, segmentation and integration.

The perception of spatial relationships among objects in a picture is one of the important selection criteria to discriminate and retrieve images in an image database system. The data structure called 2-D string, proposed by Chang et al., is adopted to represent the symbolic pictures. When there are a large number of images in the image database and each image contains many objects, the processing time for image retrievals is tremendous. It is essential to develop efficient access methods for these retrievals. In this paper, the efficient methods for retrieval by objects, retrieval by pairwise spatial relationships and retrieval by subpicture are proposed. All the methods are based on the superimposed coding technique.