download pdf in mvc : Convert pdf to tiff file SDK software project winforms wpf web page UWP IM1008593-part308

Chapter 3. Join Algorithms
22
p2 P;q 2 Q;gq 2 Q
while more tuples in inputs do
while p:a < gq:b do
advance p
end while
while p:a > gq:b do
advance gq fa group might begin hereg
end while
while p:a == gq:b do
q=gq fmark group beginningg
while p:a == q:b do
Add hp;qi to the result
Advance q
end while
Advance p fmove forwardg
end while
gq =q fcandidate to begin next groupg
end while
It should be apparent that this algorithm will give good performances if the input
datasets are already sorted.
The Reduce-Side Join algorithm described in section 3.2.1 is in many ways a dis-
tributed version of Sort-Merge Join. In Reduce-Side Join algorithm, each sorted parti-
tion is sent to a reduce function for merging.
Hash Join
TheHash Join algorithm consists of a‘build’phaseand a ‘probe’ phase. In itssimplest
variant, the smaller dataset is loaded into an in-memory hash table in the build phase.
In the ‘probe’ phase, the larger dataset is scanned and joined with the relevant tuple(s)
by looking into the hash table. The algorithm like the Sort-Merge Join algorithm, also
works only for equi-joins.
Convert pdf to tiff file - SDK software project:C# PDF Convert to Tiff SDK: Convert PDF to tiff images in C#.net, ASP.NET MVC, Ajax, WinForms, WPF
Online C# Tutorial for How to Convert PDF File to Tiff Image File
www.rasteredge.com
Convert pdf to tiff file - SDK software project:VB.NET PDF Convert to Tiff SDK: Convert PDF to tiff images in vb.net, ASP.NET MVC, Ajax, WinForms, WPF
Free VB.NET Guide to Render and Convert PDF Document to TIFF
www.rasteredge.com
Chapter 3. Join Algorithms
23
Consider two datasets P and Q. The algorithm for a simple hash join will look like
this-
for all p 2 P do
Load p into in memory hash table H
end for
for all q 2 Q do
if H contains p matching with q then
add hp;qi to the result
end if
end for
This algorithm usually is faster than the Sort-Merge Join, but puts considerable
load on memory for storing the hash-table.
The Broadcast Join algorithm described in section 3.2.3 is a distributed variant of
the above mentioned Hash Join algorithm. The smaller dataset is sent to every node
in the distributed cluster. It is then loaded into an in-memory hash table. Each map
function streams through its allocated chunk of input dataset and probes thishash table
for matching tuples.
3.2 Two-Way Joins
3.2.1 Reduce-Side Join
In this algorithm, as the name suggests, the actual join happens on the Reduce side of
the framework. The ‘map’ phase only pre-processes the tuples of the two datasets to
organize them in terms of the join key.
Map Phase
The map function reads one tuple at a time from both the datasets via a stream from
HDFS. The values from the column on which the join is being done are fetched as
keys to the map function and the rest of the tuple is fetched as the value associated
with that key. It identifies the tuples’ parent dataset and tags them. A custom class
called TextPair (See Appendix A) has been defined that can hold two Text values (see
section 2.4.8 for moredetails). The map function usesthis class to tag both thekey and
the value. The reason for tagging both of them will become clear in a while. Listing
3.1 is the code for the map function.
SDK software project:Online Convert PDF file to Tiff. Best free online PDF Tif
Using this .NET PDF to TIFF conversion control, C# developers can render and convert PDF document to TIFF image file with no loss in original file quality.
www.rasteredge.com
SDK software project:Online Convert PDF file to Word. Best free online PDF Conversion
Convert a Tiff/Tif File to PDF. Just upload your file by clicking on the blue button or drag-and-drop your Tiff or Tif file into the drop area.
www.rasteredge.com
Chapter 3. Join Algorithms
24
Figure 3.1: Reduce Side Join - Two Way
void map(Text key, Text values,
OutputCollector <TextPair, TextPair> output, Reporter
reporter) throws IOException {
output.collect(new TextPair(key.toString(), tag),
new TextPair(values.toString(), tag));
}
Listing 3.1: Reduce-Side Join -
map
function
Partitioning and Grouping Phase
The partitioner partitions the tuples among the reducers based on the join key such
that all tuples from both datasets having the same key go to the same reducer (section
2.4.6). The default partitioner had to be specifically overridden to make sure that the
partitioning was done only on the Key value, ignoring the Tag value. The Tag values
are only to allow the reducer to identify a tuple’s parent dataset.
int getPartition(TextPair key, TextPair value, int
numPartitions) {
return (key.getFirst().hashCode() & Integer.MAX_VALUE)
% numPartitions;
}
Listing 3.2: Reduce-Side Join - Partitioner function
SDK software project:Online Convert Excel to PDF file. Best free online export xlsx
Download Free Trial. Convert a Excel File to PDF. Drag and drop your excel file into the box or click the green button to browse for a file to upload.
www.rasteredge.com
SDK software project:C# Create PDF from Tiff Library to convert tif images to PDF in C#
TIFFDocument doc = new TIFFDocument(inputFilePath); // Convert loaded TIFF file to PDF document. doc.ConvertToDocument(DocumentType.PDF, outputFilePath);
www.rasteredge.com
Chapter 3. Join Algorithms
25
But this is not sufficient. Even though this will ensure that all tuples with the same
key go to thesameReducer, there still existsaproblem. Thereducefunction iscalled
once for a key and the list of values associated with it. This list of values is generated
by grouping together all the tuples associated with the same key (see section 2.4.6).
We are sending a composite TextPair key and hence the Reducer will consider (key,
tag) as a key. This means, for eg., two different reduce functions will be called for
[Key1, Tag1] and [Key1, Tag2]. To overcome this, we will need to override the default
grouping function as well. This function is essentially the same as the partitioner and
makes sure the reduce groups are formed taking into consideration only the Key part
and ignoring the Tag part. See figure 3.2 to understand better.
Figure 3.2: Custom Partitioning and Grouping
Reduce Phase
The framework sorts the keys (in this case, the composite TextPair key) and passes
them on with the corresponding values to the Reducer. Since the sorting isdone on the
composite key (primary sort on Key and secondary sort on Tag), tuples from one table
will all come before the other table. The Reducer then calls the reduce function for
SDK software project:C# PDF Convert to Word SDK: Convert PDF to Word library in C#.net
DocumentType.DOCX DocumentType.TIFF. zoomValue, The magnification of the original PDF page size. Description: Convert to DOCX/TIFF with specified zoom value and
www.rasteredge.com
SDK software project:VB.NET PDF File Compress Library: Compress reduce PDF size in vb.
Convert smooth lines to curves. Detect and merge image fragments. Flatten visible layers. VB.NET Demo Code to Optimize An Exist PDF File in Visual C#.NET Project
www.rasteredge.com
Chapter 3. Join Algorithms
26
each key group. The reduce function buffers the tuples of the first dataset. This is
required since once the tuples are read from the HDFS stream (see section 2.4.2), we
lose access to these values unless we reinitialize the stream. But we need these tuples
in order to join them with the tuples from the second dataset. Tuples of the second
dataset are simply read directly from the HDFS stream, one at time and joined with
all the tuples from the buffer (all the values with one reduce function are for the
same key) It was mentioned earlier that both key and values need to be tagged. This
is because the tag attached with the key is used to do a secondary sort to ensure all
tuples from one table are processed before the other. Once the reduce function is
called, it will only get the first (key, tag) pair as its key (owing to the custom grouping
function written which ignores the tags). Hence the values also need to be tagged for
the reduce function to identify their parent datasets.
void reduce(TextPair key, Iterator<TextPair> values,
OutputCollector <Text, Text> output,
Reporter
reporter)
throws IOException {
ArrayList<Text> T1 = new ArrayList<Text>();
Text tag = key.getSecond();
TextPair value = null;
while(values.hasNext())
{
value = values.next();
if(value.getSecond().compareTo(tag)==0)
{
T1.add(value.getFirst());
}
else
{
for(Text val : T1)
{
output.collect(key.getFirst(),
new Text(val.toString() + "\t"
+ value.getFirst().toString()));
}
}
}
}
Listing 3.3: Reduce-Side Join -
reduce
function
Note that the this algorithm makes no assumption about the number of times a key
repeats in either of the datasets and can handle duplicate keys.
SDK software project:C# PDF File Split Library: Split, seperate PDF into multiple files
Application. Best and professional adobe PDF file splitting SDK for Visual Studio .NET. outputOps); Divide PDF File into Two Using C#.
www.rasteredge.com
SDK software project:C# PDF Convert to Jpeg SDK: Convert PDF to JPEG images in C#.net
PDFPage page = (PDFPage)doc.GetPage(0); // Convert the first PDF page to a JPEG file. page.ConvertToImage(ImageType.JPEG, Program.RootPath + "\\Output.jpg");
www.rasteredge.com
Chapter 3. Join Algorithms
27
3.2.2 Map-Side Join
TheReduce-Sidejoin seems likethenatural way to join datasetsusing Map/Reduce. It
uses the framework’s built-in capability to sort the intermediate key-value pairs before
they reach the Reducer. But this sorting often is a very time consuming step. Hadoop
offersanother way of joining datasetsbeforethey reach the Mapper. This functionality
is present out of the box and is arguably is the fastest way to join two datasets using
Map/Reduce, but places severe constraints (see table 3.1) on the datasets that can be
used for the join.
Table 3.1: Limitation of Map-Side Join [16]
Limitation
Why
All datasets must be sorted
using the same comparator.
The sort ordering of the data in each dataset must be identi-
cal for datasets to be joined.
All datasets must be parti-
tioned using the same parti-
tioner.
Agiven key has to be in the same partition in each dataset
so that all partitions that can hold a key are joined together.
The number of partitions in
thedatasets must beidentical.
Agiven key has to be in the same partition in each dataset
so that all partitions that can hold a key are joined together.
These constraints are quite strict but are all satisfied by any output dataset of a
Hadoop job. Hence as a pre-processing step, we simply pass both the dataset through
abasicHadoop job. This job uses an IdentityMapper and an IdentityReducer which do
no processing on the data but simply pass it through the framework which partitions,
groups and sorts it. The output is compliant with all the constraints mentioned above.
Although the individual map tasks in a join lose much of the advantage of data
locality, the overall job gains due to the potential for the elimination of the reduce
phase and/or the great reduction in the amount of data required for the reduce. This
algorithm also supports duplicate keys in all datasets. More can be found out about
this kind of join in [16].
Chapter 3. Join Algorithms
28
3.2.3 Broadcast Join
Broadcast Join was studied by Blanas et. al. in [6]. If one of the datasets is very
small, such that it can fit in memory, then there isan optimization that can be exploited
to avoid the data transfer overhead involved in transferring values from Mappers to
Reducers. This kind of scenario is often seen in real-world applications. For instance,
asmallusers database may need to bejoined with alargelog. Thissmall dataset can be
simply replicated on all the machines. This can be achieved by simply using -files
or -archive directive to send the fileto each machinewhile invoking the Hadoop job.
Broadcast join is a Map-only algorithm
Map Phase
The Mapper loads the small dataset into memory and calls the map function for each
tuple from the bigger dataset. For each (key, value), the map function probes the in-
memory dataset and finds matches. This process can be further optimized by loading
the small dataset into a Hashtable. It then writes out the joined tuples. The below
shown configure function is part of the Mapper class and is called once for every
Mapper. The below code reads the ‘broadcasted’ file and loads the same into an in-
memory hash table.
public void configure(JobConf conf) {
//Read the broadcasted file
T1 = new File(conf.get("broadcast.file"));
//Hashtable to store the tuples
ht = new HashMap<String, ArrayList<String>>();
BufferedReader br = null;
String line = null;
try{
br = new BufferedReader(new FileReader(T1));
while((line = br.readLine())!=null)
{
String record[] = line.split("\t", 2);
if(record.length == 2)
{
//Insert into Hashtable
if(ht.containsKey(record[0]))
{
ht.get(record[0]).add(record[1]);
}
else
{
Chapter 3. Join Algorithms
29
ArrayList<String> value = new ArrayList <
String>();
value.add(record[1]);
ht.put(record[0], value);
}
}
}
}
catch(Exception e)
{
e.printStackTrace();
}
}
Listing 3.4: Loading the small dataset into a Hash table
The next piece of code is the actual map function that receives the records from
the HDFS and probes the HashTable containing the tuples from the broadcasted file.
Notice that it takes care of duplicate keys as well.
public void map(LongWritable lineNumber, Text value,
OutputCollector<Text, Text> output, Reporter
reporter)
throws IOException {
String[] rightRecord = value.toString().split("\t",2);
if(rightRecord.length == 2)
{
for(String leftRecord : ht.get(rightRecord[0]))
{
output.collect(new Text(rightRecord[0]), new Text
(leftRecord + "\t" + rightRecord[1]));
}
}
}
Listing 3.5: Broadcast Join Map Function
Broadcast Join benefits from the fact that it uses a small ‘local’ storage on the
individual nodes instead of the HDFS. This makes it possible to load the entire dataset
into an in-memory hash table, access to which isvery fast. But on the down side, itwill
run into problems when both the datasets are large and neither of them can be stored
locally on the individual nodes.
Chapter 3. Join Algorithms
30
3.3 Multi-Way Joins
The algorithms presented in the previous section on Two-Way joins were mainly work
that already existed. This project extends these ideas to Multi-Way joins. This section
details them. We compare the performance of this algorithms against the next two
algorithms in the next chapter.
3.3.1 Map-Side Join
Map-Side joins are the same when it comes to Multi-Way joins. They can handle as
many datasets as long as they conform to the constraints (Table3.1) mentioned earlier.
3.3.2 Reduce-Side One-Shot Join
This is basically an extension of the Reduce-Side join explained earlier (see 3.2.1).
Alist of tables is passed as part of the job configuration (passes as tables.tags) to
enable the Mapper and Reducer to know how many tables to expect and what tags
are associated with which table. For instance, to join n datasets, T
1
;T
2
;T
3
;::;T
n
,this
algorithm in simple relational algebra can be represented as -
T
1
./ T
2
./ ::: ./ T
n 1
./ T
n
Map Phase
The Mapper reads tables.tags from the job configuration and calls the map func-
tion. The map function then proceeds to tag the tuples based on the dataset they origi-
nate from. This is similar to the map phase in section 3.2.1.
Partitioning and Grouping Phase
The Partitioner and the Grouping function are the exact same as explained in section
3.2.1. They partition and group based on just the key, ignoring the tag.
Reduce Phase
The reduce phase is slightly more involved than the two sided join. The Reducer as
usual, getsthetuples sorted on the(key, tag) composite key. All tupleshaving thesame
value for the join key, will be received by the same Reducer and only one reduce
function is called for one key value. Based on the number of tables passed as part of
Chapter 3. Join Algorithms
31
the job configuration, the Reducer dynamically creates buffers to hold all but the last
datasets. The last dataset is simply streamed from the file system. As a necessary evil,
required to avoid running out of memory, thebuffers are spilled to disk if they exceed a
certain pre-defined threshold. This quite obviously will contribute to I/O and runtime.
Once the tuples for a particular key are divided as per their parent datasets, it is now
acartesian product of these tuples. Subsequently, the joined tuples are written to the
output.
Advantages and Drawbacks
 Advantages
