Data-IntensiveTextProcessingwithMapReduceJimmyLinandChrisDyer

5星 · 超过95%的资源需积分: 10 126 浏览量更新于2023-03-16 评论收藏 1.72MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

Contents 1 Introduction 1.1 Computing in the Clouds 1.2 Big Ideas 1.3 Why Is This Dierent? 1.4 What This Book Is Not 2 MapReduce Basics 2.1 Functional Programming Roots 2.2 Mappers and Reducers 2.3 The Execution Framework 2.4 Partitioners and Combiners 2.5 The Distributed File System 2.6 Hadoop Cluster Architecture 2.7 Summary 3 MapReduce Algorithm Design 3.1 Local Aggregation 3.1.1 Combiners and In-Mapper Combining 3.1.2 Algorithmic Correctness with Local Aggregation 3.2 Pairs and Stripes 3.3 Computing Relative Frequencies 3.4 Secondary Sorting 3.5 Relational Joins 3.5.1 Reduce-Side Join 64 3.5.2 Map-Side Join 66 3.5.3 Memory-Backed Join 67 3.6 Summary 4 Inverted Indexing for Text Retrieval 4.1 Web Crawling 4.2 Inverted Indexes 4.3 Inverted Indexing: Baseline Implementation 4.4 Inverted Indexing: Revised Implementation 4.5 Index Compression 4.5.1 Byte-Aligned and Word-Aligned Codes 80 4.5.2 Bit-Aligned Codes 82 4.5.3 Postings Compression 84 4.6 What About Retrieval? 4.7 Summary and Additional Readings 5 Graph Algorithms 5.1 Graph Representations 5.2 Parallel Breadth-First Search 5.3 PageRank 5.4 Issues with Graph Processing 5.5 Summary and Additional Readings 6 EM Algorithms for Text Processing 6.1 Expectation Maximization 6.1.1 Maximum Likelihood Estimation 115 6.1.2 A Latent Variable Marble Game 117 6.1.3 MLE with Latent Variables 118 6.1.4 Expectation Maximization 119 6.1.5 An EM Example 120 6.2 Hidden Markov Models 6.2.1 Three Questions for Hidden Markov Models 123 6.2.2 The Forward Algorithm 125 6.2.3 The Viterbi Algorithm 126 6.2.4 Parameter Estimation for HMMs 129 6.2.5 Forward-Backward Training: Summary 133 6.3 EM in MapReduce 6.3.1 HMM Training in MapReduce 135 6.4 Case Study: Word Alignment for Statistical Machine Translation 6.4.1 Statistical Phrase-Based Translation 6.4.2 Brief Digression: Language Modeling with MapReduce 6.4.3 Word Alignment 6.4.4 Experiments 6.5 EM-Like Algorithms 6.5.1 Gradient-Based Optimization and Log-Linear Models 6.6 Summary and Additional Readings 7 Closing Remarks 7.1 Limitations of MapReduce 7.2 Alternative Computing Paradigms 7.3 MapReduce and Beyond

资源详情

资源评论

资源推荐

Data-Intensive Text Processing

with MapReduce

Jimmy Lin and Chris Dyer

University of Maryland, College Park

Manuscript prepared April 11, 2010

This is the pre-production manuscript of a book in the Morgan & Claypool Synthesis

Lectures on Human Language Technologies. Anticipated publication date is mid-2010.

Contents

Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Computing in the Clouds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6

1.2 Big Ideas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

1.3 Why Is This Diﬀerent? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.4 What This Book Is Not . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

MapReduce Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1 Functional Programming Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2 Mappers and Reducers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3 The Execution Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4 Partitioners and Combiners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.5 The Distributed File System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.6 Hadoop Cluster Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

MapReduce Algorithm Design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.1 Local Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.1.1 Combiners and In-Mapper Combining 41

3.1.2 Algorithmic Correctness with Local Aggregation 46

3.2 Pairs and Stripes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50

3.3 Computing Relative Frequencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.4 Secondary Sorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60

3.5 Relational Joins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.5.1 Reduce-Side Join 64

3.5.2 Map-Side Join 66

3.5.3 Memory-Backed Join 67

CONTENTS iii

3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Inverted Indexing for Text Retrieval. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70

4.1 Web Crawling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71

