## Mathematics of Big Data

### Spreadsheets, Databases, Matrices, and Graphs

by Kepner, Jananthan

### Instructor Requests

Expand/Collapse All
Contents (pg. vii)
Foreword (pg. xi)
Preface (pg. xiii)
Acknowledgments (pg. xxiii)
I APPLICATIONS AND PRACTICE (pg. 1)
1 Introduction and Overview (pg. 3)
1.1 Mathematics of Data (pg. 3)
1.2 Data in the World (pg. 5)
1.3 Mathematical Foundations (pg. 9)
1.4 Making Data Rigorous (pg. 14)
1.5 Conclusions, Exercises, and References (pg. 16)
2 Perspectives on Data (pg. 19)
2.1 Interrelations (pg. 19)
2.3 Databases (pg. 22)
2.4 Matrices (pg. 26)
2.5 Graphs (pg. 27)
2.6 Map Reduce (pg. 29)
2.7 Other Perspectives (pg. 30)
2.8 Conclusions, Exercises, and References (pg. 31)
3 Dynamic Distributed Dimensional Data Model (pg. 37)
3.1 Background (pg. 37)
3.2 Design (pg. 38)
3.3 Matrix Mathematics (pg. 39)
3.4 Common SQL, NoSQL, NewSQL Interface (pg. 40)
3.5 Key-Value Store Database Schema (pg. 41)
3.6 Data-Independent Analytics (pg. 44)
3.7 Parallel Performance (pg. 49)
3.8 Computing on Masked Data (pg. 51)
3.9 Conclusions, Exercises, and References (pg. 53)
4 Associative Arrays and Musical Metadata (pg. 57)
4.1 Data and Metadata (pg. 57)
4.2 Dense Data (pg. 58)
4.3 Dense Operations (pg. 60)
4.4 Sparse Data (pg. 62)
4.5 Sparse Operations (pg. 63)
4.6 Conclusions, Exercises, and References (pg. 65)
5 Associative Arrays and Abstract Art (pg. 69)
5.1 Visual Abstraction (pg. 69)
5.2 Minimal Adjacency Array (pg. 71)
5.3 Symmetric Adjacency Array (pg. 73)
5.4 Weighted Adjacency Array (pg. 75)
5.5 Incidence Array (pg. 75)
5.6 Conclusions, Exercises, and References (pg. 78)
6 Manipulating Graphs with Matrices (pg. 81)
6.1 Introduction (pg. 81)
6.2 Matrix Indices and Values (pg. 86)
6.3 Composable Graph Operations and Linear Systems (pg. 89)
6.4 Matrix Graph Operations Overview (pg. 96)
6.5 Graph Algorithms and Diverse Semirings (pg. 105)
6.6 Conclusions, Exercises, and References (pg. 108)
7 Graph Analysis and Machine Learning Systems (pg. 115)
7.1 Introduction (pg. 115)
7.2 Data Representation (pg. 116)
7.3 Graph Construction (pg. 118)
7.4 Adjacency Array Graph Traversal (pg. 120)
7.5 Incidence Array Graph Traversal (pg. 122)
7.6 Vertex Degree Centrality (pg. 126)
7.7 Edge Degree Centrality (pg. 129)
7.8 Eigenvector Centrality (pg. 129)
7.9 Singular Value Decomposition (pg. 133)
7.10 PageRank (pg. 136)
7.11 Deep Neural Networks (pg. 138)
7.12 Conclusions, Exercises, and References (pg. 140)
II MATHEMATICAL FOUNDATIONS (pg. 145)
8 Visualizing the Algebra of Associative Arrays (pg. 147)
8.1 Associative Array Analogs of Matrix Operations (pg. 147)
8.2 Abstract Algebra for Computer Scientists and Engineers (pg. 150)
8.3 Depicting Mathematics (pg. 152)
8.4 Associative Array Class Diagrams (pg. 153)
8.5 Set (pg. 154)
8.6 Semiring (pg. 155)
8.7 Linear Algebra (pg. 158)
8.8 Ordered Sets (pg. 160)
8.9 Boolean Algebra (pg. 162)
8.10 Associative Array Algebra (pg. 164)
8.11 Conclusions, Exercises, and References (pg. 164)
9 Defining the Algebra of Associative Arra (pg. 169)
9.1 Operations on Sets (pg. 169)
9.2 Ordered Sets (pg. 175)
9.3 Supremum and Infimum (pg. 177)
9.4 Lattice (pg. 181)
9.5 The Semirings of Interest (pg. 186)
9.6 Conclusions, Exercises, and References (pg. 189)
10 Structural Properties of Associative Arrays (pg. 193)
10.1 Estimating Structure (pg. 193)
10.2 Associative Array Formal Definition (pg. 194)
10.3 Padding Associative Arrays with Zeros (pg. 197)
10.4 Zero, Null, Zero-Sum-Free (pg. 198)
10.5 Properties of Matrices and Associative Arrays (pg. 199)
10.6 Properties of Zero Padding (pg. 201)
10.7 Support and Size (pg. 207)
10.8 Image and Rank (pg. 208)
10.9 Example: Music (pg. 209)
10.10 Example: Art (pg. 211)
10.11 Properties of Element-Wise Addition (pg. 213)
10.12 Properties of Element-Wise Multiplication (pg. 217)
10.13 Array Multiplication (pg. 221)
10.14 Closure of Operations between Arrays (pg. 228)
10.15 Conclusions, Exercises, and References (pg. 229)
11 Graph Construction and Graphical Patterns (pg. 235)
11.1 Introduction (pg. 235)
11.2 Adjacency and Incidence Array Definitions (pg. 236)
11.3 Adjacency Array Construction (pg. 242)
11.4 Graph Construction with Different Semirings (pg. 250)
11.5 Special Arrays and Graphs (pg. 255)
11.6 Key Ordering (pg. 258)
11.7 Algebraic Properties (pg. 263)
11.8 Subobject Properties (pg. 264)
11.9 Conclusions, Exercises, and References (pg. 266)
III LINEAR SYSTEMS (pg. 269)
12 Survey of Common Transformations (pg. 271)
12.1 Array Transformations (pg. 271)
12.2 Identity (pg. 274)
12.3 Contraction (pg. 290)
12.4 Stretching (pg. 293)
12.5 Rotation (pg. 297)
12.6 Conclusions, Exercises, and References (pg. 299)
13 Maps and Bases (pg. 303)
13.1 Semimodules (pg. 303)
13.2 Linear Maps (pg. 307)
13.3 Linear Independence and Bases (pg. 309)
13.4 Existence of Bases (pg. 312)
13.5 Size of Bases (pg. 313)
13.6 Semialgebras and the Algebra of Arrays (pg. 317)
13.7 Conclusions, Exercises, and References (pg. 320)
14 Linearity of Associative Arrays (pg. 323)
14.1 The Null Space of Linear Maps (pg. 323)
14.2 Supremum-Blank Algebras (pg. 326)
14.3 Max-Blank Structure Theorem (pg. 334)
14.4 Examples of Supremum-Blank Algebras (pg. 338)
14.5 Explicit Computations of x(A,w) for Supremum-Blank Algebras (pg. 342)
14.6 Conclusions, Exercises, and References (pg. 348)
15 Eigenvalues and Eigenvectors (pg. 351)
15.1 Introduction (pg. 351)
15.2 Quasi-Inverses (pg. 353)
15.3 Existence of Eigenvalues for Idempotent Multiplication (pg. 359)
15.4 Strong Dependence and Characteristic Bipolynomial (pg. 360)
15.5 Eigenanalysis for Irreducible Matrices for Invertible Multiplication (pg. 367)
15.6 Eigen-Semimodules (pg. 373)
15.7 Singular Value Decomposition (pg. 378)
15.8 Conclusions, Exercises, and References (pg. 385)
16 Higher Dimensions (pg. 389)
16.1 d-Dimensional Associative Arrays (pg. 389)
16.2 Key Ordering and Two-Dimensional Projections (pg. 392)
16.3 Algebraic Properties (pg. 398)
16.4 Sub-Array Properties (pg. 400)
16.5 Conclusions, Exercises, and References (pg. 402)
Appendix: Notation (pg. 405)
Index (pg. 413)

#### Jeremy Kepner

Jeremy Kepner is an MIT Lincoln Laboratory Fellow, Founder and Head of the MIT Lincoln Laboratory Supercomputing Center, and Research Affiliate in MIT's Mathematics Department.

#### Hayden Jananthan

Hayden Jananthan is a PhD candidate in the Department of Mathematics at Vanderbilt University.

Instructors Only
You must have an instructor account and submit a request to access instructor materials for this book.
eTextbook

• Highlighting
• Bookmarking
• Note-taking