Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Distributed and Parallel Databases
Erschienen in: Distributed and Parallel Databases 3/2013

01.09.2013

A Hierarchical Grid Index (HGI), spatial queries in wireless data broadcasting

verfasst von: Kwangjin Park, Patrick Valduriez

Erschienen in: Distributed and Parallel Databases | Ausgabe 3/2013

Einloggen

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

search-config
loading …

Abstract

The main requirements for spatial query processing via mobile terminals include rapid and accurate searching and low energy consumption. Most location-based services (LBSs) are provided using an on-demand method, which is suitable for light-loaded systems where contention for wireless channels and server processing is not severe. However, as the number of users of LBSs increases, performance deteriorates rapidly since the servers’ capability to process queries is limited. Furthermore, the response time of a query may significantly increase with the concentration of users’ queries in a server at the same time. That is because the server has to check the locations of users and potential objects for the final result and then individually send answers to clients via a point-to-point channel. At this time, an inefficient structure of spatial index and searching algorithm may incur an extremely large access latency.
To address this problem, we propose the Hierarchical Grid Index (HGI), which provides a light-weight sequential location-based index structure for efficient LBSs. We minimize the index size through the use of hierarchical location-based identifications. And we support efficient query processing in broadcasting environments through sequential data transfer and search based on the object locations. We also propose Top-Down Search and Reduction-Counter Search algorithms for efficient searching and query processing. HGI has a simple structure through elimination of replication pointers and is therefore suitable for broadcasting environments with one-dimensional characteristics, thus enabling rapid and accurate spatial search by reducing redundant data. Our performance evaluation shows that our proposed index and algorithms are accurate and fast and support efficient spatial query processing.
Vorheriger Artikel Efficiently repairing and measuring replica consistency in distributed databases
Nächster Artikel Data-driven and automated prediction of service level agreement violations in service compositions

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
Fußnoten
1
The average duration for getting to the next index segment is called the probe wait [5].
 
2
Access time is the time elapsed from the time a client requests data to the point when all the required data is downloaded by the client [4].
 
3
Tuning time is the amount of time spent by a client listening to the channel. This allows determining the power consumed by the client to retrieve the required data [4].
 
4
The R-tree is a classical spatial index structure. The basic idea is to approximate a spatial object with a minimal bounding rectangle (MBR) and to index the MBRs recursively [26, 27].
 
5
Even until recently, DSI and ESS have been a representative study of index for supporting spatial query processing in wireless broadcast environments. In this paper, performance assessment was conducted on DSS that assumed the most similar environments as the proposed technique.
 
6
Each index table in the DSI and ESS has the next pointers that increase exponentially within the range of N, the total r amount of data. For example, if N=1024, a single index table has 9 next pointers of 1, 2, 4, 8, and up to 1024.
 
7
The leaf grid node refers to the node that is located at the lowest place in the tree structure. That is, the node does not have any more child grid nodes.
 
8
The exponential value allows indexing pointers to be exponentially increased at any base value e. For example, if the number of objects and the value of e are set to 8 and 2, respectively, a data item 0 has four forward pointers such as 1(20), 2(21), 4(22), and 8(23).
 
