Jure Leskovec Stanford Univ

CONTENTS

ix

3.2.2

Choosing the Shingle Size . . . . . . . . . . . . . . . . . . 78

3.2.3

Hashing Shingles . . . . . . . . . . . . . . . . . . . . . . . 79

3.2.4

Shingles Built from Words . . . . . . . . . . . . . . . . . . 79

3.2.5

Exercises for Section 3.2 . . . . . . . . . . . . . . . . . . . 80

3.3

Similarity-Preserving Summaries of Sets . . . . . . . . . . . . . . 80

3.3.1

Matrix Representation of Sets . . . . . . . . . . . . . . . . 81

3.3.2

Minhashing . . . . . . . . . . . . . . . . . . . . . . . . . . 81

3.3.3

Minhashing and Jaccard Similarity . . . . . . . . . . . . . 82

3.3.4

Minhash Signatures . . . . . . . . . . . . . . . . . . . . . 83

3.3.5

Computing Minhash Signatures . . . . . . . . . . . . . . . 83

3.3.6

Exercises for Section 3.3 . . . . . . . . . . . . . . . . . . . 86

3.4

Locality-Sensitive Hashing for Documents . . . . . . . . . . . . . 87

3.4.1

LSH for Minhash Signatures

. . . . . . . . . . . . . . . . 88

3.4.2

Analysis of the Banding Technique . . . . . . . . . . . . . 89

3.4.3

Combining the Techniques . . . . . . . . . . . . . . . . . . 91

3.4.4

Exercises for Section 3.4 . . . . . . . . . . . . . . . . . . . 91

3.5

Distance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . 92

3.5.1

Definition of a Distance Measure . . . . . . . . . . . . . . 92

3.5.2

Euclidean Distances . . . . . . . . . . . . . . . . . . . . . 93

3.5.3

Jaccard Distance . . . . . . . . . . . . . . . . . . . . . . . 94

3.5.4

Cosine Distance . . . . . . . . . . . . . . . . . . . . . . . . 95

3.5.5

Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . 95

3.5.6

Hamming Distance . . . . . . . . . . . . . . . . . . . . . . 96

3.5.7

Exercises for Section 3.5 . . . . . . . . . . . . . . . . . . . 97

3.6

The Theory of Locality-Sensitive Functions . . . . . . . . . . . . 99

3.6.1

Locality-Sensitive Functions . . . . . . . . . . . . . . . . . 99

3.6.2

Locality-Sensitive Families for Jaccard Distance . . . . . . 100

3.6.3

Amplifying a Locality-Sensitive Family . . . . . . . . . . . 101

3.6.4

Exercises for Section 3.6 . . . . . . . . . . . . . . . . . . . 103

3.7

LSH Families for Other Distance Measures . . . . . . . . . . . . . 104

3.7.1

LSH Families for Hamming Distance . . . . . . . . . . . . 104

3.7.2

Random Hyperplanes and the Cosine Distance . . . . . . 105

3.7.3

Sketches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

3.7.4

LSH Families for Euclidean Distance . . . . . . . . . . . . 107

3.7.5

More LSH Families for Euclidean Spaces . . . . . . . . . . 108

3.7.6

Exercises for Section 3.7 . . . . . . . . . . . . . . . . . . . 109

3.8

Applications of Locality-Sensitive Hashing . . . . . . . . . . . . . 110

3.8.1

Entity Resolution . . . . . . . . . . . . . . . . . . . . . . . 110

3.8.2

An Entity-Resolution Example . . . . . . . . . . . . . . . 111

3.8.3

Validating Record Matches . . . . . . . . . . . . . . . . . 112

3.8.4

Matching Fingerprints . . . . . . . . . . . . . . . . . . . . 113

3.8.5

A LSH Family for Fingerprint Matching . . . . . . . . . . 114

3.8.6

Similar News Articles . . . . . . . . . . . . . . . . . . . . 115

3.8.7

