8 citations · 16 across the 6 of their papers we have counts for
6 papers
Persistent Cache-oblivious Streaming Indexes
Andrew Twigg
In [SPAA2007], Bender et al. define a streaming B-tree (or index) as one that supports updates in amortized IOs, and present a structure achieving amortized …
Locality-preserving allocations Problems and coloured Bin Packing
Andrew Twigg, Eduardo C. Xavier
We study the following problem, introduced by Chung et al. in 2006. We are given, online or offline, a set of coloured items of different sizes, and wish to pack them into bins of…
Optimal query/update tradeoffs in versioned dictionaries
Andrew Byde, Andy Twigg
External-memory dictionaries are a fundamental data structure in file systems and databases. Versioned (or fully-persistent) dictionaries have an associated version tree where quer…
Stratified B-trees and versioning dictionaries
Andy Twigg, Andrew Byde, Grzegorz Milos +3
A classic versioned data structure in storage and computer science is the copy-on-write (CoW) B-tree -- it underlies many of today's file systems and databases, including WAFL, ZFS…
Worst-case time decremental connectivity and k-edge witness
Andrew Twigg
We give a simple algorithm for decremental graph connectivity that handles edge deletions in worst-case time and connectivity queries in , where is the…
Lower bounds for distributed markov chain problems
Rahul Sami, Andy Twigg
We study the worst-case communication complexity of distributed algorithms computing a path problem based on stationary distributions of random walks in a network with the cave…