Masters Theses

Keywords and Phrases

Big Data; Cloud; Multidimensional Indexing; Peer To Peer


"The widespread use of mobile devices and the real time availability of user-location information is facilitating the development of new personalized, location-based applications and services (LBSs). Such applications require multi-attribute query processing, handling of high access scalability, support for millions of users, real time querying capability and analysis of 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 thesis we present MGrid, a unifying indexing framework which enables key-value stores to support multidimensional queries. We organize a set of nodes in a 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. Our 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"--Abstract, pages iii-iv.


Madria, Sanjay Kumar

Committee Member(s)

Chellappan, Sriram
Lin, Dan


Computer Science

Degree Name

M.S. in Computer Science


Missouri University of Science and Technology

Publication Date



ix, 56 pages

Note about bibliography

Includes bibliographical references (pages 51-55).


© 2014 Shashank Kumar, All rights reserved.

Document Type

Thesis - Open Access

File Type




Subject Headings

Databases -- Abstracting and indexing
Information retrieval -- Computer programs
Geographic information systems

Thesis Number

T 10850

Electronic OCLC #