CAN-QTree: A Distributed Spatial Index for Peer-to-Peer Networks

Author

Huaiyu Zuo ; Ning Jing ; Yadan Deng ; Luo Chen

Author_Institution

Coll. of Electron. Sci. & Eng., Nat. Univ. of Defence Technol., Changsha

fYear

2008

fDate

25-27 Sept. 2008

Firstpage

250

Lastpage

257

Abstract

We present a distributed spatial index called CANQTree based on a content-addressable network (CAN) and QuadTree-alike structures. In our system, both spatial objects and their corresponding nodes in a QuadTree are identified by some points and mapped into CAN zones of peers. For a given spatial range query, CAN-QTree can provide O(n^1/2) search performance. With a uniform distribution of spatial objects, given epsiv > 0, CAN-QTree can provably maintain a load imbalance of at most 2+epsiv between a highest loaded peer and a lightest loaded peer. Simulations show that our CAN-QTree is an effective spatial index with a guarantee of good load-balancing.

Keywords

computational complexity; peer-to-peer computing; quadtrees; resource allocation; CAN-QTree; QuadTree-alike structures; content-addressable network; distributed spatial index; load balancing; peer-to-peer networks; Educational institutions; Fault tolerant systems; High performance computing; Hilbert space; Large-scale systems; Light scattering; Peer to peer computing; Robustness; Scalability; Spatial indexes; Content-Addressable Network; Load-Balancing; Peer to Peer; QuadTree; Spatial Index;

fLanguage

English

Publisher

ieee

Conference_Titel

High Performance Computing and Communications, 2008. HPCC '08. 10th IEEE International Conference on

Conference_Location

Dalian

Print_ISBN

978-0-7695-3352-0

Type

conf

DOI

10.1109/HPCC.2008.20

Filename

4637705