CS240H Lab 2

Hilbert R-tree

Build a purely functional implementation of the Hilbert R-tree, a data structure for managing and querying two-dimensional geometric data, such as rectangles, circles, and other shapes.

This data structure was introduced in the influential VLDB paper "Hilbert R-tree: An Improved R-tree using Fractals". You can find a PDF copy of the original paper at cis.temple.edu.

Your implementation should follow the original description from the VLDB paper.


You should implement two algorithms:

Your implementation only needs to be able to insert and search rectangles. We are not interested in more complex shapes.

Assume that all X and Y coordinates will be specified as integers between 0 and 65536.

Sample data

We have provided a sample rectangle file containing all 1,454 rectangular features from the Visual 6502 project.

Command line application

Your submission must come in the form of a command line application.

Starting up

At startup time, the application must behave as follows:


Once it has started, your application must read "query rectangles" from stdin until end-of-file.

For each query rectangle, it should print out (on stdout) three pieces of information:

Here is an example session (user input is prefixed with >>> below):

$ ./my-submission visual486.txt
visual486.txt: 15373 rectangles read in 25.3 milliseconds
>>> 3458,2482,3458,2456,3570,2456,3570,2482
found 2 matches in 14 microseconds:

Property-based tests

Your submission should include a file that contains QuickCheck tests for your R-tree implemetation, along with instructions on how to build and run your tests.

(We strongly suggest that you develop your tests and your code simultaneously, as this makes it far easier to tell when your code is going wrong.)


You should submit your work in the form of a URL to a publicly accessible git repository, which should include the source and a README file that tells us:

  1. Who you are.

  2. How to build and run your program and tests.

(Alas, due to budget cuts, we cannot afford JPEGs of ponies any longer, and we will not be awarding quatloo bonuses for extra achievements.)