Grouping and aggregating multidimensional spatial data is essential to any system requiring processing and analyzing large-scale multidimensional spatial data. Spatial data structures like R-Trees [1] are used for indexing spatial data objects by grouping them based on some heuristic, typically the spatial volume the data objects span. Similarly, Euler Histograms [2] are used to efficiently store aggregated spatial data and answer spatial queries. However, these data structures generally expect all data to be given as an input from a single data source. Due to scalability reasons large-scale systems are often distributed and obtain data from multiple sources. With data coming from distributed sources, there is a need for adapt these data structures to a distributed setup in order to design scalable solutions.
Distributed spatial data structures can be used in wide variety of distributed systems to efficiently process and analyze large-scale spatial data. For example a Publish/Subscribe system in which subscribers are organized as R-Tree is proposed in [3]. Other examples include distributed query processing of spatial data [4]. Distributed Euler histograms are used in sensor networks to count the moving objects in a given spatial area [5].
The goal of this master thesis is to design and implement data structures like R-Trees and Euler histograms in a distributed way (possibly similar to [3]) so as to allow the input to these data structures to come from several data sources. The ultimate goal is to be able to query these distributed data structures to obtain required knowledge. For example, distributed R-Tree should facilitate obtaining a set of minimum bounding rectangles based on a given cost function. Euler histograms should facilitate estimating the number of bounding rectangles that intersect a given bounding rectangle. The outcome of this thesis will be used in a design and implementation of an efficient Publish/Subscribe system which exploits the spatial nature of multidimensional publications and subscriptions to optimize several performance metrics of the system.
As part of this master thesis, the student will gain strong understanding of spatial data structures, which are widely used in a variety of computer applications. The work on a distributed implementation will provide an important experience with programming distributed systems. The work has a potential to be published in a reputed international conference or journal.
References:
[1] A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of ACM SIGMOD, 1984. Wikipedia
[2] Euler Histograms: R. Beigel and E. Tanin. The geometry of browsing. In LATIN’98, pages 331–340, Campinas, Brazil, 1998.
[3] Silvia Bianchi , Pascal Felber , Maria Gradinariu, Stabilizing Distributed R-Trees for Peer-to-Peer Content Routing, IEEE Transactions on Parallel and Distributed Systems 2010, [pdf]
[4] Cédric du Mouza, Witold Litwin and Philippe Rigaux, SD-Rtree: A Scalable Distributed Rtree, ICDE 2007 [pdf]
[5] Hairuo Xie, Egemen Tanin, Lars Kulik, Distributed Histograms for Processing Aggregate Data from Moving Objects, International Conference on Mobile Data Management, 2007 [pdf]