Algorithms   74500

« earlier    

_Building a Bw-Tree Takes More Than Just Buzz Words_, SIGMOD 2018
'An account of our disappointing journey to build a open-source lock-free Bw-Tree for the Peloton DBMS.'

'In 2013, Microsoft Research proposed the Bw-Tree (humorously
termed the “Buzz Word Tree”), a lock-free index that provides high
throughput for transactional database workloads in SQL Server’s
Hekaton engine. The Bw-Tree avoids locks by appending delta
record to tree nodes and using an indirection layer that allows it to
atomically update physical pointers using compare-and-swap (CaS).
Correctly implementing this techniques requires careful attention
to detail. Unfortunately, the Bw-Tree papers from Microsoft are
missing important details and the source code has not been released.

This paper has two contributions: First, it is the missing guide
for how to build a lock-free Bw-Tree. We clarify missing points in
Microsoft’s original design documents and then present techniques
to improve the index’s performance. Although our focus here is on
the Bw-Tree, many of our methods apply more broadly to designing
and implementing future lock-free in-memory data structures. Our
experimental evaluation shows that our optimized variant achieves
1.1–2.5× better performance than the original Microsoft proposal
for highly concurrent workloads. Second, our evaluation shows
that despite our improvements, the Bw-Tree still does not perform
as well as other concurrent data structures that use locks.'

Finally: https://twitter.com/andy_pavlo/status/986647389820747776 :

'Our results show that @ViktorLeis's ART index and @xexd's MassTree and a non-fancy B+Tree are currently the best for in-memory workloads. Skip Lists are always terrible.'
skip-lists  algorithms  data-structures  storage  bw-trees  mass-trees  benchmarks  performance  multithreading  lock-free  locking  trees 
1 hour ago by jm
Parsing: a timeline -- V3.0
My teachers came from the generation which created the ALGOL vision and started the quest for a solution to the Parsing Problem. Alan Perlis was one of them. Would he have accepted my claim that I have found the solution to the problem he posed? I do not know, but I am certain, as anyone else who knew him can attest, that he would given me a plain-spoken answer. In that spirit, I submit this timeline to the candid reader. In any case, I hope that my reader has found this journey through the history of parsing informative.
algorithms  parser  parsing  history  culture  CS 
10 hours ago by euler
Style is an Algorithm
interesting notes about how platform structures necessarily create generic aesthetics
algorithms  design  aesthetics 
12 hours ago by h_b_
A Mathematical Framework for Superintelligent Machines
We describe a class calculus that is expressive enough to describe and improve its own learning process. It can design and debug programs that satisfy given input/output constraints, based on its ontology of previously learned programs. It can improve its own model of the world by checking the actual results of the actions of its robotic activators. For instance, it could check the black box of a car crash to determine if it was probably caused by electric failure, a stuck electronic gate, dark ice, or some other condition that it must add to its ontology in order to meet its sub-goal of preventing such crashes in the future. Class algebra basically defines the eval/eval-1 Galois connection between the residuated Boolean algebras of 1. equivalence classes and super/sub classes of class algebra type expressions, and 2. a residual Boolean algebra of biclique relationships. It distinguishes which formulas are equivalent, entailed, or unrelated, based on a simplification algorithm that may be thought of as producing a unique pair of Karnaugh maps that describe the rough sets of maximal bicliques of relations. Such maps divide the n-dimensional space of up to 2n-1 conjunctions of up to n propositions into clopen (i.e. a closed set of regions and their boundaries) causal sets. This class algebra is generalized to type-2 fuzzy class algebra by using relative frequencies as probabilities. It is also generalized to a class calculus involving assignments that change the states of programs. 
INDEX TERMS 4-valued Boolean Logic, Artificial Intelligence, causal sets, class algebra, consciousness, intelligent design, IS-A hierarchy, mathematical logic, meta-theory, pointless topological space, residuated lattices, rough sets, type-2 fuzzy sets
AI  math  machinelearning  paper  research  algorithms  tweetit 
22 hours ago by sachaa
What Does The Amazon Echo Look Mean For Personal Style? - Racked
Style Is an Algorithm

No one is original anymore, not even you.
algorithms 
yesterday by jorgebarba

« earlier    

related tags

2005  341webmgmt  3d  additivism  aesthetics  ai  algorithm  algorithms  algorithmsinsociety  animated  animation  api  article  artificial-intelligence  artificialintelligence  behavior  benchmarks  bestpractices  bias  big  bigdata  blog  boids  brilliant  bw-tree  bw-trees  c++  career  cheatsheet  china  civ  codecs  coding  collective  colonialism  compiler  compilers  complexity  compression  compsci  computation  computer-science  computer  computerscience  computing  consensus  course  courses  craig_silverman  crowd  cryptograph  cryptography  cs-history  cs  culture  curation  d3  data-structures  data  database  datastructures  decolonialisation  decolonisation  deeplearning  democracy  design  development  digital_ethics  distributed  economics  editdistance  education  efficiency  engines  ethics  ethics_of_algorithms  evolution  evolutionary  fredbenenson  funny  gamedev  games  golang  google  governance  gradients  grammar  graph.algorithms  graph  graphs  grid  group  growth/mastery  hackerrank  hashing  hex  history  ikea  infographic  information  interactive  interdisciplinarity  interview  javascript  languages  learning  levenshteindistance  library  lock-free  locking  machine-learning  machine_learning  machinelearning  map  marketing  mass-trees  math  mathematics  merkle  metaresearch  mmc6612  moderation  monopsony  multiagent  multithreading  netflix  netpolicynotes  neural_networks  nlp  o  opensource  paper  parser  parsing  pasquale  pathfinding  paxos  performance  persistence  presentation  privacy  problem  programming  proof  python  quantum-computing  quantum  readlater  reference  reinforcementlearning  research  review  search  searching  security  simulation  skip-lists  slav  slides  social  social_media  socialmedia  society  software  softwareengineering  sorting  spelling  stl  storage  swift  time  tla  tlaplus  toolkit  tree  trees  triangles  tries  tutorial  tweetit  unplugged  video  visual.design  visualization  wikipedia  world  wow  yariv  youtube 

Copy this bookmark:



description:


tags: