8 ms·

Sublinear Time Algorithms

138 points by gone35 2y ago

dataflow 2y ago
> There are problems for which deterministic exact sublinear time algorithms are known. I can imagine silly examples (like "find the minimum element in this list under the assumption that no more than O(sqrt(n)) elements exceed the minimum"...), but what's an interesting example of this?
- gleenn 2y ago
  Anything probabilistic? There are so many interesting fields where you can assume the distribution of a dataset and the take a sample of data and assert things about it with a high degree of confidence. All of modern AI is built on so much of this. All the Deep Neural Nets are making grand assumptions about the shape of meaning of data, they literally assume convexity of the space and they have clearly very interesting results despite the imprecision of the model. Anything dealing with finance is also dealing in lack of data. So if you had a list of prices of a stock over time, you could probably start making assumptions exactly like that, tgat the probability that it doubles over a short time is so unlikely so you can subsample the data and have it still be super useful to make assumptions exactly, especially when you have intractably large data.
  - dataflow 2y ago
    >> deterministic exact > Anything probabilistic? Are you sure you're answering the same question I'm asking?
- _jab 2y ago
  Binary search is the obvious example. What it and your example have in common is that a significant constraint exists on the input. I can't imagine how a deterministic algorithm with unconstrained input can process that input in sublinear time, but I would love to learn otherwise.
  - dataflow 2y ago
    I can't imagine that's what they meant? The text very specifically says: "Indeed, it is hard to imagine doing much better than that, since for any nontrivial problem, it would seem that an algorithm must consider all of the input in order to make a decision." For them to be thinking of binary search, they would have to be effectively saying "it is hard to think of binary search", which would be a rather absurd position from a CS professor, especially given binary search is quite literally the first algorithm every programmer learns. So I took it to mean there's something interesting here where the inputs could literally be anything, not heavily constrained. But I can't imagine what that might be.
    - kadoban 2y ago
      > especially given binary search is quite literally the first algorithm every programmer learns. I get what you're saying, and it doesn't change your point, but: no _way_ is binary search the first algorithm people learn. For binary search to even be intelligible you already have to know, at a minumum linear search and the concept of sorting (you probably know a sorting algorithm first). You also learn dozens of other really simple algorithms first in practice.
      - bee_rider 2y ago
        Agreed, WRT the bigger picture; lots of little algorithms could come before binary search. But, giving them binary search before sorting kinda works. It is motivating. If you do sorting first, it just seems like a weird high-effort excursion into a niche bookkeeping thing about lists. Once they see how fast binary search is (just give them pre-sorted lists to run it on), sorting becomes interesting, right?
        kadoban 2y ago
        Yeah, it does work as something you learn with/right-before/right-after a sorting algorithm, depending on the teaching style.
        linguae 2y ago
- tbrownaw 2y ago
  Public opinion polling is sub-linear in the size of the population.
  - dataflow 2y ago
    > Public opinion polling is sub-linear in the size of the population. How is public opinion polling deterministic and exact?
- wellow 2y ago
  Lempel-Ziv compression is a good example: https://arxiv.org/abs/2409.12146 https://arxiv.org/abs/2409.12146
- latency-guy2 2y ago
  I wouldn't call that example silly IMO. I'd consider all the varieties of B-Tree to be real example, which goes to any DBMS. You can extend this out to any direction you want like logging for concrete examples. GIS/Mapping/computer vision has tons of algorithms and data structures that all needed to do better than linear time as well. Stream processing in general is another, but that ends up being probabilistic more often than not, so weak punt into that direction. If you expand the use case out to sublinear space as well, I'd argue for compression of all kinds.
- z2210558 2y ago
  Assuming shuffled list: estimate of mean, estimate of cardinality etc etc
  - munchler 2y ago
    I think any sort of estimation is ruled out by the word “exact”.
- qyph 2y ago
  https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test though it's number theory, and concerned with numbers of size n, rather than lists of length n. Also relevant: https://www.cs.yale.edu/homes/aspnes/pinewiki/Derandomization.html https://www.cs.yale.edu/homes/aspnes/pinewiki/Derandomizatio...
  - dataflow 2y ago
    > https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test though it's number theory, and concerned with numbers of size n, rather than lists of length n. They were talking about not reading a lot of the input, so that's not it.
  - Ar-Curunir 2y ago
    AKS is not sublinear. It runs in poly(n) time, where n is the number of bits in the input (i.e. input size).
  - alok-g 2y ago
    For that case, a better 'n' to use could be the number of digits in the number.
