CINXE.COM
New Algorithms for Fast Discovery of Association Rules
<!-- Copyright 2008 University of Rochester Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. --> <!-- document type --> <!-- Copyright 2008 University of Rochester Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. --> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html> <head> <meta name="citation_title" content="New Algorithms for Fast Discovery of Association Rules" /> <meta name="citation_author" content="Zaki, Mohammed" /> <meta name="citation_author" content="Parthasarathy, Srinivasan" /> <meta name="citation_author" content="Ogihara, Mitsunori" /> <meta name="citation_author" content="Li, Wei" /> <meta name="citation_publication_date" content="1997"> <title>New Algorithms for Fast Discovery of Association Rules</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8" /> <link rel="shortcut icon" href="/favicon.ico;jsessionid=E155C5DC85720D11E341E0177FAF273E"> <link rel="icon" type="image/ico" href="/favicon.ico;jsessionid=E155C5DC85720D11E341E0177FAF273E"> <!-- Copyright 2008 University of Rochester Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. --> <!-- Core + Skin CSS --> <link href="/page-resources/yui/assets/skins/sam/skin.css" media="all" rev="stylesheet" rel="stylesheet" type="text/css" /><link href="/page-resources/yui/reset-fonts-grids/reset-fonts-grids.css" media="all" rev="stylesheet" rel="stylesheet" type="text/css" /><link href="/page-resources/css/base-ur.css" media="all" rev="stylesheet" rel="stylesheet" type="text/css" /><link href="/page-resources/css/main_menu.css" media="all" rev="stylesheet" rel="stylesheet" type="text/css" /><link href="/page-resources/css/global.css" media="all" rev="stylesheet" rel="stylesheet" type="text/css" /><link href="/page-resources/css/tables.css" media="all" rev="stylesheet" rel="stylesheet" type="text/css" /><!-- required imports --> <script type="text/javascript" src="/page-resources/yui/utilities/utilities.js" ></script><script type="text/javascript" src="/page-resources/yui/button/button-min.js" ></script><script type="text/javascript" src="/page-resources/yui/container/container-min.js" ></script><script type="text/javascript" src="/page-resources/yui/menu/menu-min.js" ></script><!-- base path information --> <script type="text/javascript" src="/pages/js/base_path.js" ></script><script type="text/javascript" src="/page-resources/js/util/ur_util.js" ></script><script type="text/javascript" src="/page-resources/js/menu/main_menu.js" ></script><script type="text/javascript" src="/pages/js/ur_table.js" ></script><script type="text/javascript" src="/page-resources/js/public/institutional_publication_view.js" ></script><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <script type="text/javascript" src="/page-resources/js/google_analytics.js" ></script></head> <body class="yui-skin-sam"> <!-- yahoo doc 2 template creates a page 950 pixles wide --> <div id="doc2"> <!-- this is the header of the page --> <!-- Copyright 2008 University of Rochester Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. --> <!-- page header - this uses the yahoo page styling --> <div id="hd"> <div id="header"> <div id="header_logo"> <a href="/home.action;jsessionid=E155C5DC85720D11E341E0177FAF273E"><img align="left" alt="Home Page" src="/page-resources/images/all-images/ir_plus_logo.jpg"/></a> </div> <div id="header_links"> <a href="/help.action;jsessionid=E155C5DC85720D11E341E0177FAF273E">Help</a> | <a href="/contactUs.action;jsessionid=E155C5DC85720D11E341E0177FAF273E">Contact Us</a> | <a href="/about.action;jsessionid=E155C5DC85720D11E341E0177FAF273E">About</a> | <a href="/privacyPolicy.action;jsessionid=E155C5DC85720D11E341E0177FAF273E">Privacy Policy</a> <br> <a href="http://www.irplus.org/"><img class="powered_by" alt="Powered By IR Plus institutional repository software" src="/page-resources/images/all-images/poweredby.gif;jsessionid=E155C5DC85720D11E341E0177FAF273E"></a> </div> </div> <div id="mainMenu" class="yuimenubar yuimenubarnav"> <div class="bd"> <ul class="first-of-type"> <li class="yuimenubaritem first-of-type"><a class="yuimenubaritemlabel" href="/viewUserRegistration.action;jsessionid=E155C5DC85720D11E341E0177FAF273E"><span class="userImg"> </span><span class="menu_text">Create Account</span></a></li> <li class="yuimenubaritem first-of-type"><a class="yuimenubaritemlabel" href="/user/workspace.action;jsessionid=E155C5DC85720D11E341E0177FAF273E"><span class="doorInImg"> </span><span class="menu_text">Login</span></a></li> <!-- user cannot be null --> <li class="yuimenubaritemleft"><a class="yuimenubaritemlabel" href="/home.action;jsessionid=E155C5DC85720D11E341E0177FAF273E"><span class="homeImg"> </span><span class="menu_text">Home</span></a></li> </ul> </div> </div> </div> <!-- end header --><!-- this is the body region of the page --> <div id="bd"> <h3> <a tabindex="1" href="home.action">UR Research</a> > <a href="/viewInstitutionalCollection.action;jsessionid=E155C5DC85720D11E341E0177FAF273E?collectionId=3">Computer Science Department</a> > <a href="/viewInstitutionalCollection.action;jsessionid=E155C5DC85720D11E341E0177FAF273E?collectionId=97">CS Systems Technical Reports</a> > </h3> <!-- Begin - Display the Item preview --> <h3>New Algorithms for Fast Discovery of Association Rules</h3> <h3 class="errorMessage"> URL to cite or link to: <a href="http://hdl.handle.net/1802/501">http://hdl.handle.net/1802/501</a> </h3> <!-- if statements for the buttons the forms are below this in a separate statements this is due to formatting in IE 6 --> <!-- Copyright 2008 University of Rochester Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. --> <table class="greyBorderTable" > <tr> <td width="10" class="noBorderTabletd"></td> <td class="bottomBorder" align="left"> <span class="whiteFileImg"></span><!-- the is Preview flag indicates that the file is being previewed by a user this should be passed in by the importing file --> <a href="/fileDownloadForInstitutionalItem.action;jsessionid=E155C5DC85720D11E341E0177FAF273E?itemId=360&itemFileId=449" > 97.tr651.New_algorithms_for_fast_discovery_of_association_rul.ps</a> 395.27 KB (No. of downloads : 255) <br/> </td> <td class="bottomBorder" align="left"> </td> </tr> </table><!-- Copyright 2008 University of Rochester Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. --> <table class="greyBorderBlueBgTable"> <tr> <td width="60%" valign="top" class="greyBorderTableTd"> <table class="noPaddingTable" width="100%" align="left"> <tr> <td> <label for="abstract" class="previewLabel"> Abstract </label> </td> </tr> <tr> <td> Association rule discovery has emerged as an important problem in knowledge discovery and data mining. The association mining task consists of identifying the frequent itemsets, and then forming conditional implication rules among them. In this paper we present efficient algorithms for the discovery of frequent itemsets, which forms the compute intensive phase of the task. The algorithms utilize the structural properties of frequent itemsets to facilitate fast discovery. The related database items are grouped together into clusters representing the potential maximal frequent itemsets in the database. Each cluster induces a sub-lattice of the itemset lattice. Efficient lattice traversal techniques are presented, which quickly identify all the true maximal frequent itemsets, and all their subsets if desired. We also present the effect of using different database layout schemes combined with the proposed clustering and traversal techniques. The proposed algorithms scan a (pre-processed) database only once, addressing the open question in association mining, whether all the rules can be efficiently extracted in a single database pass. We experimentally compare the new algorithms against the previous approaches, obtaining improvements of more than an order of magnitude for our test databases.</td> </tr> </table> </td> <td valign="top" class="greyBorderTableTd"> <table width="100%"> <tr> <td class="previewLabel">Contributor(s):</td> </tr> <tr> <td> <a href="/viewContributorPage.action;jsessionid=E155C5DC85720D11E341E0177FAF273E?personNameId=183"> Mohammed Javeed Zaki </a> - Author<br/><br/> </td> </tr> <tr> <td> <a href="/viewContributorPage.action;jsessionid=E155C5DC85720D11E341E0177FAF273E?personNameId=195"> Srinivasan Parthasarathy </a> - Author<br/><br/> </td> </tr> <tr> <td> <a href="/viewContributorPage.action;jsessionid=E155C5DC85720D11E341E0177FAF273E?personNameId=185"> Mitsunori Ogihara (1963 - )</a> - Author<br/><br/> </td> </tr> <tr> <td> <a href="/viewContributorPage.action;jsessionid=E155C5DC85720D11E341E0177FAF273E?personNameId=198"> Wei Li </a> - Author<br/><br/> </td> </tr> <tr> <td class="previewLabel"> Primary Item Type: </td> </tr> <tr> <td> Technical Report</td> </tr> <tr> <td class="previewLabel"> Series/Report Number:</td> </tr> <tr> <td> UR CSD / TR651</td> </tr> <tr> <td class="previewLabel"> Language:</td> </tr> <tr> <td> English</td> </tr> <tr> <td class="previewLabel"> Subject Keywords: </td> </tr> <tr> <td> frequent itemsets;association rules;knowledge discovery and data mining;parallel algorithms;maximal hypergraph cliques;lattice traversals</td> </tr> <tr> <td class="previewLabel"> First presented to the public:</td> </tr> <tr> <td>7/22/2004</td> </tr> <tr> <td class="previewLabel">Original Publication Date:</td> </tr> <tr> <td>7/1997</td> </tr> <tr> <td class="previewLabel">Previously Published By:</td> </tr> <tr> <td>University of Rochester. Computer Science Department.</td> </tr> <tr> <td class="previewLabel">License Grantor / Date Granted: </td> </tr> <tr> <td> Suzanne S. Bell / 2004-07-22 21:39:32.0 ( <a href="viewItemRepositoryLicense.action;jsessionid=E155C5DC85720D11E341E0177FAF273E?versionedLicenseId=1&version=1">View License</a> ) </td> </tr> <tr> <td class="previewLabel">Date Deposited</td> </tr> <tr> <td> 2004-07-22 21:39:32.0</td> </tr> <tr> <td class="previewLabel">Date Last Updated</td> </tr> <tr> <td> 2012-09-26 16:35:14.586719</td> </tr> <tr> <td class="previewLabel">Submitter:</td> </tr> <tr> <td> Suzanne S. Bell</td> </tr> </table> </td> </tr> <tr> <td colspan="2" class="greyBorderTableTd"> <p>Copyright © This item is protected by copyright, with all rights reserved.</p> </td> </tr> </table><!-- End - Display the Item preview --> <!-- end if for show publication --> <!-- ************************* All versions Start ************************* --> <h3>All Versions</h3> <div class="dataTable"> <table width="100%" ><thead ><tr ><td > Thumbnail </td><td > Name </td><td > Version </td><td > Created Date </td></tr></thead><tbody ><tr onmouseover="this.className='highlight'" onmouseout="this.className='even'" class="even" ><td ></td><td >New Algorithms for Fast Discovery of Association Rules</td><td ><a href="institutionalPublicationPublicView.action;jsessionid=E155C5DC85720D11E341E0177FAF273E?institutionalItemId=360&versionNumber=1">1</a> </td><td >2004-07-22 21:39:32.0</td></tr></tbody></table></div> <!-- ************************* All versions End ************************* --> </div> <!-- end the body tag --> <!-- this is the footer of the page --> <!-- Copyright 2008 University of Rochester Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. --> <!-- footer --> <div id="ft"> <div class="footerLogo"><a href="http://www.rochester.edu/"><img src="/page-resources/images/all-images/ur_logo.jpg;jsessionid=E155C5DC85720D11E341E0177FAF273E" alt=""/></a></div> <ul id="bottomNav" class="basicNav"> <li><a target="_blank" href="/help.action;jsessionid=E155C5DC85720D11E341E0177FAF273E">Help</a> | </li> <li><a href="/contactUs.action;jsessionid=E155C5DC85720D11E341E0177FAF273E">Contact Us</a> | </li> <li><a href="/about.action;jsessionid=E155C5DC85720D11E341E0177FAF273E">About</a> | </li> <li><a href="/privacyPolicy.action;jsessionid=E155C5DC85720D11E341E0177FAF273E">Privacy Policy</a></li> </ul> <div class="copyright"><i>Copyright © UNIVERSITY OF ROCHESTER LIBRARIES. All Rights Reserved</i></div> </div> <!-- end footer --> </div> <!-- end doc --> <div id="withdrawDialog" class="hidden"> <div class="hd">Withdraw Publication</div> <div class="bd"> <form id="withdraw_publication" name="withdrawPublicationForm" method="post" action="/user/withdrawPublication.action;jsessionid=E155C5DC85720D11E341E0177FAF273E"> <input type="hidden" id="institutional_item_id" name="institutionalItemId" value="360" /> <input type="hidden" id="institutional_item_version" name="versionNumber" value="1" /> <div id="withdraw_error_div" class="errorMessage"></div> <table class="formTable"> <tr> <td align="left" class="label">Reason for withdraw :*</td> <td align="left" class="input"><textarea cols="42" rows="4" id="withdraw_reason" name="withdrawReason"></textarea></td> </tr> <tr> <td align="left" class="label">Display metadata:</td> <td align="left" class="input"><input type="checkbox" id="withdraw_metadata" name="showMetadata" value="true" /></td> </tr> <tr> <td align="left" class="label">Withdraw all versions:</td> <td align="left" class="input"><input type="checkbox" id="withdraw_versions" name="withdrawAllVersions" value="true" /> </td> </tr> </table> </form> </div> </div> <div id="reinstateDialog" class="hidden"> <div class="hd">Reinstate Publication</div> <div class="bd"> <form id="reinstate_publication" name="reinstatePublicationForm" method="post" action="/user/reinstatePublication.action;jsessionid=E155C5DC85720D11E341E0177FAF273E"> <input type="hidden" id="institutional_item_id" name="institutionalItemId" value="360" /> <input type="hidden" id="institutional_item_version" name="versionNumber" value="1" /> <div id="reinstate_error_div" class="errorMessage"></div> <table class="formTable"> <tr> <td align="left" class="label">Reason for reinstate :*</td> <td align="left" class="input"><textarea cols="42" rows="4" id="withdraw_reason" name="withdrawReason"></textarea></td> </tr> <tr> <td align="left" class="label">Reinstate all versions:</td> <td align="left" class="input"><input type="checkbox" id="reinstate_versions" name="reinstateAllVersions" value="true" /> </td> </tr> </table> </form> </div> </div> <!-- delete item confirm dialog --> <div id="deleteItemConfirmDialog" class="hidden"> <div class="hd">Delete?</div> <div class="bd"> <p>Do you want to delete this Institutional Publication?</p> </div> </div> <!-- end delete item confirm dialog --> </body> </html>