40 citations · 168 across the 23 of their papers we have counts for
12 papers · 1 filter
Obtaining Approximately Optimal and Diverse Solutions via Dispersion
Jie Gao, Mayank Goswami, Karthik C. S. +3
There has been a long-standing interest in computing diverse solutions to optimization problems. Motivated by reallocation of governmental institutions in Sweden, in 1995 J. Krarup…
Batched Predecessor and Sorting with Size-Priced Information in External Memory
Michael A. Bender, Mayank Goswami, Dzejla Mededovic +2
In the unit-cost comparison model, a black box takes an input two items and outputs the result of the comparison. Problems like sorting and searching have been studied in this mode…
On the I/O complexity of the k-nearest neighbor problem
Mayank Goswami, Riko Jacob, Rasmus Pagh
We consider static, external memory indexes for exact and approximate versions of the -nearest neighbor (-NN) problem, and show new lower bounds under a standard indivisibili…
Multi-finger binary search trees
Parinya Chalermsook, Mayank Goswami, László Kozma +2
We study multi-finger binary search trees (BSTs), a far-reaching extension of the classical BST model, with connections to the well-studied -server problem. Finger search is a p…
Buffered Count-Min Sketch on SSD: Theory and Experiments
Mayank Goswami, Dzejla Medjedovic, Emina Mekic +1
Frequency estimation data structures such as the count-min sketch (CMS) have found numerous applications in databases, networking, computational biology and other domains. Many app…
Bloom Filters, Adaptivity, and the Dictionary Problem
Michael A. Bender, Martin Farach-Colton, Mayank Goswami +3
The Bloom filter---or, more generally, an approximate membership query data structure (AMQ)---maintains a compact, probabilistic representation of a set S of keys from a universe U…
Distance Sensitive Bloom Filters Without False Negatives
Mayank Goswami, Rasmus Pagh, Francesco Silvestri +1
A Bloom filter is a widely used data-structure for representing a set and answering queries of the form "Is in ?". By allowing some false positive answers (saying "yes"…
The landscape of bounds for binary search trees
Parinya Chalermsook, Mayank Goswami, László Kozma +2
Binary search trees (BSTs) with rotations can adapt to various kinds of structure in search sequences, achieving amortized access times substantially better than the Theta(log n) w…
Pattern-avoiding access in binary search trees
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST…
Greedy Is an Almost Optimal Deque
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Patrascu (DHIKP) to accommodate for insertions and deletions. Within this…
Self-Adjusting Binary Search Trees: What Makes Them Tick?
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
Splay trees (Sleator and Tarjan) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs)…
Approximate Range Emptiness in Constant Time and Optimal Space
Mayank Goswami, Allan Grønlund, Kasper Green Larsen +1
This paper studies the \emph{-approximate range emptiness} problem, where the task is to represent a set of points from and answer emptiness…