DBLab School of Computer and Electrical Engineering KDBSL NTUA
Tuesday, July 07, 2020
Τίτλος Towards a Distributed Spatial Access Scheme for Extended Objects
Έγγραφο Προβολή εγγράφου
Συγγραφέας George Tsatsanifos

George Tsatsanifos [23/11/2009]

Towards a Distributed Spatial Access Scheme for Extended Objects

This work aims at providing a pure multi-dimensional, indexing infrastructure for large-scale distributed systems of multi-tier architecture. We propose a new peer-to-peer variant for which we implemented a virtual distributed k-d tree, and developed novel, efficient algorithms for multi-dimensional lookups, orthogonal search and K nearest neighbors queries. The most prominent feature of our work is its enhanced scalability, as it performs extremely well for all query types, even for high-dimensional workloads (in O(log n), where n stands for the overlay size). In addition, we provide a simple, efficient fault-tolerance mechanism, to compensate for unexpected peer failures.

The latter part of the presentation focuses on spatial access methods for large-scale decentralized systems. In particular, we provide rigorous distributed algorithms, which perform containment, intersection and enclosure search for hyper-rectangles serving as minimum bounding boxes (MBBs) for extended objects. Our approach exploits point access methods (PAMs) combined with endpoint transformation methods for storing and searching D-dimensional hyper-rectangles, which have been mapped to 2D-dimensional points.

[ Back ]