THE DISTANCE-AGGREGATION QUERY IN SUB-LINEAR TIME

Abstract

In this thesis, we study a very general query problem, the Distance Aggregation Query (DAQ) problem. To address the DAQ problem, we propose a framework named Locality-Sensitive Hashing (LSH) based Distance Aggregation Search (LSH-DAS), which can handle many instances of DAQ with various distance functions and aggregation operators by using proper LSH families and search frameworks. To further enable more distance functions and improve the performance of different aggregation operators, we first propose two new LSH families for the weighted Euclidean distance. Then, we propose a novel LSH search framework based on the Longest Circular Co-Substring for NNS. Next, we propose an improvement over the existing LSH search framework for Kernel Density Estimation (KDE) and show a real-life application of detecting obstacles using the proposed search framework for KDE. Finally, we conclude this thesis and show several possible directions of future works.