17 ms·

Ask HN: What is new in algorithms and data structures these days?

737 points by jvanderbot 4y ago

Algs/DS were my first love in CS. Nowadays, all we hear about is AI/ML. There must be hardware/software improvements coming from or necessitating fundamental Algs/DS research. Care to share any of the favorite recent results? Are there big fields still making gains behind all this computing surge?

hidudeb 4y ago
[flagged]
barbarr 4y ago
I'm not in the field but it seems that SODA (ACM/SIAM Symposium on Discrete Algorithms) is a top conference in DSA and might be a good place to check. Here's the abstract book for 2022: [1]. [1] https://www.siam.org/Portals/0/Conferences/About_SIAM_Conferences/SODA_2022_ABSTRACTS_V2_interactive.pdf https://www.siam.org/Portals/0/Conferences/About_SIAM_Confer...
sarojmoh1 4y ago
First Love?! Haha, jk. I'm currently re-studying them just bc I'm interview prepping. I wonder if whiteboarding for DS/Algo is gonna be a thing of the past too though. I would imagine there's certainly new DS/Algos in progress to aide ML training efficiency
epberry 4y ago
Unfortunately for you my favorite recent algorithms result uses AI as part of improving a very traditional algorithm. The paper is "Learned Index Structures" https://blog.acolyer.org/2018/01/08/the-case-for-learned-index-structures-part-i/ https://blog.acolyer.org/2018/01/08/the-case-for-learned-ind...
- morkpek 4y ago
  This is a wonderful paper. In a similar vein, "Algorithms with Predictions" (https://arxiv.org/pdf/2006.09123.pdf https://arxiv.org/pdf/2006.09123.pdf) presents a bunch of fun algorithmic problems related to bringing AI into traditional algorithms.
curiousgibbon 4y ago
Negative weight single source shortest paths in near-linear time: https://arxiv.org/abs/2203.03456 https://arxiv.org/abs/2203.03456 Obligatory Quanta link: https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/ https://www.quantamagazine.org/finally-a-fast-algorithm-for-...
- nodespace 4y ago
  Are there any implimentations of this? I got started working on one for rust, but got kinda stuck in a few places. This could be very useful for RTS AI I think, or anything where you need to optimize managing resources and build orders, if I understand negative weight shortest paths correctly.
samwillis 4y ago
Anything CRDT (conflict free replicated datatypes: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...) related is fun to read up on and play with. Papers and references (page maintained by central academic in the world of CRDTs): https://crdt.tech https://crdt.tech Group doing research into how they can be used to build interesting collaborative (and async) applications: https://www.inkandswitch.com https://www.inkandswitch.com A few of the major open source implementations - mostly for rich text editing or JSON like data structures: - Yjs: https://github.com/yjs/yjs https://github.com/yjs/yjs - Automerge: https://github.com/automerge/automerge https://github.com/automerge/automerge - Peritext: https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/ - Dimond types: https://github.com/josephg/diamond-types https://github.com/josephg/diamond-types People building eventually consistent database syncing with them: - https://electric-sql.com https://electric-sql.com (Postgres <-> SQLite) - https://vlcn.io https://vlcn.io (SQLite <-> SQLite) Open source colaborative servers (coordination, persistance, presence): - https://github.com/ueberdosis/hocuspocus https://github.com/ueberdosis/hocuspocus - https://github.com/partykit/partykit https://github.com/partykit/partykit - https://github.com/firesync-org/firesync https://github.com/firesync-org/firesync
- josephg 4y ago
  Diamond types author here. I’m working on another blog post - I had a big breakthrough getting collaborative text editing many times faster again using some new ideas. I’m in the process of writing up our new work now. And there’s another hard problem I’m stuck on: so, CRDTs like mine and Yjs use (random agent id, sequence number) as unique IDs for operations. But a troublesome user might reuse an operation ID, sending different operations to different peers and giving them the same (agent, seq) pair. This results in really awful, weird bugs. Martin Kleppman wrote a paper about BFT in CRDTs. His suggestion is we do what git does and use SHA hashes for IDs instead. But there’s two problems: 1. We don’t want to store a hash for every keystroke a user makes. That would get big, fast. We want a DAG of hashes like git, except a hash is generated with each keystroke. How do we build an efficient system that can query by hash, without storing all of the hashes? 2. I want users to be able to permanently delete inserted text. If I accidentally paste an AWS key into a document, I don’t want that key in the document history forever. How do I enable that while still getting all the benefits of the hashing system above? (Note if your hash includes the typed character, even if you delete the character itself from disk, you can trivially brute force the hash to recover any typed characters). Each of these problems in isolation has a solution. But the real prize is how do you solve both at the same time? I think this problem has a solution but I don’t think anyone has solved it yet. Want to name an algorithm and get my eternal respect? Here’s your chance.
hnfong 4y ago
CS 168: The Modern Algorithmic Toolbox, Spring 2023 https://web.stanford.edu/class/cs168/index.html https://web.stanford.edu/class/cs168/index.html I didn't have time to go through all of this, but the parts that I did read were very interesting to me. It's not even cutting edge new stuff of 202x, probably most of them are new-ish results from ~2000 onwards.
- trebligdivad 4y ago
  Thanks! That looks great, for those of us who did our algorithm courses too long ago!
vitorsr 4y ago
- Streaming algorithms [1] - Eventual consistency [2] - Refinement types [3], [4] [1] https://www2.cs.uh.edu/~ceick/6340/Streams.pdf https://www2.cs.uh.edu/~ceick/6340/Streams.pdf [2] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/final-printversion-10-5-14.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... [3] https://ranjitjhala.github.io/static/trust_but_verify.pdf https://ranjitjhala.github.io/static/trust_but_verify.pdf [4] https://ranjitjhala.github.io/static/refinement_types_for_typescript.pdf https://ranjitjhala.github.io/static/refinement_types_for_ty...
- NeuroCoder 4y ago
  Refinement types are pretty interesting and I've seen mention of them recently. I'm curious if there are any practical reasons we don't see them implemented in more languages.
  - klibertp 4y ago
    > Refinement types are pretty interesting Indeed. To me, they look like a formalized subset of precondition contracts that can be checked statically. I don't think the idea is new, I seem to recall Ada and Eiffel having something like this, but I first learned about them via Racket[1]. I still don't know how they work or what's needed to implement them. Interestingly, Raku has a similar concept called `subset`, eg. subset OneToTen of Int where * > 0 & * < 10; but from what I know no static analysis is done on the refinement/"where" part, it's a runtime assertion only. [1] https://blog.racket-lang.org/2017/11/adding-refinement-types.html https://blog.racket-lang.org/2017/11/adding-refinement-types...
    - lizmat 4y ago
      subset OneToTen of Int where 1..10; Why make it more complicated? :-) The secret is that given values are smartmatched against the given object. And the values 1 through 10 will return True if smartmatched against the 1..10 Range object. The `of Int' ensures that only integer values are allowed, otherwise 3.14 would also match. Unless of course, that is what you intended. In which case you can omit the "of Int".
cjalmeida 4y ago
It's not particularly new, but recently I've been involved a lot with solving large combinatorial optimization problems https://en.m.wikipedia.org/wiki/Combinatorial_optimization https://en.m.wikipedia.org/wiki/Combinatorial_optimization Algos to solve those both exact methods and heuristics are super useful in real world applications, and very underappreciated by the HN crowd IMO.
- JZL003 4y ago
  Yes! Me too, there's a whole world out there and it's codified in bullet-proof programs like CPLEX or gurobi. Sadly they are expensive and it's not obvious if a given problem's size and complexity will tailor itself to some of their heuristics. Have you been doing it by hand or using a big program?
  - kherud 4y ago
    Answer Set Programming is an incredibly powerful tool to declaratively solve combinatorial problems. Clingo is one of the best open source implementations in my opinion: https://github.com/potassco/clingo https://github.com/potassco/clingo - Based on conflict driven nogood learning, it has incredible performance (including good multithreading) - It has different optimization and enumeration modes - It has strong built-in heuristics, but also allows manual heuristics - It allows incremental solving - It has a nice API to integrate other solving paradigms (like difference logic and constraint programming, for which implementations already exist) - There is a huge ecosystem around it And much more, go check it out!
  - cjalmeida 4y ago
    At $DayJob, we deal with OR problems for large companies and typically, when possible, we leverage Gurobi to solve Mixed Integer Linear Programming (MIP) formulations. However it's not unusual for the problems to be huge to the point even Gurobi can't solve them in a reasonable time. And of course, there's the case where the problem can't be formulated (or approximated) as a linear program at all. So, in a couple projects I was involved we had to resort to manually constructed heuristics such as Simulated Annealing (SA) and Large Neighborhood Search (LNS). A very cool large scale approach we resorted in some problems (eg. airline scheduling) was Column Generation[1]. Not only it solved in minutes what took hours in the MIP implementation, unlike SA and LNS it's and exact method that provide valid bounds to global optimality. [1]: https://en.wikipedia.org/wiki/Column_generation https://en.wikipedia.org/wiki/Column_generation
mad 4y ago
The Cuckoo Trie, an ordered index data structure explicitly designed to have memory-level parallelism, which out-of-order processors can exploit to execute DRAM accesses in parallel: https://arxiv.org/pdf/2201.09331.pdf https://arxiv.org/pdf/2201.09331.pdf
shae 4y ago
I'd suggest looking up succinct data structures, cache oblivious data structures, and probabilistic data structures.
- mamcx 4y ago
  Anything specific that could cover what "NDArray-like" structures are? In concrete, to make row-oriented/column-oriented hybrids? (I wish to found a way to encode the equivalent of `struct Data{col1:Vec<..>, ...>})
