M-Grid: A Scalable Distributed Framework for Multidimensional Indexing and Querying Spatial Data

Speaker:  Sanjay Kumar Madria – Rolla, MO, United States
Topic(s):  Information Systems, Search, Information Retrieval, Database Systems, Data Mining, Data Science


The widespread use of mobile devices and the real time availability of user-location information both facilitating the development of new personalized, location-based applications and services (LBSs). Such applications require multi attribute query processing, scalability for supporting millions of users, real time querying capability and analyzing large volumes of data. 
Cloud computing aided a new generation of distributed databases commonly known as key-value stores. Key-value stores were designed to extract value from very large volumes of data while being highly available, fault-tolerant and scalable, hence providing much needed features to support LBSs. However, complex queries on multidimensional data cannot be processed efficiently as they do not provide means to access multiple attributes.  In this talk, I will present MGrid, a unifying indexing framework which enables key-value stores to support multidimensional queries. We organize a set of nodes in a modified P-Grid overlay network which provides fault-tolerance and efficient query processing. We use Hilbert Space Filling Curve based linearization technique which preserves the data locality to efficiently manage multi-dimensional data in a key-value store. We propose algorithms to dynamically process range and k nearest neighbor (kNN) queries on linearized values. This removes the overhead of maintaining a separate index table. The approach is completely independent from the underlying storage layer and can be implemented on any cloud infrastructure. Experiments on Amazon EC2 show that MGrid achieves a performance improvement of three orders of magnitude in comparison to MapReduce and four times to that of MDHBase scheme.

About this Lecture

Number of Slides:  35
Duration:  60 minutes
Languages Available:  English
Last Updated: 

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.