Multidimensional Indexing using Space Filling Curves (SFCs)

A critical issue in distributed environments is the efficient search of stored data according to their annotations. The importance of search mechanisms increases for P2P networks due to their data centric nature, since they are mainly used for publishing and discovery of content. However, the distributed nature of P2P systems poses difficulties in the development of indexing methods to support complex queries.

Our aim is to develop a multidimensional indexing scheme in order to support advanced searches in annotations of the actual data stored in P2P overlays. The proposed indexing method exploits the fundamental property of SFCs to continuously map a compact interval to a n-dimensional space and vice versa. SFCs also preserve locality, namely points of a referred interval are mapped to close points in the n-dimensional space.

We have considered that data items to be stored in distributed repositories are described by metadata attributes. Therefore, we propose the implementation of a DHT-based “Metadata overlay”. In order to ensure the efficiency of the search mechanism and fast responses, we enhanced the indexing method used in DHTs. Assuming that the set of n attributes to be indexed form a n-dimensional space, we have used the Hilbert SFC to map the n-dimensional space to a single dimension. The derived value of the corresponding point in the single dimension is indicative of the attributes describing the data item and can be used as a key during the insertion of the metadata files in the Metadata overlay.

Currently, our Java implementation performs the following actions:

• The mapping of the coordinates of a point in the n-dimensional space to its position in the Hilbert SFC
• The mapping of a point in the Hilbert SFC to the coordinates of the corresponding point in the n-dimensional space
• The traversing of the curve in order to enumerate the points of the n-dimensional space along the Hilbert SFC and to find adjacent points

The mapping of points among the Hilbert SFC and the n-dimensional space is done as imposed by the Butz algorithm (Butz 1971). Our implementation is based on the C code for Fast Hilbert Curve Generation provided by D. Moore.