Efficient Processing of Aggregate-distance Queries on Heterogeneous Neighboring Objects using MapReduce

  • 王 梓憲

Student thesis: Master's Thesis


Currently most of the processing techniques for the conventional location-based queries focus only on a single type of objects However in real-life applications the user may be interested in obtaining information about different types of objects in terms of their neighboring relationship We term the different types of objects closer to each other the heterogeneous neighboring objects (HNOs for short) Efficient processing of the location-based queries on the HNOs is more complicated than that on a single data source because the neighboring relationship between the HNOs inevitably affects the query result In this thesis we present a novel and important query on the HNOs namely the aggregate-distance query (AggDQ for short) which can provide useful object information by considering both the spatial closeness of objects to the sets of query objects and the neighboring relationship between objects Given a set of query objects Q an integer k and a distance d the AggDQ retrieves the k-sets of HNOs for each query object q such that the distance between any two objects in each set of HNOs is less than or equal to d and the aggregate-distances of the k-sets of HNOs to q are the smallest among all sets of HNOs To efficiently process the AggDQ in a distributed and parallel manner we divide the given space into grid cells and develop two algorithms based on the MapReduce framework namely the MR-AggDQ and EMR-AggDQ algorithms Comprehensive experiments using both real and synthetic datasets are conducted to demonstrate the efficiency and scalability of the proposed algorithms
Date of Award2016 Aug 1
Original languageEnglish
SupervisorChiang Lee (Supervisor)

Cite this