Dynamics on emerging spaces: modeling the emergence of novelties

February 3, 2017November 11, 2019 ~ Adrian Colyer ~ 3 Comments

Dynamics on expanding spaces: modeling the emergence of novelties Loreto et al., ArXiv 2017 Something a little bit left field today to close out the week. I was drawn into this paper by an MIT Technology Review article entitled "Mathematical model reveals the patterns of how innovations arise." Who wouldn't want to read about that!? ... Continue Reading

Algorithmic improvements for fast concurrent cuckoo hashing

November 3, 2016November 11, 2019 ~ Adrian Colyer ~ Leave a comment

Algorithmic improvements for fast concurrent cuckoo hashing Li et al, EuroSys 2014 Today’s paper continues the work on optimistic cuckoo hashing that we looked at yesterday, extending it to support multiple writers and even higher throughput. One of the original goals for the research was to take advantage of the hardware transactional memory support in ... Continue Reading

MemC3: Compact and concurrent Memcache with dumber caching and smarter hashing

November 2, 2016November 11, 2019 ~ Adrian Colyer ~ 5 Comments

MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing Fan et al. NSDI 2013 At the core of this paper is an improved hashing algorithm called optimistic cuckoo hashing, and a CLOCK-based eviction algorithm that works in tandem with it. They are evaluated in the context of Memcached, where combined they give up ... Continue Reading

Time-adaptive sketches (Ada sketches) for summarizing data streams

July 21, 2016November 11, 2019 ~ Adrian Colyer ~ 2 Comments

Time-adaptive sketches (Ada Sketches) for Summarizing Data Streams Shrivastava et al. SIGMOD 2016 More algorithm fun today, and again in the context of data streams. It’s the 3 V’s of big data, but not as you know it: Volume, Velocity, and Var… Volatility. Volatility here refers to changing patterns in the data over time, and ... Continue Reading

Range thresholding on streams

July 20, 2016November 11, 2019 ~ Adrian Colyer ~ Leave a comment

Range thresholding on streams Qiao et al. SIGMOD 2016 It’s another streaming paper today, also looking at how to efficiently handle a large volume of concurrent queries over a stream, and also claiming a significant performance breakthrough of several orders of magnitude. We’re looking at a different type of query though, known as a range ... Continue Reading

Sharing-aware outlier analytics over high-volume data streams

July 19, 2016November 11, 2019 ~ Adrian Colyer ~ 1 Comment

Sharing-aware outlier analytics over high-volume data streams Cao et al. SIGMOD 2016 With yesterday’s preliminaries on skyline queries out of the way, it’s time to turn our attention to the Sharing-aware Outlier Processing (SOP) algorithm of Cao et al. The challenge that SOP addresses is that of building a stream-based outlier detection system that can ... Continue Reading

Progressive skyline computation in database systems

July 18, 2016November 11, 2019 ~ Adrian Colyer ~ 8 Comments

Progressive skyline computation in database systems Papadias et al. SIGMOD 2003 I’m still working through some of the papers from SIGMOD 2016 (as some of you spotted, that was the unifying them for last week). But today I’m jumping back to 2003 to provide some context for a streaming analytics paper we’ll be looking at ... Continue Reading

Spheres of influence for more effective viral marketing

July 15, 2016November 11, 2019 ~ Adrian Colyer ~ 1 Comment

Spheres of influence for more effective viral marketing Mehmood et al. SIGMOD ’16 In viral marketing the idea is to spread awareness of a brand or campaign by exploiting pre-existing social networks. The received wisdom is that by targeting a few influential individuals, they will be able to spread your marketing message to a large ... Continue Reading

Transactional data structure libraries

June 24, 2016 ~ Adrian Colyer ~ Leave a comment

Transactional Data Structure Libraries Spiegelman et al. PLDI 2016 Today’s choice won a distinguished paper award at the recent PLDI 2016 conference. Spiegelman et al. show how to add transactional support to in-memory concurrent data structure libraries in a way that doesn’t sacrifice performance. Since the advent of the multi-core revolution, many efforts have been ... Continue Reading

the morning paper

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

Algorithms and data structures