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.