4.2 Inverted Indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.3 Inverted Indexing: Baseline Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

4.4 Inverted Indexing: Revised Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . .77

4.5 Index Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.5.1 Byte-Aligned and Word-Aligned Codes 80

4.5.2 Bit-Aligned Codes 82

4.5.3 Postings Compression 84

4.6 What About Retrieval? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.7 Summary and Additional Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Graph Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91

5.1 Graph Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

5.2 Parallel Breadth-First Search. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .94

5.3 PageRank. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102

5.4 Issues with Graph Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

5.5 Summary and Additional Readings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .110

EM Algorithms for Text Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

6.1 Expectation Maximization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

6.1.1 Maximum Likelihood Estimation 115

6.1.2 A Latent Variable Marble Game 117

6.1.3 MLE with Latent Variables 118

6.1.4 Expectation Maximization 119

6.1.5 An EM Example 120

6.2 Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

6.2.1 Three Questions for Hidden Markov Models 123

6.2.2 The Forward Algorithm 125

6.2.3 The Viterbi Algorithm 126

C H A P T E R 1

Introduction

MapReduce [45] is a programming model for expressing distributed computations on

massive amounts of data and an execution framework for large-scale data processing

on clusters of commodity servers. It was originally developed by Google and built on

well-known principles in parallel and distributed processing dating back several decades.

MapReduce has since enjoyed widespread adoption via an open-source implementation

called Hadoop, whose development was led by Yahoo (now an Apache project). Today,

a vibrant software ecosystem has sprung up around Hadoop, with signiﬁcant activity

in both industry and academia.

This book is about scalable approaches to processing large amounts of text with

MapReduce. Given this focus, it makes sense to start with the most basic question:

Why? There are many answers to this question, but we focus on two. First, “big data”

is a fact of the world, and therefore an issue that real-world systems must grapple with.

Second, across a wide range of text processing applications, more data translates into

more eﬀective algorithms, and thus it makes sense to take advantage of the plentiful

amounts of data that surround us.

Modern information societies are deﬁned by vast repositories of data, both public

and private. Therefore, any practical application must be able to scale up to datasets

of interest. For many, this means scaling up to the web, or at least a non-trivial frac-

tion thereof. Any organization built around gathering, analyzing, monitoring, ﬁltering,

searching, or organizing web content must tackle large-data problems: “web-scale” pro-

cessing is practically synonymous with data-intensive processing. This observation ap-

plies not only to well-established internet companies, but also countless startups and

niche players as well. Just think, how many companies do you know that start their

pitch with “we’re going to harvest information on the web and. . . ”?

Another strong area of growth is the analysis of user behavior data. Any operator

of a moderately successful website can record user activity and in a matter of weeks (or

sooner) be drowning in a torrent of log data. In fact, logging user behavior generates

so much data that many organizations simply can’t cope with the volume, and either

turn the functionality oﬀ or throw away data after some time. This represents lost

opportunities, as there is a broadly-held belief that great value lies in insights derived

from mining such data. Knowing what users look at, what they click on, how much

time they spend on a web page, etc. leads to better business decisions and competitive

advantages. Broadly, this is known as business intelligence, which encompasses a wide

range of technologies including data warehousing, data mining, and analytics.

剩余174页未读，继续阅读

xf457hby

2015-09-12

正需要，挺好的一本书，做大数据处理的时候很有参考价值

yiyiwangjie

粉丝: 4
资源: 15

会员权益专享

Data-Intensive Text Processing with MapReduce Jimmy Lin and Chri...

评论2

会员权益专享

最新资源

Data-Intensive Text Processing with MapReduce Jimmy Lin and Chri...

评论2

mapreduce相关文献

designing data-intensive applications pdf

Designing Data-Intensive Applications The Big Ideas Behind Reliable Scalable

design data-intensive application 电子版

云计算 mapreduce - <Data-Intensive[1].Text.Processing.With.MapReduce>

Spark for Python Developers 无水印pdf 0分

Data Science at the Command Line

Spark for Python Developers

Data Intensive Computing Applications for Big Data 无水印原版pdf

推荐几本分布式数据库的书籍

k-means mean shift

Verilog fifo

Asynchronous Android Programming

JavaScript Concurrency pdf 无水印 0分

esp32s3 arduino psram arduino

thread pool

会员权益专享

最新资源