- LukeEF 4y ago
  Succinct data structures ftw.
giogadi 4y ago
IMO the hip new thing in algorithms and data structures is to Just Use Arrays For Everything
- bckr 4y ago
  Got a source?
  - CountHackulus 4y ago
    I'm not OP, but I'm guessing he could be referring to something like this talk? https://www.youtube.com/watch?v=LrVi9LHP8Bk https://www.youtube.com/watch?v=LrVi9LHP8Bk I'm honestly not sure otherwise.
    - mejutoco 4y ago
      I think OP is talking about ML and matrix (array) multiplication to learn the right weights in a neural network.
  - medler 4y ago
    This is a lecture series, not new research, but one of the main takeaways is if you want good performance on modern machines, you had better be using arrays: https://youtube.com/playlist?list=PLHxtyCq_WDLXFAEA-lYoRNQIezL_vaSX- https://youtube.com/playlist?list=PLHxtyCq_WDLXFAEA-lYoRNQIe...
- dymk 4y ago
  Surely it’s the interesting things built on top of the arrays?
- yamazakiwi 4y ago
  Are you talking about Vector DB's?
  - masklinn 4y ago
    Also ECS / columnar data?
abeppu 4y ago
For numerical algorithms, probabilistic numerics is an interesting research corner. It both provides a new perspective on existing algorithms, and provides a framework for tailoring new ones to specific problems. https://www.probabilistic-numerics.org/ https://www.probabilistic-numerics.org/
revskill 4y ago
Searching.
chc4 4y ago
In compilers, there's been a recent uptick in industry research and adoption into using equivalency classes and graphs (egraphs) for doing optimization passes in a way that preserves information and solves the phase ordering problem. Egg[0] was one of the big libraries that came out of it, but can only handle term rewriting without guards, and so can't express y/x*x -> y because it's unsound when x=0, or optimization passes that are across control flow points and thus some of the eclasses are only valid in some locations. The Cranelift developers adapted it into a construction they call aegraphs[1] that handles this, and are migrating Cranelift to use these passes for all optimizations, which is (hopefully) faster and achieves more optimization opportunitie; Chris Fallin is presenting about their aegraph work at PLDI this year. 0: https://egraphs-good.github.io/ https://egraphs-good.github.io/ 1: https://github.com/cfallin/rfcs/blob/main/accepted/cranelift-egraph.md https://github.com/cfallin/rfcs/blob/main/accepted/cranelift...
- chc4 4y ago
  The other recent research that's been interesting to watch has been in logic programming (Prolog and Datalog), where there's been a lot of papers extending Datalog with semilattice types that are more efficient for computing dataflow-type queries (and even getting lattice types added to Souffle recently), including papers like datafun[0] extending it to sound incremental queries for more efficient execution - and there's even a paper by the Egg authors using it for efficient eclass-based Datalog queries using lattices[1]. It also seems like there has been more work recently in actually integrating logic programming in existing languages and programs, like ascent[2], instead of it being off in it's own world like it seems has historically been the case. 0: http://www.rntz.net/files/seminaive-datafun.pdf http://www.rntz.net/files/seminaive-datafun.pdf 1: https://www.mwillsey.com/papers/egglog https://www.mwillsey.com/papers/egglog 2: https://s-arash.github.io/ascent/cc22main-p95-seamless-deductive-inference-via-macros.pdf https://s-arash.github.io/ascent/cc22main-p95-seamless-deduc...
  - ggleason 4y ago
    Yeah, it's really unfortunate that these amazing advances in datalog don't make it into general purpose languages.
