Barbay
le Jeudi 13 Décembre 2001 à 14h30
(LRI)
Intersection et autres problèmes d'ensembles triés pour moteur
de recherche : bornes inférieures et algorithmes
Résumé/Abstract :
Soit le problème consistant à calculer l'intersection de
k ensembles triés de taille donnée. Dans le modèle
de calcul limité aux comparaisons, nous prouvons une nouvelle borne
inférieure, relative à la complexité
non-déterministe de l'instance, c'est-à-dire la taille
de la preuve du résultat. Cette borne inférieure implique que
l'algorithme donné par Demaine, López-Ortiz et Munro est optimal
dans le sens "adaptatif". Nous étendons ces résultats au
problème d'ensemble de t-seuil, qui ne contient que les
éléments présents dans au moins t ensembles.
Les résultats sur ces deux problèmes seront
présentés à la conférence SODA.
Ces problèmes sont appliqués aux moteurs de recherche
indexés, dans le cadre du projet FFSS, sous la forme de deux variantes,
l'intersection bidimensionelle et l'interunion, sur lesquels sont
définis également des bornes inférieures et des
algorithmes. Le projet FFSS, qui consiste en un nouveau protocole de partage de
fichier (d'utilisation similaire à Samba, mais avec des options
intégrées de NetEject) doublé d'un moteur d'index et de
recherche sur les partages, est en ce moment testé en version béta
sur le réseau universitaire étudiant de la
Fédération AURORE, à l'université Paris-Sud.
Il est encore d'intéressants problèmes ouverts et applications,
et le concept de l'analyse de la complexité dans le pire des cas sur des
familles d'instances autres que celles définies par la taille des
instances, formalisé à l'occasion de ces travaux, semble
prometteur.
Intersection and t-threshold problem on sorted sets, lower bound and
algorithms
Consider the problem of computing the intersection of k sorted
sets. In the comparison model, we prove a new lower bound which
depends on the non-deterministic complexity of the instance, and
implies that the algorithm of Demaine, López-Ortiz and
Munro is optimal in this "adaptive" sense (for k much
smaller than n). We extend the lower bound and the algorithm to the
t-threshold problem, which consists in finding the elements
which are in at least t of the k sets.
These problems will be presented at the conference SODA02.
These problems are motivated by boolean queries in indexed text database
systems. Two variants of the intersection problem, bidimensional intersection
and interunion problem, are studied in the context of the FFSS project, a new
sharing file system protocol, associated with an indexed search engine.
This protocol is currently tested on the local student network of the
Federation AURORE, at University Paris-Sud.
There are some interesting open problems and applications, and the analysis
of the worst case in the "adaptive" sense, formalized for this work, seems
promising.