Brief Announcement: SplayNets

详细信息    查看全文

• 作者：Stefan Schmid (17)
  Chen Avin (18)
  Christian Scheideler (19)
  Bernhard Haeupler (20)
  Zvi Lotker (18)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7611
• 期：1
• 页码：441-442
• 全文大小：155KB
• 参考文献：1. Sleator, D., Tarjan, R.: Self-adjusting binary search trees. JACM聽32(3), 652鈥?86 (1985) CrossRef
  
• 作者单位：Stefan Schmid (17)
  Chen Avin (18)
  Christian Scheideler (19)
  Bernhard Haeupler (20)
  Zvi Lotker (18)
  
  17. TU Berlin & T-Labs, Germany
  18. BGU, Israel
  19. U. Paderborn, Germany
  20. MIT, USA
  

文摘

This paper initiates the study of self-adjusting distributed data structures or networks. In particular, we present SplayNets: a binary search tree based network that is self-adjusting to the routing requests. We derive entropy bounds on the amortized routing cost and show that our splaying algorithm has some interesting properties.