jm + trees   9

US immigration asking tech interview trivia questions now
what the absolute fuck. Celestine Omin on Twitter: "I was just asked to balance a Binary Search Tree by JFK's airport immigration. Welcome to America."
twitter  celestine-omin  us-politics  immigration  tests  interviews  bst  trees  data-structures  algorithms 
24 days ago by jm
BTrDB: Optimizing Storage System Design for Timeseries Processing
interesting, although they punt to Ceph for storage and miss out the chance to make a CRDT
storage  trees  data-structures  timeseries  delta-delta-coding  encoding  deltas 
may 2016 by jm
Beautiful algorithm visualisations from Mike Bostock
This is a few days old, but unmissable. I swear, the 'Wilson's algorithm transformed into a tidy tree layout' viz brought tears to my eyes ;)
dataviz  algorithms  visualization  visualisation  mazes  trees  sorting  animation  mike-bostock 
june 2014 by jm
Hydra Takes On Hadoop
The intuition behind Hydra is something like this, "I have a lot of data, and there are a lot of things I could try to learn about it -- so many that I'm not even sure what I want to know.” It's about the curse of dimensionality -- more dimensions means exponentially more cost for exhaustive analysis. Hydra tries to make it easy to reduce the number of dimensions, or the cost of watching them (via probabilistic data structures), to just the right point where everything runs quickly but can still answer almost any question you think you might care about.


Getting Started blog post:
hyrda  hadoop  data-processing  big-data  trees  clusters  analysis 
april 2014 by jm
Berkeley DB Java Edition Architecture [PDF]
background white paper on the BDB-JE innards and design, from 2006. Still pretty accurate and good info
bdb-je  java  berkeley-db  bdb  design  databases  pdf  white-papers  trees 
may 2013 by jm
The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases [PDF]
'Main memory capacities have grown up to a point where most databases fit into RAM. For main-memory database systems, index structure performance is a critical bottleneck. Traditional in-memory data structures like balanced binary search trees are not efficient on modern hardware, because they do not optimally utilize on-CPU caches. Hash tables, also often used for main-memory indexes, are fast but only support point queries. To overcome these shortcomings, we present ART, an adaptive radix tree (trie) for efficient indexing in main memory. Its lookup performance surpasses highly tuned, read-only search trees, while supporting very efficient insertions and deletions as well. At the same time, ART is very space efficient and solves the problem of excessive worst-case space consumption, which plagues most radix trees, by adaptively choosing compact and efficient data structures for internal nodes. Even though ART’s performance is comparable to hash tables, it maintains the data in sorted order, which enables additional operations like range scan and prefix lookup.' (via Tony Finch)
via:fanf  data-structures  trees  indexing  cache-aware  tries 
january 2013 by jm
HAT-trie: A Cache-conscious Trie-based Data Structure for Strings [PDF]
'Tries are the fastest tree-based data structures for managing strings in-memory, but are space-intensive. The burst-trie is almost as fast but reduces space by collapsing trie-chains into buckets. This is not however, a cache-conscious approach and can lead to poor performance on current processors. In this paper, we introduce the HAT-trie, a cache-conscious trie-based data structure that is formed by carefully combining existing components. We evaluate performance using several real-world datasets and against other highperformance data structures. We show strong improvements in both time and space; in most cases approaching that of the cache-conscious hash table. Our HAT-trie is shown to be the most efficient trie-based data structure for managing variable-length strings in-memory while maintaining sort order.' (via Tony Finch)
via:fanf  data-structures  tries  cache-aware  trees 
january 2013 by jm
Open Data Structures
A free-as-in-speech as well as -beer textbook of data structures, covering a great range, including some I hadn't heard of before. Here's the full list: ArrayStack, FastArrayStack, ArrayQueue, ArrayDeque, DualArrayDeque, RootishArrayStack, SLList, DLList,
SEList, SkiplistSSet, SkiplistList, ChainedHashTable, LinearHashTable, BinaryTree, BinarySearchTree, Treap, ScapegoatTree, RedBlackTree, BinaryHeap, MeldableHeap, AdjacencyMatrix, AdjacencyLists, BinaryTrie, XFastTrie, and YFastTrie
algorithms  books  data-structures  computer-science  coding  tries  skiplists  arrays  queues  heap  trees  graphs  hashtables 
may 2012 by jm
Graft punk: Breaking the law to help urban trees bear fruit
This is brilliant. I find it pretty offensive that "ornamental" fruit trees are chosen by urban councils, so that fruit doesn't fall on the path and become slippery or whatever -- come on, that's just what trees do! 'They’re covertly grafting — a practice of connecting two branches in a way that will allow their vascular tissues to join together -- fruit tree limbs onto the trunks of ornamental cherry, plum, and pear trees.'
public  roads  trees  nature  city  urban  fruit  guerrilla  grafting 
april 2012 by jm

Copy this bookmark: