A faster way to compute edit distance does not exist

http://www.bostonglobe.com/ideas/2015/08/10/computer-scientists-have-looked-for-solution-that-doesn-exist/tXO0qNRnbKrClfUPmavifK/story.html

by dnt404-1 • 11 years ago

150 54 11 years ago

bostonglobe.com

sanxiyn• 11 years ago

Previously here: https://news.ycombinator.com/item?id=9698785

erikb2• 11 years ago

Edit distance is useful, but also very time-consuming to calculate.

So I guess we will soon see a lot of crypto based on calculating edit distances?

leni5362• 11 years ago

It's still polynomial though, I think it's not practical for crypto.

Dylan168072• 11 years ago

n^100 is perfectly good for crypto.

n^2 is insufficient, but 'polynomial' as a category is not necessarily bad.

P=NP is not the end of the world, by itself.

Sharlin2• 11 years ago

No. Quadratic speed is way too fast for crypto - besides, asymmetric cryptography relies on problems that are difficult to solve but candidate solutions are easy to validate! This is what the complexity class NP is about. As far as I know there's no way to check a solution for edit distance any faster than it takes to compute it in the first place. Also, the new proof just shows that edit distance is quadratic if P!=NP.

erikb2• 11 years ago

Yeah, don't know enough about it.

Scea913• 11 years ago

I get what you mean but 'easy to validate' in the context of NP means 'can be validated in polynomial time'. It seems to me that you imply that edit distance is harder to validate than problems in NP. Edit distance itself is in NP since P is in NP.

bbrazil2• 11 years ago

It's only quadratic, for asymmetric crypto you'd want something with a much higher complexity and preferably non-polynomial.

tomelders• 11 years ago

Hmmmm. That got me thinking about spam, and I went off on a tangent.

What if an email could be parsed in such a way as to generate seed data for an an NP problem which the sender must solve and supply the answer in the in the email header...

If the receiver can instantly dismiss any emails that provide an answer that can not be verified, then that could have a huge impact on the the spammers ability to send spam in the volumes they currently enjoy. A penalty of 5 seconds per email is unlikely to impact ordinary users, but would be a major pain for spammers.

Also, could this be used to throttle user input to mitigate brute force attacks?

skosch• 11 years ago

You're not the first one to think of this: https://en.wikipedia.org/wiki/Challenge%E2%80%93response_spa...

Scea913• 11 years ago

You would quickly run out of instances of a given NP problem that can be solved under 5 seconds.

im3w1l• 11 years ago

The fact that edit distance is only computable in quadratic time has big implications for genomics. The human genome contains about 3 billion base pairs. To compute the edit distance between two human genomes takes 3 billion-squared operations (to appreciate how big that is, write a 9 followed by 18 zeroes). That’s a number of operations, explains Piotr Indyk of MIT, that is “computationally infeasible.” Which is to say that our best computers chugging away for a really long time still won’t generate an answer.

As was commented last time this was posted: Just because it's not possible to do better in the general case doesn't mean it isn't possible to do better in your case. For all we know, human genomes may not actually be 100% random strings, but may have some kind of structure that makes it possible to do it faster. Even when solving the problem exactly.

new299• 11 years ago

Human genomes are very much not random strings, and in any case if calculating the edit distance between two human genomes they are likely largely similar, and if memory serves there are suffix tree/array based algorithms for bounded edit-distance calculations.

Moreover, I'm not sure if it would ever actually be useful to compute the edit distance between two full genomes. Edit distances/local/global alignments are useful for short fragments (gene's/reads etc) but not the full sequence.

dekhn• 11 years ago

The challenge with comparing genomes is that you can't just do edit distance using a naive substitution table. It has to be probabilistic and contextual (for it to be scientifically useful), because genome sequences are actually sampled estimates of the true genome sequence. You have to tolerate errors, and when you do that, the exploration space gets huge.

Instead of aligning two genomes this way, people normally start with a very well calibrated and fairly accurate reference sequence, then align to that structure probabilistically, and "call the joint variants".

This is actually far more interesting that doing the raw hard problems that computer scientists love to talk about theoretically. One of the reasons it's so interesting is that different genomes differ by operations that are much more complex than simple edit distance- for example, large regions can be excised, and placed, in reverse order, in completely other parts of the genome. Trying to use a DP edit distance calculation to detecet those is futile.

http://bcb.io/2014/10/07/joint-calling/

leni5362• 11 years ago

It's a nice theoretical result. In practice there are some quirks though:

- I assume this is worst case complexity. While this is useful, maybe the average time can be much lower for certain data (like the genome).

- I assume the theorem doesn't restrict the input strings in any way. If you put restrictions on the input then there could be a faster algorithm than the general one. I don't know if this can be applied to the genome though.

