Abstract
We describe a new structure called Virtual and Consistent Hyperbolic tree (VCH-tree) for implementing a distributed database system. This structure is based on the hyperbolic geometry and can support queries over large spatial data sets, distributed over interconnected servers. The VCH-tree is comparable to the well-known R-tree structure, but it leverages the hyperbolic geometry properties of the Poincaré disk model. It maintains a balanced Q-degree spatial tree that scales with insertions of data objects into a large number of servers, reachable through hyperbolic coordinates. A user application manipulates the structure from a client node. The client can connect to the system through one of the servers that is already in the VCH-tree. Messages are then routed towards the proper server by a greedy algorithm which uses the 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 exhibits expected performances for being used by distributed database applications.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anderson, J.W.: Hyperbolic Geometry. Springer undergraduate mathematics series, 2nd edn. Springer, Berlin (2005)
Crainiceanu, A., Linga, P., Gehrke, J., Shanmugasundaram, J.: Querying peer-to-peer networks using p-trees. In: Proceedings of the 7th International Workshop on the Web and Databases: Colocated with ACM SIGMOD/PODS 2004, WebDB 2004, pp. 25–30. ACM, New York (2004). http://doi.acm.org/10.1145/1017074.1017082
Devine, R.: Design and implementation of DDH: a distributed dynamic hashing algorithm. In: Lomet, D.B. (ed.) FODO 1993, vol. 730, pp. 101–114. Springer, Heidelberg (1993)
Gaede, V., Günther, O.: Multidimensional access methods. ACM Comput. Surv. 30(2), 170–231 (1998). http://doi.acm.org/10.1145/280277.280279
Guttman, A.: R-trees: a dynamic index structure for spatial searching. SIGMOD Rec. 14(2), 47–57 (1984). http://doi.acm.org/10.1145/971697.602266
Hambrusch, S.E., Khokhar, A.A.: Maintaining spatial data sets in distributed-memory machines, pp. 702–707. IEEE Computer Society (1997)
Idowu, S.A., Maitanmi, S.O.: Transactions- distributed database systems: issues and challenges. IJACSCE 2(1), 24–26 (2014)
Jajodia, S., Litwin, W., Schwarz, T.J.E.: LH*RE: a scalable distributed data structure with recoverable encryption, pp. 354–361. IEEE (2010)
Jansson, J., Sung, W.-K.: Constructing the R* consensus tree of two trees in subcubic time. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 573–584. Springer, Heidelberg (2010)
Karlsson, J.S.: hQT*: a scalable distributed data structure for high-performance spatial accesses, pp. 37–46 (1998)
Kleinberg, R.: Geographic routing using hyperbolic space. In: 26th IEEE International Conference on Computer Communications, INFOCOM 2007, pp. 1902–1909. IEEE, May 2007
Kriakov, V., Delis, A., Kollios, G.: Management of highly dynamic multidimensional data in a cluster of workstations. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 748–764. Springer, Heidelberg (2004)
Lakshman, A., Malik, P.: Cassandra: a decentralized structured storage system. SIGOPS Oper. Syst. Rev. 44(2), 35–40 (2010). http://doi.acm.org/10.1145/1773912.1773922
Litwin, W., Neimat, M.A.: k-RP*s: a scalable distributed data structure for high-performance multi-attribute access, pp. 120–131. IEEE Computer Society (1996)
Montresor, A., Jelasity, M.: PeerSim: a scalable P2P simulator. In: Proceedings of the 9th International Conference on Peer-to-Peer (P2P 2009), pp. 99–100, Seattle, WA (2009)
Silberschatz, A., Korth, H., Sudarshan, S.: Database Systems Concepts, 5th edn. McGraw-Hill, Inc., New York (2006)
Tiendrebeogo, T., Ahmat, D., Magoni, D.: Reliable and scalable distributed hash tables harnessing hyperbolic coordinates. In: 2012 5th International Conference on New Technologies, Mobility and Security (NTMS), pp. 1–6, May 2012
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Tiendrebeogo, T., Magoni, D. (2015). Virtual and Consistent Hyperbolic Tree: A New Structure for Distributed Database Management. In: Bouajjani, A., Fauconnier, H. (eds) Networked Systems . NETYS 2015. Lecture Notes in Computer Science(), vol 9466. Springer, Cham. https://doi.org/10.1007/978-3-319-26850-7_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-26850-7_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26849-1
Online ISBN: 978-3-319-26850-7
eBook Packages: Computer ScienceComputer Science (R0)