- minutillo 2y ago
  https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-sea...
  - dataflow 2y ago
    Isn't that O(mn) worst-case run time?
    - quuxplusone 2y ago
      No, it's O(n) worst case. (The Wikipedia sidebar says "O(mn)," but that's apparently for a maimed version of the algorithm without a key part they're calling "the Galil rule." That's a special usage of the phrase "worst case"! In the absolute worst case, your implementation could have a bug and never terminate at all!) Anyway, the point is that it's O(n/m) in the usual case. Which remains technically linear, not sub-linear; but at least it's O(n) with a constant factor smaller than 1.
      - dataflow 2y ago
        > No, it's O(n) worst case. (The Wikipedia sidebar says "O(mn)," but that's apparently for a maimed version of the algorithm without a key part they're calling "the Galil rule.") It's not "maimed", it's literally the original algorithm. And what the article was specifically analyzing. And exactly what the parent was citing. "No" here makes no sense, unless your goal was just to write "no" to someone on the internet. > That's a special usage of the phrase "worst case"! In the absolute worst case, your implementation could have a bug and never terminate at all! Wikipedia is describing that algorithm, not a different broken one. If your code is buggy then you're not implementing that algorithm, you're implementing a different one that happens to be buggy. It's completely absurd to suggest "the absolute worst case" of an algorithm could include that of a different algorithm. Whether the latter is correct or buggy. > Anyway, the point is that it's O(n/m) in the usual case. Sure, and the halting problem is O(1) in the best case. > Which remains technically linear, not sub-linear So it's neither an example of what the page was talking about (sublinear) nor an answer to my question (interesting sublinear). > but at least it's O(n) with a constant factor smaller than 1. If "usually only reads a fraction of the input" was what I was looking for, I would've realized String.indexOf(char) or Array.find(element) is an answer, and not needed to ask a question here.
- BugsJustFindMe 2y ago
  Consider that you often need to decide when to stop looking at data before making a decision using what you've seen so far. https://en.wikipedia.org/wiki/Optimal_stopping https://en.wikipedia.org/wiki/Optimal_stopping
  - dataflow 2y ago
    Cool as that is, I don't think that's a "deterministic exact sublinear time algorithm".
    - BugsJustFindMe 2y ago
      You're probably right. Apologies. I think I misread the question initially.
- ssivark 2y ago
  Think from an information theory perspective. It is rarely true that you cannot say anything more about the data than what is assumed by classical algorithms. We almost always have some more information depending on the specific domain under consideration. Eg: Sorting a list of ages might be very different from sorting a list of account balances. Any time I have information that reduces the entropy of the dataset, I want to be able to leverage that into runtime improvements of algorithms for pertinent questions. And it would be great to develop a structured framework for that instead of handling special cases in an ad-hoc manner.
  - ssivark 2y ago
    As one example of such a more general framework -- (variants of) belief propagation might be a good answer if dataset constraints could be cleanly formulated as distributions to be reasoned with.
    - oxavier 2y ago
      My work is about inferring solutions to Constraint Satisfaction Problem by using belief propagation in the corresponding constraint network, a few keywords caught my eye here :) Do you have any illustrative example so I can understand better what you are hinting at? Cheers
- an_ko 2y ago
  Fully dynamic connectivity on general graphs comes to mind. https://en.m.wikipedia.org/wiki/Dynamic_connectivity https://en.m.wikipedia.org/wiki/Dynamic_connectivity (Graphs, with operations to connect and disconnect nodes, and to check whether two nodes are connected by some path.) State of the art there is poly-logarithmic time worst case.
- JonChesterfield 2y ago
  Data structured as trees permit a lot of sublinear operations. Set intersection for example, you traverse the two trees in the same order, and where a node exists in one and not the other, you know nothing under it is in the intersection.
  - Aurornis 2y ago
    In this case, Sublinear Algorithms refers to algorithms that don't consider the entire input set. A B-Tree would not qualify because it must first consider the entire input set. Only later operations can be less than O(n) because you've already done O(n) or greater work on the data set.
- indoordin0saur 2y ago
  I'm surprised this is even a debate on HN. Aren't we mostly computer scientists here? Several examples on wikipedia: https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_commo...
