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
Wireless Networks
Erschienen in: Wireless Networks 4/2019

25.01.2018

A hierarchical binary quadtree index for spatial queries

verfasst von: Kwangjin Park

Erschienen in: Wireless Networks | Ausgabe 4/2019

Einloggen

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

search-config
loading …

Abstract

An index structure adequate for broadcasting environments must consider the order of data delivery, index size, and selective tuning. This paper introduces a light-weight bit sequence grid-based spatial index, referred to as a binary quadtree, which allows for the sequential search and selective tuning of data. Then, the paper suggests a search algorithm that can efficiently search spatial objects. The results from theoretical analysis and experiments show that the proposed algorithm with the binary quadtree is fast and energy efficient in both range queries and k-nearest neighbor queries.
Vorheriger Artikel Impact of relative speed on node vicinity dynamics in VANETs
Nächster Artikel Optimal throughput performance in full-duplex relay assisted cognitive networks

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 [10, 11].
 
2
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.
 
3
Each index table in the DSI and ESS has the next pointers that increase exponentially within the range of N. For example, if N = 1024, a single index table has 9 next pointers of 1, 2, 4, 8, and up to 1024.
 
Literatur
1.
Pai, N., & Li, Y. (2014). Competing advertising and pricing strategies for location-based commerce. In Proceedings of European conference on system science (ECIS).
2.
Zheng, B., Xu, J., Lee, W., & Lee, L. (2006). Grid-partition index: A hybrid method for nearest-neighbor queries in wireless location-based services. VLDB Journal, 15, 21–39.CrossRef
3.
Park, K., & Song, D. (2016). A partial index for distributed broadcasting in wireless mobile networks. Information Sciences (INS), 348, 142–152.CrossRef
4.
Wang, Y., Xu, C., Gu, Y., Chen, M., & Yu, G. (2013). Spatial query processing in road networks for wireless data broadcast. Wireless Networks (WINET), 19(4), 477–494.CrossRef
5.
Sun, W., Chen, C., Zheng, B., Chen, C., & Liu, P. (2015). An air index for spatial query processing in road networks. IEEE Transactions on Knowledge and Data Engineering, 27(2), 382–395.CrossRef
6.
Xiong, Y., Deng, Y., Wang, W., & Ma, J. (2014). Phoenix: A collaborative location-based notification system for mobile networks. Mathematical Problems in Engineering, 307498, 12.
7.
Gedik, B., Singh, A., & Liu, L. (2004) Energy efficient exact kNN search in wireless broadcast environments. In ACM international workshop on geographic information systems (GIS) (pp. 137–146).
8.
Zheng, B., Lee, W., Lee, K., Lee, D., & Shao, M. (2009). A distributed spatial index for error-prone wireless data broadcast. VLDB Journal, 18, 959–986.CrossRef
9.
Acharya, S., Alonso, R., Franklin, M., & Zdonik, S. (1995) Broadcast disks: Data management for asymmetric communications environments. In Proceedings of the international conference on management of data (SIGMOD) (pp. 199–210)
10.
Imielinski, R., Viswanathan, S., & Badrinath, B. (1997). Data on air-organization and access. IEEE Transactions on Knowledge and Data Engineering (TKDE), 9(3), 353–372.CrossRef
11.
Imielinski, T., Viswanathan, S., & Badrinath, B. (1994). Energy efficiency indexing on air. In Proceedings of the international conference on management of data (SIGMOD) (pp. 25–36)
12.
Park, K., & Valduriez, P. (2013). A hierarchical grid index (HGI), spatial queries in wireless data broadcasting. Distributed and Parallel Databases (DAPD), 31(3), 413–446.CrossRef
13.
Acharya, S., Franklin, M., & Zdonik, S. (1995). Dissemination-based data delivery using broadcast disks. IEEE Personal Communications, 2(6), 50–60.CrossRef
14.
Liu, C., & Lin, K. (2007). Disseminating dependent data in wireless broadcast environments. Distributed and Parallel Databases (DAPD), 22(1), 1–25.CrossRef
15.
Mouratidis, K., Bakiras, S., & Papadias, D. (2009). Continuous monitoring of spatial queries in wireless broadcast environments. IEEE Transactions on Mobile Computing (TMC), 8(10), 1297–1311.CrossRef
16.
Nicopolitidis, P., Papadimitriou, G., & Pomportsis, A. (2006). Exploiting locality of demand to improve the performance of wireless data broadcasting. IEEE Transactions on Vehicular Technology (TVT), 55(4), 1347–1361.CrossRef
17.
Li, Y., Li, J., Shu, L., Li, Q., Li, G., & Yang, F. (2014). Searching continuous nearest neighbors in road networks on the air. Information Systems (IS), 42, 177–194.CrossRef
18.
Zhong, J., Wu, W., Shi, Y., & Gao, X. (2011) Energy-efficient tree-based indexing schemes for information retrieval in wireless data broadcast. In Proceedings of database systems for advanced applications (DASFAA) (pp. 335–351)
19.
Xu, J., Lee, W., & Tang, X. (2004). Exponential index: A parameterized distributed indexing scheme for data on air. In Proceedings of international conference on. mobile systems, applications, and services (MobiSys) (pp. 153–164)
20.
Shen, J., & Chang, Y. (2008). An efficient nonuniform index in the wireless broadcast environments. Journal of Systems and Software (JSS), 81, 2091–2103.CrossRef
21.
Kellaris, G., & Mouratidis, K. (2010). Shortest path computation on air indexes. Proceedings of the VLDB Endowment (PVLDB), 3(1), 747–757.CrossRef
22.
Park, K., & Choo, H. (2007). Energy-efficient data dissemination schemes for nearest neighbor query processing. IEEE Transactions on Computers, 56(6), 754–768.MathSciNetCrossRefMATH
23.
Hambrusch, S., Liu, C., Aref, W., & Prabhakar, S. (2001) Query processing in broadcasted spatial index trees. In Proceedings of advances in spatial and temporal databases (SSTD) (pp. 502–521)
24.
Liu, C., & Fu, S. (2008). Effective protocols for kNN search on broadcast multi-dimensional index trees. Information Systems (IS), 33, 18–35.CrossRef
25.
Nagarkar, P., Candan, K. S., & Bhat, A. (2015). Compressed spatial hierarchical bitmap (cSHB) indexes for efficiently processing spatial range query workloads. Proceedings of the VLDB Endowment (PVLDB), 8(12), 1382–1393.CrossRef
26.
Galdames, P., & Cai, Y. (2012). Efficient processing of location-cloaked queries. In Proceedings of IEEE conference on computer communications (INFOCOM) (pp. 2480–2488).
27.
Guttman, A. (1984). R-trees: A dynamic index structure for spatial searching. In Proceedings of the international conference on management of data (SIGMOD) (pp. 47–57).
28.
Kellaris, G., & Mouratidis, K. (2010). Shortest path computation on air indexes. In International conference on very large data bases (VLDB) (pp. 747–757)
29.
Li, Y., Shu, L., Zhu, R., & Li, L. (2017). A novel distributed air index for efficient spatial query processing in road sensor networks on the air. International Journal on Communication Systems, 30(5), 1–23.CrossRef
30.
Shen, J., & Jian, M. (2017). Spatial query processing for skewed access patterns in non-uniform wireless data broadcast environments. International Journal of Ad Hoc and Ubiquitous Computing, 25(1/2), 4–16.CrossRef
31.
Song, D., & Park, K. (2016). A partial index for distributed broadcasting in wireless mobile networks. Information Sciences, 348, 142–152.CrossRef
32.
Luby, M. (2012). Best practices for mobile broadcast delivery and playback of multimedia content. In Proceedings of IEEE international symposium on broadband multimedia systems and broadcasting (BMSB) (pp. 1–7).
33.
Camp, T., Boleng, J., & Davies, V. (2002). A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing (WCMC), 2(5), 483–502.CrossRef
Metadaten
Titel
A hierarchical binary quadtree index for spatial queries
verfasst von
Kwangjin Park
Publikationsdatum
25.01.2018
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 4/2019
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-018-1661-z

Weitere Artikel der Ausgabe 4/2019

Wireless Networks 4/2019 Zur Ausgabe

OriginalPaper

Stability-based routing, link scheduling and channel assignment in cognitive radio mobile ad-hoc networks

OriginalPaper

Mobile sensor nodes scheduling for bounded region coverage

OriginalPaper

PATH: privacy-preserving auction for heterogeneous spectrum allocations

OriginalPaper

SRDPV: secure route discovery and privacy-preserving verification in MANETs

OriginalPaper

Secure and efficient binding updates in host-based distributed mobility management

OriginalPaper

Dynamic resource allocation in mobile heterogeneous cellular networks

Neuer Inhalt

    Bildnachweise