hQT*: A Scalable Distributed Data Structure for High-Performance Spatial Access

Spatial data storage stresses the capability of conventional DBMSs. We present a scalable distributed data structure, hQTs, which offers support for efficient spatial point and range queries using order preserving hashing. It is designed to deal with skewed data and extends results obtained with scalable distributed hash files, LH*, and other hashing schemas. Performance analysis shows that an hQT* file is a viable schema for distributed data access, and in contrast to traditional quad-trees it avoids long traversals of hierarchical structures. Furthermore, the novel data structure is a complete design addressing both scalable data storage and local server storage management as well as management clients addressing. We investigate several different client updating schemes, enabling better access load distribution for many "slow" clients.