- deycallmeajay 2y ago
  What about GWP-ASan? It basically samples a portion of allocations with ASan looking for memory corruption bugs. If your app is used enough it’ll find the bugs eventually without the performance overhead. https://llvm.org/docs/GwpAsan.html https://llvm.org/docs/GwpAsan.html
- ice-water 2y ago
  A round-robin tournament with n players, where you have the results (win/lose) of all the games and you must determine whether there is a player who won all his games. The input is the n(n-1)/2 bits indicating the results, but the existence of a winner can be determined in O(n) steps (fun exercise).
dooglius 2y ago
Often for problems taking integer input x, formal CS will define the input to be something like 1^x (the character '1' repeated x times, as opposed to binary) so that the time complexity is in terms of x. This class of problems seems amenable to sublinear time since only only needs log(x) steps to determine x.
- LPisGood 2y ago
  Actually if you try to formally define sublinear time algorithms in this manner they all collapse to constant time algorithms. To see why, realize that to determine x, the TM needs to look at x many bits. If this algorithm only needed, say, log(x) many bits to produce output then all input values with more than log(x) bits are indistinguishable by this TM.
  - tromp 2y ago
    The notion of sublinear time only makes sense with Random-access Machines [1], not with Turing Machines. [1] https://en.wikipedia.org/wiki/Random-access_machine https://en.wikipedia.org/wiki/Random-access_machine
    - dooglius 2y ago
      Pretty much any standard notion of time complexity requires one to assume a random access machine, or else e.g. an array access is O(index) time.
      - tromp 2y ago
        Turing machines are still quite prevalent in complexity theory. Of course, robust classes like P and NP are invariant under various models, but also classes like DTIME and NTIME are defined for (single- or multi-tape) Turing machines [1]. [1] https://en.wikipedia.org/wiki/DTIME https://en.wikipedia.org/wiki/DTIME
shae 2y ago
This sounds like a useful way to mix in statistics and get useful approximations. I'm reading one of the survey links and it's approximately eye opening.
doormatt 2y ago
So like HyperLogLog?
- qyph 2y ago
  Hyperloglog analyses generally assume access to the full data stream, and so are O(n) at a minimum. Perhaps by running hyperloglog on a sublinear sample of the dataset you'd get an algorithm in this class.
  - doormatt 2y ago
    That makes sense, thanks for explaining!
- dataflow 2y ago
  HyperLogLog uses sublinear space, not sublinear time.

138 points by gone35 2y ago

> There are problems for which deterministic exact sublinear time algorithms are known. I can imagine silly examples (like "find the minimum element in this list under the assumption that no more than O(sqrt(n)) elements exceed the minimum"...), but what's an interesting example of this?

gleenn 2y ago
Anything probabilistic? There are so many interesting fields where you can assume the distribution of a dataset and the take a sample of data and assert things about it with a high degree of confidence. All of modern AI is built on so much of this. All the Deep Neural Nets are making grand assumptions about the shape of meaning of data, they literally assume convexity of the space and they have clearly very interesting results despite the imprecision of the model. Anything dealing with finance is also dealing in lack of data. So if you had a list of prices of a stock over time, you could probably start making assumptions exactly like that, tgat the probability that it doubles over a short time is so unlikely so you can subsample the data and have it still be super useful to make assumptions exactly, especially when you have intractably large data.
- dataflow 2y ago
  >> deterministic exact > Anything probabilistic? Are you sure you're answering the same question I'm asking?
_jab 2y ago
Binary search is the obvious example. What it and your example have in common is that a significant constraint exists on the input. I can't imagine how a deterministic algorithm with unconstrained input can process that input in sublinear time, but I would love to learn otherwise.
- dataflow 2y ago
  I can't imagine that's what they meant? The text very specifically says: "Indeed, it is hard to imagine doing much better than that, since for any nontrivial problem, it would seem that an algorithm must consider all of the input in order to make a decision." For them to be thinking of binary search, they would have to be effectively saying "it is hard to think of binary search", which would be a rather absurd position from a CS professor, especially given binary search is quite literally the first algorithm every programmer learns. So I took it to mean there's something interesting here where the inputs could literally be anything, not heavily constrained. But I can't imagine what that might be.
  - kadoban 2y ago
    > especially given binary search is quite literally the first algorithm every programmer learns. I get what you're saying, and it doesn't change your point, but: no _way_ is binary search the first algorithm people learn. For binary search to even be intelligible you already have to know, at a minumum linear search and the concept of sorting (you probably know a sorting algorithm first). You also learn dozens of other really simple algorithms first in practice.
    - bee_rider 2y ago
      Agreed, WRT the bigger picture; lots of little algorithms could come before binary search. But, giving them binary search before sorting kinda works. It is motivating. If you do sorting first, it just seems like a weird high-effort excursion into a niche bookkeeping thing about lists. Once they see how fast binary search is (just give them pre-sorted lists to run it on), sorting becomes interesting, right?
      - kadoban 2y ago
        Yeah, it does work as something you learn with/right-before/right-after a sorting algorithm, depending on the teaching style.
      - linguae 2y ago
