UNIGE document Doctoral Thesis
previous document  unige:40731  next document
add to browser collection
Title

Scalable approximate k-NN in multidimensional big data

Author
Director
Defense Thèse de doctorat : Univ. Genève, 2014 - Sc. 4712 - 2014/08/08
Abstract This thesis studies the scalability of the similarity search problem in large-scale multidimensional data. Similarity search, translating into the neighbour search problem, finds many applications for information retrieval, visualization, machine learning and data mining. The current exponential growth of data motivates the need for approximate and scalable algorithms. In most of existing algorithms and data-structures, there is a trade-off to be found between efficiency, complexity, scalability and memory efficiency. To address these issues, we explore recent techniques for similarity search. One remarkable recent technique is the Permutation-Based Indexing. Data objects are represented by a list of pivots, ordered with respect to their distances from the object. The similarity between two objects is then estimated based on these lists, following the idea that neighbouring objects have the same neighbourhood. In this thesis, we introduce a formal representation of the permutation-based indexing model. In particular, we introduce different strategies for selecting the pivots, pursuing the goal of high efficiency and low query response time. We propose a scalable, fast and memory-efficient data structure for nearest neighbour search. We provide models for permutation-based indexing on shared memory architecture, including CPU and GPU. In addition, we propose several distributed models for permutation-based indexing using MPI and MapReduce. In doing so, we provide an enhanced programming model using MPI to speedup further the MapReduce strategy. We analyse the proposed techniques and algorithms using standard public large-scale datasets containing millions of objects, and give comparisons to the most recent data structures and algorithms for similarity search.
Keywords Similarity SearchK-Nearest NeighbourBig DataMap-ReducePermutation-Based IndexingLarge Scale IndexingMPIParallel Computing
Identifiers
URN: urn:nbn:ch:unige-407315
Full text
Thesis (7.1 MB) - public document Free access
Structures
Research group Information Retrieval and Machine Group
Citation
(ISO format)
MOHAMED, Hisham. Scalable approximate k-NN in multidimensional big data. Université de Genève. Thèse, 2014. https://archive-ouverte.unige.ch/unige:40731

836 hits

607 downloads

Update

Deposited on : 2014-10-06

Export document
Format :
Citation style :