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
The VLDB Journal
Erschienen in: The VLDB Journal 2/2007

01.04.2007 | Regular Paper

Using a distributed quadtree index in peer-to-peer networks

verfasst von: Egemen Tanin, Aaron Harwood, Hanan Samet

Erschienen in: The VLDB Journal | Ausgabe 2/2007

Einloggen

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

search-config
loading …

Abstract

Peer-to-peer (P2P) networks have become a powerful means for online data exchange. Currently, users are primarily utilizing these networks to perform exact-match queries and retrieve complete files. However, future more data intensive applications, such as P2P auction networks, P2P job-search networks, P2P multiplayer games, will require the capability to respond to more complex queries such as range queries involving numerous data types including those that have a spatial component. In this paper, a distributed quadtree index that adapts the MX-CIF quadtree is described that enables more powerful accesses to data in P2P networks. This index has been implemented for various prototype P2P applications and results of experiments are presented. Our index is easy to use, scalable, and exhibits good load-balancing properties. Similar indices can be constructed for various multidimensional data types with both spatial and non-spatial components.
Nächster Artikel SQL extension for spatio-temporal data

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
Literatur
1.
Aboulnaga, A., Naughton, J.F.: Accurate estimation of the cost of spatial selections. In: Proceedings of the 16th IEEE International Conference on Data Engineering, pp. 123–134. San Diego, CA (2000)
2.
Andrzejak, A., Xu, Z.: Scalable, efficient range queries for Grid information services. In: Proceedings of the IEEE International Conference on Peer-to-Peer Computing, pp. 33–40. Linkoping, Sweden (2002)
3.
Aref, W.G., Samet, H.: Extending a DBMS with spatial operations. In: Proceedings of Advances in Spatial Databases, SSD'91, pp. 299–318. Zurich, Switzerland (1991)
4.
Aspnes, J., Kirsch, J., Krishnamurthy, A.: Load balancing and locality in range-queriable data structures. In: Proceedings of the Symposium on Principles of Distributed Computing, pp. 115–124. St. Johns, Canada (2004)
5.
Aspnes, J., Shah, G.: Skip graphs. In: Proceedings of SODA, pp. 384–293. Baltimore, MD (2003)
6.
Banaei-Kashani, F., Shahabi, C.: SWAM: A family of access methods for similarity-search in peer-to-peer data networks. In: Proceedings of the Conference on Information and Knowledge Management-CIKM, pp. 304–313. Washington, DC (2004)
7.
Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)CrossRefMathSciNet
8.
Bharambe, A.R., Agrawal, M., Seshan, S.: Mercury: Supporting scalable multi-attribute range queries. In: Proceedings of the ACM SIGCOMM'04, pp. 353–366. Portland, OR (2004)
9.
Cai, M., Frank, M., Chen, J., Szekely, P.: MAAN: A multi-attribute addressable network for Grid information services. In: Proceedings of the International Workshop on Grid Computing, pp. 184–191. Phoenix, AZ (2003)
10.
Cheng, W.C., Chou, C.F., Golubchik, L., Khuller, S., Wan, Y.C.: Large-scale data collection: a coordinated approach. In: Proceedings of the IEEE InfoCom'03, pp. 218–228. San Francisco, CA (2003)
11.
Crainiceanu, A., Linga, P., Gehrke, J., Shanmugasundaram, J.: Querying peer-to-peer networks using P-Trees. In: Proceedings of the ACM SIGMOD'04, WebDB Workshop, pp. 25–30. Paris, France (2004)
12.
Daskos, A., Ghandeharizadeh, S., An, X.: PePeR: A distributed range addressing space for P2P systems. In: Proceedings of the International Workshop on Databases, Information Systems, and Peer-to-Peer Computing (held in conjunction with VLDB), pp. 200–218. Berlin, Germany (2003)
13.
Demirbas, M., Ferhatosmanoglu, H.: Peer-to-peer spatial queries in sensor networks. In: Proceedings of the IEEE International Conference on Peer-to-Peer Computing, pp. 32–39. Linkoping, Sweden (2003)
14.
Ganesan, P., Bawa, M., Garcia-Molina, H.: Online balancing of range-partitioned data with applications to peer-to-peer systems. In: Proceedings of the International Conference on Very Large Databases-VLDB, pp. 444–455. Toronto, Canada (2004)
15.
Ganesan, P., Yang, B., Garcia-Molina, H.: One torus to rule them all: Multidimensional queries in P2P systems. In: Proceedings of the ACM SIGMOD'04, WebDB Workshop, pp. 19–24. Paris, France (2004)
16.
Gao, J., Guibas, L.J., Hershberger, J., Zhang, L.: Fractionally cascaded information in a sensor network. In: Proceedings of the IPSN'04, pp. 311–319. Berkeley, CA (2004)
17.
Gupta, A., Agrawal, D., El Abbadi, A.: Approximate range selection queries in peer-to-peer systems. In: Proceedings of the First Biennial Conference on Innovative Data Systems Research. Asilomar, CA (2003)
18.
Harwood, A., Karunasekera, S., Nutanong, S., Tanin, E., Truong, M.: Complex applications over peer-to-peer networks. In: Poster Proceedings of the ACM Middleware'04, p. 327. Toronto, Canada (2004)
19.
Kedem, G.: The quad-CIF tree: a data structure for hierarchical on-line algorithms. In: Proceedings of the 19th Design Automation Conference, pp. 352–357. Las Vegas, NV (1982)
20.
Kothari, A., Agrawal, D., Gupta, A., Suri, S.: Range addressable network: A P2P cache architecture for data ranges. In: Proceedings of the IEEE International Conference on Peer-to-Peer Computing, pp. 14–22. Linkoping, Sweden (2003)
21.
Li, J., Jannotti, J., Couto, D.S.J.D., Karger, D.R., Morris, R.: A scalable location service for geographical ad hoc routing. In: Proceedings of the ACM MOBICOM'00, pp. 120–130. Boston, MA (2000)
22.
Li, X., Kim, Y.J., Govidan, R., Hong, W.: Multi-dimensional range queries in sensor networks. In: Proceedings of the ACM SenSys'03, pp. 63–75. Los Angeles, CA (2003)
23.
Litwin, W., Risch, T.: LH*g: A high-availability scalable distributed data structure by record grouping. IEEE Trans. Knowl. Data Eng. 14(4), 923–927 (2002)CrossRef
24.
Misra, A., Castro, P., Lee, J.: CLASH: A protocol for Internet-scale utility-oriented distributed computing. In: Proceedings of the International Conference on Distributed Computing Systems, pp. 273–281. Tokyo, Japan (2004)
25.
Mondal, A., Yilifu, Kitsuregawa, M.: P2PR-tree: An R-tree-based spatial index for peer-to-peer environments. In: Proceedings of the International Workshop on Peer-to-Peer Computing and Databases (held in conjunction with EDBT), pp. 516–525. Heraklion-Crete, Greece (2004)
26.
Ramabhadran, S., Ratnasamy, S., Hellerstein, J.M., Shenker, S.: Prefix hash tree. In: Proceedings of ACM PODC, p. 368. St. Johns, Canada (2004)
27.
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. In: Proceedings of the ACM SIGCOMM'01, pp. 161–172. San Diego, CA (2001)
28.
Rowstron, A., Druschel, P.: Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Proceedings of the ACM Middleware'01, pp. 329–350. Heidelberg, Germany (2001)
29.
Sahin, O.D., Gupta, A., Agrawal, D., El Abbadi, A.: A peer-to-peer framework for caching range queries. In: Proceedings of the 20th IEEE International Conference on Data Engineering, pp. 165–176. Boston, MA (2004)
30.
Samet, H.: Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, Reading, MA (1990)
31.
Samet, H.: The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA (1990)
32.
Samet, H.: Foundations of Multidimensional Data Structures. Morgan Kaufmann, San Francisco (2005)
33.
Sevcik, K., Koudas, N.: Filter trees for managing spatial data over a range of size granularities. In: Proceedings of the International Conference on Very Large Databases-VLDB, pp. 16–27. Mumbai, India (1996)
34.
Silaghi, B., Bhattacharjee, B., Keleher, P.: Query routing in the TerraDir distributed directory. In: Proceedings of the SPIE ITCOM'02. Boston, MA (2002)
35.
Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for Internet applications. In: Proceedings of the ACM SIGCOMM'01, pp. 149–160. San Diego, CA (2001)
36.
Tanin, E., Harwood, A., Samet, H., Nutanong, S., Truong, M.: A serverless 3D world. In: Proceedings of the Symposium on Advances in Geographic Information Systems, pp. 157–165. Arlington, VA (2004)
37.
Ulrich, T.: Loose octrees. In: M. DeLoura (ed.) Game Programming Gems, pp. 444–453. Charles River Media, Rockland, MA (2000)
38.
Zhao, B.Y., Huang, L., Stribling, J., Rhea, S.C., Joseph, A.D., Kubiatowicz, J.: Tapestry: A resilient global-scale overlay for service deployment. IEEE J. Selected Areas Commun. 22(1), 41–53CrossRef
Metadaten
Titel
Using a distributed quadtree index in peer-to-peer networks
verfasst von
Egemen Tanin
Aaron Harwood
Hanan Samet
Publikationsdatum
01.04.2007
Verlag
Springer-Verlag
Erschienen in
The VLDB Journal / Ausgabe 2/2007
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-005-0001-y

Weitere Artikel der Ausgabe 2/2007

The VLDB Journal 2/2007 Zur Ausgabe

Regular Paper

MEMS based storage architecture for relational databases

Regular Paper

An adaptive and dynamic dimensionality reduction method for high-dimensional indexing

OriginalPaper

SQL extension for spatio-temporal data

Regular Paper

Constrained data clustering by depth control and progressive constraint relaxation

Regular Paper

Path and cache conscious prefetching (PCCP)

Original Article

Compression techniques for fast external sorting