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 Generalized data structure synthesis
Tag: Algorithms and data structures
Handy algorithms and data structures – e.g., for approximations
Analytics with smart arrays: adaptive and efficient language-independent data
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 Analytics with smart arrays: adaptive and efficient language-independent data
Towards web-based delta synchronization for cloud storage systems
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 Towards web-based delta synchronization for cloud storage systems
Clay codes: moulding MDS codes to yield an MSR code
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 Clay codes: moulding MDS codes to yield an MSR code
Quantum algorithms: an overview
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 Quantum algorithms: an overview
Enabling signal processing over data streams
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 Enabling signal processing over data streams
Complete event trend detection in high-rate data streams
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 Complete event trend detection in high-rate data streams
A general purpose counting filter: making every bit count
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 A general purpose counting filter: making every bit count
BBR: Congestion-based congestion control
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 BBR: Congestion-based congestion control
RedQueen: An online algorithm for smart broadcasting in social networks
RedQueen: An online algorithm for smart broadcasting in social networks Zarezade et al., WSDM 2017 Update: see also this very helpful project page by the authors: RedQueen. Ssshh, don't tell the folks in marketing ;). This paper starts out with a simple question "when's the best time to tweet if you want to get noticed?," … Continue reading RedQueen: An online algorithm for smart broadcasting in social networks
the morning paper 