di4na 4y ago
Parsing but also casting to string efficiently is still an open problem with regular breakthrough. Ryu or Dragonbox for float to string come to mind. Parsing with errors that are useful for the human is definitely an open research topic. Capabilities have seen interesting work, in particular in relationships to effect handlers. Hyperloglog and other datasketch keep seeing incremental progress. I have not had time to read it all but Omar Ertl has a massive reduction in memory use in UltraLogLog that i expect a paper on soon. The code is already up.
- hinkley 4y ago
  I've been poking at prometheus internals lately and I am starting to wonder if histograms need some sort of hyperloglog treatment to improve on buckets. They don't seem like a very accurate solution.
  - di4na 4y ago
    You may appreciate ddsketch https://www.datadoghq.com/blog/engineering/computing-accurate-percentiles-with-ddsketch/ https://www.datadoghq.com/blog/engineering/computing-accurat... Or tdigest. For the prom use case, i usually prefer ddsketch. Easier to integrate. Tdigest is really complicated. That said there are definitely interesting work that need to happen on compressing time series histograms for heatmaps. Iirc influx had some interesting work there.
  - drewbug01 4y ago
    Have you seen the Prometheus “native”/“sparse” histograms that are being worked on: https://promcon.io/2022-munich/talks/native-histograms-in-prometheus/ https://promcon.io/2022-munich/talks/native-histograms-in-pr... They’ve released it as experimental recently, and we’ve found it to be a massive improvement over the original histograms. It’s still bucket-based at the end of the day, but the exponential bucket layout and sparse representation seems to work really well in practice.
sanxiyn 4y ago
Theoretical advances are constant (just check the literature), but two particular advances in the last decade are of practical importance: one for sort and one for hash table. As in: check the implementation you are using, if it doesn't incorporate these advances you are leaving substantial performance (2x is not out of the question) on the table. How Branch Mispredictions don't affect Quicksort (2016) https://arxiv.org/abs/1604.06697 https://arxiv.org/abs/1604.06697 Quicksort is still the algorithm of choice for general purpose internal unstable sort. In modern hardwares, quicksort spends a lot of time recovering from branch misprediction, because quicksort's comparison branches are inherently unpredictable. The problem is severe to the extent that with branchful quicksort, uneven split with more recursion is faster than even split, because it makes branches more predictable! Exact penalty is hardware microarchitecture specific, but one report is 20:80 split being optimal. So... you should use branchless quicksort! The technique was pioneered by an implementation called BlockQuicksort, but pdqsort (for pattern-defeating quicksort) https://arxiv.org/abs/2106.05123 https://arxiv.org/abs/2106.05123 is also popular. pdqsort incorporates branchless technique and also includes other enhancements. Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step (2017) https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables Hash table is the workhorse of data structures, and while improvements are possible for specific usage patterns, open addressing with linear probing is still the fastest implementation for general purpose. So called "Swiss Table" combines cache-friendly metadata layout with SIMD-enhanced probing. These two optimizations work well with each other and combination of two is particularly effective.
- hinkley 4y ago
  I recall years ago someone suggesting that a 1:2 split being faster and I'm wondering if they were seeing the same thing, and either didn't follow it through to conclusion or the goalposts keep moving in each generation of processors.
  - sanxiyn 4y ago
    It is plausible that they were seeing the same thing.
- 4y ago
transformi 4y ago
Follow-up, anything in graph-theory?
- kzrdude 4y ago
  I'm not exactly up to date, but last few years has seen practical improvements to graph isomorphism algorithms.
