CSLab Web>P2P>GREDIA (2009-06-23, AthanassiaAssiki)

GREDIA: Grid enabled access to rich media content

Overview

is an FP6 project funded by the European Union.

Our team, as technical coordinators and Grid technology experts, is developing a generic middleware platform, based on our proposed service-oriented architecture, RDLS (Rich Data Location Services) , which enables efficient content management in Grid environments.

Our design introduces concepts from Peer-to-Peer and distributed computing in order to provide a scalable and reliable infrastructure for storage, search and retrieval of annotated multimedia content.

To ensure fast media lookups in the distributed repositories of a Virtual Organization, our system incorporates a multidimensional indexing scheme, which serves the need for supporting both point and range queries over a set of meta-data attributes. The distributed index is built on top of XOROS, a DHT that supports mutable objects. What is more, we are using Space Filling Curves (SFCs) to deal with arbitrary multi-attribute queries.

File transfers are conducted using GridTorrent, a grid-enabled, Peer-to-Peer mechanism that allows the aggregate data transfer throughput to scale, effectively coping with flash crowds.

RDLS can be efficiently integrated in existing Grid middlewares, such as Globus Toolkit 4, as it complies with WSRF, a standard posed by the Open Grid Forum. GridTorrent has backward compatibility with the file transfer utility GridFTP, adopted by the Grid community.

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.

People

Publications

A. Asiki, K. Doka, I. Konstantinou, A. Zissimos and N. Koziris, "A Distributed Architecture for Multi-dimensional Indexing and Data Retrieval in Grid Environments". In Proceedings of the Cracow 07 Grid Workshop, Cracow, Poland, October 2007
A. Asiki and K. Doka and I. Konstantinou and A. Zissimos and N. Koziris and P. Tsanakas, A grid middleware for data management exploiting peer-to-peer techniques Future Generation Computer Systems, Volume 25, Issue 4, April 2009, Pages 426-435, ISSN 0167-739X, DOI: 10.1016/j.future.2008.09.005