Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New string search algorithm

volnitsky.com

Post reply on HN
Print view View original

41–50 of 63 posts

Re: New string search algorithm

#41

Post by kragen »

cperciva wrote: post #40
kragen wrote: post #39

Earlier quoted context omitted.

Unfortunately I don't have access to the Samplesort paper, so I don't know which sense of "asymptotically optimal" you're using here. Quicksort is already asymptotically optimal in the sense that its asymptotic average performance is Θ(N log N), which is the best a sorting algorithm can do. It's true that dual-pivot quicksort is a step in the direction of Samplesort. (I do understand Samplesort well enough to say tha…

The asymptotic optimality of samplesort is in the sense that it takes (1 + o(1)) N log N / log 2 comparisons, i.e., you can't beat it by any constant factor. Bentley's comments from that email don't make any sense to me. I can't understand what he was thinking, unless he's just unusually prone to flattering other people's work (I don't know Bentley personally, but I've met other people who do this, much to my irritat…

> The asymptotic optimality of samplesort is in the sense that it takes (1 + o(1)) N log N / log 2 comparisons, i.e., you can't beat it by any constant factor.

Why isn't it used everywhere that people currently use Quicksort? I've never actually heard of anyone using Samplesort except in a parallel context.

Re: New string search algorithm

#42

Post by cperciva »

kragen wrote: post #41
cperciva wrote: post #40

Earlier quoted context omitted.

The asymptotic optimality of samplesort is in the sense that it takes (1 + o(1)) N log N / log 2 comparisons, i.e., you can't beat it by any constant factor. Bentley's comments from that email don't make any sense to me. I can't understand what he was thinking, unless he's just unusually prone to flattering other people's work (I don't know Bentley personally, but I've met other people who do this, much to my irritat…

> The asymptotic optimality of samplesort is in the sense that it takes (1 + o(1)) N log N / log 2 comparisons, i.e., you can't beat it by any constant factor. Why isn't it used everywhere that people currently use Quicksort? I've never actually heard of anyone using Samplesort except in a parallel context.

Two reasons: 1. It's a PITA to implement; 2. You need a large N to overcome the o(1), and at that point you're usually dominated by the performance of your memory hierarchy rather than by the cost of doing compares.

Last I heard, python's built-in sort was a type of samplesort, though, so it isn't completely unused.

Re: New string search algorithm

#43

Post by kragen »

cperciva wrote: post #42
kragen wrote: post #41

Earlier quoted context omitted.

> The asymptotic optimality of samplesort is in the sense that it takes (1 + o(1)) N log N / log 2 comparisons, i.e., you can't beat it by any constant factor. Why isn't it used everywhere that people currently use Quicksort? I've never actually heard of anyone using Samplesort except in a parallel context.

Two reasons: 1. It's a PITA to implement; 2. You need a large N to overcome the o(1), and at that point you're usually dominated by the performance of your memory hierarchy rather than by the cost of doing compares. Last I heard, python's built-in sort was a type of samplesort, though, so it isn't completely unused.

Your #2 suggests that it would be slower than ordinary Quicksort on normal-sized datasets. But dual-pivot quicksort is faster than ordinary Quicksort on normal-sized datasets. So in at least one sense, dual-pivot is not a step in the direction of samplesort.

Python's built-in sort is timsort, last I heard, which is a variant of mergesort that looks for existing sorted or backwards runs in order to run faster in the common cases of mostly-sorted or mostly-backwards data. It's true that Python's built-in sort was a samplesort variant until 2002, though, which I didn't know.

(It does seem like Samplesort's virtue of minimizing comparisons would be particularly desirable in an environment like Python, where every comparison potentially involves a call into slow interpreted code.)

Re: New string search algorithm

#44

Post by jacobolus »

cperciva wrote: post #42
kragen wrote: post #41

Earlier quoted context omitted.

> The asymptotic optimality of samplesort is in the sense that it takes (1 + o(1)) N log N / log 2 comparisons, i.e., you can't beat it by any constant factor. Why isn't it used everywhere that people currently use Quicksort? I've never actually heard of anyone using Samplesort except in a parallel context.

Two reasons: 1. It's a PITA to implement; 2. You need a large N to overcome the o(1), and at that point you're usually dominated by the performance of your memory hierarchy rather than by the cost of doing compares. Last I heard, python's built-in sort was a type of samplesort, though, so it isn't completely unused.

The previous Python sort was a type of samplesort, but the current one is a “adaptive, stable, natural mergesort” by Tim Peters (“timsort”). On random data I think it performs about the same or slightly worse, but when data has some structure, it performs much better. See http://bugs.python.org/file4451/timsort.txt

Re: New string search algorithm

#45

Post by dasht »

epistasis wrote: post #34
dasht wrote: post #33

Earlier quoted context omitted.

Thanks. That's interesting. I'm pretty confident that you don't really need to compress the reference that way. It doesn't make a lot of intuitive sense that you would, in a way: streaming over the reference can be very fast and the question is how many reads you can align per pass, how flexibly, and with how low a pre-processing cost. I think my stuff (which doesn't count since we didn't get to publication stage for…

You'd be prerty confident in the other direction once you understand the problem better. The BWT is not compression as much as an extremely clever way of rearranging the haystack. There are many many different string alignment (not string search) algorithms that are useful with DNA, and where the BWT is used your algorithm is not going to be in the realm of useful. BWT based aligners run in time completely independen…

Given a (not even very large) cluster, we (with the fairly brute force-ish but cleverly tuned NFA) can populate hash tables for the read-based NFA of your 2 billion needles just about as fast as you can transmit the data and give you optimal alignment (by flexible criteria) just about as fast as you can then stream through the 3 billion base pairs. We are down to, at most, single or double digit dollar differences either way, but mine is vastly simpler and easier to tweak. Probably, we can do my way cheaper as the commodity computing market improves.

If you want to tell me that BWT is more useful for something like searching an FBI or CIA DNA database, and that intel types want to encourage commercial development of BWT (even if irrational for the customers) to subsidize its covert use in intel -- that I can believe. I can see where it would be helpful not for resequencing (a way to read off interesting details of an individuals genotype based on a lot of reads) but rather for fingerprinting of suspects and surveillance targets against a large database of reference genomes.

Re: New string search algorithm

#46

Post by [deleted] »

dasht wrote: post #45
epistasis wrote: post #34

Earlier quoted context omitted.

You'd be prerty confident in the other direction once you understand the problem better. The BWT is not compression as much as an extremely clever way of rearranging the haystack. There are many many different string alignment (not string search) algorithms that are useful with DNA, and where the BWT is used your algorithm is not going to be in the realm of useful. BWT based aligners run in time completely independen…

Given a (not even very large) cluster, we (with the fairly brute force-ish but cleverly tuned NFA) can populate hash tables for the read-based NFA of your 2 billion needles just about as fast as you can transmit the data and give you optimal alignment (by flexible criteria) just about as fast as you can then stream through the 3 billion base pairs. We are down to, at most, single or double digit dollar differences ei…

[deleted]

Re: New string search algorithm

#47

Post by repsilat »

pjscott wrote: post #13
tansey wrote: post #4

From the site: >Preprocessing phase in O(M) space and time complexity. Searching phase average O(N) time complexity and O(N*M) worst case complexity. I don't trust the analysis of someone referring to "average O(N) time"; Big O notation refers to boundary times. Edit: Okay, based on arguments here and on [1], I'm going to accept that maybe he's just bastardizing the notation. [1] http://stackoverflow.com/questions/39…

It could be just an abuse of notation, in the same way that people say that Quicksort is O(n lg n) on average. Sure, on perverse data the best time bound you can prove is O(n^2), but on random data you get expected O(n lg n) time, and on typical data with good partition selection you can generally expect to not go quadratic. (You could also use the O(n) time median algorithm to construct a truly O(n lg n) Quicksort,…

> ...an abuse of notation, in the same way that people say that Quicksort is O(n lg n) on average.

I think I may have misunderstood what you meant by this. If I have, I apologise, if I haven't...

Talking about the average-case complexity of algorithms with Big-Oh notation is in no way an "abuse" of that notation. If the average time complexity of an algorithm is `O(f(n))`, then its running time averaged over all inputs of size `n` is bounded above (in some sense) by `f(n)`.

I guess that statement doesn't say that the number of comparisons or swaps or "steps" the algorithms must make to complete is `O(n lg n)`. Perhaps that's what you meant.

Re: New string search algorithm

#48

Post by anatoly »

kragen wrote: post #39
cperciva wrote: post #37

Earlier quoted context omitted.

Dual-Pivot Quicksort is an "awesome new algorithm"? Hardly. It's very small step in the direction of Samplesort -- which is asymptotically optimal and has been around for four decades. Dual-Pivot Quicksort is a demonstration that someone didn't read the existing literature; nothing more.

Unfortunately I don't have access to the Samplesort paper, so I don't know which sense of "asymptotically optimal" you're using here. Quicksort is already asymptotically optimal in the sense that its asymptotic average performance is Θ(N log N), which is the best a sorting algorithm can do. It's true that dual-pivot quicksort is a step in the direction of Samplesort. (I do understand Samplesort well enough to say tha…

When that thread came up originally, I was intrigued by the idea of the dual-pivot quicksort, and went on to browse Robert Sedgewick's Ph.D. thesis, _Quicksort_, published in 1978. Sedgewick considers and analyzes several variants of quicksort in his thesis, and I've quickly discovered that he analyzes and dismisses the dual-pivot variant under a different name. I don't know whose analysis is better, but it does follow that we shouldn't treat dual-pivot qsort as an original invention (not to detract from Vladimir Yaroslavskiy's doubtless ingenuity).

Here's an excerpt from the email I wrote to Prof. Sedgewick back then; he didn't reply, so I've no idea what he thinks about this:

"I believe that your PhD thesis studies this under the name of "double partition modification". I could find no real difference between the two algorithms. Yaroslavsky claims to achieve a factor of 0.8 improvements over the standard quicksort on the number of exchanges (neutral on comparisons), while your analysis led you to reject the technique after concluding it required many more comparisons than the standard quicksort. I've only attempted very cursorily to reconcile the math; it seems that both your thesis and Yaroslavsky arrive at 0.8n(log n) as the average number of swaps, but you have (1/3) n(log n) as the average number of swaps in the classic algorithm while Yaroslavsky has 1.0 n(log n) for the same thing, so what he sees as an improvement you viewed as a disaster. My interpretation of this may be wrong, and I haven't attempted to verify either analysis yet."

The "classic algorithm" in the above is the classic quicksort as presented by Sedgewick in the thesis, which is slightly different than e.g. the standard Java implementation. I lost interest soon thereafter and stopped investigating this, but it shouldn't be too difficult to find out who was right in that algorithm comparison, if someone's interested enough.

Re: New string search algorithm

#49

Post by fmap »

kragen wrote: post #43
cperciva wrote: post #42

Earlier quoted context omitted.

Two reasons: 1. It's a PITA to implement; 2. You need a large N to overcome the o(1), and at that point you're usually dominated by the performance of your memory hierarchy rather than by the cost of doing compares. Last I heard, python's built-in sort was a type of samplesort, though, so it isn't completely unused.

Your #2 suggests that it would be slower than ordinary Quicksort on normal-sized datasets. But dual-pivot quicksort is faster than ordinary Quicksort on normal-sized datasets. So in at least one sense, dual-pivot is not a step in the direction of samplesort. Python's built-in sort is timsort, last I heard, which is a variant of mergesort that looks for existing sorted or backwards runs in order to run faster in the c…

I just read the original paper on samplesort, so this might not be the most up to date description, but the basic idea is as follows:

- From an input sequence of length n, choose a random subsequence of length k.

- Sort the subsequence.

- Partition the remaining (n-k) elements of the original sequence into the (k+1) partitions given by the subsequence.

- Sort the (k+1) partitions.

In the paper, the partitioning and sorting is always done using quicksort. Any n*log(n) sorting algorithm should work though, which includes using samplesort recursively.

If you use an optimal value for k (and this might be a significant fraction of n), you can prove that lim_{n->infty} E(C_n)/log(n!) = 1, where E(C_n) is the expected number of comparisons for a sequence of length n.

Now, using samplesort recursively, quicksort is samplesort with k = 1. Double-Pivot quicksort is samplesort with k = 2.

Re: New string search algorithm

#50

Post by atjj »

dasht wrote: post #45
epistasis wrote: post #34

Earlier quoted context omitted.

You'd be prerty confident in the other direction once you understand the problem better. The BWT is not compression as much as an extremely clever way of rearranging the haystack. There are many many different string alignment (not string search) algorithms that are useful with DNA, and where the BWT is used your algorithm is not going to be in the realm of useful. BWT based aligners run in time completely independen…

Given a (not even very large) cluster, we (with the fairly brute force-ish but cleverly tuned NFA) can populate hash tables for the read-based NFA of your 2 billion needles just about as fast as you can transmit the data and give you optimal alignment (by flexible criteria) just about as fast as you can then stream through the 3 billion base pairs. We are down to, at most, single or double digit dollar differences ei…

Burroughs-Wheeler transform is not just an academic idea, but is the basis for one of the standard tools for aligning short reads: http://bowtie-bio.sourceforge.net/index.shtml . There was a mention of compression earlier in the thread, but this is a red herring: BWT also used in bzip2's compression, but the use with DNA sequences is not to compress, but a pre-processing step on the haystack. As epistasis said, when you have billions needles, it makes sense to pre-process the haystack so that the per-needle cost is as low as possible.

As for the FBI's DNA database, this does not consist of sequence data, but, I believe, just microsatellite data. Even if they had full sequence data, it wouldn't make sense to search for new samples against the whole database, but to align the sample with a reference genome and then match the variations across a database of variations.

Post reply on HN