- tylerhou 4y ago
  BNW was in March of last year: https://arxiv.org/abs/2203.03456 https://arxiv.org/abs/2203.03456 Here is my summary of the algorithm from another HN post: https://news.ycombinator.com/item?id=34479148#34481937 https://news.ycombinator.com/item?id=34479148#34481937
zelphirkalt 4y ago
There is ongoing research for purely functional data structures and many implementations to be written for many functional languages, to make use of PFDS. Whenever one sees a traditional data structure, one can ask oneself, what a persistent functional one might look like, or whether a different solution would be pursued in FP languages. Traditional data structures are often a question of transcribing from an example language into a target language, with variuos language specific changes for optimization. Finding a good way to implement things without mutation or side-effects, is a challenge.
- TN1ck 4y ago
  What are the advancements since Clojure brought them to a mainstream language? More data structures got functional counterparts or better optimizations for “solved” ones like lists?
  - eru 4y ago
    For example, Chazelle's Soft Heap got a purely functional counterpart in 2013.
LukeEF 4y ago
How about some succinct data structures and delta encoding for modern databases [1]. Succinct data structures are a family of data structures which are close in size to the information theoretic minimum representation (while still being queryable). [1] https://github.com/terminusdb/terminusdb/blob/dev/docs/whitepaper/terminusdb.pdf https://github.com/terminusdb/terminusdb/blob/dev/docs/white...
softwaredoug 4y ago
Nobody has mentioned Approximate Nearest Neighbor search (aka vector search), which IMO, are fundamental data structures advancements. Basically given a set of million (billion, trillion...) ~1000 valued vectors, and a query ~1000 valued vector, find the closest vector in the indexed set. This is "nearest neighbor" search and there have been increasingly more and more sophisticated approaches: http://ann-benchmarks.com http://ann-benchmarks.com https://haystackconf.com/us2022/talk-6/ https://haystackconf.com/us2022/talk-6/ And has spawned companies like Weaviate, Pinecone, etc etc (a half a dozen others)
- fzliu 4y ago
  Most commonly used ANN algorithms today are clever optimizations atop "old" data structures. DiskANN is a recent favorite: https://milvus.io/blog/2021-09-24-diskann.md https://milvus.io/blog/2021-09-24-diskann.md
  - kokanee 4y ago
    "Most commonly used X today are clever optimizations atop old Y" is pretty much the story of technology, isn't it?
    - RoyGBivCap 4y ago
      It's lego all the way down to the clock cycle.
- marginalia_nu 4y ago
  What sort of dataset are you indexing that has trillion entries? That's 100,000 english wikipedias or 50 googles.
  - lacker 4y ago
    That's about the number of pixels in a 2-hour movie at 4k. Not too common yet, but once it's possible we're going to want to feed this amount of data into neural networks.
eternalban 4y ago
This is something I planned (2015) on sharing at some point but then years flew by and here we are .. :} It is a cacheline sized 'container' (CLC) of machine-word length records, with one record used to store the record order and remaining bits for metadata. So you can project different kinds of container semantics, such as FIFO or LRU -- any ordered set semantics -- on this meta record. Using arrays of CLCs you can create e.g. a segmented LRU, where the overhead per item is substantially less than a conventional pointer-based datastructure, and, is naturally suited for concurrent operations (for example by assigning a range to distinct worker threads), and ops require a few or couple of lines to be touched. The LRU (or whatever) semantics in aggregate will be probabilistic, as the LRU order is deterministic per unit container only. It is very fast :) https://github.com/alphazero/libclc/blob/master/include/libclc.h#L51 https://github.com/alphazero/libclc/blob/master/include/libc... https://github.com/alphazero/libclc/blob/master/include/libclc/__clc_cache.h#L52 https://github.com/alphazero/libclc/blob/master/include/libc... As for the non-deterministic aspects: Since container semantics e.g. LRU order is only applied at unit level, the overall cache is ~LRU. We can strictly quantify the 'ordering error' by observing the age of items in FIFO mode as they are removed: for a deterministic container the age of the item is equal to the total capacity of the queue, for a segmented (array) composed of FIFO queues, the age will have a effectively gaussian distribution around the capacity (number of units x unit capacity). But since these containers can use as few as 9 bits per entry vs 24 or more bytes for pointer based solutions (which use linked-lists), for the same allocation of memory, the capacity of the array of CLCs will be much greater, so, the distribution tail of 'short-lived' items will actually be longer lived than items in a strict queue for the same exact memory. Additional techniques, such as n-array hashing, and low order 'clock' bits at container level, can tighten this distribution significantly (i.e. ~LRU -> LRU) via better loading factors.
sireat 4y ago
For Maximum Flow (and Minimal Cut) through flow network we are getting close to linear time: 2022 Paper https://arxiv.org/abs/2203.00671 https://arxiv.org/abs/2203.00671
bmitc 4y ago
I'm interested in knowing about graph layout algorithms that allow specific constraints. If anyone knows about these things please let me know. I do not, but I have a use case for them. For example, the constraints may be: 1) The graph is read left to right. This informs the layout such that those spiral and circular graph layout algorithms that blow out the graph do not work. 2) Try to keep certain types of nodes vertical aligned, so that they lie on the same horizontal line. 3) Minimize edge crosses. 4) Have the edges be not lines but paths made up of horizontal and vertical lines. This probably requires some path finding as well. 5) Be able to live update in the sense that a new node or edge entry into the graph does not drastically re-layout the graph for reasonable inserts.
- alejohausner 4y ago
  Look at graphviz. Their "dot" program satisfies 1 through 4. Your fifth wish is hard to satisfy.
  - eru 4y ago
    You could probably satisfy 5 with some kind of (mixed integer) linear optimization or so.
    - bmitc 4y ago
      Would you mind elaborating? Thanks ahead of time.
      - eru 4y ago
        Well, you formulate all your constraints in the language of your favourite constraint based programming solver (eg convex optimisation or mixed integer linear optimisation etc). For simplicity, let's call your candidate solution x (where x is a vector of suitable size) and the constraints are formulated as some function f from your vector to real numbers, so that the problem reduces to "minimize f(x)". Then it's relatively easy to formulate your (5) as an additional constraint in the same language: Given a previous solution x_0, find a new solution x_1 to slightly different constraints f_1 by minimizing af_1(x_1) + bdistance(x_1-x0) You'd need to decide on the weights a and b and on the distance function. (Instead combining distance from old solution and constraints linearly, you could also use other ways to combine them. Eg you could also say: Keep f_1(x_1) <= epsilon and minimize distance(x_1-x_0). Or you could do minimize the sum of squares: af_1(x_1)^2 + bdistance(x_1-x0)^2 Specifics depends on what works well for your problem, and what your solver can handle. See https://developers.google.com/optimization https://developers.google.com/optimization for a free library of solvers.