(a) Joining in one go means no setting up of multiple jobs as will be the case
in the next section (3.3.3).
(b) No intermediate results involved which could lead to substantial space sav-
ings.
 Disadvantages
(a) Buffering tuples can easily run in to memory problems, especially if the
data is skewed. In fact, this algorithm failed to complete and gave Out-
OfMemory exceptions a number of times when we tried to run it with
datasetshaving morethan 2.5 million tuplesin ourexperiments(seesection
4.4.1).
(b) If used for more than 5 datasets, its highly likely that the buffer will over-
flow.
3.3.3 Reduce-Side Cascade Join
This isaslightly different implementation oftheReduce-SideJoin for Multi-Way joins.
Instead joining all the datasets in one go, they are joined two at a time. In other words,
it is an iterative implementation of the two-way Reduce-Side Join The implementation
is the same as the Reduce-Side Join mentioned in section 3.2.1. The calling program
isresponsible for creating multiple jobs for joining the datasets, two at a time. Consid-
ering n tables, T
1
;T
2
;T
3
;::;T
n
,T
1
is joined with T
2
as part of one job. The result of this
join is joined with T
3
and so on. Expressing the same in relational algebra -
(:::(((T
1
./ T
2
)./ T
3
)./ T
4
)::: ./ T
n 1
)./ T
n
Documents you may be interested
Documents you may be interested