{
  "pdf_file_name" : "07449817.pdf",
  "pages" : [ {
    "page_number" : 1,
    "words" : [ "Discovering", "Long", "Maximal", "Frequent", "Pattern", "Shu-Jing", "Lin", "National", "Chung-Shan", "Institute", "of", "Science", "Technology", "Taoyuan", "Taiwan", "Yi-Chung", "Chen", "and", "Don-Lin", "Yang", "Department", "Information", "Engineering", "Computer", "Feng", "Chia", "University", "Taichung", "Jungpin", "Wu", "Statistics", "TaiwanAbstract—Association", "rule", "mining", "the", "most", "commonly", "used", "method", "for", "data", "has", "numerous", "applications", "Although", "many", "approaches", "that", "can", "find", "association", "rules", "have", "been", "developed", "utilize", "maximum", "frequent", "itemsets", "are", "short", "Existing", "methods", "fail", "to", "perform", "well", "in", "involving", "large", "amounts", "incur", "longer", "Apriori-like", "algorithms", "this", "problem", "because", "they", "generate", "candidate", "spend", "considerable", "time", "scanning", "databases", "is", "their", "processing", "bottom-up", "layered", "This", "paper", "solves", "via", "a", "novel", "hybrid", "Multilevel-Search", "algorithm", "The", "concurrently", "uses", "bidirectional", "Pincer-Search", "parameter", "prediction", "mechanism", "along", "with", "search", "Parameterised", "reduce", "number", "consequently", "database", "scans", "Experimental", "results", "demonstrate", "proposed", "performs", "especially", "when", "length", "than", "or", "equal", "eight", "concurrent", "approach", "our", "multilevel", "faster", "execution", "improved", "efficiency", "Keywords—data", "itemset", "long", "I", "INTRODUCTION", "In", "knowledge", "discovery", "1", "2", "an", "analytic", "applied", "automatically", "semi-automatically", "look", "meaningful", "patterns", "main", "goal", "extract", "useful", "information", "from", "huge", "effective", "efficient", "manner", "3", "Data", "very", "both", "management", "decision", "making", "Association", "4", "frequently", "technique", "Apriori", "discover", "relationships", "between", "various", "points", "Many", "based", "on", "as", "it", "simple", "straightforward", "two", "phases", "finding", "generation", "verification", "A", "set", "items", "appear", "together", "records", "occurrence", "frequency", "meets", "pre-defined", "threshold", "To", "all", "m-itemsets", "m", "starting", "maximal", "must", "produce", "2m", "its", "subsets", "scan", "times", "With", "exponential", "complexity", "restricted", "only", "overcome", "limitation", "proposes", "efficiently", "extracts", "where", "no", "superset", "paper’s", "contribution", "literature", "effectively", "seeking", "5", "using", "top-down", "searches", "remainder", "organized", "follows", "Section", "II", "explores", "relevant", "related", "III", "introduces", "concept", "pseudo", "code", "IV", "presents", "detailed", "implementation", "explanatory", "examples", "V", "provides", "comparisons", "experimental", "analysis", "evaluations", "VI", "contains", "concluding", "remarks", "future", "directions", "research", "RELATED", "WORK", "organizations", "utilizing", "6", "increasing", "Definition", "Let", "i1", "i2", "ik", "be", "k", "distinct", "transaction", "T", "represent", "purchased", "by", "customer", "supermarket", "D", "transactions", "An", "X", "Itemsets", "referred", "k-itemsets", "said", "support", "if", "fraction", "denoted", "support(X", "user", "define", "minimum", "which", "percentage", "form", "R", "Y", "defined", "confidence", "factor", "such", "customarily", "represented", "100", "evaluate", "strength", "otherwise", "infrequent", "interesting", "strong", "level", "focuses", "7-9", "proper", "MFS", "MFI", "Kedem", "2002", "10", "quickly", "searched", "Denwattana", "1368th", "International", "Conference", "Advanced", "Computational", "Intelligence", "Chiang", "Mai", "Thailand", "February", "14-16", "2016", "978-1-4673-7782-9/16/$31.00" ]
  }, {
    "page_number" : 2,
    "words" : [ "IEEEGetta", "2001", "11", "proposed", "the", "Parameterised", "algorithm", "based", "on", "Apriori", "Hong", "et", "al", "2009", "12", "who", "a", "mining", "applied", "idea", "of", "bottom-up", "search", "with", "multiple", "levels", "to", "reduce", "number", "candidate", "itemsets", "and", "database", "scans", "accelerate", "process", "finding", "maximal", "frequent", "The", "method", "in", "this", "paper", "mainly", "integrates", "concepts", "from", "both", "Pincer-Search", "algorithms", "III", "OUR", "EFFICIENT", "ALGORITHM", "FOR", "DISCOVERING", "MAXIMAL", "FREQUENT", "ITEMSETS", "A", "Concept", "Informing", "Proposed", "Approach", "Multilevel-Search", "is", "top-down", "searches", "This", "can", "go", "up", "or", "down", "many", "one", "pass", "First", "constructs", "statistics", "table", "sets", "required", "parameters", "as", "does", "For", "instance", "parameter", "n", "indicates", "how", "lattice", "13", "be", "traversed", "at", "time", "Parameter", "k", "start", "level", "next", "step", "predict", "k+n-1)-itemsets", "scan", "once", "verify", "them", "When", "prediction", "incorrect", "scanned", "again", "correct", "error", "continues", "works", "efficiently", "by", "using", "bidirectional", "until", "end", "condition", "met", "Thus", "eliminate", "more", "redundant", "than", "other", "methods", "also", "reduces", "B", "No", "Missing", "Candidate", "Itemsets", "starts", "2", "value", "increased", "Then", "predicted-frequent", "are", "produced", "used", "lower-level", "Section", "IV.D", "describes", "detail", "Lemma", "1", "Pruning", "that", "not", "result", "any", "missing", "Proof", "finds", "without", "need", "recover", "itemset", "otherwise", "recovery", "procedure", "make", "necessary", "correction", "Here", "proof", "C", "Algorithm", "definition", "symbols", "MFCI", "Maximal", "MFI", "Ck", "k-itemsets", "Lk", "Frequent", "inf", "Infrequent", "RC", "Remaining", "ST", "Statistics", "minsup", "minimum", "support", "tm", "user", "specified", "threshold", "m-support", "tl", "transaction", "length", "kC", "Predicted-frequent", "Predicted-infrequent", "Input", "user-defined", "Output", "contains", "all", "Results", "Call", "generate", "i.e", "Scan", "count", "supports", "for", "every", "1-item", "L1", "Join", "C2", "i", "while", "Lk-1", "do", "Predict_candidates", "3", "predicted-infrequent", "4", "predicted-candidate", "5", "approach", "6", "Move", "7", "infrequent", "8", "Update", "if", "9", "10", "there", "an", "Recovery", "remaining", "approaches", "14", "15", "16", "17", "18", "end-if", "19", "n+k-1)-itemsets", "Cn+k", "20", "21", "subsets", "22", "Ln+k-1", "frequent(n+k-1)-itemsets", "23", "Lk+1", "Lk+n-1", "24", "k+n", "25", "end-while", "26", "27", "return", "Fig", "pseudo", "code", "set", "candidate-to-be-frequent", "appearing", "transactions", "m", "available", "resource" ]
  }, {
    "page_number" : 3,
    "words" : [ "137Fig", "1", "shows", "the", "pseudo", "code", "of", "proposed", "Multilevel-Search", "algorithm", "A", "detailed", "description", "is", "provided", "in", "Section", "IV", "which", "various", "examples", "are", "used", "to", "explain", "its", "implementation", "THE", "IMPLEMENTATION", "OF", "MULTILEVEL-SEARCH", "ALGORITHM", "Implementation", "has", "following", "four", "tasks", "Generate", "a", "Statistics", "Table", "statistics", "table", "ST", "built", "by", "scanning", "database", "once", "Fig", "2", "The", "records", "number", "times", "every", "1-item", "appears", "transactions", "then", "find", "frequent", "1-itemsets", "i.e", "L1", "default", "k", "value", "k-level", "MFCI", "combination", "all", "items", "If", "Lk-1", "and", "Ck", "not", "empty", "Predict_candidates", "procedure", "range", "traversed", "levels", "be", "predicted", "from", "level", "k+n-1", "bottom-up", "approach", "TABLE", "I", "EXAMPLE", "DB", "TID", "Itemset", "ABCEF", "3", "BCDEF", "4", "ABCD", "5", "ABCE", "6", "ABC", "7", "ABF", "8", "ACE", "9", "BCE", "10", "BDE", "Example", "To", "elucidate", "how", "evolves", "Parameterised", "Denwattana", "Getta’s", "dataset", "11", "Tables", "II", "With", "use", "this", "paper", "demonstrates", "that", "more", "efficient", "than", "their", "Each", "record", "example", "contains", "transaction’s", "set", "total", "six", "unique", "exist", "with", "letters", "A~F", "occurrences", "each", "lengths", "values", "m", "start", "minimal", "length", "transaction", "maximal", "Specifically", "among", "ten", "five", "3-length", "two", "4-length", "three", "5-length", "B", "Predict", "Candidate", "Itemsets", "generates", "predicted-candidate", "itemsets", "according", "user-defined", "parameters", "include", "user-specified", "threshold", "any", "tm", "tl", "traverse", "pass", "n", "Here", "support", "appearing", "m-length", "ranges", "Additionally", "must", "less", "or", "equal", "based", "on", "available", "resource", "begins", "prediction", "uses", "generate", "When", "candidate", "k-itemsets", "belong", "predicted-frequent", "they", "marked", "kC", "Predicted-infrequent", "calculation", "for", "defined", "as", "follows", "An", "item", "x’s", "nsactionslength", "tra", "theofnumber", "Thensactionslength", "x", "ofnumber", "Themm", "scope", "tl-length", "Qualified", "satisfy", "combined", "becoming", "MCk", "subset", "belongs", "Otherwise", "it", "predicted-infrequent", "Lk", "produce", "Ck+1", "This", "repeated", "until", "reaches", "k+n-1)-level", "search", "While", "k+n-1)-itemsets", "generated", "at", "eliminate", "other", "lower", "simplify", "discussion", "minsup", "20", "80", "Based", "C", "D", "E", "F", "These", "C2", "Thus", "L1={A", "STATISTICS", "Items", "Total", "sup", "9C", "8D", "3E", "7F", "0", "Algorithm", "Input", "Output", "Scan", "For" ]
  }, {
    "page_number" : 4,
    "words" : [ "138", "Algorithm", "Predict_candidates", "procedure", "Input", "A", "statistics", "table", "ST", "Lk-1", "k-level", "and", "the", "user", "defined", "parameters", "tm", "tl", "n", "Output", "Predicted-frequent", "predicted-infrequent", "itemsets", "from", "k", "to", "k+n-1", "level", "1", "Scan", "2", "Ck", "is", "generated", "3", "if", "subsets", "of", "MCk", "move", "kC", "4", "else", "5", "for", "i", "k+1", "n+k-1", "6", "Ck+1", "7", "MCk+1", "1kC", "8", "9", "end-for", "10", "predicted", "1nkC", "then", "delete", "Fig", "The", "pseudo", "code", "some", "infrequent", "1-itemsets", "exist", "cardinality", "MFCI", "would", "be", "reduced", "by", "In", "this", "case", "top-down", "search", "goes", "down", "levels", "in", "one", "pass", "as", "with", "Pincer-Search", "algorithm", "Initially", "MFI", "an", "empty", "set", "Next", "prediction", "finds", "MC2", "C2", "obtain", "2C", "Because", "no", "2-length", "transaction", "exists", "example", "process", "starts", "3-length", "transactions", "Only", "1-item", "B", "satisfies", "80", "because", "item’s", "support", "value", "80%8054", "Three", "C", "satisfy", "threshold", "4-length", "Table", "III", "user-specified", "so", "used", "consider", "up", "5-length", "last", "column", "PC2", "all", "under", "different", "m-length", "are", "merged", "E", "F", "As", "D", "not", "a", "subset", "it", "belongs", "Consequently", "Then", "joined", "generate", "C3", "These", "procedures", "repeated", "3C", "4C", "has", "completed", "Since", "work", "wants", "find", "maximal", "frequent", "their", "sub-itemsets", "can", "pruned", "lower-level", "candidates", "using", "predicted-frequent", "4-itemsets", "approach", "After", "eliminating", "candidate", "follows", "MFCI={A", "Update", "Maximal", "Frequent", "Candidate", "Itemsets", "database", "scanned", "again", "actual", "If", "frequent-candidate", "verified", "after", "counting", "frequencies", "they", "moved", "updated", "according", "inf", "examination", "required", "check", "whether", "any", "incorrect", "occurs", "Example", "scanning", "count", "k-itemsets", "itemset", "found", "L2={B", "L3", "L4={A", "utilizes", "update", "Considering", "becomes", "Finally", "processing", "However", "removed", "Both", "Recover", "There", "two", "error", "types", "its", "To", "rectify", "these", "wrongly", "additional", "must", "which", "called", "Remaining", "k-TABLE", "THE", "ITEMSETS", "SATISFYING", "1-ITEM", "THRESHOLD", "TM", "trans", "Merged", "A,B,C", "B,C,E,F", "MC2={A,B,C,E,F", "PC3", "MC3={A,B,C,E,F", "PC4", "MC4={A,B,C,E,F", "PC5", "MC5={B,C,E,F" ]
  }, {
    "page_number" : 5,
    "words" : [ "139itemsets", "RC", "Fig", "4", "shows", "the", "recovery", "procedure", "If", "any", "predicted-frequent", "j-itemset", "i.e", "jC", "turns", "out", "to", "be", "an", "infrequent", "itemset", "after", "calculation", "all", "of", "its", "subsets", "from", "k-level", "j-1)-level", "will", "produced", "Similarly", "if", "predicted-infrequent", "becomes", "a", "frequent", "supersets", "j+1)-level", "k+n-1)-level", "After", "is", "database", "scanned", "again", "count", "support", "and", "MFCI", "for", "correcting", "prediction", "errors", "When", "frequent-candidate", "in", "qualified", "counting", "it", "moved", "MFI", "The", "updated", "according", "inf", "found", "As", "Section", "II", "must", "These", "two", "properties", "are", "used", "produce", "new", "By", "eliminating", "n+k-1)-itemsets", "using", "subset", "belonging", "not", "listed", "itemsets", "L(n+k-1", "Then", "joins", "candidate", "Cn+k", "above", "elimination", "deleted", "then", "recovered", "complete", "n+k)-itemsets", "approach", "uses", "prune", "value", "k", "increased", "n+k", "It", "repeats", "steps", "until", "L(k-1", "Ck", "empty", "final", "result", "returned", "Algorithm", "Recovery", "Input", "Incorrect", "user", "defined", "parameters", "n", "Output", "Remaining", "1", "Take", "apart", "incorrect", "generate", "remaining", "2", "3", "Join", "pseudo", "code", "Example", "From", "some", "likely", "because", "three", "B", "D", "C", "E", "2C", "become", "verification", "For", "correction", "these", "combined", "as", "follows", "2RC", "3RC", "4RC", "MFCI={A", "F", "Thus", "A", "counted", "update", "set", "4-itemsets", "yield", "C5", "eliminate", "which", "maximal", "5-itemsets", "via", "top-down", "yielding", "following", "results", "L2", "L3={B", "L4", "Final", "Because", "entire", "ends", "here", "V", "EXPERIMENTAL", "RESULTS", "AND", "DISCUSSION", "Experimental", "Environment", "Experiments", "were", "performed", "on", "IntelR", "XeonTM", "MP", "CPU", "at", "2.00GHz", "with", "3800", "MB", "RAM", "running", "Windows", "2000", "programs", "developed", "Microsoft", "Visual", "Basic", "6.0", "Pincer-Search", "Parameterised", "algorithms", "also", "implemented", "comparison", "IBM", "dataset", "generator", "was", "test", "databases", "Table", "IV", "defines", "lists", "experiments", "We", "generated", "twenty", "total", "each", "type", "had", "five", "types", "mainly", "short", "moderate", "long", "length", "range", "1~4", "5~8", "9~12", "All", "Multilevel-Search", "examine", "their", "respective", "performance", "Data", "Analysis", "Efficiency", "Assessment", "Three", "tm", "tl", "algorithm", "affect", "efficiency", "execution", "time", "instance", "when", "parameter", "too", "large", "many", "Conversely", "small", "To", "demonstrate", "simplicity", "ease-of-use", "multiple", "various", "settings", "proposed", "without", "complex", "analysis", "datasets", "Suitable", "adopted", "TABLE", "DEFINITIONS", "OF", "PARAMETERS", "number", "transactions", "T", "average", "L", "potentially-frequent", "N", "distinct", "items", "DATABASES", "Type", "Database", "T2.L10.N500.D100K", "10", "500", "100000", "T8.L10.N500.D100K", "8", "T10.L10.N500.D100K", "T12.L10.N500.D100K", "12" ]
  }, {
    "page_number" : 6,
    "words" : [ "140", "perform", "an", "efficiency", "assessment", "of", "target", "algorithms", "Consequently", "these", "parameters", "are", "set", "as", "follows", "1", "If", "the", "average", "transaction", "length", "is", "2", "n", "to", "and", "tm", "65", "8~10", "4", "80", "3", "The", "user-specified", "threshold", "tl", "depends", "on", "database", "used", "Table", "V", "In", "first", "experiments", "T2.L10.N500.D100K", "databases", "compare", "Multilevel-Search", "Pincer-Search", "Parameterised", "Fig", "5", "shows", "that", "algorithm", "performs", "better", "than", "other", "two", "for", "short", "maximal", "frequent", "itemsets", "Here", "multilevel", "multilayer", "interchangeably", "transactions", "in", "T8.L10.N500.D100K", "datasets", "8", "6", "With", "minimal", "support", "10", "difference", "execution", "time", "not", "significant", "between", "Multilevel-search", "Pincer-search", "while", "poorly", "When", "increases", "fewer", "candidates", "found", "performance", "doubled", "20", "less", "remains", "best", "T10.L10.N500.D100K", "dataset", "7", "minimum", "over", "times", "faster", "Due", "going", "up", "or", "down", "multiple", "levels", "one", "pass", "overall", "winner", "Using", "T12.L10.N500.D100K", "experiment", "results", "show", "similar", "both", "use", "top-down", "approach", "find", "improve", "their", "Since", "goal", "this", "paper", "efficient", "solutions", "long", "patterns", "taken", "by", "scans", "number", "candidate", "when", "T", "12", "examined", "detail", "Experiment", "Tables", "VI", "VII", "has", "total", "scanned", "Although", "generates", "instances", "still", "Comparison", "three", "with", "TABLE", "THE", "AVERAGE", "TIMES", "OF", "DATABASE", "SCAN", "MINSUP=20", "Databases", "Apriori", "T2.L10.N500.D100", "T8.L10.N500.D100", "T10.L10.N500.D100", "11", "T12.L10.N500.D100", "13" ]
  }, {
    "page_number" : 7,
    "words" : [ "141", "winner", "because", "the", "extra", "candidate", "itemsets", "come", "from", "recovery", "procedure", "and", "no", "data", "scan", "is", "involved", "To", "assess", "performance", "of", "these", "algorithms", "this", "paper", "compares", "average", "execution", "times", "for", "three", "kinds", "databases", "with", "minimal", "support", "20", "experiments", "are", "performed", "fifteen", "each", "algorithm", "Table", "VIII", "shows", "time", "transaction", "lengths", "T", "8", "10", "12", "elucidate", "in", "IX", "clearly", "that", "Multilevel-Search", "2.32", "faster", "than", "Pincer-Search", "2.99", "Parameterised", "Separate", "ratio", "improvement", "terms", "also", "presented", "VI", "CONCLUSIONS", "AND", "FUTURE", "WORK", "This", "proposes", "a", "novel", "to", "mine", "efficiently", "long", "association", "rules", "Using", "concept", "predicting", "frequent", "infrequent", "by", "parameter", "settings", "combines", "top-down", "search", "mechanism", "bottom-up", "multilevel", "searching", "rapidly", "identify", "maximal", "After", "finding", "can", "generate", "all", "method", "especially", "useful", "when", "an", "itemset", "Experimental", "results", "verify", "proposed", "However", "has", "room", "its", "prediction", "The", "effects", "parameters", "n", "tm", "tl", "be", "determined", "further", "study", "Experiments", "showed", "accuracy", "declines", "too", "many", "levels", "scanned", "one", "pass", "produces", "large", "number", "Better", "will", "reduce", "redundant", "database", "scans", "In", "future", "it", "planned", "use", "statistical", "approach", "improve", "apply", "parallel", "computing", "14", "better", "ACKNOWLEDGMENT", "work", "was", "supported", "part", "Ministry", "Science", "Technology", "Taiwan", "under", "grants", "MOST", "104-2221-E-035-089", "104-2218-E-035-012", "REFERENCES", "1", "M", "S", "Chen", "J", "Han", "P", "Yu", "Data", "Mining", "An", "Overview", "Database", "Perspective", "IEEE", "Transactions", "on", "Knowledge", "Engineering", "vol", "6", "pp", "866-883", "1996", "2", "Kamber", "Concepts", "Techniques", "Burlington", "Morgan", "Kaufmann", "2011", "3", "Dong", "BitTableFI", "Efficient", "Frequent", "Itemsets", "Algorithm", "Knowledge-Based", "Systems", "4", "329-335", "2007", "R", "Agrawal", "Srikant", "Fast", "Association", "Rules", "Large", "Databases", "Proc", "20th", "International", "Conference", "Very", "Bases", "Santiago", "1994", "487-499", "5", "Y", "Tsay", "Chiang", "CBAR", "Method", "18", "2-3", "99-105", "2005", "Irina", "Tudor", "rule", "mining", "as", "technique", "BULETINUL", "universitatii", "Petrol-Gaze", "din", "Ploiesti", "LX", "page", "49-56", "2008", "7", "B", "New", "Maximum", "Multiple-Level", "3rd", "Innovative", "Computing", "Information", "Control", "ICICIC'08", "Proceedings", "332-335", "D", "Burdick", "Calimlim", "Gehrke", "Mafia", "A", "transactional", "17th", "ICDE", "2001", "Heidelberg", "Germany", "443-452", "9", "Flannick", "Yiu", "MAFIA", "Performance", "Study", "Maximal", "2003", "Workshop", "Itemset", "Implementations", "FIMI'03", "Melbourne", "Florida", "November", "Lin", "Z.M", "Kedem", "Pincer-search", "Discovering", "Set", "553-566", "2002", "11", "N", "Denwattana", "J.R", "Getta", "12th", "Australasian", "45-51", "Hong", "C", "Horng", "H", "Wu", "L", "Wang", "improved", "using", "predictive", "Expert", "Applications", "36", "72-80", "2009", "13", "Z", "Abdullah", "Herawan", "Deris", "Highly", "Correlated", "Least", "Scalable", "Trie-Based", "Journal", "Chinese", "Institute", "Engineers", "35", "547-554", "2012", "Yeh", "Big", "Parallel", "Comparison", "Distributed", "MapReduce", "Methodologies", "Master", "thesis", "Dept", "Management", "National", "Central", "University", "2015", "TABLE", "THE", "RATIO", "OF", "IMPROVEMENT", "IN", "TERMS", "EXECUTION", "TIME", "minsup=20", "length", "transactions", "Average", "2.94", "2.45", "1.57", "1.44", "4.77", "2.78", "VII", "AVERAGE", "NUMBER", "CANDIDATE", "ITEMSETS", "MINSUP", "Parame-terised", "Multilevel", "Search", "258", "338", "280", "913", "1356", "782", "1117", "1778", "1421", "COMPARISON", "SECONDS", "1885.48", "3155.97", "5155.97", "3399.14", "924.30", "6157.23", "9157.23", "5412.92", "642.29", "1290.64", "3290.64", "1741.19" ]
  } ]
}