Exercises for Section 3.8 . . . . . . . . . . . . . . . . . . . 117

3.9

Methods for High Degrees of Similarity

. . . . . . . . . . . . . . 118

---

x

CONTENTS

3.9.1

Finding Identical Items . . . . . . . . . . . . . . . . . . . 118

3.9.2

Representing Sets as Strings . . . . . . . . . . . . . . . . . 118

3.9.3

Length-Based Filtering . . . . . . . . . . . . . . . . . . . . 119

3.9.4

Prefix Indexing . . . . . . . . . . . . . . . . . . . . . . . . 119

3.9.5

Using Position Information . . . . . . . . . . . . . . . . . 121

3.9.6

Using Position and Length in Indexes . . . . . . . . . . . 122

3.9.7

Exercises for Section 3.9 . . . . . . . . . . . . . . . . . . . 125

3.10 Summary of Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . 126

3.11 References for Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . 128

4

Mining Data Streams

131

4.1

The Stream Data Model . . . . . . . . . . . . . . . . . . . . . . . 131

4.1.1

A Data-Stream-Management System . . . . . . . . . . . . 132

4.1.2

Examples of Stream Sources . . . . . . . . . . . . . . . . . 133

4.1.3

Stream Queries . . . . . . . . . . . . . . . . . . . . . . . . 134

4.1.4

Issues in Stream Processing . . . . . . . . . . . . . . . . . 135

4.2

Sampling Data in a Stream . . . . . . . . . . . . . . . . . . . . . 136

4.2.1

A Motivating Example . . . . . . . . . . . . . . . . . . . . 136

4.2.2

Obtaining a Representative Sample . . . . . . . . . . . . . 137

4.2.3

The General Sampling Problem . . . . . . . . . . . . . . . 137

4.2.4

Varying the Sample Size . . . . . . . . . . . . . . . . . . . 138

4.2.5

Exercises for Section 4.2 . . . . . . . . . . . . . . . . . . . 138

4.3

Filtering Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

4.3.1

A Motivating Example . . . . . . . . . . . . . . . . . . . . 139

4.3.2

The Bloom Filter . . . . . . . . . . . . . . . . . . . . . . . 140

4.3.3

Analysis of Bloom Filtering . . . . . . . . . . . . . . . . . 140

4.3.4

Exercises for Section 4.3 . . . . . . . . . . . . . . . . . . . 141

4.4

Counting Distinct Elements in a Stream . . . . . . . . . . . . . . 142

4.4.1

The Count-Distinct Problem . . . . . . . . . . . . . . . . 142

4.4.2

The Flajolet-Martin Algorithm . . . . . . . . . . . . . . . 143

4.4.3

Combining Estimates . . . . . . . . . . . . . . . . . . . . 144

4.4.4

Space Requirements . . . . . . . . . . . . . . . . . . . . . 144

4.4.5

Exercises for Section 4.4 . . . . . . . . . . . . . . . . . . . 145

4.5

Estimating Moments . . . . . . . . . . . . . . . . . . . . . . . . . 145

4.5.1

Definition of Moments . . . . . . . . . . . . . . . . . . . . 145

4.5.2

The Alon-Matias-Szegedy Algorithm for Second

Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

4.5.3

Why the Alon-Matias-Szegedy Algorithm Works . . . . . 147

4.5.4

Higher-Order Moments . . . . . . . . . . . . . . . . . . . 148

4.5.5

Dealing With Infinite Streams . . . . . . . . . . . . . . . . 148

4.5.6

Exercises for Section 4.5 . . . . . . . . . . . . . . . . . . . 149

4.6

Counting Ones in a Window . . . . . . . . . . . . . . . . . . . . . 150

4.6.1

The Cost of Exact Counts . . . . . . . . . . . . . . . . . . 151

4.6.2

The Datar-Gionis-Indyk-Motwani Algorithm . . . . . . . 151

4.6.3

Storage Requirements for the DGIM Algorithm . . . . . . 153

---