tbrownaw 2y ago
Public opinion polling is sub-linear in the size of the population.
- dataflow 2y ago
  > Public opinion polling is sub-linear in the size of the population. How is public opinion polling deterministic and exact?
wellow 2y ago
Lempel-Ziv compression is a good example: https://arxiv.org/abs/2409.12146 https://arxiv.org/abs/2409.12146
latency-guy2 2y ago
I wouldn't call that example silly IMO. I'd consider all the varieties of B-Tree to be real example, which goes to any DBMS. You can extend this out to any direction you want like logging for concrete examples. GIS/Mapping/computer vision has tons of algorithms and data structures that all needed to do better than linear time as well. Stream processing in general is another, but that ends up being probabilistic more often than not, so weak punt into that direction. If you expand the use case out to sublinear space as well, I'd argue for compression of all kinds.
z2210558 2y ago
Assuming shuffled list: estimate of mean, estimate of cardinality etc etc
- munchler 2y ago
  I think any sort of estimation is ruled out by the word “exact”.
qyph 2y ago
https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test though it's number theory, and concerned with numbers of size n, rather than lists of length n. Also relevant: https://www.cs.yale.edu/homes/aspnes/pinewiki/Derandomization.html https://www.cs.yale.edu/homes/aspnes/pinewiki/Derandomizatio...
- dataflow 2y ago
  > https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test though it's number theory, and concerned with numbers of size n, rather than lists of length n. They were talking about not reading a lot of the input, so that's not it.
- Ar-Curunir 2y ago
  AKS is not sublinear. It runs in poly(n) time, where n is the number of bits in the input (i.e. input size).
- alok-g 2y ago
  For that case, a better 'n' to use could be the number of digits in the number.
minutillo 2y ago
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-sea...
- dataflow 2y ago
  Isn't that O(mn) worst-case run time?
  - quuxplusone 2y ago
    No, it's O(n) worst case. (The Wikipedia sidebar says "O(mn)," but that's apparently for a maimed version of the algorithm without a key part they're calling "the Galil rule." That's a special usage of the phrase "worst case"! In the absolute worst case, your implementation could have a bug and never terminate at all!) Anyway, the point is that it's O(n/m) in the usual case. Which remains technically linear, not sub-linear; but at least it's O(n) with a constant factor smaller than 1.
    - dataflow 2y ago
      > No, it's O(n) worst case. (The Wikipedia sidebar says "O(mn)," but that's apparently for a maimed version of the algorithm without a key part they're calling "the Galil rule.") It's not "maimed", it's literally the original algorithm. And what the article was specifically analyzing. And exactly what the parent was citing. "No" here makes no sense, unless your goal was just to write "no" to someone on the internet. > That's a special usage of the phrase "worst case"! In the absolute worst case, your implementation could have a bug and never terminate at all! Wikipedia is describing that algorithm, not a different broken one. If your code is buggy then you're not implementing that algorithm, you're implementing a different one that happens to be buggy. It's completely absurd to suggest "the absolute worst case" of an algorithm could include that of a different algorithm. Whether the latter is correct or buggy. > Anyway, the point is that it's O(n/m) in the usual case. Sure, and the halting problem is O(1) in the best case. > Which remains technically linear, not sub-linear So it's neither an example of what the page was talking about (sublinear) nor an answer to my question (interesting sublinear). > but at least it's O(n) with a constant factor smaller than 1. If "usually only reads a fraction of the input" was what I was looking for, I would've realized String.indexOf(char) or Array.find(element) is an answer, and not needed to ask a question here.
BugsJustFindMe 2y ago
Consider that you often need to decide when to stop looking at data before making a decision using what you've seen so far. https://en.wikipedia.org/wiki/Optimal_stopping https://en.wikipedia.org/wiki/Optimal_stopping
- dataflow 2y ago
  Cool as that is, I don't think that's a "deterministic exact sublinear time algorithm".
  - BugsJustFindMe 2y ago
    You're probably right. Apologies. I think I misread the question initially.
