Tri par sélection | EPFL Graph Search

Le tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Cet algorithme est simple, mais considéré comme inefficace car il s'exécute en temps quadratique en le nombre d'éléments à trier, et non en temps pseudo linéaire. Description, pseudo-code et variantes Sur un tableau de n éléments (numérotés de 0 à n-1 , attention un tableau de 5 valeurs (5 cases) sera numéroté de 0 à 4 et non de 1 à 5), le principe du tri par sélection est le suivant :

rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 0 ;
rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ;
continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

En pseudo-code, l'algorithme s'écrit ainsi : procédure tri_selection(tableau t) n ← longueur(t) pour i de 0 à n - 2 min ← i
pour j de i + 1 à n - 1 si t[j] < t[min], alors min ← j

Disambiguation Canvas: A Precise Selection Technique for Virtual Environments

Ronan Boulic, Henrique Galvan Debarba, Anderson Maciel

We present the disambiguation canvas, a technique developed for easy, accurate and fast selection of small objects and objects inside cluttered virtual environments. Disambiguation canvas rely on selection by progressive refinement, it uses a mobile device and consists of two steps. During the first, the user defines a subset of objects by means of the orientation sensors of the device and a volume casting pointing technique. The subsequent step consists of the disambiguation of the desired target among the previously defined subset of objects, and is accomplished using the mobile device touchscreen. By relying on the touchscreen for the last step, the user can disambiguate among hundreds of objects at once. User tests show that our technique performs faster than ray-casting for targets with approximately 0.53 degrees of angular size, and is also much more accurate for all the tested target sizes.

Springer Berlin Heidelberg2013

Towards a Disambiguation Canvas

Ronan Boulic, Anderson Maciel

We present Disambiguation canvas, a technique for selection by progressive refinement using a mobile device and consisting of two steps. During the first, the user defines a subset of objects through the orientation sensors of the device and a volume-casting pointing technique. The subsequent step consists of the disambiguation of the desired target among the previously-defined subset of objects, and is accomplished using the mobile device touchscreen. By relying on the touchscreen for the last step the user can disambiguate among hundreds of objects at once, previous progressive refinement techniques do not scale as well as ours. Disambiguation canvas is mainly developed for easy, accurate and fast selection of small objects, or objects inside cluttered virtual environments. User tests show that our technique performs faster than ray-casting for targets with approximate to 0 : 53 degrees of angular size, and is also much more accurate for all the tested target sizes.

Ieee2013

Heterogeneous Recommendations: What You Might Like To Read After Watching Interstellar

Rachid Guerraoui, Anne-Marie Kermarrec, Tao Lin, Rhicheek Patra

Recommenders, as widely implemented nowadays by major e-commerce players like Netflix or Amazon, use collaborative filtering to suggest the most relevant items to their users. Clearly, the effectiveness of recommenders depends on the data they can exploit, i.e., the feedback of users conveying their preferences, typically based on their past ratings. As of today, most recommenders are homogeneous in the sense that they utilize one specific application at a time. In short, Alice will only get recommended a movie if she has been rating movies. But what if she has been only rating books and would like to get recommendations for a movie? Clearly, the multiplicity of web applications is calling for heterogeneous recommenders that could utilize ratings in one application to provide recommendations in another one. This paper presents X-Map, a heterogeneous recommender. X-Map leverages meta-paths between heterogeneous items over several application domains, based on users who rated across these domains. These meta-paths are then used in X-Map to generate, for every user, a profile (AlterEgo) in a domain where the user might not have rated any item yet. Not surprisingly, leveraging meta-paths poses non-trivial issues of (a) meta-path-based inter-item similarity, in order to enable accurate predictions, (b) scalability, given the amount of computation required, as well as (c) privacy, given the need to aggregate information across multiple applications. We show in this paper how X-Map addresses the above-mentioned issues to achieve accuracy, scalability and differential privacy. In short, X-Map weights the meta-paths based on several factors to compute inter-item similarities, and ensures scalability through a layer-based pruning technique. X-Map guarantees differential privacy using an exponential scheme that leverages the meta-path-based similarities while determining the probability of item selection to construct the AlterEgos. We present an exhaustive experimental evaluation of X-Map using real traces from Amazon. We show that, in terms of accuracy, X-Map outperforms alternative heterogeneous recommenders and, in terms of throughput, X-Map achieves a linear speedup with an increasing number of machines.

Assoc Computing Machinery2017

Heterogeneous Recommendations: What You Might Like To Read After Watching Interstellar

Rachid Guerraoui, Anne-Marie Kermarrec, Tao Lin, Rhicheek Patra

Assoc Computing Machinery2017