nach oben

Cluster Computing

Erschienen in:

26.05.2017

A PR-quadtree based multi-dimensional indexing for complex query in a cloud system

verfasst von: Jian-feng Li, Shi-ping Chen, Lin-mao Duan, Liang Niu

Erschienen in: Cluster Computing | Ausgabe 4/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The state-of-the-art indexing mechanisms for distributed cloud data management systems can not support complex queries, such as multi-dimensional query and range query. To solve this problem, we propose a multi-dimensional indexing mechanism named PR-Chord to support complex queries. PR-Chord is composed of the global index named PR-Index and the Chord network. The multi-dimensional space formed by the range of the multi-dimensional data is divided into hyper-rectangle spaces equally. The PR-Index is a hierarchical index structure based on the improved PR quadtree to index these spaces. The complex query is transformed into the query of leaf nodes of PR-Index. We design the algorithms of query, insertion and deletion to support complex queries. Since PR-Index does not store the multi-dimensional data, its maintenance cost is zero. PR-Chord has the advantages of load balancing and simple algorithm. The experiment results demonstrate that PR-Chord has good query efficiency.

Vorheriger Artikel Robust and reliable estimation via recursive nonlinear dynamic data reconciliation based on cubature Kalman filter

Nächster Artikel Computational optimal control for the time fractional convection-diffusion-reaction system

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ghemawat, S., Gobioff, H., Leung, S.-T.: The google file system. In: Proceedings of the 19th ACM Symposium on Operating Systems Principles, pp. 29–43 (2003)

Chang, F., Dean, J., Ghemawat, S., et al.: Bigtable: a distributed storage system for structured data. In: Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, pp. 205–218 (2006)

Dean, J., Ghemawat, S.: Mapreduce: simplified data processing on large clusters. In: Proceedings of the 5th USENIX Symposium on Operating Systems Design and Implementation, pp. 137–150 (2004)

Osanaiye, O.A., Cai, H., Choo, K., Dehghantanha, A., Xu, Z., Dlodlo, M.E.: Ensemble-based multi-filter feature selection method for DDoS detection in cloud computing. EURASIP J. Wireless Commun. Netw. 2016, 130 (2016)CrossRef

Liu, J., Tian, Y., Yu, X., Yang, Z., Jia, X., Ma, C., Xu, Z.: A multi-source approach for bug triage. Int. J. Softw. Eng. Knowl. Eng. 26(9–10), 1593–1604 (2016)CrossRef

DeCandia, G., Hastorun, D., Jampani, M., et al.: Dynamo: amazon’s highly available key-value store. In: Proceedings of the 21st ACM Symposium on Operating Systems Principles, pp. 205–220 (2007)

Lakshman, A., Malik, P.: Cassandra: a decentralized structured storage system. ACM SIGOPS Oper. Syst. Rev. 44(2), 35–40 (2010)CrossRef

Ma, Y., Meng, X.: Research on indexing for cloud data management. J. Softw. 26(1), 145–166 (2015). (in Chinese)

Xia, Z., Junzhou, L., Aibo, S., et al.: A multidimensional indexing for complex query in cloud computing. J. Comput. Res. Dev. 50(8), 1592–1603 (2013). (in Chinese)

10.

Stoica, I., Morris, R., Karger, D., et al.: Chord: a scalable peer-to-peer lookup service for internet applications. In: Proceedings of 2001 SIGCOMM, vol. 31, pp. 149–160 (2001)

11.

Zhao, B., Kubiatowicz, J., Tapestry, J.A.: An infrastructure for fault-tolerant wide-area location and routing. UCB//CSD-01-1141, University of California at Berkeley, California (2001)

12.

Ratnasamy, S., Francis, P., Handley, M., et al.: A scalable content-addressable network. In: Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 161–172 (2001)

13.

Rowstron, A., Pastry, D.P.: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms, Heidelberg, pp. 329–350 (2001)

