Now showing items 1-8 of 8

    • Approximate Matching for Peer-to-Peer Overlays with Cubit 

      Wong, Bernard; Slivkins, Aleksandrs; Sirer, Emin Gun (2008-05-19)
      Keyword search is a critical component in most content retrieval systems. Despite the emergence of completely decentralized and efficient peer-to-peer techniques for content distribution, there have not been similarly ...
    • Distance Estimation and Object Location via Rings of Neighbors 

      Slivkins, Aleksandrs (Cornell University, 2006-08-13)
      We consider four problems on distance estimation and object location which share the common flavor of capturing global information via informative node labels: low-stretch routing schemes, distance labeling, searchable ...
    • "Distance Estimation and Object Location via Rings of Neighbors" 

      Slivkins, Aleksandrs (Cornell University, 2005-02-12)
      We approach several problems on distance estimation and object location using a common technique called \emph{rings of neighbors}. Using this technique on metrics of low doubling dimension, we obtain significant improvements ...
    • Meridian: A Lightweight Framework for Network Positioning without Virtual Coordinates 

      Wong, Bernard; Slivkins, Aleksandrs; Sirer, Emin Gun (Cornell University, 2005-03-04)
      Selecting nodes based on their position in the network is a basic building block for many distributed systems. This paper describes a peer-to-peer overlay network for performing position-based node selection. Our system, ...
    • Network Distance Estimation with Guarantees for All Node Pairs 

      Slivkins, Aleksandrs (Cornell University, 2006-07-06)
      An active line of research in the networking community studies the distance matrix defined by the node-to-node latencies in the Internet and, in particular, provides a number of quite successful distributed approaches ...
    • Network Failure Detection and Graph Connectivity 

      Kleinberg, Jon; Sandler, Mark; Slivkins, Aleksandrs (Cornell University, 2002-11-22)
      We consider a model for monitoring the connectivity of a network subject to node or edge failures. In particular, we are concerned with detecting \emph{$(\vareps, k)$-failures}: events in which an adversary deletes up ...
    • On Fixed-Parameter Tractability of Some Routing Problems 

      Slivkins, Aleksandrs; Pal, Martin (Cornell University, 2002-08-29)
      Disjoint Paths is the problem of finding paths between given pairs of terminals in a graph such that no vertices are shared between paths. We analyze fixed-parameter tractability of several new Disjoint Paths-like routing ...
    • Parametrized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs 

      Slivkins, Aleksandrs (Cornell University, 2003-04-01)
      Given a graph and pairs $s_i t_i$ of terminals, the edge-disjoint paths problem is to determine whether there exist $s_i t_i$ paths that do not share any edges. We consider this problem on ditected acyclic graphs. It is ...