18 citations · 72 across the 35 of their papers we have counts for
7 papers · 2 filters
Competitive Online Search Trees on Trees
Prosenjit Bose, Jean Cardinal, John Iacono +2
We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tre…
A parallel priority queue with fast updates for GPU architectures
Kyle Berney, John Iacono, Ben Karsin +1
The single-source shortest path (SSSP) problem is a well-studied problem that is used in many applications. In the parallel setting, a work-efficient algorithm that additionally at…
External Memory Planar Point Location with Fast Updates
John Iacono, Ben Karsin, Grigorios Koumoutsos
We study dynamic planar point location in the External Memory Model or Disk Access Model (DAM). Previous work in this model achieves polylog query and polylog amortized update time…
Belga B-trees
Erik D. Demaine, John Iacono, Grigorios Koumoutsos +1
We revisit self-adjusting external memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distr…
Encoding 3SUM
Sergio Cabello, Jean Cardinal, John Iacono +3
We consider the following problem: given three sets of real numbers, output a word-RAM data structure from which we can efficiently recover the sign of the sum of any triple of num…
Cache-Oblivious Priority Queues with Decrease-Key and Applications to Graph Algorithms
John Iacono, Riko Jacob, Konstantinos Tsakalidis
We present priority queues in the cache-oblivious external memory model with block size and main memory size that support on elements, operation \textsc{UPDATE} (combin…