14.

Maymounkov, P., Kademlia, M.D.: A peer-to-peer information system based on the XOR metric. In: IPTPS’01 Revised Papers from the First International Workshop on Peer-to-Peer Systems, pp. 53–65 (2002)

15.

Samet, H.: Foundations of Multidimensional and Metric Data Structures, pp. 28–48. Tsinghua University Press, Beijing (2011)

16.

Bereczkya, N., Duchb, A., Németha, K., et al.: Quad-kd trees: a general framework for kd trees and quad trees. Theor. Comput. Sci. 616(2), 126–140 (2016)CrossRef

17.

Wu, S., Jiang, D., Ooi, B.C., et al.: Efficient B-tree based indexing for cloud data processing. In: Proceedings of the VLDB Endowment, pp. 1207–1218 (2010)

18.

Wang, J., Wu, S., Gao, H., et al.: Indexing multi-dimensional data in a cloud system. In: Proceedings of the ACM SIGMOD/PODS Conference, pp. 591–602 (2010)

19.

Zhang, X., Ai, J., Wang, Z., et al.: An efficient multi-dimensional index for cloud data management. In: Proceedings of the CIKM Workshop on Cloud Data Management, pp. 17–24 (2009)

20.

Ding, L., Qiao, B., Wang, G., et al.: An efficient quad-tree based index structure for cloud data management. In: Proceedings of the 12th International Conference on Web-Age Information Management, pp. 238–250 (2010)

21.

Nishimura, S., Das, S., Agrawal, D., et al.: MD-HBase: design and implementation of an elastic data infrastructure for cloud-scale location services. Distrib. Parallel Databases 31(2), 289–319 (2013)CrossRef

22.

Hsu, Y., Pan, Y., Wei, L., et al.: Key formulation schemes for spatial index in cloud data managements. In: Proceedings of the 13th IEEE Conference on Mobile Data Management, pp. 21–26 (2012)

23.

Carlini, E., Lulli, A., Ricci, L.: Dragon: multidimensional range queries on distributed aggregation trees. Future Gener. Comput. Syst. 55(2), 101–115 (2016)CrossRef

24.

Aguilera, M.K., Golab, W., Shah, M.A.: A practical scalable distributed B-tree. In: The Proceedings of the VLDB Endowment (PVLDB), vol. 1, pp. 598–609 (2008)

25.

Aguilera, M.K., Merchant, A., Shah, M.A., et al.: Sinfonia: a new paradigm for building scalable distributed systems. In: SOSP’07 Proceedings of Twenty-First ACM SIGOPS Symposium on Operating Systems Principles, pp. 159–174 (2007)

26.

Tanin, E., Harwood, A., Samet, H.: Using a distributed quadtree index in peer-to-peer networks. Int. J. Very Large Data Bases 16(2), 165–178 (2007)CrossRef

27.

Bently, J.L., Stanat, D.F.: Analysis of range searches in quad trees. Inf. Process. Lett. 3(6), 170–173 (1975)CrossRefMATH

28.

Lee, D.T., Wong, C.K.: Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees[J]. Acta Inf. 9(1), 23–29 (1977)CrossRefMATHMathSciNet

Titel: A PR-quadtree based multi-dimensional indexing for complex query in a cloud system
verfasst von: Jian-feng Li
Shi-ping Chen
Lin-mao Duan
Liang Niu
Publikationsdatum: 26.05.2017
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe 4/2017
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-017-0928-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2017

Semi-supervised classification of multiple kernels embedding manifold information

Dynamic load balancing in distributed exascale computing systems

Iterative learning control applied to a hybrid rehabilitation exoskeleton system powered by PAM and FES

MapReduce-based skyline query processing scheme using adaptive two-level grids

The model and algorithm of distributing cooperation profits among operators of urban rail transit under PPP pattern

A node coverage algorithm for a wireless-sensor-network-based water resources monitoring system

Premium Partner