- People are interested in the constant factor too.

codeflo• 11 years ago

Also, a fast approximation with a good error bound might be good enough for many applications in biology.

Asbostos• 11 years ago

Absolutely. This is surely more theoretical than practical. Solving a linear system of equations has cubic complexity but we still routinely solve systems with millions of equations. Billions are probably being done too. We just take advantages of special features that allow us to do things faster than the worst case - such as having a sparse matrix.

wolfgke3• 11 years ago

Does a similar result hold, if we don't consider inserts, deletions and substitutions (definition of edit distance), but only inserts and deletions?

evandijk70• 11 years ago

How do you define an edit distance (the number of operations required to transform one string to the other) if you don't allow substitutions?

Eg. what's the edit distance between these two strings?

AAAA BBBB

Traditionally, it would be 4, but it's unclear if you allow only inserts and deletions.

greendestiny• 11 years ago

It's not unclear, any substitution can be replicated by a deletion and insertion. I have no idea if that leads to a simpler case of the edit distance algorithm.

wolfgke3• 11 years ago

  > Eg. what's the edit distance between these two strings?
  > 
  > AAAA BBBB
  > 
  > Traditionally, it would be 4, but it's unclear if you
  > allow only inserts and deletions.

It is >= 8, since you surely have to remove 4 As and insert 4 Bs. Since these 8 transformations indeed transform AAAA into BBBB, it is exactly 8.

It is very easy to generalize the Wagner-Fisher algorithm (https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...) to this "simpler" variant of edit distance, but this algorithm will still have a (worst-case) runtime of O(m*n), where m, n are the lengths of the two strings.

Of course, the question remains: Is there a (worst-case) faster algorithm?

jongraehl3• 11 years ago

I don't know about the mathematical result (the conditional proof), but I do know that it's easy to expand or limit the edit operations, or change their costs, while keeping the dynamic program order the same (so not e.g. allowing 'move this whole phrase' type edits - that would probably be cubic or worse). If you're considering the generalized 'set any costs you like for the operations' problem then you could set the subst cost as 2 and the insert and delete as 1.

Again, I know that's not precisely what you asked. I can't think of a reduction from "insert+delete only" problems to "insert+delete+subst" (all operations cost 1) problems (where solving the latter gives you a solution to the former, and the size is no more than k times the original).

a3_nm2• 11 years ago

The title of the Boston Globe article and of the HN submission is misleading.

The article does not prove that subquadratic edit distance algorithms do not exist. It only proves it conditional to another unproven complexity hypothesis (SETH). In other words, it shows that if such algorithms exist, then faster algorithms exist for another problem (SAT for CNF formulae with certain size bounds), where we haven't been able to find them yet. See the original article http://arxiv.org/abs/1412.0348 whose title is more accurate.

This is important work, of course, and provides more evidence that faster edit distance computation is not possible, but it is not proven yet.

logicallee• 11 years ago

I don't get it - how does the author of the piece not know this? He seems to reflect an excellent understanding, and it's bizarre that he would would miss this.

mckoss• 11 years ago

Often times authors of articles are not the same people who write their titles ... it may even be changed without their knowledge (until the paper is actually printed).

dsfsdfd• 11 years ago

beat me to it

brudgers3• 11 years ago

There are really two notions of proof here [and hence truths and facts]. The article uses proof in a scientific sense, where P!=NP is accepted as empirical fact by the community of computer scientists in the same manner that biologists take natural selection as empirical fact.

To put it another way, representing the world as if P!=NP is no less reasonable than representing the world as if Newtonian physics are applicable.

a3_nm2• 11 years ago

Theoretical CS is usually not thought of as an experimental or empirical field. When a paper in that field claims "X does not exist", this has to mean that the inexistence of X was proven, not that a body of empirical knowledge against the existence of X has been collected. By contrast, such things are called "plausibility arguments", "heuristics", etc.

There is such a thing as experimental truth, but it applies to experimental fields, and theoretical CS is usually not thought as one of them. I still think it is misleading to claim that the inexistence of something has been proven if it is conditional to another hypothesis.

ChrisLomont2• 11 years ago

The article uses proof in a scientific sense

Science does not deal in proofs, for example, the wiki page on scientific method does not use the word except in the mathematical sense [0].

Science deals in hypotheses, evidence, and models.

[0] https://en.wikipedia.org/wiki/Scientific_method

joe_the_user2• 11 years ago

The thing is the article implies the paper proves a link to p!=NP but the actual paper only claims "evidence" that there is a link, so there are multiple stages where the link is sketchy.

tomerv• 11 years ago

The wording in the article also makes it sound like the existence of a faster algorithm for edit distance would imply P=NP ("Most if not nearly all computer scientists believe the P equal to NP problem is false", although later a variant of the problem is mentioned), but that's not the conclusion of the theorem.