ssivark 2y ago
Think from an information theory perspective. It is rarely true that you cannot say anything more about the data than what is assumed by classical algorithms. We almost always have some more information depending on the specific domain under consideration. Eg: Sorting a list of ages might be very different from sorting a list of account balances. Any time I have information that reduces the entropy of the dataset, I want to be able to leverage that into runtime improvements of algorithms for pertinent questions. And it would be great to develop a structured framework for that instead of handling special cases in an ad-hoc manner.
- ssivark 2y ago
  As one example of such a more general framework -- (variants of) belief propagation might be a good answer if dataset constraints could be cleanly formulated as distributions to be reasoned with.
  - oxavier 2y ago
    My work is about inferring solutions to Constraint Satisfaction Problem by using belief propagation in the corresponding constraint network, a few keywords caught my eye here :) Do you have any illustrative example so I can understand better what you are hinting at? Cheers
an_ko 2y ago
Fully dynamic connectivity on general graphs comes to mind. https://en.m.wikipedia.org/wiki/Dynamic_connectivity https://en.m.wikipedia.org/wiki/Dynamic_connectivity (Graphs, with operations to connect and disconnect nodes, and to check whether two nodes are connected by some path.) State of the art there is poly-logarithmic time worst case.
JonChesterfield 2y ago
Data structured as trees permit a lot of sublinear operations. Set intersection for example, you traverse the two trees in the same order, and where a node exists in one and not the other, you know nothing under it is in the intersection.
- Aurornis 2y ago
  In this case, Sublinear Algorithms refers to algorithms that don't consider the entire input set. A B-Tree would not qualify because it must first consider the entire input set. Only later operations can be less than O(n) because you've already done O(n) or greater work on the data set.
indoordin0saur 2y ago
I'm surprised this is even a debate on HN. Aren't we mostly computer scientists here? Several examples on wikipedia: https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_commo...
deycallmeajay 2y ago
What about GWP-ASan? It basically samples a portion of allocations with ASan looking for memory corruption bugs. If your app is used enough it’ll find the bugs eventually without the performance overhead. https://llvm.org/docs/GwpAsan.html https://llvm.org/docs/GwpAsan.html
ice-water 2y ago
A round-robin tournament with n players, where you have the results (win/lose) of all the games and you must determine whether there is a player who won all his games. The input is the n(n-1)/2 bits indicating the results, but the existence of a winner can be determined in O(n) steps (fun exercise).

dooglius 2y ago

Often for problems taking integer input x, formal CS will define the input to be something like 1^x (the character '1' repeated x times, as opposed to binary) so that the time complexity is in terms of x. This class of problems seems amenable to sublinear time since only only needs log(x) steps to determine x.

LPisGood 2y ago
Actually if you try to formally define sublinear time algorithms in this manner they all collapse to constant time algorithms. To see why, realize that to determine x, the TM needs to look at x many bits. If this algorithm only needed, say, log(x) many bits to produce output then all input values with more than log(x) bits are indistinguishable by this TM.
- tromp 2y ago
  The notion of sublinear time only makes sense with Random-access Machines [1], not with Turing Machines. [1] https://en.wikipedia.org/wiki/Random-access_machine https://en.wikipedia.org/wiki/Random-access_machine
  - dooglius 2y ago
    Pretty much any standard notion of time complexity requires one to assume a random access machine, or else e.g. an array access is O(index) time.
    - tromp 2y ago
      Turing machines are still quite prevalent in complexity theory. Of course, robust classes like P and NP are invariant under various models, but also classes like DTIME and NTIME are defined for (single- or multi-tape) Turing machines [1]. [1] https://en.wikipedia.org/wiki/DTIME https://en.wikipedia.org/wiki/DTIME

shae 2y ago

This sounds like a useful way to mix in statistics and get useful approximations. I'm reading one of the survey links and it's approximately eye opening.

doormatt 2y ago

So like HyperLogLog?

qyph 2y ago
Hyperloglog analyses generally assume access to the full data stream, and so are O(n) at a minimum. Perhaps by running hyperloglog on a sublinear sample of the dataset you'd get an algorithm in this class.
- doormatt 2y ago
  That makes sense, thanks for explaining!
dataflow 2y ago
HyperLogLog uses sublinear space, not sublinear time.