Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Cluster Computing
Published in: Cluster Computing 4/2017

26-05-2017

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

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

Published in: Cluster Computing | Issue 4/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article Robust and reliable estimation via recursive nonlinear dynamic data reconciliation based on cubature Kalman filter
next article Computational optimal control for the time fractional convection-diffusion-reaction system

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
1.
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)
2.
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)
3.
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)
4.
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
5.
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
6.
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)
7.
Lakshman, A., Malik, P.: Cassandra: a decentralized structured storage system. ACM SIGOPS Oper. Syst. Rev. 44(2), 35–40 (2010)CrossRef
8.
Ma, Y., Meng, X.: Research on indexing for cloud data management. J. Softw. 26(1), 145–166 (2015). (in Chinese)
9.
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
Metadata
Title
A PR-quadtree based multi-dimensional indexing for complex query in a cloud system
Authors
Jian-feng Li
Shi-ping Chen
Lin-mao Duan
Liang Niu
Publication date
26-05-2017
Publisher
Springer US
Published in
Cluster Computing / Issue 4/2017
Print ISSN: 1386-7857
Electronic ISSN: 1573-7543
DOI
https://doi.org/10.1007/s10586-017-0928-y

Other articles of this Issue 4/2017

Cluster Computing 4/2017 Go to the issue

OriginalPaper

HBase storage schemas for massive spatial vector data

OriginalPaper

The risks assessment via a regional approach using multivariate regional frequency clustering method

OriginalPaper

: a QoS-based energy-aware task scheduling method in cloud environment

OriginalPaper

Low-complexity PTS PAPR reduction scheme for UFMC systems

OriginalPaper

Adaptive resource provisioning method using application-aware machine learning based on job history in heterogeneous infrastructures

OriginalPaper

The finite element method for the reliability analysis of lining structures based on Monte Carlo stochastic

Premium Partner

    Image Credits