Literatur
1.
Acharya, S., Alonso, R., Franklin, M., Zdonik, S.: Broadcast disks: data management for asymmetric communications environments. In: Proceedings of ACM SIGMOD Conference on Management of Data (SIGMOD’95), May 1995, pp. 199–210 (1995)
2.
Datta, A., Celik, A., Kim, J.K., VanderMeer, D., Kumar, V.: Adaptive broadcast protocols to support power conservation retrieval by mobile users. In: Proceedings of IEEE International Conference Data Engineering (ICDE’97), April 1997, pp. 124–133 (1997). CrossRef
3.
Datta, A., VanderMeer, D.E., Celik, A., Kumar, V.: Broadcast protocols to support efficient retrieval from databases by mobile users. ACM Trans. Database Syst. 24(1), 1–79 (1999) CrossRef
4.
Imielinski, T., Viswanathan, S., Badrinath, B.R.: Energy efficiency indexing on air. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, May 1994, pp. 25–36 (1994)
5.
Imielinski, T., Viswanathan, S., Badrinath, B.R.: Data on air—organization and access. IEEE Trans. Knowl. Data Eng. 9(3), 353–372 (1997) CrossRef
6.
Shanmugasundaram, J., Nithrakashyap, A., Sivasankaran, R.M., Ramamritham, K.: Efficient concurrency control for broadcast environments. In: Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD’99), June 1999, pp. 85–96 (1999)
7.
Zheng, B., Lee, D.L.: Information dissemination via wireless broadcast. Commun. ACM 48(5), 105–110 (2005) CrossRef
8.
Zheng, B., Xu, J., Lee, W.-C., Lee, D.L.: Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services. VLDB J. 15(1), 21–39 (2006) CrossRef
9.
Lee, K.C.K., Lee, W.-C., Winter, J., Zheng, B., Xu, J.: CS cache engine: data access accelerator for location-based service in mobile environments. In: Proc. of Special Interest Group on Management of Data (SIGMOD), pp. 787–789 (2006)
10.
Ku, W., Zimmermann, R., Wang, H.: Location-based spatial query processing in wireless broadcast environments. IEEE Trans. Mob. Comput. 7(6), 778–791 (2008) CrossRef
11.
Mouratidis, K., Bakiras, S., Papadias, D.: Continuous monitoring of spatial queries in wireless broadcast environments. IEEE Trans. Mob. Comput. 8(10), 1297–1311 (2009) CrossRef
12.
Park, K., Choo, H.: Energy-efficient data dissemination schemes for nearest neighbor query processing. IEEE Trans. Comput. 56(6), 754–768 (2007) MathSciNetCrossRef
13.
Xu, J., Zheng, B., Lee, W.-C., Lee, D.L.: Energy efficient index for querying location-dependent data in mobile broadcast environments. In: Proc. of ICDE, pp. 239–250 (2003)
14.
Zheng, B., Lee, W.-C., Lee, D.L.: On searching continuous k nearest neighbors in wireless data broadcast systems. IEEE Trans. Mob. Comput. 6(7), 748–761 (2007) CrossRef
15.
Tao, Y., Papadias, D., Shen, Q.: Continuous nearest neighbor search. In: Proc. of VLDB, pp. 287–298 (2002)
16.
Park, K., Choo, H., Valduriez, P.: A scalable energy-efficient continuous nearest neighbor search in wireless broadcast systems. Wirel. Netw. 16(4), 1011–1031 (2010) CrossRef
17.
Hu, Q., Lee, W.-C., Lee, D.L.: Power conservative multi-attribute queries on data broadcast. In: Proc. Int’l Conf. Data Eng. (ICDE’00), pp. 157–166 (2000) CrossRef
18.
Hambrusch, S.E., Liu, C.-M., Aref, W., Prabhakar, S.: Query processing in broadcasted spatial index trees. In: Proc. of Symposium on Spatial and Temporal Databases (SSTD), pp. 502–521 (2001)
19.
Xu, J., Lee, W.-C., Tang, X.: Exponential index: a parameterized distributed indexing scheme for data on air. In: Proc. of MobiSys, pp. 153–164 (2004) CrossRef
20.
Xuan, P., Sen, S., Gonzalez, O., Fernandez, J., Ramamritham, K.: Broadcast on demand: efficient and timely dissemination of data in mobile environments. In: Proc. of IEEE Real Time Technology and Applications Symposium, pp. 38–48 (1997) CrossRef
21.
Liu, C.-M., Lin, K.-F.: Disseminating dependent data in wireless broadcast environments. Distrib. Parallel Databases 22(1), 1–25 (2007) CrossRef
22.
Nicopolitidis, P., Papadimitriou, G.I., Pomportsis, A.S.: Exploiting locality of demand to improve the performance of wireless data broadcasting. IEEE Trans. Veh. Technol. 55(4), 1347–1361 (2006) CrossRef
23.
Wang, H., Zimmermann, R.: Processing of continuous location-based range queries on moving objects in road networks. IEEE Trans. Knowl. Data Eng. 23(7), 1065–1078 (2011) CrossRef
24.
Zhang, W., Yang, X., Wu, W., Xiang, G.: An optimized query index method based on R-tree. In: Proc. of International Joint Conference on Computational Sciences and Optimization, pp. 1007–1011 (2011)
25.
Roussopoulos, N., Kelley, F.V.S.: Nearest neighbor queries. In: Proc. of SIGMOD, pp. 71–79 (1995)
26.
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proc. of Special Interest Group on Management of Data (SIGMOD), pp. 47–57 (1984)
27.
Jagadish, H.V., Ooi, B.C., Vu, Q.H., Zhang, R., Zhou, A.: VBI-tree: a peer-to-peer framework for supporting multi-dimensional indexing schemes. In: Proc. of International Conference on Data Engineering (ICDE), p. 34 (2006)
28.
Ku, W.-S., Zimmermann, R., Wan, C.-N., Wang, H.: MAPLE: a mobile scalable P2P nearest neighbor query system for location-based services. In: Proc. of International Conference on Data Engineering (ICDE), p. 160 (demo) (2006)
29.
Lee, W.-C., Zheng, B.: DSI: a fully distributed spatial index for location-based wireless broadcast services. In: Proc. of ICDCS, Columbus, USA, 6–10 June 2005, pp. 349–358 (2005)
30.
Zheng, B., Lee, W.-C., Lee, K., Lee, D., Shao, M.: A distributed spatial index for error-prone wireless data broadcast. VLDB J. 18(4), 959–986 (2009) CrossRef
31.
Gedik, B., Singh, A., Liu, L.: Energy efficient exact kNN search in wireless broadcast environments. In: Proc. Ann. ACM Int’l Workshop Geographic Information Systems (GIS’04), pp. 137–146 (2004) CrossRef
32.
Park, K., Valduriez, P., Choo, H.: Mobile continuous nearest neighbor queries on air. In: Proc. of ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM-GIS), p. 65 (2008)
33.
Camp, T., Boleng, J., Davies, V.: A survey of mobility models for ad hoc network research. Wirel. Commun. Mob. Comput. 2(5), 483–502 (2002) CrossRef
34.
Mouratidis, K., Bakiras, S., Papadias, D.: Continuous monitoring of spatial queries in wireless broadcast environments. IEEE Trans. Mob. Comput. 8(10), 1297–1311 (2009) CrossRef
35.
Chowdhury, P., Sarkar, S., Reaz, A.: Comparative cost study of broadband access technologies. In: Proc. of Advanced Networks and Telecommunication Systems, pp. 1–3 (2008)
Metadaten
Titel
A Hierarchical Grid Index (HGI), spatial queries in wireless data broadcasting
verfasst von
Kwangjin Park
Patrick Valduriez
Publikationsdatum
01.09.2013
Verlag
Springer US
Erschienen in
Distributed and Parallel Databases / Ausgabe 3/2013
Print ISSN: 0926-8782
Elektronische ISSN: 1573-7578
DOI
https://doi.org/10.1007/s10619-013-7121-y