Explore
For Enterprise
Join for Free
Log In

瀏覽
搜索
企業版
登錄
免費加入

MapReduce Examples: Inverted Index, Join

Loading...

大规模数据处理：系统与算法

华盛顿大学

4.3（698 個評分） | 49K 名學生已註冊

課程 1（共 4 門，大规模数据科学專項課程）

Data analysis has replaced data acquisition as the bottleneck to evidence-based decision making --- we are drowning in it. Extracting knowledge from large, heterogeneous, and noisy datasets requires not only powerful computing resources, but the programming abstractions to use them effectively. The abstractions that emerged in the last decade blend ideas from parallel databases, distributed systems, and programming languages to create a new class of scalable data analytics platforms that form the foundation for data science at realistic scales. In this course, you will learn the landscape of relevant systems, the principles on which they rely, their tradeoffs, and how to evaluate their utility against your requirements. You will learn how practical systems were derived from the frontier of research in computer science and what systems are coming on the horizon. Cloud computing, SQL and NoSQL databases, MapReduce and the ecosystem it spawned, Spark and its contemporaries, and specialized systems for graphs and arrays will be covered. You will also learn the history and context of data science, the skills, challenges, and methodologies the term implies, and how to structure a data science project. At the end of this course, you will be able to: Learning Goals: 1. Describe common patterns, challenges, and approaches associated with data science projects, and what makes them different from projects in related fields. 2. Identify and use the programming models associated with scalable data manipulation, including relational algebra, mapreduce, and other data flow models. 3. Use database technology adapted for large-scale analytics, including the concepts driving parallel databases, parallel query processing, and in-database analytics 4. Evaluate key-value stores and NoSQL systems, describe their tradeoffs with comparable systems, the details of important examples in the space, and future trends. 5. “Think” in MapReduce to effectively write algorithms for systems including Hadoop and Spark. You will understand their limitations, design details, their relationship to databases, and their associated ecosystem of algorithms, extensions, and languages. write programs in Spark 6. Describe the landscape of specialized Big Data systems for graphs, arrays, and streams

查看授課大綱

您將學習的技能

Relational Algebra, Python Programming, Mapreduce, SQL

審閱

4.3（698 個評分）

5 stars
397 ratings
4 stars
183 ratings
3 stars
67 ratings
2 stars
33 ratings
1 star
18 ratings

DK

Jan 24, 2016

Good! I like the final (optional) project on running on a large dataset through EC2. The lectures aren't as polished and compact as they could be but certainly a very valuable course.

LG

Jun 20, 2017

Comprehensive and clear explanation of theory and interlinks of the up-to-date tools, languages, tendencies. Kudos and thanks to Bill Howe.\n\nHighly recommended.

從本節課中

MapReduce and Parallel Dataflow Programming

The MapReduce programming model (as distinct from its implementations) was proposed as a simplifying abstraction for parallel manipulation of massive datasets, and remains an important concept to know when using and evaluating modern big data platforms.

MapReduce Abstraction4:41

MapReduce Data Model3:44

Map and Reduce Functions2:36

MapReduce Simple Example3:47

MapReduce Simple Example cont'd3:10

MapReduce Example: Word Length Histogram2:56

MapReduce Examples: Inverted Index, Join6:18

教學方

Bill Howe
Director of Research

腳本

[MUSIC] So, now this top chunk gets assigned to Map Task 1 and it produces this little histogram of accounts of yellow words, red words, blue words and pink words. And, we can imagine you should think about how the code might look if you had to write this. Right, you would need to take the length, you know either go over all the words in the document just like we did before. But now instead of it needing a key being the word itself, you would count its length and put in a case statement and figure out what color it is in this notation and add that to account. So the output is these four key value pairs. And in chunk two we do the same thing and produce a different set of four key value pairs. Then in the shuffle step, all the yellow key value pairs will be grouped together, and there's two of them. All the red ones get grouped together and so on. And then in the reduce phase, you'll add these two numbers together to produce 37, okay. So the structure here is really identical to word count. It's just basically a change to the map function and in fact, in this case, you could actually literally use the exact same reduce function. All right, for every key, add up all the contributions of it. You wouldn't need to change your use at all. And this is something else you'll see is that, you know, certain functions are more general than others and you'll reuse them time and again. For example, counting things and adding things up is pretty common in these map reduce algorithms. And so reduce, general reduce functions that add things and count things come up time and again. Okay, fine. So word count, generally the canonical place to start when thinking about map reduce. Word length, very minor variation on that. So let's think of another sort of minor variation on that. And this one, inarguably is even simpler than word count. So here we want to build an inverted index. And what an inverted index is when you have a corpus of documents, you can presumably efficiently access any given document by it's name, right. So if you want to look up a URL on the web, you can do so. But for a search engine, a very primitive search engine, you might want to look up documents that contain a particular word. And so do building this index to support word lookup to provide a list of document IDs that contain that word is called an inverted index and it's one of the primitive steps in doing any kind of text retrieval kind of system. Okay. So now, you know, imagine we just had tweets instead of documents. And the input here is that the keys are these tweet ID's that I've invented, and the value is the text of the tweet itself. And so the desired output here is the word along with a collection of tweet IDs. Okay? So how do we do this? Well, again, the code is actually simpler than it was before. Because now on the reduce phase, instead of and so, well, think about it for a moment. The map phase, instead of producing each word, pancake, and 1, for an occurrence. We won't do that. Instead, we'll put out pancake, and the document ID itself. Right? And all of these guys will be produced. And so this tweet1, the map task that processes this tweet1 will put out tweet1, love, tweet1 and so on. Okay, further in optimization here is if you see the word, I guess I should've had an example of this in here. But if you see the word pancake twice in the same tweet, do you need to put it out, do you need to emit the key value pair twice? Probably not to build this index because all you're trying to record is that the tweet contains the word "pancake". Not that it,not how many times it appears. So fine, these key value pairs get shuffled across the network. And now the reduce task, what does it do? Well, it's going to get a key pancakes. This should have an s on it I guess. And it's gonna have an iterator over all the document IDs that contain pancakes, which in this case is tweet1 and tweet2. So do we need to do any processing on this key and group of values? The answer in this case is no. The reduce function is complete, is nonexistent. There's nothing to do. Right? The group is exactly what you want in this case. And this pattern actually shows up somewhat often, as well. Where you do want the map and you do want the shuffle face to do the grouping, but all you want to do is perform the grouping, you didn't actually care about the reduce function. So you're not counting these things, you're not adding them up in anyway, you're not doing any processing on the tweets, you just wanna omit that. And that's perfectly fine, because this group of values is perfectly serviceable as a value itself. Okay? So if you are used to say relational databases you know, nested structures, collections of values within a single cell in a table in a single row are generally disallowed, all right. And this is actually first normal form if you're familiar with that. But here we don't care, its any key and any value. A key can have sub-structure and a value can have sub-structure. Okay, fine. So, that is how to build and inverted index in map reduce. Let me stop there and next time we will talk about this relational join example. [MUSIC]

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版
面向校園

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司