Virtual and Consistent Hyperbolic Tree: A New Structure for Distributed Database Management

International audienceThis paper describes a new scalable, reliable and consistent structure for implementing a distributed database system. This structure is based on the hyperbolic geometry and we call it a Virtual and Consistent Hyperbolic tree (VCH-tree). This structure is intended for supporting queries over possibly large spatial datasets distributed over interconnected servers. The VCH-tree is comparable to the well-known R-tree structure, but it uses the hyperbolic geometry properties of the Poincaré disk model. It uses a distributed balanced Q-degree spatial tree that scales with data objects' insertions into potentially any number of storage servers through virtual hyperbolic coordinates. A user application manipulates the structure from a client node. The client can connect to the system through one of the database servers that is already in the VCH-tree. Messages are then routed towards the proper server by a greedy algorithm which is using the virtual hyperbolic coordinates attributed to each server. We have performed simulations to assess the efficiency and reliability of the VCH-tree. Results show that our VCH-tree is consistent and has expected performances given the scalability and flexibility it provides to distributed database applications