[MUSIC]. 
Welcome back. 
So this time, I want to talk about what 
this term, scalable, means. 
We made the point that working with 
really large data is an important aspect 
of data science and we mentioned the word 
scalability before we haven't talked 
about really what that might mean. 
So a couple different ways to think about 
it that I want to talk about here on this 
slide are, are here. 
So you know, operationally and in the 
past one way to think about this was look 
it needs to work on data that doesn't fit 
in main memory on a single machine. 
Okay. 
You maybe you still have one machine to 
work with but this means that if it can 
you know, you need to be able to bring 
data off of disks in pieces. 
Operate on it and then maybe write it out 
in pieces, okay? 
And so, a bundle of algorithms that could 
work on data in this fashion by bringing 
in data piece by piece to memory, such 
that the memory footprint at any, any 
given point was small. 
this is something the database has 
provided. 
Alright, so you could write a query and 
you knew for sure that it was going to 
finish as long as the data was there on 
disk. 
And you had sort of a minimal amount of 
memory. 
At least, at least to get started. 
Okay. 
But, and I might, I might use the term 
out of core processing here. 
So, out of core means uses the disk to 
operate. 
So, in core means the entire, everything 
you're doing fits entirely in main 
memory. 
Out of core means you sort of need to 
work with the disk appropriately. 
And so databases were, the database 
community were specialists at out of core 
processing of large data sets. 
But increasingly, this notion of 
scalability wasn't really enough, okay. 
And so you saw this pretty acutely with 
websites that were coming online in the 
2000's, where, you know, one big server, 
no matter how big you bought that server. 
You couldn't bring data off of disks fast 
enough to meet all the requests. 
And so had to start being sure that 
things were in memory, and the only to do 
that is start adding more machines, okay. 
And so, increasingly, especially, you 
know, Google is especially is sort of 
known for this, although many of the 
large media companies do this. 
It's scalable really kind of means being 
able to use up to thousands to maybe even 
more tens of thousands of cheap 
computers. 
And, and apply them all to the same 
problem. 
And so we might call this. 
scale out. 
While getting bigger and bigger and 
bigger main memory and more and more 
cores perhaps would be scale up. 
Okay. 
Fine. 
So another way of looking this is may be 
its little more precise is to think 
whether its going to in terms of 
algorithmic complexity that you may or 
may not familiar with been how much 
computer science you take in but then it 
give you just a flavor of what's going on 
here. 
So in the past. 
You might call an algorithm scalable if, 
for, if given n date items, your 
algorithm does no more than n to to the m 
operations on it. 
Okay. 
So this may, it may be 1, in which case 
it's a linear time algorithm, or it may 
be 2, in which case it's a quadratic time 
algorithm, and so on. 
But this was deemed, you know, tractable. 
Right, and so you'd prove properties 
about, you, you would prove that you can 
find in a, a polynomial time algorithm to 
solve some problem and it was sort of 
thought to be scalable or, or assumed, 
you know, well assumed, it was, that was 
the definition of what scalable was. 
Things that were non-polynomial. 
you know that took more than this, for 
example, exponential, we might have n to 
the n or exponential time algorithms, and 
they grew much, much faster, and they 
were, they didn't scale, okay. 
But, you know, this isn't a very tight 
bound on scalability in practice, right. 
A quadratic time algorithm may be sort of 
feasible. 
You start getting into the fourth, and so 
forth. 
It becomes pretty difficult to do for, 
for very large data sets. 
Okay. 
So, now you would say that it really 
can't just be into the m. 
It's gotta be into the m over k. 
Over some, for some pretty large k. 
So you have to have a lot of K being the 
number of computers you can apply to the 
problem. 
And so, you have to call it an algorithm 
that can really exploit this properly. 
Okay, and then one more point that I'm 
going to make now, but we're not going to 
return to in this segment. 
but, but I hope to at the end of the 
course, is that you know, it could be 
that soon even this isn't good enough. 
And for N data items you really should do 
no more than N log in operations. 
And so, the N here means for every, for 
every data item that comes in over the 
wire. 
So, this is, this is applicable to sort 
of streaming applications. 
And the data is coming in so fast, they 
only get one pass at it. 
So, for every operation I have, I'm 
allowed to process that data item. 
And then I'm allowed to put it in some 
sort of a, of an index, and that's this 
log in factor, okay. 
And so, whenever you see log, you should 
think trees. 
So, I'm allowed to take each item, 
inspect it, and work with it, and then 
stick it in some tree dra-, data 
structure. 
But that might be about it. 
Its just too big to make multiple passes 
out, okay and so example this might be 
this Large Synoptic Survey Telescope that 
we, heard about taking sort of 3 
terabytes a night. 
You can't sort of make too many passes on 
this data at, at one time, okay and so 
this whole area we think of is streaming 
data which I guess I have written here 
but I'll write it again. 
And we'll come back to some of the 
techniques for dealing with big data in 
a, in a streaming context. 
Okay, so fine. 
So, two different views of what scalable 
might mean. 
And we're going to talk in this segment 
to give, to give you some examples and 
some intuition for this, can we make use 
of lots of computers. 
and this N over K, okay? 
Alright, so here's a little example 
problem, that's admittedly somewhat over 
simplified. 
So, we want to find all the matching DNA 
sequences. 
Where a set of sequences a short string 
consisting of the letters g, a, t, and c. 
And you're given a short sequence and you 
want to find all the ones that just 
exactly match that. 
Okay, so find me all the sequences that 
are exactly equal to this one you're 
given. 
So how might you do this. 
Well with this little cartoon imagine 
that each of these black lines is a 
sequence. 
Alright so this black line can correspond 
to this sequence and this black line 
corresponds to this sequence and all the 
other black lines are other sequences. 
And you know, think to yourself for a 
minute, propose an algorithm to, to find 
sequences matching your target sequence. 
Okay. 
Well, making no assumptions about the 
data whatsoever. 
It's just given to you as a list. 
One thing you can do, is, use a linear 
search. 
And so we're going to, inspect the first 
item, and we're going to compare it, to 
our target sequence. 
And if they're equal. 
Great we found one, and if they're not 
equal what do you do, we move on on to 
the next one. 
So this is not equal and this, this all 
happens in time equals 0, and then we 
move o to the next one. 
So at time equals one we check for 
equality and if it doesn't match we keep 
moving on, and so on and so on until we 
get to time 17 where we find. 
A match. 
And here I've said contains instead of 
equal. 
I guess I changed the, the meaning here. 
But so, yes, we found a match and we sent 
it to the output. 
Okay. 
So how long does this take, how many 
operations did we do? 
Well, we did 40 records. 
I'm sorry, we were given 40 records in 
this cartoon and we made 40 comparisons. 
And so with in records, and in 
comparisons, we say that the algorithmic 
complexity is order N. 
OK, so this is a linear time algorithm 
for this simple search and retrieval 
task. 
So the question is, can we do any better? 
And if you've, had some experience 
thinking about data structures, taking 
some data structures classes, you should 
be thinking, yes we can. 
So one way to do this is to sort the 
sequences. 
So how does this happen? 
Well, certainly we could still do the 
linear time algorithm and inspect these 
guys one at a time, but we can also do 
something a little bit smarter. 
What if we start in the middle? 
So, we start in the middle and compare 
our target Sequence to the sequence we 
found here and they're not equal. 
But we can see this one that we found is 
less than our target sequence. 
OK. 
So we know the sequence we're on is to 
the left of our target sequence. 
We know the target sequence is to the 
right. 
Right, it must be somewhere in this 
direction. 
So we've just moved the need to check 
half of the data, right, 20 records. 
So now jump to the middle of this guy and 
compare again, and now we see that well, 
boy, we overshot. 
This one is greater than this one. 
We'll once again. 
Let's see. 
Here, we've removed half of these guys, 
on the first step. 
And here, we now, we've removed half of 
these guys. 
And now we know it's in this range. 
Skip to the half again. 
And you compare this one. 
And now it's less than so we're sort of 
bouncing back and forth around our 
target. 
Let's see if I can draw this a little bit 
than I did, cross those out, cross those 
out. 
And now cross these out And so we know 
it's somewhere on this side. 
And in the next step, we find a match. 
Okay. 
And here, if we have multiple copies of 
the same item. 
We know that they'll be, they'll appear 
next to each other. 
So we could just walk through the 
records, gathering up all the ones that 
match if we needed to. 
Okay. 
So how long did this take? 
Well, here, we still had 40 records. 
But we only made four comparisons. 
Right. 
So within records we made login 
comparisons. 
We did, we navigated this, this sort of 
implicit binary tree. 
We did a binary search over this sorted 
data, okay. 
And so this lookup was order login, now 
we did have to sort the data ahead of 
time, and if you have to include that, 
then that's an in login operation. 
And we're not going to intially talk 
about. 
But once you have that sorted data 
available to you, it's now you know, 
really takes a log in operations. 
So this is perhaps far better 
scalability, alright? 
And this is a, this is a good trick. 
And it's such a good trick that it's been 
baked into many systems. 
Especially I'll argue relational 
database, and we made this point before, 
but I want to make it again. 
I said databases are good at these kinds 
of needle in the haystack problems, 
right? 
It's extracting small results from big 
data sets. 
They can transparently provide this sort 
of old style of scalability. 
What I mean by old style of scalability 
is that fits in main memory, as we've 
said a couple of times. 
And your query will always finish 
regardless of the size you main memory. 
In addition, you can it makes an 
excellent sort of index platform, a 
platform for building and using and 
reusing indexes. 
Okay, so, relational databases are good 
at this old style schema building, this 
sort of out of core algorithms and 
they're also good at this old style 
scalability in the sense of finding logs, 
right? 
Finding logarithmic time algorithms. 
Okay. 
So, when the indexes are easily built, 
and automatically used When appropriate, 
and we talked a little bit about this 
during relational databases. 
You can write a single statement CREATE 
INDEX give it a name on a table and a 
column name, and it will sort records 
according to that column. 
You know, the actual data on disk may or 
may not be physically sorted depending on 
uh,the details of, of which system you're 
using in how, how this is working. 
In typically in this statement it would 
not actually moving the physical records 
around but it would build an auxiliary 
index but regardless you get to take 
advantage of this logarithmic time access 
pattern. 
Okay. 
So just by writing this 1 statement in 1 
line of, of code you can create the index 
and take advantage of it. 
Okay, and then every query that comes 
afterward that needs to to use that, that 
would benefit from using that index is 
able to. 
The optimised automatically selects the 
correct index if it's appropriate to use. 
So this is much easier than you sort of 
having to rewrite your code by hand in 
order to either make it out of core. 
Right? 
Or to take advantage of an index, okay. 
So when you're comparing relational 
databases to, say, scripts in R or 
scripts in Python, there's a lot of 
algorithmic work that's already been done 
for you that you're getting for free just 
by turning your problem into a sequel 
statement. 
Fine so you're you know, bind in, bind 
into a lot of code if you can tie one arm 
behind your back and write it as a sequel 
statement. 
It's not just sequel versus, versus a 
much more expressive language like code. 
You're actually getting a lot of benefit 
out of doing [UNKNOWN] okay. 
So let's look at another task Called read 
trimming. 
So here we're given the same set of DNA 
sequences, but instead of searching for 
one particular sequence, we're going to 
trim the final few base pairs from each 
sequence. 
Okay? 
So we're going to trim off a suffix and 
return the data set where each read, read 
is now just a prefix of the, of a former 
read Read, okay. 
So fine. 
So how do we do this. 
On the reason why you need to trim off 
the suffix. 
This actually comes up in practice and 
the reason is that the accuracy of the 
sequencer drops off fairly and properly 
after a certain length of read and 
trimming off the last. 
Several base pairs, from every single 
read is, kind of a pre-processing 
operation. 
OK. 
Fine, so. 
How do we do this? 
Well, we can do the same trick that we 
tried the first time with the search 
task, meaning that we can process each 
record in turn one at a time, all right. 
So at time 0, we can trim off the, suffix 
here and just return to TACCT. 
And in time 1, we can trim off this 
suffix, and so on. 
And at time 17, there's our old friend. 
That begins with GATTA and so on but here 
you know, unlike the search task there's 
no index that's really going to help us 
right we have to touch every single 
record and manipulate it right we have to 
take a prefix from and remove a suffix 
and so the operation is fundamentally 
order in right there's not going to be a 
algorithm that is less than order in 
right you have to atleast touch every 
single record. 
Okay, but can we do any better? 
Well, yeah, right. 
Processing the first task is completely 
independent from processing the the last 
task, which is completely independent 
from processing this task, well, 
actually, saying task, processing the 
record. 
Okay. 
So while there's no index, we can break 
this data set into pieces and process 
each piece independently. 
Okay. 
So imagine we take our single data set 
and break it into these chunks and assign 
each chunk to a different machine or 
maybe a different processor, to be a 
little bit more general. 
Now at times 0 we can process one 
sequence from each chunk all at the same 
time, and at time one we process the 
second sequence from each chunk all at 
the same time, and so on. 
And so here, how much work did we do? 
Well, we did the same amount of work, we 
still process all 40 records. 
But how much time did it take? 
Well it only took seven, I say cycles 
here, s-, seven, time units to be a 
little more general, because we were 
given these six workers. 
And so, the complexity here is n over k, 
right?. 
For every item we can divide by but, we 
do, on average, for any items we do 
[LAUGH] in over k times stands for 
completed the work. 
Okay? 
[BLANK_AUDIO]