ww520 4y ago
Not sure it's still considered new as it has come out for couple years, adaptive radix tree and its variants are pretty promising.
xiaodai 4y ago
Cache oblivious algorithms and lock free data structures
yieldcrv 4y ago
Merkle trees and state tries were not in my formal education But I had to learn them and employ them alot lately, very good for resource constrained environments
- eru 4y ago
  Not sure there's much new with Merkle trees. But Verkle trees are relatively new and fascinating: https://vitalik.ca/general/2021/06/18/verkle.html https://vitalik.ca/general/2021/06/18/verkle.html
lqr 4y ago
The field of "algorithms with predictions" studies how to use predictions/learning within traditional CS problem settings: > We introduce algorithms that use predictions from machine learning applied to the input to circumvent worst-case analysis. We aim for algorithms that have near optimal performance when these predictions are good, but recover the prediction-less worst case behavior when the predictions have large errors. An example is using learning to decide which variable to discretize next in a branch-and-bound integer linear programming solver. The algorithm might be extremely similar to the classic version, but the analysis is new. https://arxiv.org/abs/2006.09123 https://arxiv.org/abs/2006.09123 More broadly, I think there's a lot of work on applying more refined analysis to classic algorithms - online settings, smoothed analysis, etc.
inciampati 4y ago
Yes. There is ongoing work in making succinct full text indexes that use substantially less space than the text they model. See work on the r-index: https://doi.org/10.1089/cmb.2019.0309 https://doi.org/10.1089/cmb.2019.0309
TallGuyShort 4y ago
Algs/DS are still pretty fundamental to AI. Hyperparameter optimization algorithms like SHA/ASHA, stochastic gradient descent, PBT, etc. Structures like transformers, the various topologies, convolutions, etc. Not tickling the same itches?
Twisol 4y ago
E-graphs are pretty awesome, and worth keeping in your back pocket. They're like union-find structures, except they also maintain congruence relations (i.e. if `x` and `y` are in the same set, then `f(x)` and `f(y)` must likewise be in the same set). https://egraphs-good.github.io/ https://egraphs-good.github.io/ (Incidentally, union-find structures are also great to know about. But they're not exactly "new".)
aaron695 4y ago
[dead]
kccqzy 4y ago
Differential dataflow is seriously amazing: https://github.com/timelydataflow/differential-dataflow/blob/master/differentialdataflow.pdf https://github.com/timelydataflow/differential-dataflow/blob... Implemented in Rust: https://crates.io/crates/differential-dataflow https://crates.io/crates/differential-dataflow
eru 4y ago
I'm working on a paper to show that you can 'simulate' a heap in linear time. What I mean is: in the comparison model, assume start with an empty heap, a sequence of instructions like "insert element x" and "remove minimum element" of length n. There's an algorithm that can tell you in O(n) time, which items are still left in the heap at the end (and thus also which items have been removed at some point in time). The algorithm can't tell you exactly _when_ items have been removed, because that would be equivalent to sorting, and you need at least O(n log n) to sort in the comparison model. I've worked on this problem on and off for about a decade now as a little hobby project. I would have been happy to prove it impossible or to find a solution. Interestingly, it is possible and the solution is relatively simple, too. (I have no clue whether this is useful for anything. In practice you probably just run the obvious O(n log n) algorithm which probably has much better constant factors. I'm doing this purely for the theory.) The data structure / algorithm I found is expressible in a purely functional setting, and (spoiler alert) builds on top of Chazelle's Soft Heap.
- cochne 4y ago
  Doesn't that imply a linear "n largest" algorithm? I guess that might already exist, but I wasn't aware of that!
  - kopecs 4y ago
    Quickselect and non-randomized variations should get you that; no?
    - eru 4y ago
      Yes, exactly. But this reduction from 'select n largest' to my problem is still instructive: it tells us that in some sense any (deterministic) solution to my pet problem has to be at least as complicated as (deterministic) median finding.
  - eru 4y ago
    Yes, that does imply a linear 'n largest algorithm'. Specifically also linear median finding. As the sibling comment points out, that's not news. But it's very good for you to pick up that implication from first principles alone. It's part of figuring out how to solve this.
Vervious 4y ago
There's a lot of new results in cryptography/distributed algorithms, motivated in part by applications to blockchains. But even if you don't believe in blockchains they are interesting. - better zero knowledge proofs/arguments - better consensus protocols (my expertise!) - multiparty computation is nearing practicality, as is fully homomorphic encryption Also, lots of fascinating theoretical progress on primitives such as indistinguishability obfuscation, post-quantum schemes, quantum crypto, etc.
- throw101010 4y ago
  > better consensus protocols (my expertise!) As it is your domain of expertise, can you give more details on the new/improved ones please?
  - Vervious 4y ago
    There are improvements in both performance and understandability. On the performance front, see Algorand's consensus protocol (2016 ish), which can run on 10,000s of nodes, using a cryptographic technique called "sortition" which sub-selects a small committee of nodes to actually broadcast messages of the consensus protocol. On the understandability front, this is my research area; we put out a new protocol recently (https://eprint.iacr.org/2023/463 https://eprint.iacr.org/2023/463) that is faster and much easier than PBFT (and crash fault equivalents like Paxos/Raft). But there's a long line of prior work here. Traditionally, consensus (PBFT,Paxos,Raft) has run on a small set of nodes (i.e. a dozen) and also has used what are called "stable leaders", where a single leader process sequences all transactions until it is detected to be faulty. Stable leaders are great for data centers. Blockchains made it so that now protocols support thousands of nodes, and also use "rotating leaders", where a different node proposes each block (for fairness reasons). It happens that using rotating leaders allows for simpler protocols (in particular, with easier proofs).
    - throw101010 4y ago
      Thank you, very interesting I hadn't seen this concept of Dummy Blocks before!
erichocean 4y ago
Self-adjusting code is underutilized IMO. Hyperdimensional computing combines LLM-style AI with Lisp-style AI, making it possible to code within a latent space. Pretty weird, but cool. Electric Clojure is pretty groundbreaking, possibly similar to React's impact once it gets ported to a more popular platform. I think there are real opportunties going forward to build dedicated compilers and the corresponding runtimes for distributed computing and related algorithms and data structures. Really anything that is extremely error prone, difficult, or complex would benefit from building a runtime and compiler that simply solves the problem. MLIR has good infrastructure for that. Interprocedural data flow analysis is now scaling well in the LLVM/MLIR context: DFI: An Interprocedural Value-Flow Analysis Framework that Scales to Large Codebases https://arxiv.org/abs/2209.02638 https://arxiv.org/abs/2209.02638
EdSchouten 4y ago
A couple of days ago I stumbled upon Prolly trees: https://docs.dolthub.com/architecture/storage-engine/prolly-tree https://docs.dolthub.com/architecture/storage-engine/prolly-... In a nutshell: B+ trees that are stable w.r.t. insertion order. Great if you want to test them for equivalence/deduplicate them efficiently.
usefulcat 4y ago
(Mostly) branchless binary search, ~twice as fast as std::lower_bound: https://probablydance.com/2023/04/27/beautiful-branchless-binary-search/#more-11376 https://probablydance.com/2023/04/27/beautiful-branchless-bi...
at_a_remove 4y ago
This isn't anything most people would care about, but I do some GIS work and if you enjoy the process of taking the Very Obvious To a Human and explaining how to do ... whatever ... to a handful of sand and tamed lightning, well, there's just so many problems to solve. Just as an example, when you look at land parcels, you often get these irritating slivers (or splinters, even more apt because they are a pain and you have to dig them out) of land. You and I can look at a plot and point one out, but to a computer ... Well, one of the hallmarks of a splinter is that there's an awful lot of fencing but very little land. Or put another way, a lot of perimeter to area enclosed. Simple division doesn't suffice here, because the end result ought to be a dimensionless number so that scale doesn't interfere. Alright, perimeter squared divided by area. The lowest you can get is a little over twelve, for a circle. A square gets you sixteen. But a splinter might give you a value well over a hundred. Now, this sounds nice. You've got some values that are no gos (anything under twelve indicates an error), a reasonable bottom limit, a range where a human ought to take a look at it, and then a third range where you just say, "Yeah, that's a splinter alright, no need to bother a human." Sounds good. But then ... Wyoming. Scale does end up mattering. A parcel that was two feet across and a hundred long has the same "sliver value" as one that is two hundred feet across and ten thousand feet long. Yet the latter is still quite useful. You can run a road through it and tack on some strip malls. So it isn't useless. Okay, so you say "that's great, we'll just set a lower bound on the shortest side, anything bigger than that and you'll have to reconsider." ... but we've assumed that we have handy little rectangles and that we know what the sides are. It's GIS. We have a bag of points tracing the outline of a polygon. It isn't necessarily just four points. Each side might have a bunch of points that are roughly co-linear. You and I can look at it and say "Yeah, that's a rectangle alright," but the computer cannot. And so here I am trying to develop an algorithm to determine how many sides a human would see versus just this list of points. All so I can better define my splinters. Problems like this abound and they're quite interesting to think about. It's one of my favorite parts of programming and it requires some deep introspection, some meta-cognition: how do I recognize this, anyway? What is going on in my mind that I can do this?
turndown 4y ago
I guess I will ask since I couldn’t find it looking, does anyone happen to have a link to the person that was creating atomic data structures by making them fit into a uint64_t? Or am I misremembering?
anonymoushn 4y ago
I would recommend this book https://en.algorithmica.org/ https://en.algorithmica.org/. My opinion on things is that cache-oblivious programming is dead end and the constant factors by which cache-aware algorithms win are significant and worth taking.
- vlmutolo 4y ago
  Counterintuitively, “Cache-oblivious” algorithms typically refer to algorithms that are cache-friendly even for an unknown cache size, or for multiple levels of caches of varying (unknown) sizes. A good example is the memory hierarchy, from registers to L1–L3 processor cache to RAM to disk. Each have their own “block” size for memory transfers, and a cache-oblivious algorithm is designed to target all of those block sizes simultaneously. https://en.m.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.m.wikipedia.org/wiki/Cache-oblivious_algorithm
  - anonymoushn 4y ago
    Yes, that's correct, and specializing your code to the actual cache line and page sizes will generally yield significant speedups compared to this approach.
searchfan 4y ago
Quantum. Will cause us to forget everything we know about classical data structures & algorithms.
erikaww 4y ago
There is a bit of work within the last 5 years with creating more algorithms for temporal networks (think graphs that change over time like social networks, neural networks (with evolving architectures) or economic chain networks). These are essentially streaming algorithms over temporal edgelists. I worked on a research project that visualized these networks in real time. Very fun stuff.
- vladsanchez 4y ago
  Can you please share references? I'm interested in "temporal" topics.
eevmanu 4y ago
there was a recent HN post related to this topic https://news.ycombinator.com/item?id=32186203 https://news.ycombinator.com/item?id=32186203
husamia 4y ago
in memory computation using cheap analog chips

chaxor 4y ago

I am interested in a concept close to a CRDT - but I think meaningfully different. Is there a 'data structure' or 'scheme/setup' which fits the below description? Have a repo (with a specific git commit hash), which is specifically constructed to reproducibly construct some data (database, dataset, set of examples files, etc) (which can then be checked by a checksum), such that when a different person pulls and executes that code, a decision could be made to either run the code again, or to pull it from the decentralized group of people that have that repo database. This is effectively "code as data" which is checked by a key value pairing: [git commit hash <==> data checksum hash]. So if you have a process that runs for 24 days on a good machine and produces a 30 MB file for people to use, they can check for reproducibilityif they want with the code, or just grab the file from everyone who pulled the repo to save time. Obviously having defaults for download or rerun could be determined by certain logic like execution time etc, but the base idea is something I've looked into for a while. Is there a name for this type of setup?

killthebuddha 4y ago
I'm very unsure that I understand your requirements, but if I squint really really hard it looks like you're asking for a blockchain.
- chaxor 4y ago
  Hmmm... Perhaps that could be one component, but I don't know if proof of work in the typical way would be required? As in 'guessing' a hash (I don't know much about that area so I could be wrong here)., I don't think would be needed - but perhaps the proof of work could simply be 'calculate the output that you want to make anyway' - such as the weights of a neural network, a read only database to do complex queries on, an operating system compilation with specific configuration, a dataset of estimates of some physical science data using a particular algorithm, etc. So instead of using CPU cycles to do finance/currency things (or whatever is done in that arena), this would calculate whatever data you actually want directly. In some cases it could be a ton of calculation (estimating electron density functional, or training NN weights) to receive a small file (DFT functionals are quite small). Or it could be some calculation for a large amount of data (ETL for big we scraped data). One important aspect which is similar to the currency/Blockchain realm is that the commits would specify the data state, so the data would likely be mostly read-only for people, but if they change it, it would simply branch off to a different hash pair.
