BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Robert Sama

Robert Sama contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithms

Trust snapshot

Quick read

Trust 13 - UnverifiedVerification L1Unclaimed author
2works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

2 published item(s)

preprint2023arXiv

SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree

We consider the fundamental problem of designing a self-adjusting tree, which efficiently and locally adapts itself towards the demand it serves (namely accesses to the items stored by the tree nodes), striking a balance between the benefits of such adjustments (enabling faster access) and their costs (reconfigurations). This problem finds applications, among others, in the context of emerging demand-aware and reconfigurable datacenter networks and features connections to self-adjusting data structures. Our main contribution is SeedTree, a dynamically optimal self-adjusting tree which supports local (i.e., greedy) routing, which is particularly attractive under highly dynamic demands. SeedTree relies on an innovative approach which defines a set of unique paths based on randomized item addresses, and uses a small constant number of items per node. We complement our analytical results by showing the benefits of SeedTree empirically, evaluating it on various synthetic and real-world communication traces.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Deterministic Self-Adjusting Tree Networks Using Rotor Walks

We revisit the design of self-adjusting single-source tree networks. The problem can be seen as a generalization of the classic list update problem to trees, and finds applications in reconfigurable datacenter networks. We are given a fixed balanced binary tree T connecting n nodes V = {v_1, ... , v_n}. A source node v_0, attached to the root of the tree, issues communication requests to nodes in V, in an online and adversarial manner; the access cost of a request to a node v, is given by the current depth of v in T. The online algorithm can try to reduce the access cost by performing swap operations, with which the position of a node is exchanged with the position of its parent in the tree; a swap operation costs one unit. The objective is to design an online algorithm which minimizes the total access cost plus adjustment cost (swapping). Avin et al. recently presented Random-Push, a constant competitive online algorithm for this problem, based on random walks, together with an analysis exploiting the most recently used (MRU) property of random walks. We study analytically and empirically, online algorithms for this problem. In particular, we explore how to derandomize Random-Push. We consider a simple derandomized algorithm which we call Rotor-Push, as its behavior is reminiscent of rotor walks. We first prove that Rotor-Push is constant competitive: its competitive ratio is 12 and hence by a factor of five lower than the best existing competitive ratio. In contrast to Random-Push, the algorithm does not feature the MRU property, which requires a new analysis. We present a significantly improved and simpler analysis for the randomized algorithm, showing that it is 16-competitive. We compare empirically all self-adjusting single-source tree networks, using synthetic and real data with varying locality and observe that Rotor-Push and Random-Push have almost identical performance.

0 citations0 reviewsNo code linkedOpen access