Generalized data structure synthesis

June 21, 2018 ~ Adrian Colyer ~ 15 Comments

Generalized data structure synthesis Loncaric et al., ICSE'18 Many systems have a few key data structures at their heart. Finding correct and efficient implementations for these data structures is not always easy. Today’s paper introduces Cozy (https://cozy.uwplse.org), which can handle this task for you given a high-level specification of the state, queries, and update operations ... Continue Reading

Analytics with smart arrays: adaptive and efficient language-independent data

June 14, 2018 ~ Adrian Colyer ~ 1 Comment

Analytics with smart arrays: adaptive and efficient language-independent data Psaroudakis et al., EuroSys'18 (If you don’t have ACM Digital Library access, the paper can be accessed either by following the link above directly from The Morning Paper blog site). We’re going lower-level today, with a look at some work on adaptive data structures by Oracle. ... Continue Reading

Towards web-based delta synchronization for cloud storage systems

March 2, 2018 ~ Adrian Colyer ~ 2 Comments

Towards web-based delta synchronization for cloud storage systems Xiao et al., FAST’18 If you use Dropbox (or an equivalent service) to synchronise file between your Mac or PC and the cloud, then it uses an efficient delta-sync (rsync) protocol to only upload the parts of a file that have changed. If you use a web ... Continue Reading

Clay codes: moulding MDS codes to yield an MSR code

March 1, 2018 ~ Adrian Colyer ~ 1 Comment

Clay codes: moulding MDS codes to yield an MSR code Vajha et al., FAST’18 As we know, storage fails (or the nodes to which it is directly attached, which amounts to pretty much the same thing). Assuming we can detect the failure, we need to recover from it. In order to be able to recover, ... Continue Reading

Quantum algorithms: an overview

February 6, 2018 ~ Adrian Colyer ~ 13 Comments

Quantum algorithms: an overview Montanaro, npj Quantum Information 2016 This is a paper that Preskill cited in his keynote address (see yesterday’s post). It covers some of the same ground that we looked at yesterday, but also has some additional material and perspective of interest — and I’ll focus on those parts today. We’ll touch ... Continue Reading

Enabling signal processing over data streams

August 10, 2017 ~ Adrian Colyer ~ 1 Comment

Enabling signal processing over data streams Nikolic et al., SIGMOD '17 If you're processing data coming from networks of sensors and devices, then it's not uncommon to use a mix of relational and signal processing operations. Data analysts use relational operators, for example, to group signals by different data sources or join signals with historical ... Continue Reading

Complete event trend detection in high-rate data streams

August 9, 2017 ~ Adrian Colyer ~ 6 Comments

Complete Event Trend detection in high-rate event streams Poppe et al., SIGMOD'17 Today's paper choice looks at the tricky problem of detecting Complete Event Trends (CET) in high-rate event streams. CET detection is useful in fraud detection, health care analytics, stock trend analytics and other similar scenarios looking for complex patterns in event streams. Detecting ... Continue Reading

A general purpose counting filter: making every bit count

August 8, 2017 ~ Adrian Colyer ~ 13 Comments

A general purpose counting filter: making every bit count Pandey et al., SIGMOD'17 It's been a while since we looked at a full on algorithms and data structures paper, but this one was certainly worth waiting for. We're in the world of Approximate Membership Query (AMQ) data structures, of which probably the best known example ... Continue Reading

BBR: Congestion-based congestion control

March 31, 2017November 11, 2019 ~ Adrian Colyer ~ 8 Comments

BBR: Congestion-based congestion control Cardwell et al., ACM Queue Sep-Oct 2016 With thanks to Hossein Ghodse (@hossg) for recommending today's paper selection. This is the story of how members of Google's make-tcp-fast project developed and deployed a new congestion control algorithm for TCP called BBR (for Bandwidth Bottleneck and Round-trip propagation time), leading to 2-25x ... Continue Reading

the morning paper

a random walk through Computer Science research, by Adrian Colyer
Made delightfully fast by strattic

Algorithms and data structures