scrumlord 4y ago
[dead]

Karrot_Kream 4y ago

> Algos to solve those both exact methods and heuristics are super useful in real world applications, and very underappreciated by the HN crowd IMO. There just aren't many situations where they're useful. Time scheduling, logistics, operations, there are only a handful of places where these problems are so important that they need to be solved optimally or nearly optimally.

yes_man 4y ago

Dumb example but still example from practical world. Your body (assuming you are a human) has trillions of cells. Each cell way more complicated than what a 1000-dimensional vector can represent, but maybe it could be a loose estimate of some properties in each cell. Now the algorithm could be about finding the most similar cell. Could be useful for finding e.g. other cancer cells based on properties in one cancer cell. Not that this is a practical example because we technically cannot index all cells in each body. But even if such an algorithm being studied today might be useful one day when we do capability to collect such data

marginalia_nu 4y ago
Where are you going to store this data? It's dozens of petabytes.
- yes_man 4y ago
  Should theoretical research of data structures and algorithms have been capped at 1GB in 1980 because that was the biggest single hard drive available back then and you couldn’t store for example a 2GB dataset on a disk?
  - marginalia_nu 4y ago
    Not at all, I'll still call out fantastic claims when I see them though.
    - karpierz 4y ago
      Google has definitely indexed over a trillion pages.
      - marginalia_nu 4y ago
        Do you have any sources for this claim? As far as I am aware Google doesn't publish any statistics about the size of its index, which no doubt varies.
        groby_b 4y ago
        https://www.google.com/search/howsearchworks/how-search-works/organizing-information/#:~:text=The%20Google%20Search%20index%20contains,of%20the%20words%20it%20contains https://www.google.com/search/howsearchworks/how-search-work....
        marginalia_nu 4y ago
        Well what do you know, they contradict the claim made above.
        karpierz 4y ago
        Sorry, they've crawled trillions of pages, and narrowed it down to an index of 100s of billions. Conveniently, the link answers your question of "can you have PB sized indices?" to which we can clearly say, yes.
