# Algorithms and Complexity Group Seminar

2011 Jan 12 at 13:30

DC 1304

## A Wavelet tree based representation of minimum bounding rectangles

Diego Seco, graduate student, David R. Cheriton School of Comp. Sci., Univ. Waterloo

The way memory hierarchy has evolved in recent decades has opened new challenges in the development of indexing structures. In this talk we present an approach to represent geographic data based on compact data structures used in other fields such as text or image compression. A wavelet tree-based structure allows us to represent a maximal set of Minimum Bounding Rectangles (MBRs) solving orthogonal range queries in logarithmic time. A set of MBRs is maximal if it does not contain any MBR whose projection in the x-axis is within the projection over the x-axis of other MBR in the set. In the general case, k maximal sets are needed to properly encompass the dataset and the query time complexity can be bounded by O(k log n).

This is joint work with Gonzalo Navarro.