BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Martín Farach-Colton

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
Data Structures and Algorithms

Catalog footprint

Research overview

2works
1topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

2 publications

preprint2022arXiv

Online List Labeling: Breaking the log⁡2n\log^2n Barrier

The online list labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing set of nn items in an array of mm slots, while maintaining the invariant that the items appear in sorted order, and while minimizing the relabeling cost, defined to be the number of items that are moved per insertion/deletion. For the linear regime, where m=(1+Θ(1))nm = (1 + Θ(1)) n, an upper bound of O(log⁡2n)O(\log^2 n) on the relabeling cost has been known since 1981. A lower bound of Ω(log⁡2n)Ω(\log^2 n) is known for deterministic algorithms and for so-called smooth algorithms, but the best general lower bound remains Ω(log⁡n)Ω(\log n). The central open question in the field is whether O(log⁡2n)O(\log^2 n) is optimal for all algorithms. In this paper, we give a randomized data structure that achieves an expected relabeling cost of O(log⁡3/2n)O(\log^{3/2} n) per operation. More generally, if m=(1+ε)nm = (1 + \varepsilon) n for ε=O(1)\varepsilon = O(1), the expected relabeling cost becomes O(ε−1log⁡3/2n)O(\varepsilon^{-1} \log^{3/2} n). Our solution is history independent, meaning that the state of the data structure is independent of the order in which items are inserted/deleted. For history-independent data structures, we also prove a matching lower bound: for all εε between 1/n1/31 / n^{1/3} and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is Θ(ε−1log⁡3/2n)Θ(\varepsilon^{-1}\log^{3/2} n).

Open access
preprint2022arXiv

What Does Dynamic Optimality Mean in External Memory?

In this paper, we revisit the question of how the dynamic optimality of search trees should be defined in external memory. A defining characteristic of external-memory data structures is that there is a stark asymmetry between queries and inserts/updates/deletes: by making the former slightly asymptotically slower, one can make the latter significantly asymptotically faster (even allowing for operations with sub-constant amortized I/Os). This asymmetry makes it so that rotation-based search trees are not optimal (or even close to optimal) in insert/update/delete-heavy external-memory workloads. To study dynamic optimality for such workloads, one must consider a different class of data structures. The natural class of data structures to consider are what we call buffered-propagation trees. Such trees can adapt dynamically to the locality properties of an input sequence in order to optimize the interactions between different inserts/updates/deletes and queries. We also present a new form of beyond-worst-case analysis that allows for us to formally study a continuum between static and dynamic optimality. Finally, we give a novel data structure, called the \jellotree, that is statically optimal and that achieves dynamic optimality for a large natural class of inputs defined by our beyond-worst-case analysis.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.