- sophacles 4y ago
  It's only a few racks worth of disk servers. If I was building it from my 5 minutes of googling, using 15TB nvme u2 drives, and easily available server chasis, I can get 24 drives per 2u of a rack. That's 360 TB + a couple server nodes. So ~6u per PB. A full height rack is 42u, so 6-7PB per rack once you take up some of the space with networking, etc. So dozens is doable in a short datacenter row. Realistically you could fit a lot more storage per U, depending on how much compute you need per unit of data. The example above assumes all the disks are at the front of the server only, if you mount them internally also, you can fit a lot more. (see Backblaze's storage pods for how they did it with spinning disks). Dozens of PB is not that much data in 2023.
  - SoftTalker 4y ago
    > Dozens of PB is not that much data in 2023. Yes it is. Just transferring it at data center speeds will take days if not weeks.
    - rsrsrs86 4y ago
      A truck has more bandwidth than network adapters technically
  - marginalia_nu 4y ago
    This is still like tens of thousands of dollars of equipment to store information about a single person's biology.
    - sophacles 4y ago
      Probably an order of magnitude or two more. Still something that is feasable in a research context - early MRI and genome sequencing had similar "too much data" problems like this, but the researchers still built it out to learn stuff. Tech marched forward and these days no one really blinks about it. I presume that if such a "all the cells scanner" was invented today, it would only be used for research for a long time - and that by the time it became widespread data storage will have caught up.
- tourist2d 4y ago
  Where do you think computers store data?

samwillis 4y ago
> Or any video game Agreed, BFT is clearly needed for multiplayer CRDT backed video games. > I assume you’re talking about weird merges from users putting markdown in a text crdt? Nope, although that is an issue. In that case the document shouldn't be markdown, it should be a rich text CRDT that's converted to markdown as output. On the conflicts I mentioned, an example, say you are building a to do list app. First let's do it with Prosemirror and Yjs, but for some reason we have decided to limit the length of a to do list to 10 items. Prosemirror will let you do that when defining a schema, have a maximum number of child nodes of the parent node type. With the current Yjs/Prosemirror system, if you have 9 items in the list and two people concurrently add a 10th, one of them will be dropped by prosemirror (deterministically). The document schema enforced that rule outside of the CRDT implementation. Yjs xmlFragments do not have the concept of these sort of rules. Now say you want to do this with the json like Map and Array types. Again the array type does not have the concept of a length limit, it will merge the two concurrent edits and create a document with 11 entries. In this case your application needs to manage the no longer complying document to correct it. The issue comes if you are naively merging the documents on the server, and dumping the json, it will not take into account your applications own conflict resolution. My suggestion is that a CRDT schema could do this, it would be a bit like a JSON Schema, but with rules about how to correct misshapen structures. So yes, I agree these generic rich text plus JSON types cover what 99% of applications need, but they also need to enforce a shape to the data structure that isn't built into the generic types. Having a way to do that as part of the merging layer, rather than application layer, would help to ensure correctness.
- josephg 4y ago
  Yeah I hear you. I've still never found a good way to implement schema validation rules like "this list cannot have more than 10 items" on top of a CRDT. Eventually consistent collaborative editing systems (like CRDTs and OT based systems) are optimistic. They allow any edits, and then later merge things if necessary. But if you only find out the list has 11 elements at the merging step, what do you do? Its too late to reject either of the inserts which put you in that state. My best answer at the moment is to tell people to rethink validation rules like that. I can't think of a lot of good use cases for collaborative editing where a "length <= 10" rule is something you want. Unfortunately, validation rules are really important for referential integrity. If you add a reference to some item in a data set and I concurrently delete that item, what should happen? Does the delete get undone? Does the reference get removed? Is the reference just invalid now? Should references only be to an item at some point in time? (Eg like a git SHA rather than a path)? Maybe optimistic systems just can't have referential integrity? Its an uncomfortable problem.

josephg 4y ago

> So, why does it have to be every keystroke? We can batch them locally. This approach would absolutely work. Thanks for bringing it up! The problem is that it has a cost I'd rather not pay. The problem is that batching only works if you don't send anything until the end of the batch. And that gives you an awful tradeoff - the more "live" your editing system is, the bigger the overhead. Its really nice seeing someone type live. Seeing their changes "pop in" after 5 seconds doesn't feel great. It doesn't feel current. And I think its too slow for pair programming over zoom and things like that. It also makes the DAG of changes much more complicated, because there's a much higher chance that changes are concurrent when there's that much latency. And that in turn also makes other aspects of the system do a lot more work to merge. With hashing alone, you don't need to batch changes like that. Instead, you can just store hashes on disk for (for example) every 100 changes, and regenerate the changes in the middle when needed. (Though you need some other tricks so you can know where to look for a given hash). Respect where its due, that would 100% solve it. I'm just looking for a way we can delete data without needing to give up the liveness. > We should also permit the author of an operation to rollback the operation. This doesn't completely solve the problem of hashes and guessability. Say in the 5 second batch I only type 1 character. We store some metadata, the character and the hash of the metadata & character. Then in the next 5 seconds I issue a rollback operation to delete that character. If I delete the character from durable storage, I can still figure out what the character was by brute forcing things and checking the hash for that batch. I think thats fixable by adding junk data to every batch. I just bet there's ways to avoid doing that.

vivegi 4y ago
Are you using a rolling hash (such as the one employed in Rabin-Karp string search algorithm)? You can then store the hash at check points and the intermediate hashes between checkpoints can be regenerated using the rolling hash. +[h1] +[batch1] +[h2] [batch2] -[h3] +[batch3] +[h4] You would then have the operations log for a replica as +[forwardhash(null)] +[hello] +[forwardhash(hello)] +[world] -[reversehash(world)] +[ ] +[forwardhash(wor) -[ld]+[k] This sequence would give the following replica states after processing each hash: +[forwardhash(null)] +[hello] -> hello +[forwardhash(hello)] +[world] -> helloworld -[reversehash(world)] +[ ] -> hello world +[forwardhash(wor) -[ld]+[k] -> hello work The direction of the roll is just a sign bit of the hash. We don't need to encode positions separately as it is a function of the state of the replica and the sign of the hash.