排序對關聯演算法速度的影響

何達明

doi:10.6840/cycu200200609

18.208.126.232，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 Business > Graduate School of Information Management
Social Sciences > Management

Bibliography Management Tool

Related Links

Report an Issue

Search for full text in Holdings

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

排序對關聯演算法速度的影響

Partial order improve the performance of the association rule computing

何達明 , Masters　　Advisor：劉士豪　　

繁體中文 DOI： 10.6840/cycu200200609

關聯式規則；交易物項；頻物項集合；非高頻物項集合；資料挖掘； sortcompress ； fp-tree ； apriori ； association rules ； datamining

Abstract │ Reference (10) │ Altmetrics

Abstract 〈TOP〉

Parallel Abstract 〈TOP〉

Abstract

In recent years many business use computer to keep their transaction data and control their business process. Until now all Corp. has their own computers keep a lot’s of their process digital data. Faster and faster data generates. Those data conclude very important information and some useful knowledge , but we had no idea to use and discover it , but now the information science has a big improves, the faster computer, the larger size disk, the more popular database application, those let’s can find the knowledge hides in database.

The way to find knowledge in data is called “Data mining”. One data mining method is called “Association Rules”. A classical method “Apriori” has use on it for many years, It’s a way to look for Association Rules but it’s really not a good way, Apriori use the Psychology “Guess and filter” so spend many efforts on something no need to care about, so It’s need many main memory and compute time. Someone discovered a smart way to do it. Use a compressed tree to record the pattern with counts , so can in two pass database read to find whole all association rules. The compressed tree we call it “FP-Tree”. It’s a pretty nice method to find association rules. It’s brought a reduced complexity order and lower efforts. But it’s not made by the god. It’s need much memory to construct the FP-Tree. So it can hardly use on very large database, if it need to swap the tree between memory and disk. It’s may be a nightmare. The master idea of FP-Tree is compress transaction database into a limited main memory.
Main memory faster than disk for ten thousand times. So use it can reduce lot’s of efforts on swap and scan.

Now we find an new way with large compress ratio on transfer transaction data into to main memory can stored and can easy to use it to extracts association rules. We named this logarithm “SortCompress”. We use a compress array to keep the transaction association rules and use sort to help the compress process faster. It slower than FP-Tree a little, but it just need half size memory to stored it, so we can process more complexity transaction data use just an normal computer, and do it well. Now we will introduce that how we do it.

Keywords: datamining, association rules, apriori, fp-tree, sortcompress,

Reference ( 10 ) 〈TOP〉

[1] A. Savasere, E. Omiecinski, and S. Navathe, “An Efficient Algorithm for Mining Association Rules in Large Databases”, In Proceedings of 21st VLDB, pp.432-444,1995
連結：
[2] D. Lin and Z. M. Kedem, “Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Set”, In Proceedings of VI Intl. Conference on Extending Database Technology, 1998.
連結：
[6] J.S.Park,M.S.Chen,and P.S.Ui,”An Effective Hash Based Algorithm for Mining Association Rules”, Proceedings of the ACM SIGMOD, pp.1750186,1995
連結：
[7] M.Houtsma and A. Swami, “Set-Oriented Mining of Association Rules in Relational Databases,” 11th int’l Conference on Data Engineer, 1995
連結：
參考文獻

Altmetrics

〈TOP〉

E-mail ：

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

E-mail ：