A more accurate wording would be that the existence of a fast algorithm for edit distance implies that P is "close" to NP, because there would exist a sub-exponential algorithm for SAT (but not necessarily a polynomial algorithm).

joe_the_user2• 11 years ago

The title isn't misleading. The title is a reasonable summary of what the article aims to say, in actuality. What article is attempting to say may be wrong but that's a different issue.

larsga• 11 years ago

This is misleading twice over. First, as a3_nm notes, this proof depends on unproven conjectures, and so this isn't proven yet.

Secondly, it is possible to do better than the Wagner-Fischer algorithm in certain cases. I figured this out myself and was about to write a paper on it when I realized that other researchers had beat me to it by a couple of decades.

If the two strings are equal you can establish that the edit distance is 0 in linear time, obviously. If you consider how the algorithm fills out the square down the diagonal you'll see that if there's only a one-letter difference you only actually need to fill out small parts of the grid around that difference.

This is generalizable, so the complexity actually depends on the distance between the strings.

podgib• 11 years ago

In practice, yes, the computation time required to compute edit distance will depend on the actual data. Similarly, 'sorting' a list that is already sorted can be done in linear time, and near-sorted lists can be sorted much faster than a randomly ordered list.

This is certainly useful in practice, but it doesn't affect whether the worst- or average-case complexity is quadratic. I'd like to see a quadratic (or exponential etc) time problem that couldn't be solved faster in many cases.

nomercy400• 11 years ago

As a quadratic algoritm, assuming 13 million base pairs can be solved in 7 seconds on a GTX275 (according to a paper on edit distance computation), is it correct to assume that 3 billion base pairs can be solved in (3bil * 3bil / (13mil * 13mil/7)) in 373443 seconds, or about 103 hours. Isn't that fast enough for a quadratic algorithm that samples DNA to be useful?

noir_lord• 11 years ago

I wondered about that as well, 3 billion squared is a massive number but we have processors in the billions of operations per second per core and machines with hundreds of thousands of processors.

I'm curious how fast we could do it on the raw 'string' in the worst case (assuming DNA is entirely random) but it's out of my scope, anyone hazard a guess?

dr_zoidberg• 11 years ago

I think the article is talking about the "full fledged" problem, while the computation you talk about could be using a set of optimizations aimed particularly at base-pair edit distance problem.

For example, I could assume that there no deletions and insertions, only changes and then the problem becomes embarrasingly paralell and extremely easy to express in assembly-like operations. So I could paralellize it on a GPU by splitting the string into fixed length substrings and get huge gains. Problem is, can it be safely assumed that there are no deletions and insertions?

Wikipedia has a list with some modifications that can also be used to speedup the calculation under certain constraints: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...

jongraehl3• 11 years ago

The name "Wagner-Fischer" is new to me. I usually cite this as Levenshtein [1965]. Even the Wagner-Fischer wp page notes that Levenshtein was first by a long shot. https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...

markbnj• 11 years ago

Yeah this struck me as well. I've always heard it described as Levenshtein edit distance.

omouse• 11 years ago

That was refreshing; a regular newspaper publishing an article about computer science. And it does a fairly good job, I wish I could see something related to CS rather than to web apps and startups in the Canadian newspapers.

amelius• 11 years ago

Now we can start looking for a more precisely defined problem, that can be solved faster than in quadratic time.

Or in other words, for certain classes of inputs, we can find a faster algorithm. We only need to find/define those classes.

CephalopodMD• 11 years ago

This is interesting, but it looks like this proves nothing according to the article since we don't know if P==NP. We are no closer to understanding whether or not a faster way to compute edit distance exists. All we know now is that it matches up to a class of problems that we _think_ are probably hard. It is still possible that we might find a faster solution to the problem.

I'd like to request a title change - "New proof that a faster way to compute edit distance might be tied up in the P vs. NP problem"

nemo44x• 11 years ago

Hence the need and desire for approximation algorithms. Often, you can give up a tiny amount of precision in exchange for dramatically increased performance - if you can make an assumption.

For instance, computing cardinality of a value over a huge dataset (distributed or otherwise) that is assumed to be evenly distributed would take memory proportional to the size of the dataset for 100% precision. Implementing a cardinality approximation algorithm like HyperLogLog++ lets you get a pretty close to accurate result for this calculation but with far fewer resources. There are many others and I think it is important to consider this trade off when it is appropriate.

Of course, it makes an assumption that the data is distributed more or less evenly.

gtrubetskoy• 11 years ago

An article on edit distance without mentioning the person who invented it - Levenshtein. https://en.wikipedia.org/wiki/Vladimir_Levenshtein

A faster way to compute edit distance does not exist

Related Stories