PRACTICAL COAL MINING: A GUIDE FOR MINING PROFESSIONALS
TABLE OF CONTENTS 1 INTRODUCTION 1 1 1 COMMON PROBLEM 1 1 2 DATA INTEGRATION AND DATA MANAGEMENT 3 1 2 1 INFORMATION QUALITY OVERVIEW 3 1 2 2 CUSTOMER DATA INTEGRATION 4 1 2 3 DATA MANAGEMENT 8 1 2 4 PRACTICAL PROBLEMS TO DATA INTEGRATION AND MANAGEMENT 9 1 3 ANALYTICS 10 1 3 1 MODEL DEVELOPMENT 10 1 3 2 CURRENT MODELING AND OPTIMIZATION TECHNIQUES 11 1 3 3 SPECIFIC ALGORITHMS AND TECHNIQUES FOR IMPROVEMENT 12 1 3 4 INCREMENTAL OR EVOLUTIONARY UPDATES 13 1 3 5 VISUALIZATION 15 1 4 CONCLUSION 15 1 5 REFERENCES 16 2 A DECLARATIVE APPROACH TO ENTITY RESOLUTION 17 2 1 INTRODUCTION 17 2 2 BACKGROUND 18 2 2 1 ENTITY RESOLUTION DEFINITION 18 2 2 2 ENTITY RESOLUTION DEFENSE 18 2 2 3 ENTITY RESOLUTION TERMINOLOGY 19 2 2 4 DECLARATIVE LANGUAGES 20 2 3 THE DECLARATIVE TAXONOMY THE NOUNS 20 2 3 1 ATTRIBUTES 21 2 3 2 REFERENCES 21 2 3 3 PATHS AND MATCH FUNCTIONS 22 2 3 4 ENTITIES 24 2 3 5 SUPER GROUPS 25 2 3 6 MATCHING GRAPHS 26 2 4 A DECLARATIVE TAXONOMY THE ADJECTIVES 27 2 4 1 ATTRIBUTE ADJECTIVES 27 2 4 2 REFERENCE ADJECTIVES 29 2 5 THE DECLARATIVE TAXONOMY THE VERBS 29 2 5 1 ATTRIBUTE VERBS 29 2 5 2 REFERENCE VERBS 30 2 5 3 ENTITY VERBS 32 2 6 A DECLARATIVE REPRESENTATION 33 2 6 1 THE XML SCHEMA 34 2 6 2 A REPRESENTATION FOR THE OPERATIONS 36 2 7 CONCLUSION 37 2 8 EXERCISES 37 2 9 REFERENCES 37 3 TRANSITIVE CLOSURE OF DATA RECORDS APPLICATION AND COMPUTATION 39 3 1 INTRODUCTION 39 3 1 1 MOTIVATION 40 3 1 2 LITERATURE REVIEW 42 3 2 PROBLEM DEFINITION 43 3 3 SEQUENTIAL ALGORITHMS 45 3 3 1 A BREADTH FIRST SEARCH BASED ALGORITHM 45 3 3 2 A SORTING AND DISJOINT SET BASED ALGORITHM 47 3 3 3 EXPERIMENT 51 3 4 PARALLEL AND DISTRIBUTED ALGORITHMS 53 3 4 1 AN OVERVIEW OF A PARALLEL AND DISTRIBUTED SCHEME 53 3 4 2 GENERATE MATCHING PAIRS 55 3 4 3 CONVERSION PROCESS 55 3 4 4 CLOSURE PROCESS 56 3 4 5 A MPI BASED PARALLEL AND DISTRIBUTED ALGORITHM 62 3 4 6 EXPERIMENT 64 3 5 CONCLUSION 70 3 6 EXERCISES 71 3 7 ACKNOWLEDGMENTS 73 3 8 REFERENCES 74 4 SEMANTIC DATA MATCHING PRINCIPLES AND PERFORMANCE 77 4 1 INTRODUCTION 77 4 2 PROBLEM STATEMENT DATA MATCHING FOR CUSTOMER DATA INTEGRATION 78 4 3 SEMANTIC DATA MATCHING 78 4 3 1 BACKGROUND ON LATENT SEMANTIC ANALYSIS 78 4 3 2 ANALYSIS 80 4 4 EFFECT OF SHARED TERMS 81 4 4 1 FUNDAMENTAL LIMITATIONS ON DATA MATCHING 81 4 4 2 EXPERIMENTS 82 4 5 RESULTS 83 4 6 CONCLUSION 87 4 7 EXERCISES 89 4 8 ACKNOWLEDGMENTS 89 4 9 REFERENCES 89 5 APPLICATION OF THE NEAR MISS STRATEGY AND EDIT DISTANCE TO HANDLE DIRTY DATA 91 5 1 INTRODUCTION 91 5 2 BACKGROUND 92 5 2 1 TECHNIQUES USED FOR GENERAL SPELLING ERROR CORRECTION 93 5 2 2 DOMAIN SPECIFIC CORRECTION 95 5 3 INDIVIDUAL NAME SPELLING CORRECTION ALGORITHM THE PERSONAL NAME RECOGNITION STRATEGY PNRS 96 5 3 1 EXPERIMENT RESULTS 98 5 4 CONCLUSION 99 5 5 EXERCISES 99 5 6 REFERENCES 100 6 A PARALLEL GENERAL PURPOSE SYNTHETIC DATA GENERATOR 103 6 1 INTRODUCTION 103 6 2 SDDL 104 6 2 1 MIN MAX CONSTRAINTS 105 6 2 2 DISTRIBUTION CONSTRAINTS 106 6 2 3 FORMULA CONSTRAINTS 106 6 2 4 ITERATIONS 106 6 2 5 QUERY POOLS 108 6 3 POOLS 108 6 4 PARALLEL DATA GENERATION 110 6 4 1 GENERATION ALGORITHM 1 111 6 4 2 GENERATION ALGORITHM 2 112 6 5 PERFORMANCE AND APPLICATIONS 113 6 6 CONCLUSION AND FUTURE DIRECTIONS 114 6 7 EXERCISES 116 6 8 REFERENCES 117 7 A GRID OPERATING ENVIRONMENT FOR CDI 119 7 1 INTRODUCTION 119 7 2 GRID BASED SERVICE DEPLOYMENT 120 7 2 1 EVOLUTION OF THE ACXIOM GRID A CASE STUDY 120 7 2 2 SERVICES GRID 122 7 2 3 GRID MANAGEMENT 124 7 3 GRID BASED BATCH PROCESSING 127 7 3 1 WORKFLOW GRID 127 7 3 2 I O CONSTRAINTS 133 7 3 3 DATA GRID 135 7 3 4 DATABASE GRID 137 7 3 5 DATA MANAGEMENT 138 7 4 CONCLUSION 140 7 5 EXERCISES 141 8 PARALLEL FILE SYSTEMS 143 8 1 INTRODUCTION 143 8 2 COMMERCIAL DATA AND ACCESS PATTERNS 144 8 2 1 LARGE FILE ACCESS PATTERNS 145 8 2 2 FILE SYSTEM INTERFACES 146 8 3 BASICS OF PARALLEL FILE SYSTEMS 147 8 3 1 COMMON STORAGE SYSTEM HARDWARE 148 8 4 DESIGN CHALLENGES 149 8 4 1 PERFORMANCE 150 8 4 2 CONSISTENCY SEMANTICS 150 8 4 3 FAULT TOLERANCE 151 8 4 4 INTEROPERABILITY 152 8 4 5 MANAGEMENT TOOLS 153 8 4 6 TRADITIONAL DESIGN CHALLENGES 154 8 5 CASE STUDIES 154 8 5 1 MULTI PATH FILE SYSTEM MPFS 154 8 5 2 PARALLEL VIRTUAL FILE SYSTEM PVFS 157 8 5 3 THE GOOGLE FILE SYSTEM GFS 160 8 5 4 PNFS 163 8 6 CONCLUSION 167 8 7 EXERCISES 167 8 8 REFERENCES 168 9 PERFORMANCE MODELING OF ENTERPRISE GRIDS 169 9 1 INTRODUCTION AND BACKGROUND 169 9 1 1 PERFORMANCE MODELING 169 9 1 2 CAPACITY PLANNING TOOLS AND METHODOLOGY 171 9 2 MEASUREMENT COLLECTION AND PRELIMINARY ANALYSIS 173 9 3 WORKLOAD CHARACTERIZATION 174 9 3 1 K MEANS CLUSTERING 176 9 3 2 HIERARCHICAL WORKLOAD CHARACTERIZATION 181 9 3 3 OTHER ISSUES IN WORKLOAD CHARACTERIZATION 182 9 4 BASELINE SYSTEM MODELS AND TOOL CONSTRUCTION 184 9 4 1 ANALYTIC MODELS 184 9 4 2 SIMULATION TOOLS FOR ENTERPRISE GRID SYSTEMS 191 9 5 ENTERPRISE GRID CAPACITY PLANNING CASE STUDY 192 9 5 1 DATA COLLECTION AND PRELIMINARY ANALYSIS 194 9 5 2 WORKLOAD CHARACTERIZATION 194 9 5 3 DEVELOPMENT AND VALIDATION OF THE BASELINE MODEL 195 9 5 4 MODEL PREDICTIONS 196 9 6 SUMMARY 199 9 7 EXERCISES 199 9 8 REFERENCES 200 10 DELAY CHARACTERISTICS OF PACKET SWITCHED NETWORKS 203 10 1 INTRODUCTION 203 10 2 HIGH SPEED PACKET SWITCHING SYSTEMS 204 10 2 1 PACKET SWITCHED GENERAL ORGANIZATION 204 10 2 2 SWITCHING FABRIC STRUCTURES FOR PACKET SWITCHES 205 10 3 TECHNICAL BACKGROUND 207 10 3 1 PACKET SCHEDULING IN PACKET SWITCHES 207 10 3 2 INTRODUCTION TO NETWORK CALCULUS 208 10 2 3 QUEUING SCHEMES FOR PACKET SWITCHES 206 10 4 DELAY CHARACTERISTICS OF OUTPUT QUEUING SWITCHES 210 10 4 1 OUTPUT QUEUING SWITCH SYSTEM 210 10 4 2 OQ SWITCH MODELING AND ANALYSIS 211 10 4 3 OUTPUT QUEUING EMULATION FOR DELAY GUARANTEE 212 10 5 DELAY CHARACTERISTICS OF BUFFERED CROSSBAR SWITCHES 212 10 5 1 BUFFERED CROSSBAR SWITCH SYSTEM 212 10 5 2 MODELING TRAFFIC CONTROL IN BUFFERED CROSSBAR SWITCHES 214 10 5 3 DELAY ANALYSIS FOR BUFFERED CROSSBAR SWITCHES 215 10 5 4 NUMERICAL EXAMPLES 216 10 6 DELAY COMPARISON OF OUTPUT QUEUING TO BUFFERED CROSSBAR 217 10 6 1 MAXIMUM PACKET DELAY COMPARISON 217 10 6 2 BANDWIDTH ALLOCATION FOR DELAY PERFORMANCE GUARANTEES 218 10 6 3 NUMERICAL EXAMPLES 219 10 7 SUMMARY 221 10 8 EXERCISES 222 10 9 REFERENCES 222 11 KNOWLEDGE DISCOVERY IN TEXTUAL DATABASES A CONCEPT ASSOCIATION MINING APPROACH 225 11 1 INTRODUCTION 225 11 1 1 GRAPH REPRESENTATION 228 11 2 METHOD 228 11 2 1 CONCEPT BASED ASSOCIATION RULE MINING APPROACH 228 11 2 2 CONCEPT EXTRACTION 229 11 2 3 MINING CONCEPT ASSOCIATIONS 231 11 2 4 GENERATING A DIRECTED GRAPH OF CONCEPT ASSOCIATIONS 231 11 3 EXPERIMENTS AND RESULTS 233 11 3 1 ISOLATED WORDS VS MULTI WORD CONCEPTS 233 11 3 2 NEW METRICS VS THE TRADITIONAL SUPPORT CONFIDENCE 235 11 4 CONCLUSIONS 240 11 5 EXAMPLES 241 11 6 EXERCISES 242 11 7 REFERENCES 242 12 MINING E DOCUMENTS TO UNCOVER STRUCTURES 245 12 1 INTRODUCTION 245 12 2 RELATED RESEARCH 246 12 3 DISCOVERY OF THE PHYSICAL STRUCTURE 247 12 3 1 PARAGRAPH 247 12 3 2 HEADING 248 12 3 3 TABLE 252 12 3 4 IMAGE 253 12 3 5 CAPTURING THE PHYSICAL STRUCTURE OF AN E DOCUMENT 254 12 4 DISCOVERY OF THE EXPLICIT TERMS USING ONTOLOGY 263 12 4 1 THE STEMMER 264 12 4 2 THE ONTOLOGY 264 12 4 3 DISCOVERY PROCESS 266