Browsing by Author "Shan, MK"

Now showing 1 - 15 of 15

A framework for temporal similarity measures of content-based scene retrieval
(2001-04-01)
Shan, MK
;
Lee, SY
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
The distinguished features of video retrieval lie in the similarity measures and content-based retrieval. Most research on content-based video retrieval represents the content of video as a set of frames, leaving out the temporal ordering of frames in the shot. In this paper, the similarity measures of video content are investigated. We propose a series of similarity measures based on the similarity of frame sequence which take temporal ordering into consideration. All the algorithms corresponding to the similarity measures are based on the approach of dynamic programming. (C) 2001 Published by Elsevier Science B.V.
Allocation of signature file on parallel device for WWW index servers
(1999-03-01)
Shan, MK
;
Lee, SY
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Signature files are widely used in information retrieval and database. They act as search filters for content-based retrieval. In a large database server, a parallel device is utilized to achieve concurrency access. Efficient allocation of signature files on parallel devices minimizes the query response time and is important in the design of access methods for large scale index servers. We have developed an algorithm to organize the storage of signatures in parallel secondary storage to reduce the query response time. First, signature file is clustered into signature pages. Then, the clustered signature pages are distributed among the disks using the parity check matrix of error correcting code in coding theory. Through the construction of error correcting code, the least frequently simultaneously accessed pages are allocated on the same disk. Performance analysis shows that this algorithm improves the efficiency of access.
Content-based video retrieval based on similarity of frame sequence
(1998)
Shan, MK
;
Lee, SY
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Video retrieval is one of the important design issues of multimedia database management systems. The distinguished features of video retrieval lie in the similarity measures and content-based retrieval. Most research on content-based video retrieval represents the content of video as a set of frames leaving out the temporal ordering of frames in the shot. In this paper, the similarity measures of video content are investigated. We propose a series of similarity measures based on the similarity of frame sequence which take temporal ordering into consideration. The corresponding algorithms are also presented. The effectiveness of the developed similarity measures measured by precision and recall is also described.
Content-based video retrieval via motion trajectories
(1998)
Shan, MK
;
Lee, SY
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Motion is one of the most prominent features of video. For content-based video retrieval, motion trajectory is the intuitive specification of motion features. In this paper, approaches for video retrieval via single motion trajectory and multiple motion trajectories are addressed. For the retrieval via single motion trajectory, the trajectory is modeled as a sequence of segments and each segment is represented as the slope. Two quantitative similarity measures and corresponding algorithms based on the sequence similarity are presented. For the retrieval via multiple motion trajectories, the trajectories of the video are modeled as a sequence of symbolic pictures. Four quantitative similarity measures and algorithms, which are also based on the sequence similarity, are proposed. All the proposed algorithms are developed based on the dynamic programming approach.
DSM-TKP: Mining Top-K Path traversal patterns over Web click-streams
(2005)
Li, HF
;
Lee, SY
;
Shan, MK
;
資訊工程學系
;
Department of Computer Science
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-sequences. 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.
Dynamic allocation of signature files on parallel devices
(1998-11-01)
Shan, MK
;
Lee, SY
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Signature file is one of the efficient access methods for retrieval of text database. In a large database server, parallel device is utilized to achieve concurrent access. Efficient allocation of signature file on parallel device minimizes the query response time and is important in the design of large databases. In this paper, we investigate the design of parallel signature file. We propose a new dynamic allocation technique to distribute the signature file on parallel device. It is an improvement of previous approach of Fragmented Signature File. While Fragmented Signature File uses Quick Filter to distribute the partitioned frame signature file, the proposed Parallel Signature Wie uses a declustering technique. The proposed Parallel Signature File has some advantages. First, the qualified frame signature blocks are distributed more uniformly than Fragmented Signature Files. Second, the proposed scheme can also be used in dynamic environment. Performance analysis shows that performance of the proposed approach outperforms that of Fragmented Signature File and is not far from theoretical optimal response time. (C) 1998 Published by Elsevier Science Ltd.
Dynamic allocation of signature files on parallel devices
(1998-11-01)
Shan, MK
;
Lee, SY
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Signature file is one of the efficient access methods for retrieval of text database. In a large database server, parallel device is utilized to achieve concurrent access. Efficient allocation of signature file on parallel device minimizes the query response time and is important in the design of large databases. In this paper, we investigate the design of parallel signature file. We propose a new dynamic allocation technique to distribute the signature file on parallel device. It is an improvement of previous approach of Fragmented Signature File. While Fragmented Signature File uses Quick Filter to distribute the partitioned frame signature file, the proposed Parallel Signature Wie uses a declustering technique. The proposed Parallel Signature File has some advantages. First, the qualified frame signature blocks are distributed more uniformly than Fragmented Signature Files. Second, the proposed scheme can also be used in dynamic environment. Performance analysis shows that performance of the proposed approach outperforms that of Fragmented Signature File and is not far from theoretical optimal response time. (C) 1998 Published by Elsevier Science Ltd.
Looking for new, not known music only: Music retrieval by melody style
(2004)
Kuo, FF
;
Shan, MK
;
資訊工程學系
;
Department of Computer Science
With the growth of digital music, content-based music retrieval (CBMR) has attracted increasingly attention. For most CBMR systems, the task is to return music objects similar to query in syntactic properties such as pitch and interval contour sequence. These approaches provide users the capability to look for music that has been heard. However, sometimes, listeners are looking, not for music they have been known, but for music that is new to them. Moreover, people sometimes want to retrieve music that "feels like" another music object or a music style. To the best of our knowledge, no published work investigates the content-based music style retrieval. This paper describes an approach for CBMR by melody style. We proposed four types of query specification for melody style query. The output of the melody style query is a music list ranked by the degree of relevance, in terms of music style, to the query. We developed the melody style mining algorithm to obtain the melody style classification rules. The style ranking is determined by the style classification rules. The experiment showed the proposed approach provides a satisfactory way for query by melody style.
Mining frequent closed structures in stremying melody sequences
(2004)
Li, HF
;
Lee, SY
;
Shan, MK
;
資訊工程學系
;
Department of Computer Science
In this paper, 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 algorithm FCS-strearn satisfies the main performance requirements, namely, single-pass, bounded memory, and real-time, for data stream mining.
Multidimensional interval filter: A new indexing method for subpicture query of image retrieval
(1998-11-01)
Shan, MK
;
Lee, SY
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
In this paper a new indexing method, called multidimensional interval filter, is proposed to speed up processing of subpicture query. The basic idea is the transformation of spatial information of each image into a multidimensional rectangle. Processing of subpicture query becomes that of rectangle containment query which can be further speeded up by some well-developed spatial access methods such as R-Trees. (C) 1998 Elsevier Science B.V. All rights reserved.
Online mining (recently) maximal frequent itemsets over data streams
(2005)
Li, HF
;
Lee, SY
;
Shan, MK
;
資訊工程學系
;
Department of Computer Science
A data stream is a massive, open-ended sequence of data elements continuously generated at a rapid rate. Mining data streams is more difficult than mining static databases because the huge, high-speed and continuous characteristics of streaming data. In this paper, we propose a new one-pass algorithm called DSM-MFI (stands for Data Stream Mining for Maximal Frequent Itemsets), which mines the set of all maximal frequent itemsets in landmark windows over data streams. A new summary data structure called summary frequent itemset forest (abbreviated as SFI-forest) is developed for incremental maintaining the essential information about maximal frequent itemsets embedded in the stream so far. Theoretical analysis and experimental studies show that the proposed algorithm is efficient and scalable for mining the set of all maximal frequent itemsets over the entire history of the data streams.
Online mining changes of items over continuous append-only and dynamic data streams
(2005)
Li, HF
;
Lee, SY
;
Shan, MK
;
資訊工程學系
;
Department of Computer Science
Online mining changes over data streams has been recognized to be an important task in data mining. Mining changes over data streams is both compelling and challenging. In this paper, we propose a new, single-pass algorithm, called MFC-append ((M) under bar ining (F) under bar requency (C) under bar hanges of append-only data streams), for discovering the frequent frequency-changed items, vibrated frequency changed items, and stable frequency changed items over continuous append-only data streams. A new summary data structure, called Change-Sketch, is developed to compute the frequency changes between two continuous data streams as fast as possible. Moreover, a MFC-append-based algorithm, called MFC-dynamic ((M) under bar ining (F) under bar requency (C) under bar hanges of dynamic data streams), is proposed to find the frequency changes over dynamic data streams. Theoretical analysis and experimental results show that our algorithms meet the major performance requirements, namely single-pass, bounded space requirement, and real-time computing, in mining data streams.
Online mining maximal frequent structures in continuous landmark melody streams
(2005-08-01)
Li, HF
;
Lee, SY
;
Shan, MK
;
資訊工程學系
;
Department of Computer Science
In this paper, we address the problem of online mining maximal frequent structures (Type I & II melody structures) in unbounded, continuous landmark melody streams. An efficient algorithm, called MMSLMS (Maximal Melody Structures of Landmark Melody Streams), is developed for online incremental mining of maximal frequent melody substructures in one scan of the continuous melody streams. In MMSLMS, a space-efficient scheme, called CMB (Chord-set Memory Border), is proposed to constrain the upper-bound of space requirement of maximal frequent melody structures in such a streaming environment. Theoretical analysis and experimental study show that our algorithm is efficient and scalable for mining the set of all maximal melody structures in a landmark melody stream. (c) 2005 Elsevier B.V. All rights reserved.
Placement of partitioned signature file and its performance analysis
(1998-02-01)
Shan, MK
;
Lee, SY
;
交大名義發表
;
資訊科學與工程研究所
;
National Chiao Tung University
Signature file access method is widely used in information retrieval and database. It acts as a search filter for content-based retrieval. One of the efficient organizations of signature file is Quick Filter. Quick Filter partitions the signatures into signature pages using linear hashing. While seek and latency time dominate the performance of disk access, efficient placement of the partitioned signature pages is necessary. In this paper, we investigate the placement of partitioned signature file to minimize the number of clusters pertinent to the query signature in dynamic environment. We present the placement using Gray code to minimize the number of qualified clusters. To accommodate the dynamic feature, linear hashing for partitioning the signatures into Gray code order is modified. The performance measured by the number of clusters accessed is analyzed. The formula of performance for a specific query signature is also derived. It is useful for the access cost estimation of query optimization in information retrieval. Performance analysis shows that placement using Gray code order outperforms that using binary code code. (C) Elsevier Science Inc. 1998.
PNP: Mining of profile navigational patterns
(2002)
Li, HF
;
Shan, MK
;
資訊工程學系
;
Department of Computer Science
Web usage mining is a key knowledge discovery research and as such has been well researched. So far, this research has focused mainly on databases containing access log data only. However, many real-world databases contain users profile data and current solutions for this situation are still insufficient. In this paper we have a large database containing of user profile information together with users web-pages navigational patterns. The user profile data includes quantitative attributes, such as salary or age, and categorical attributes, such as sex or marital status. We introduce the concept of profile navigation patterns, which discusses the problem of relating user profile information to navigation behavior. An example of such profile navigation pattern might be "20% of married people between age 25 and 30 have the similar navigational behavior <(ac)(c,b)(b,e)(e,a)(od)> ", where a, b, c, d, e are web pages in a web site. The navigation sequences may contain the generic traversal behavior, e.g. trend to backward moves, cycles etc. The objective of mining profile navigation patterns is to identify browser profile for web personalization. We present PNP, a new algorithm that discovers these profile navigation patterns. Scale-up experiments show that PNP scales linearly with the number of transactions.