分散式環境下基於序列型樣之 KNN 查詢

萬年松

3.236.156.34，Hello！

Close
Search Quick Search Advanced Search Publication Search	Personal Service Member Login Searching History Use Bonus Card SYMSKAN
Browse Browse by University of Graduate Thesis Browse by Pinyin of Graduate Thesis Browse by Conference Proceedings Topic Browse by Conference Proceedings Publisher Browse by Pinyin of Conference Proceedings Browse by eBook Category Browse by eBook Topic Browse by eBook Publisher
Customer Services Authorize Airiti Recommend a Journal

Search Symbol (Half-width)	Description of Search Symbols
Space	"AND" indicates the intertwining of key terms used in a search
Double Quotation Marks ("") ( " " )	Double quotation marks indicate the beginning and end of a phrase, and the search will only include terms that appear in the same order of those within the quotations. Example: "image process" ： " image process "
?	Indicates a variable letter. Entering two ? will indicate two variable letters, and so on. Example: "Appl?", search results will yield apple, apply… e , appl y … ( (often used to English word searches) )
*	Indicates an unlimited number of variable letters to follow, from 1~n. Example: Enter "appl*", search results will yield apple, apples, apply, applied, application…(often used in English word searches) e , appl es , appl y , appl ied , appl ication … ( (often used to English word searches) )
AND、OR、NOT	Boolean logic combinations of key words is a skill used to expand or refine search parameters. (1) AND (1) AND: Refines search parameters (2) OR (2) OR: Expands search parameters (3) NOT: Excludes irrelevant parameters

DOI stands for Digital Object Identifier （ D igital O bject I dentifier ） ,
and is the unique identifier for objects on the internet. It can be used to create persistent link and to cite articles.

Using DOI as a persistent link

To create a persistent link, add「http://dx.doi.org/」「 http://dx.doi.org/ 」 before a DOI.
For instance, if the DOI of an article is 10.5297/ser.1201.002 , you can link persistently to the article by entering the following link in your browser: http://dx.doi.org/ 10.5297/ser.1201.002 。
The DOI link will always direct you to the most updated article page no matter how the publisher changes the document's position, avoiding errors when engaging in important research.

Cite a document with DOI

When citing references, you should also cite the DOI if the article has one. If your citation guideline does not include DOIs, you may cite the DOI link.

DOIs allow accurate citations, improve academic contents connections, and allow users to gain better experience across different platforms. Currently, there are more than 70 million DOIs registered for academic contents. If you want to understand more about DOI, please visit airiti DOI Registration （ doi.airiti.com ）。

Data Source

College of Electrical Engineering & Computer Science > Department of Electrical Engineering
Engineering > Electrical Engineering

Bibliography Management Tool

Related Links

Report an Issue

Search in Library

There is no full-text available at the moment. Airiti would like to request author's authorization. I would like to provide authorization.

分散式環境下基於序列型樣之 KNN 查詢

Distributed KNN Query Processing for Sequences with Similar Patterns

萬年松 , Masters　　Advisor：蔡曉萍　　

繁體中文

分散式資料庫；漸進式；二分探測；序列型樣探勘； KNN 查詢； Distributed Databases ； Incremental ； Binary Probing ； Sequence Pattern Mining ； KNN Query

Abstract │ Reference (45) │ Altmetrics

Abstract 〈TOP〉

Parallel Abstract 〈TOP〉

Sequence data are ubiquitous in our daily life, such as i.e., moving object trajectories、biological gene sequences、records of the commodity purchasing, which are of high research value. Sequence Pattern Analysis is one of the most important research fields in data mining. Its goal is to discover important features (patterns) hidden in sequence data, such as movement regularity in trajectories, motif in DNA or protein sequences, or purchasing behavior in transaction sequences. Recently, with the advance of DNA microarray chips, sensing, and wireless techniques, the huge amounts of sequence data are rapidly accumulated. Since a centralized server cannot afford the huge and ubiquitous sequence data, a distributed approach is the natural trend.

Facing the huge and distributed sequence data, how to query data efficiently is an important and difficulty problem. In the thesis, we focus on the problem of distributed KNN query of sequences with similar patterns. To solve this problem, we propose a distributed and incremental KNN query with binary probing (DIKNN-BP) algorithm. It mines sequence patterns by using Probabilistic Suffix Tree（PST）and transmits pattern to remote servers in a progressive manner. The remote servers estimate the upper and lower bound of similarity value between target object and remote candidate objects and based on which to prune unqualified candidates. In addition, we derive five theorems and propose a binary probing approach to speed up the converge of upper and lower bound, also the KNN query. According to the experimental results, our DIKNN-BP algorithm can obtain the KNN solution with fewer patterns transmitted and with less data transmitted. Compared with a naive approach, it achieves a shorter query execution time.

Reference ( 45 ) 〈TOP〉

[3] Jiong Yang and Meng Hu. Trajpattern: Mining sequential patterns from imprecise trajectories of mobile objects. In Proceedings of the 10th International Conference on Advances in Database Technology, pages 664–681, 2006.
連結：
[5] Ming-Yen Lin and Suh-Yin Lee. Improving the efficiency of interactive sequential pattern mining by incremental pattern discovery. In Proceedings of the 36th Annual Hawaii International Conference on System Sciences, page 68b, Jan. 2003.
連結：
[6] Darya Chudova and Padhraic Smyth. Pattern discovery in sequences under a markov assumption. In Proceedings of the 8th ACM SIGKDD International
連結：
[8] A. K. Jain, M. N. Murty, and P. J. Flynn. Data clustering: a review. ACM Computing Surveys, 31(3):264–323, September 1999.
連結：
[10] Mi-Yen Yeh, Kun-Lung Wu, Philip S. Yu, and Ming-Syan Chen. Leewave: Level-wise distribution of wavelet coefficients for processing knn queries over distributed streams. Proceedings of the VLDB Endowment, 1(1):586–597, Aug. 2008.
連結：

Altmetrics

〈TOP〉

E-mail ：

When an article is available to download, a notice will be sent to your mailbox address.

E-mail ：