Disk-based algorithms for big data

Disk-Based Algorithms for Big Data is a product of recent advances in the areas of big data, data analytics, and the underlying file systems and data management algorithms used to support the storage and analysis of massive data collections. The book discusses hard disks and their impact on data management, since Hard Disk Drives continue to be common in large data clusters. It also explores ways to store and retrieve data though primary and secondary indices. This includes a review of different in-memory sorting and searching algorithms that build a foundation for more sophisticated on-disk approaches like mergesort, B-trees, and extendible hashing. Following this introduction, the book transitions to more recent topics, including advanced storage technologies like solid-state drives and holographic storage; peer-to-peer (P2P) communication; large file systems and query languages like Hadoop/HDFS, Hive, Cassandra, and Presto; and NoSQL databases like Neo4j for graph structures and MongoDB for unstructured document data. Designed for senior undergraduate and graduate students, as well as professionals, this book is useful for anyone interested in understanding the foundations and advances in big data storage and management, and big data analytics. **About the Author** Dr. Christopher G. Healey is a tenured Professor in the Department of Computer Science and the Goodnight Distinguished Professor of Analytics in the Institute for Advanced Analytics, both at North Carolina State University in Raleigh, North Carolina. He has published over 50 articles in major journals and conferences in the areas of visualization, visual and data analytics, computer graphics, and artificial intelligence. He is a recipient of the National Science Foundation’s CAREER Early Faculty Development Award and the North Carolina State University Outstanding Instructor Award. He is a Senior Member of the Association for Computing Machinery (ACM) and the Institute of Electrical and Electronics Engineers (IEEE), and an Associate Editor of ACM Transaction on Applied Perception, the leading worldwide journal on the application of human perception to issues in computer science. Cover 1 Half Title 2 Title Page 4 Copyright Page 5 Dedication 6 Table of Contents 8 List of Tables 16 List of Figures 18 Preface 20 Chapter 1: Physical Disk Storage 22 1.1 PHYSICAL HARD DISK 23 1.2 CLUSTERS 23 1.2.1 Block Allocation 24 1.3 ACCESS COST 25 1.4 LOGICAL TO PHYSICAL 26 1.5 BUFFER MANAGEMENT 27 Chapter 2: File Management 30 2.1 LOGICAL COMPONENTS 30 2.1.1 Positioning Components 31 2.2 IDENTIFYING RECORDS 33 2.2.1 Secondary Keys 33 2.3 SEQUENTIAL ACCESS 34 2.3.1 Improvements 34 2.4 DIRECT ACCESS 35 2.4.1 Binary Search 36 2.5 FILE MANAGEMENT 37 2.5.1 Record Deletion 37 2.5.2 Fixed-Length Deletion 38 2.5.3 Variable-Length Deletion 40 2.6 FILE INDEXING 41 2.6.1 Simple Indices 41 2.6.2 Index Management 42 2.6.3 Large Index Files 43 2.6.4 Secondary Key Index 43 2.6.5 Secondary Key Index Improvements 45 Chapter 3: Sorting 48 3.1 HEAPSORT 48 3.2 MERGESORT 53 3.3 TIMSORT 55 Chapter 4: Searching 58 4.1 LINEAR SEARCH 58 4.2 BINARY SEARCH 59 4.3 BINARY SEARCH TREE 59 4.4 k-d TREE 61 4.4.1 k-d Tree Index 62 4.4.2 Search 64 4.4.3 Performance 65 4.5 HASHING 65 4.5.1 Collisions 65 4.5.2 Hash Functions 66 4.5.3 Hash Value Distributions 67 4.5.4 Estimating Collisions 68 4.5.5 Managing Collisions 69 4.5.6 Progressive Overflow 69 4.5.7 Multirecord Buckets 71 Chapter 5: Disk-Based Sorting 74 5.1 DISK-BASED MERGESORT 75 5.1.1 Basic Mergesort 75 5.1.2 Timing 76 5.1.3 Scalability 77 5.2 INCREASED MEMORY 78 5.3 MORE HARD DRIVES 78 5.4 MULTISTEP MERGE 79 5.5 INCREASED RUN LENGTHS 80 5.5.1 Replacement Selection 80 5.5.2 Average Run Size 82 5.5.3 Cost 82 5.5.4 Dual Hard Drives 82 Chapter 6: Disk-Based Searching 84 6.1 IMPROVED BINARY SEARCH 84 6.1.1 Self-Correcting BSTs 85 6.1.2 Paged BSTs 85 6.2 B-TREE 87 6.2.1 Search 89 6.2.2 Insertion 89 6.2.3 Deletion 91 6.3 B* TREE 92 6.4 B+ TREE 94 6.4.1 Prefix Keys 95 6.5 EXTENDIBLE HASHING 96 6.5.1 Trie 97 6.5.2 Radix Tree 97 6.6 HASH TRIES 97 6.6.1 Trie Insertion 99 6.6.2 Bucket Insertion 100 6.6.3 Full Trie 100 6.6.4 Trie Size 100 6.6.5 Trie Deletion 101 6.6.6 Trie Performance 102 Chapter 7: Storage Technology 104 7.1 OPTICAL DRIVES 105 7.1.1 Compact Disc 105 7.1.2 Digital Versatile Disc 106 7.1.3 Blu-ray Disc 106 7.2 SOLID STATE DRIVES 107 7.2.1 Floating Gate Transistors 108 7.2.2 Read–Write–Erase 109 7.2.3 SSD Controller 109 7.2.4 Advantages 110 7.3 HOLOGRAPHIC STORAGE 110 7.3.1 Holograms 110 7.3.2 Data Holograms 112 7.3.3 Commercialization 112 7.4 MOLECULAR MEMORY 112 7.5 MRAM 114 Chapter 8: Distributed Hash Tables 116 8.1 HISTORY 117 8.2 KEYSPACE 117 8.3 KEYSPACE PARTITIONING 118 8.4 OVERLAY NETWORK 118 8.5 CHORD 118 8.5.1 Keyspace 119 8.5.2 Keyspace Partitioning 119 8.5.3 Overlay Network 120 8.5.4 Addition 121 8.5.5 Failure 121 Chapter 9: Large File Systems 122 9.1 RAID 122 9.1.1 Parity 123 9.2 ZFS 124 9.2.1 Fault Tolerance 125 9.2.2 Self-Healing 125 9.2.3 Snapshots 125 9.3 GFS 126 9.3.1 Architecture 126 9.3.2 Master Metadata 127 9.3.3 Mutations 127 9.3.4 Fault Tolerance 128 9.4 HADOOP 128 9.4.1 MapReduce 129 9.4.2 MapReduce Implementation 130 9.4.3 HDFS 131 9.4.4 Pig 132 9.4.5 Hive 136 9.5 CASSANDRA 137 9.5.1 Design 138 9.5.2 Improvements 140 9.5.3 Query Language 141 9.6 PRESTO 142 Chapter 10: NoSQL Storage 146 10.1 GRAPH DATABASES 147 10.1.1 Neo4j 147 10.1.2 Caching 149 10.1.3 Query Languages 150 10.2 DOCUMENT DATABASES 151 10.2.1 SQL Versus NoSQL 152 10.2.2 MongoDB 153 10.2.3 Indexing 155 10.2.4 Query Languages 156 Appendix A: Order Notation 158 A.1 Θ-NOTATION 158 A.2 O-NOTATION 159 A.3 Ω-NOTATION 160 A.4 INSERTION SORT 160 A.5 SHELL SORT 162 Appendix B: Assignment 1: Search 166 B.1 KEY AND SEEK LISTS 167 B.2 PROGRAM EXECUTION 167 B.3 IN-MEMORY SEQUENTIAL SEARCH 168 B.4 IN-MEMORY BINARY SEARCH 168 B.5 ON-DISK SEQUENTIAL SEARCH 169 B.6 ON-DISK BINARY SEARCH 169 B.7 PROGRAMMING ENVIRONMENT 170 B.7.1 Reading Binary Integers 170 B.7.2 Measuring Time 171 B.7.3 Writing Results 171 B.8 SUPPLEMENTAL MATERIAL 172 B.9 HAND-IN REQUIREMENTS 172 Appendix C: Assignment 2: Indices 174 C.1 STUDENT FILE 174 C.2 PROGRAM EXECUTION 176 C.3 IN-MEMORY PRIMARY KEY INDEX 176 C.4 IN-MEMORY AVAILABILITY LIST 177 C.4.1 First Fit 178 C.4.2 Best Fit 178 C.4.3 Worst Fit 178 C.5 USER INTERFACE 179 C.5.1 Add 179 C.5.2 Find 180 C.5.3 Del 180 C.5.4 End 180 C.6 PROGRAMMING ENVIRONMENT 180 C.6.1 Writing Results 181 C.7 SUPPLEMENTAL MATERIAL 181 C.8 HAND-IN REQUIREMENTS 182 Appendix D: Assignment 3: Mergesort 184 D.1 INDEX FILE 184 D.2 PROGRAM EXECUTION 185 D.3 AVAILABLE MEMORY 185 D.4 BASIC MERGESORT 185 D.5 MULTISTEP MERGESORT 186 D.6 REPLACEMENT SELECTION MERGESORT 187 D.7 PROGRAMMING ENVIRONMENT 188 D.7.1 Measuring Time 188 D.7.2 Writing Results 189 D.8 SUPPLEMENTAL MATERIAL 189 D.9 HAND-IN REQUIREMENTS 189 Appendix E: Assignment 4: B-Trees 192 E.1 INDEX FILE 192 E.2 PROGRAM EXECUTION 193 E.3 B-TREE NODES 193 E.3.1 Root Node Offset 194 E.4 USER INTERFACE 194 E.4.1 Add 195 E.4.2 Find 195 E.4.3 Print 196 E.4.4 End 196 E.5 PROGRAMMING ENVIRONMENT 196 E.6 SUPPLEMENTAL MATERIAL 197 E.7 HAND-IN REQUIREMENTS 197 Index 200 Designed for senior undergraduate and graduate students, as well as professionals, this book provides a foundational discussion of physical storage devices and explains how algorithm performance is affected by the underlying storage system. -- Edited summary from book