13
Remix : une architecture pour la recherche dans les masses de donn´ ees index´ ees Gilles Georges, Steven Derrien, St´ ephane Rubini, Fr´ ed´ eric Raimbault, Laurent Amsaleg, Dominique Lavenier To cite this version: Gilles Georges, Steven Derrien, St´ ephane Rubini, Fr´ ed´ eric Raimbault, Laurent Amsaleg, et al.. Remix : une architecture pour la recherche dans les masses de donn´ ees index´ ees. Symposium en archichecture de machines (Sympa) 2006, Oct 2006, Perpignan, France. pp.142-153, 2006. <hal-00505589> HAL Id: hal-00505589 https://hal.archives-ouvertes.fr/hal-00505589 Submitted on 24 Jul 2010 HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entific research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destin´ ee au d´ epˆ ot et ` a la diffusion de documents scientifiques de niveau recherche, publi´ es ou non, ´ emanant des ´ etablissements d’enseignement et de recherche fran¸cais ou ´ etrangers, des laboratoires publics ou priv´ es.

Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

Embed Size (px)

Citation preview

Page 1: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

Remix : une architecture pour la recherche dans les

masses de donnees indexees

Gilles Georges, Steven Derrien, Stephane Rubini, Frederic Raimbault, Laurent

Amsaleg, Dominique Lavenier

To cite this version:

Gilles Georges, Steven Derrien, Stephane Rubini, Frederic Raimbault, Laurent Amsaleg, et al..Remix : une architecture pour la recherche dans les masses de donnees indexees. Symposiumen archichecture de machines (Sympa) 2006, Oct 2006, Perpignan, France. pp.142-153, 2006.<hal-00505589>

HAL Id: hal-00505589

https://hal.archives-ouvertes.fr/hal-00505589

Submitted on 24 Jul 2010

HAL is a multi-disciplinary open accessarchive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come fromteaching and research institutions in France orabroad, or from public or private research centers.

L’archive ouverte pluridisciplinaire HAL, estdestinee au depot et a la diffusion de documentsscientifiques de niveau recherche, publies ou non,emanant des etablissements d’enseignement et derecherche francais ou etrangers, des laboratoirespublics ou prives.

Page 2: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

����������� �������������������������� �"!��$#%�'&���($���'�)������"�*���,+-���.��/�0�1214365 56/��87$9��*0:��/$;<+2/�=�>� �)�����

?A@CBEDF GIHKJL@NMCOQPSRLTVUS@WPXU�HLOQ@ZY�[\HLO^]>M_O$@WPSRL@WOQPSRL@a`bMcJKde]f@gdehiMcd�d�@gde`K@`K[%JKJLjW@gd^TkJL`K@8lKjW@gd

mon$mqpsr�tvu*psw1 x�y n�z-p>tvtv{|p>} 1 x�y n�~\����{'}�{ 1 xb� n�~��,{'���$�,���'� 2 xb� n��%�Lw2�,�|p>u 1 x zIn � �s�*p>}�{|p>t 1

1 � ~ �vy ��� ��� ~ � �A�c� � ~ y�� ~%p>}�}�psw2 � }�{'�*p>tkwv{'�k����p��ctkp>�f�,u}�p y ��� ��� �,}�}�psw

� �)�����:�

� p� �tkr,¡Vp>�%~"ps¢ �¤£ �K �r���t%r��¥¡vps¦>�v{�§¨��pq �tkr� ©rwkp>t\��}�pª�,tk¦f«�{'�kps¦>�v��tkp����,�k�>tv{|p>�'�|pª��pswv�v{'}��spª¬���¦s¦s�>�|�>tkp>t%�6�tkps¦f«�p>tk¦k«�pL�S­ {'}¥§®r�tv���,�v{|r�}:���,}�w-�|psw�����wkwkpsw-��po��r�}�}��spsw<n y r�}¯¦s°-��t-pswk�"��}�pI�L�>�Lr�{'tkpK��pI�vtk±sw-utf�,}���p¦<�, $��¦>{'�k�-�>�vtkr�{'�kp>�Lp>})�"¦sr��� ��|�sp�¬ª��pswCtkpswfwkr���tk¦spswctkps¦sr�}¥²�u��tf�,���|psw<nQ³"}� �p>���\�,�|r�tkw\��¦s¦s�s��p>t´tf�, �{|��p>�Lp>}���,�¥µK��r�}�}��spsw"¶·¦sr��K $�,tf�,�v{'�*p>�Lp>}��´¬-��psw¸wv�� � ©r�tv�kw¨��p\wv�kr�¦k¹�,u*p´��p´�»º� ©p´�¥{|wk¼)��p\���,u}��>�v{|¼)��p�½¨p>�¨p>})��{|wf�¾�u*p>t¨��pswWwv�vtf�,�k�>u{|psw���pCtkps¦k«�p>tk¦k«�p%{'}�}�r<��,})�kpswcr�tv{|p>})�k�spsw � }�r��f�,�K�Lp>})� � wk��t��¿­ {'}���p4µ��,�v{|r�}���psw¨��r�}�}��spsw�n � � �tkr�utf�,�K���,�v{|r�}��¥�bwvº¥wv�k±>�Lp\~"ps¢ �¤£ pswv�¨ �tv{|wkp\p>} ¦k«$�,tvu*p% $�,t���}�À4ÁvÂ�Ã�Ä4Å�Æ�Á2ÇC¼���{�u��{|��p\�|p%¦sr�}�¦sp> ��kp>��t��p> ���{|wW�6��wv ©�s¦>{�²$¦<�,�v{|r�}��S­ ��}�p´}�r����*p>�'�|p"�, � ��'{|¦<�,�v{|r�}q¡���wf¼)�ȭɬ�wf���K{|wkp´p>}K°-����tkp´wv��tW�|p´wv�� � ©r�tv�Wtkps¦sr�}¥²��u��tf�,���|pn)�cp>���,tv�v{|¦>�|pC �tk�swkp>}��kp´�|pswg�Lr��v{'��,�v{|r�}�w � �¿­É�,tk¦k«�{'�kps¦>�v��tkp"p>�g�¿­Êp>})��{'tkr�}�}�p>�Lp>})�C��p¸ �tkr�utf�,�K���,�v{|r�}�¥�Ëwvº¥wv�k±>�Lpq~"ps¢ �¤£ n

ÌQÍLÎ>Ï�Ð<Ñ,ÒSÓ �8Ô Ð�ÕÖÒ�Ï

� ��tkps¦f«�p>tk¦k«�p% $�,t�wv{'�K{'�6�,tv{'�k�\¦sr�}�wv{|wk�kp\¬�tkp>�vtkr����*p>t � ���,}�wW��}�pC�$��wkp´��p\��r�}�}��spsw � ��}�r��K ��'��wv{|p>��tkw¨r��¥¡vp>�kw× ÁvÆ<Ø4Ù�Ä2Ú\�S­ ��}Ûr��¥¡Vp>�´tkps¼���Ü>�kpn�cpC�¤º� ©p\��p´tkps¦f«�p>tk¦k«�p�wkpc§·r�}���p%p>}Lu*�>}��>tf�,�$wv��t¨��}�p\}�r��v{|r�}���p\�¥{|wv�f�,}�¦sp\p>}��vtkp%r��¥¡vp>�kw"¶Ö ��'��wW�6���¥{|wv�f�,}�¦sppswv��§¿�,{'���|p´ ��'��wW�6�-wv{'�K{'�6�,tv{'�k�%p>})�vtkp\r��¥¡vp>�kw¨pswv�g§®r�tv�kp�½ � �|pCtk�swv���'�f�,����pC�6��tkps¦f«�p>tk¦k«�p��>�f�,})�¸�,�|r�tkw¨�|p�¶·r��L�|psw2½r��¥¡vp>��¶·w2½" ©rwkwk�s���,})�ª�6���¥{|wv�f�,}�¦spK�6�� ��'��wq§¿�,{'���|pK $�,t�tf�, � ©r�tv�I¬ �¿­Êr��¥¡vp>��tkps¼���Ü>�kpn � pK}�r��ª��tkpb�S­Êr��¥¡vp>�kw¬Ûtkp>�kp>}�{'to �p>���oÜ>�vtkp�wkr�{'�ª �tk�4�»���>�kp>tv�K{'}��ݶÖ�|psw

Nr��¥¡vp>�kwI �rwfwk�s���,})�o�6�Þ�¥{|wv�f�,}�¦sp �6�Û ��'��wª§¿�,{'���|p�½ � wkr�{'�

ß$p4µ¥{'���|pL¶Ö�kr���w\�|psw\r��¥¡vp>�kw\��r�}��%�6�o�¥{|wv�f�,}�¦sp�pswk�´{'}¥§·�>tv{|p>��tkpI¬I��}Ûwkp>��{'�È��r�}�}���½4n�c{|p>}à¼��È­ {'�\ ©p>tv�Lp>�v�kpÛ�S­Êr����kp>}�{'t���}�pÞ¼)�$�,�'{'�k�Û��pËtk�swv���'�f�,�kwb�>�|p>�*�sp � ¦sp��¤º� ©pË��pËtkps¦f«�p>tk¦k«�páwkp�§¿�,{'��p>}u*�>}��>tf�,�c $�,tª��}Ý $�,tk¦sr���tkwop4µ�«$�,��wv�v{�§%��pb�6���$��wfpb�S­Êr��¥¡vp>�kw<n��cpb $�,tk¦sr���tkwo¦sr��K ��|p>�o �p>���Iw<­É�s�*�>tkp>toÜ>�vtkp�vtk±sw-¦sr�â��kp>�¥µáp>}.�kp>�K �w � wkr�{'�q¬b¦<�,��wkpo�¥�á}�r��ª��tkpK�S­É��¦s¦s±sw-�K{|w-p>}b¡vp>� � wkr�{'�-¬ ¦<�,��wkpo��pª�6� ¦k«$�,tvu*pK��p¦<�,�|¦>���¥�'{|�sp\¬%�¿­Ê�>���,�'�$�,�v{|r�}���pswg�¥{|wv�f�,}�¦spsw�p>})�vtkp´r��¥¡vp>�kw<n � }�¦>{|��p>�K�Lp>}�� �  $�,tk¦spC¼)��pc�|pc�kp>�K �wW��pctkps¦k«�p>tk¦k«�p�>�*r��'��p-�'{'}��<�,{'tkp>�Lp>}����s�*ps¦-�6�ª�f�,{'�'�|pq��p-�6�ª�$��wkp � ¦sp>�v�kp��, � �tkr�¦k«�pq ©rwkp-��pswC �tkr����|±>�Lpsw´ ©r���t\��p�utf�,}���psw����wkwfpsw´��p���r�}�}��spsw<nã r���t¨�>��{'�kp>tg��}K $�,tk¦sr���tkwWwvº¥wv�k�>���,�v{|¼���p � �|pswgr��¥¡Vp>�kwg ©p>���*p>})��Ü>�vtkpc{'}���p4µ��sw¨¬" $�,tv�v{'t¨��p¸�|p>��tkw¨ �tkr� �tv{|�>�k�sw<n� }�pKtkps¦k«�p>tk¦f«�pb¦sr�}�wk{|wv�kpb�,�|r�tkwI¬�p4µ��vtf�,{'tkp��|psw� �tkr� �tv{|�>�k�swI��pL�6��tkps¼���Ü>�kp �  ���{|wI¬�}�pLwfr��'�'{|¦>{'�kp>tª¼���pK�|pswr��¥¡vp>�kw\¼���{S �rwkwf±s��p>})�\�kr����%r��� $�,tv�v{|p���p�¦spsw´ �tkr� �tv{|�>�k�sw<nã r���tC{'�'�'��wv�vtkp>t � r�}  ©p>���¸ �tkp>}��¥tkp��¿­Êp4µ�p>�K ��|po¶·wk{'�K ��'{�²$��½���p"�¿­ {'}���p4µ��,�v{|r�}��S­ ��} �kp4µ¥�kpIä�r�}b��ª¦sr�}�wv�vtv��{'tkp

∗ å)æWç¾è¿ékê·æ�ë8ì8ækí�îÖïÞæVð·ëÈñ�ò,ó2ò,ô�õgç�ókèXö'÷ ø8ù�îÈí-ó2ð®ð®æ�ð�ú�ægûgé4ò¾ò,õVæ�ð�ü6ýfþ4þ2ÿ��©ýfþ4þ ���

142

Page 3: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

��}:{'}���p4µ¯¼)��{W ©rwkwk±s��p � p>})�vtk�spswI¦sr�tvtkpswv �r�}����,}��ª�,�¥µ � �Lr��kw��¥{��S�>tkp>})�kw�tk�> �p>tv�kr�tv{|�swª���,}�wq�|pK�kp4µ¥�kpn�¸«$��¼)��p�p>})�vtk�sp���p-�¿­ {'}���p4µ:¶Ö{|¦>{S��}��Lr��2½c ©r�{'})�kp-�*p>tkw´��}�p-�'{|wv�kpq��p- �«�tf��wfpsw�¶Ö�|psw´r��¥¡Vp>�kw4½cr��˦sp-�Lr��\pswv� �tk�swkp>})�<n

� }�p�tkps¦k«�p>tk¦f«�pc���,}�w�¦sp>�v�kp¨�$��wfp¨{'}���p4µ��sp¨ ©p>���8 $�,tXp4µ�p>�K ��|pC�s�*r�{'t8 ©r���tXr��¥¡vps¦>�v{�§$��p¨tkp>�vtkr����*p>t��kr����kpswX�|psw �«�tf��wkpsw%wk{'�K{'�6�,{'tkpsw%¬I��}�p- �«�tf��wkpqtkps¼���Ü>�kpn��W}Ë�S­É�,���vtkpsw%�kp>tv�Lpsw´tkp>�vtkr����*p>t"��pswC �«�tf��wkpsw%¼)��{S ©rwkwk±s��p>}��¬L ©p>�Û �tk±sw��|psw"�LÜ>�Lpsw��Lr��kw�p>�����,}�w��|p��LÜ>�Lpor�tk�¥tkpnQ�"{'}�wv{ � �,�Þ�'{|p>�.��p� $��wkwfp>t�p>}átkp>����p��¿­Êp>}�wkp>�����|p��psw� �«�tf��wfpsw��¥���kp4µ¥�kp � r�}b}�p\wk�>�|ps¦>�v{|r�}�}�p�¼)��p%¦sp>�'�|psw¸¼���{$¦sr��K ©r�tv�kp>})�C�|psw¨�Lr��kw¸tkps¦k«�p>tk¦f«��sw<n � p\}�r�����tkp��pq �«�tf��wkpsw%¬K�vtf�,{'�kp>t%pswv�\��r�}�¦��,{'}�wv{X¦sr�}�wv{|���>tf�,���|p>�Lp>})��tk�s�¥��{'�<n�c{|p>}à¼)��p��|p�u)�,{'}  ���{|wfwkp4�¿�V�»Ü>�vtkpË�>}�r�tv�Lp� $�,tLtf�, � ©r�tv��¬á��}  $�,tk¦sr���tkw�p4µ¥«$�,��wv�v{�§ � {'�C§®�,���L¦sp> ©p>}����,})�¦sr��K ��kp>t%wv��tC�|pswC�kp>�K �w´�S­É��¦s¦s±sw%�,�¥µb��r�}�}��spswª¶·r��Û�,�¥µ r��¥¡vp>�kw2½¸¼)��{© ©p>���*p>})�\Ü>�vtkp-p4µ��vtkÜ>�Lp>�Lp>}��% ©�>}$�¾��'{|wf�,})�b��±swK�|r�tkwK¼)��p��6�á�f�,{'�'�|pÛ��p��6�á�$��wkp�pswv�Lwv�� ©�>tv{|p>��tkpˬá�6�.¦<�, $��¦>{'�k�Ë��p��6�á�L�>�Lr�{'tkp˦sp>})�vtf�,�|pÞ��p�6�Ý����¦k«�{'}�p � p>��¼)��pá¦sp>�v�kpÛ�$��wfpÞ��r�{'����r�}�¦áÜ>�vtkpáwk�kr�¦f¹*�spáwk��t���} �¥{|wk¼���pÛ���,u}��>�v{|¼���pn��W} p��Sp>� � �6�}$�,�v��tkp%�LÜ>�Lp%��p\�¿­ {'}���p4µ��,�v{|r�}�{'�K ��'{|¼���p\��} ��¦s¦s±swc�,�|�<�,�kr�{'tkp"�,�¥µLr��¥¡vp>�kw�p>����}�p\tkps¼)��Ü>�kp% �p>����wfr��'�'{|¦>{'�kp>t�¿­É�,}$�,�'º�wfp��S­ ��} }�r�����tkp�{'�K ©r�tv�f�,})�´�S­Êr��¥¡vp>�kw<n�zq�,}�wC¦sp�¦<��w � �|p%u)�,{'}� $�,t¸tf�, � ©r�tv�C¬���}���¦s¦s±swcwf�s¼)��p>}��v{|p>�}È­Êpswv�\ $��w´u)�,tf�,}��v{¿n�\²�}.��p���{|p>}.¦sr��K �tkp>}��¥tkpI�¿­ {'�K $��¦>����pª¦sp��kp>�K �w-�S­É��¦s¦s±swq�,�¥µÛ��r�}�}��spsw � }�r���w% �tkr� ©rwkr�}�w"��}�p��Lr����4��'{|wf�,�v{|r�} ¶Ö�vtk±sw"wv{'�K ��'{�²$�sp�½%¼)��{È ©p>tv�Lp>�%��pq�Lp>�v�vtkpªp>}Þp>��{|��p>}�¦sp � ���,}�w%�|p�¦<��w%�S­ ��}áwv�kr�¦f¹��,u*p�wv��t%�¥{|wk¼���p���,u}��>�v{|¼)��p � ¦sp>�v�kpq{'}¥ß���p>}�¦sp�wk��t´�|psw´ �p>tV§®r�tv���,}�¦spsw\tk�sp>�'�|psw"�S­ ��}�pq{'}���p4µ��,�v{|r�}Èn

y {�r�}Iwv�� � ©rwkp¸��}ªtkps¦sr�����tkp>�Lp>})�¨¦sr��K ��|p>�¨p>}��vtkpc�|pswX�kp>�K �wg��p¸�vtf�,{'�kp>�Lp>})��p>���kp>�K �wg�S­É��¦s¦s±sw¨�,�¥µªr��¥¡vp>�kwr�}Û ©p>���"pswv�v{'�Lp>t"�|p��kp>�K �w��S­Êp4µ¥�s¦>���v{|r�}Þ �r���t"��}Û $�,tk¦sr���tkw�wvº¥wv�k�>���,�v{|¼)��p ¶

tscan

½ � r��Þ��}�p�{'}���p4µ��,�v{|r�}¶tindex

½C $�,t�ä

tscan = K × max

{

S/BPtdist

¶��½

tindex = P × max

{

tacces + nobj × S/BPnobj × tdist

¶�*½

zq�,}�w´¦sp>�v�kp�§·r�tv�ª���6�,�v{|r�} � K tkp> �tk�swkp>}��kpq�|p�}�r�����tkp��S­Êr��¥¡vp>�kw´��p��6���$��wfp � P �|p�}�r��ª��tkpq�Lr<º*p>}Ë�S­É��¦s¦s±sw¬-�¿­ {'}���p4µK �r���t¸¦k«$��¼���p´tkps¼)��Ü>�kp � nobj

�|p´}�r�����tkp%�Lr<º*p>} �S­Êr��¥¡Vp>�kwc��wkwkr�¦>{|�sw¨¬q¦k«$��¼���p%p>}��vtk�sp\��p´�¿­ {'}���p4µ �S�6���f�,{'�'�|p%�Lr�º*p>}�}�p"�S­ ��}�r��¥¡Vp>� � taccess

�|p\�kp>�K �wC�S­É��¦s¦s±swC�,�b�¥{|wk¼���p\���,u}��>�v{|¼���p � tdist

�|p\�kp>�K �wc ©r���t¦<�,�|¦>���|p>t\��}�p��¥{|wv�f�,}�¦spqp>}��vtkp�r��¥¡vp>�kw � p>� BP

�6�I�$�,}���p� $��wkwf�,})�kp�p>})�vtkpq�|pq�¥{|wv ©rwv{'�v{�§g��pqwv�kr�¦f¹��,u*pqp>�´�|psw��}�{'�k�sw%��pq�vtf�,{'�kp>�Lp>}��<nã tkp>}�r�}�w¨�¿­Êp4µ�p>�K ��|p\�S­ ��}�p´�$��wfp´��p

106r��¥¡Vp>�kw\¶

K½���pC�f�,{'�'�|p\�>u)�,�|p\¬��� � -r�¦>�kp>�kw%¶

S½4n y �� � ©rwkr�}�w¨¼���pC�|p

�kp>�K �wC �r���tC¦<�,�|¦>���|p>tC�6���¥{|wk�f�,}�¦sp�p>}��vtkp��r��¥¡vp>�kwCwkr�{'�c�>u)�,�S¬2× 10−6

wkps¦sr�}���po¶tdist

½ � ¼)�È­ ��}�p"tkps¼���Ü>�kp $�,t-{'}���p4µ��,�v{|r�}.}��s¦spswkwv{'�kp

103��¦s¦s±swq¬L�¿­ {'}���p4µ ¶

P½ � wkr�{'�����N��p��6���$��wkpop>�-¼)�È­ ��}�pop>})�vtk�spo��pª�¿­ {'}���p4µ

pswv�I��wfwkr�¦>{|�spKp>}Ý�Lr<º*p>}�}�p�¬���r��¥¡vp>�kwb¶nobj

½4n��cr�}�wv{|���>tkr�}�wªp>}�wk��{'�kp�¼���pK�6���$��wkpÞ¶·¦sr��K�Lp�wf���*p>tkwk{|r�}{'}���p4µ¥�sp�½´pswv�´wv�kr�¦f¹*�sp�wv��tC��}Ë�¥{|wk¼���p� �rwkwf�s���,})�\��}�p-�$�,}���p- $��wkw2�,})�kp���p��� o¢ár)�,w�¶

BP½�p>�´��}��kp>�K �w

�S­É��¦s¦s±sw%�¥{|wk¼���p���p��� o�Lwª¶taccess

½4nzq�,}�w\¦spq¦<��w � }�r���w\r����kp>}�r�}�w%��}��kp>�K �w\�S­Êp4µ¥�s¦>���v{|r�}Û �r���t´�¿­ {'}���p4µ��,�v{|r�}Ë�vtk±sw\wv�� ©�>tv{|p>��t%¬o¦sp>�'��{Stkp>�6�,�v{�§¬o��}� $�,tk¦sr���tkw�wvº�wk�k�>���,�v{|¼)��pq��p-�6�o�$��wfp ä

tscan �owkps¦sr�}���psw"p>�

tindex �� Kwfps¦sr�}���psw<n

� �È�, � $�,tf���|�\��r�}�¦-¼���p � ���,}�wC�|p-¦<��w´��p��¿­ ���v{'�'{|wf�,�v{|r�}Ë��p��¿­ {'}���p4µ��,�v{|r�} � ��p>�¥µb $�,tf�,�L±>�vtkpsw\wkr�{|p>}��%¬�¦sr�}�wk{�����>tkp>t��,�v�kp>}��v{'�*p>�Lp>})�oä

143

Page 4: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

x �|p��kp>�K �w\�S­É��¦s¦s±swqä�{'�S��p>��{|p>}��\¦>tv{'�v{|¼)��pq��±swC�|r�tkw´¼���p��6�ª�f�,{'�'�|pq��p"�6�ª�$��wkp-���> $��wkwfp"�6�ª�f�,{'�'�|pq��p��6�ª�L�4��Lr�{'tkp\¦sp>}��vtf�,�|p"p>�¨¼���p\¦sp>�'�|p4�»¦>{$��r�{'� �  $�,t�¦sr�}�wk�s¼���p>})�¸Ü>�vtkp%wv�kr�¦f¹*�sp\wv��tW��}�wk�� � �r�tv����pC�L�>�Lr�tv{|w2�,�v{|r�}��pq�¤º� ©p��¥{|wk¼���pn$��­Êpswv�\ $�,t"p4µ¥p>�K ��|p��|pq¦<��w\�|r�tkwk¼��È­Êr�}Û¦sr�}�wv{|��±>tkp���psw%����wkwkpsw\��p���r�}�}��spsw\�kp>�'�|psw%¼���p�|psw��$�,}�¼���psw%u*�>}�r��K{|¼���psw � �|psw%�$�,}�¼���psw-�S­ {'���,u*psw � �|psw%�$�,}�¼���psw���{|���sr � �|psw���r�}�}��spsw-�����'�v{'�L�s�¥{6���¥�� p>� � p>�k¦n

x �6� wk�>�|ps¦>�v{'��{'�k�Ý䨦­Êpswv�b�|pËtf�, � ©r�tv� P/Kn ã �'��wb¦spËtf�, � ©r�tv�bpswv��§®�,{'���|p �  ��'��wL�|pË}�r��ª��tkpÞ�S­Êr��¥¡vp>�kw�¬

�,}$�,�'º¥wkp>t´�¥{'�K{'})��pn � ­Êp>}�¡vp>���S­ ��}�p�{'}���p4µ��,�v{|r�}�p���¦<��¦sp-pswv�C��r�}�¦���p�tk�s�¥��{'tkpq�,� ���¾µ�{'�ª���a�6����,�|p>��t��p ¦sp�tf�, � ©r�tv�<n �W} �S­É�,���vtkpswI�kp>tv�Lpsw � �|pswª �tkr� �tv{|�>�k�swo���v{'�'{|wk�spswI �r���tª�¿­ {'}���p4µ��,�v{|r�} ��r�{'�*p>})�KÜ>�vtkpb�|psw ��'��w-�¥{|wk¦>tv{'�K{'}$�,}��kpsw- �rwkwk{'���|psw% ©r���t% ©p>tv�Lp>�v�vtkpo��p�}�pªwk�>�|ps¦>�v{|r�}�}�p>tq¼)�È­ ��}á �p>�v{'�"}�r�����tkpK�S­Êr��¥¡vp>�kw �p>�\�K{'}�{'�K{|wfp>t"¬I�6�I§®r�{|w´�|psw´�kp>�K �w\�S­É��¦s¦s±sw"p>�\�|psw´�kp>�K �w´�'{|�sw��,�¥µ�¦<�,�|¦>���|w"��pq�¥{|wv�f�,}�¦spn

� ­Êr��¥¡vps¦>�v{�§¨�¥�� �tkr,¡Vp>�"~%ps¢ �»£ pswv�\��r�}�¦���pq �tkr� ©rwkp>t´��}�p��,tk¦f«�{'�kps¦>�v��tkp����,�k�>tv{|p>�'�|p�¦<�, $�,���|pbä

�n Ó���� Ô*Ô*� Ó���ÑÛÑ���ÕÖÓ�� � ��Ï�Ð �*Ð���� � �¥Ð<ÒQÕÖÑ� � ��Ï�Ð�� � Ï��$Ñ��Ï8ÓAÏXÒ ��� Ñ��.Ó���Ò ��� �*Ð � Í � pI�����qpswv���p-tkp>}��¥tkpq �rwfwv{'���|p-�6�I�K{|wkpqp>}Ë°-����tkp��S­É�,�'u*r�tv{'�v«��Lpsw%�S­ {'}���p4µ��,�v{|r�}Þp���¦<��¦spsw\wk��t´��}Ë�*r��'���Lp���p��r�}�}��spsw´¦sr�}�wk�s¼)��p>}���¶Ö ��'��wv{|p>��tkw´¦sp>})�f�,{'}�psw%��pqmqr)½4n��"{'}�wv{ �  ��'�������´¼)��p-��p-wv�kr�¦k¹*p>tC�¿­ {'}¥§®r�tv���,�v{|r�}wv��t�wk�� � �r�tv�����,u}��>�v{|¼)��p � ~"ps¢ �¤£  �tkr� �rwfpª�S­ ���v{'�'{|wkp>t-��}�pª�L�>�Lr�{'tkpo��pª�¤º� ©p � �6��wk«á��pªutf�,}���p¦<�, $��¦>{'�k��¶�� ���m-r)½C¼���{È�¥{|wv ©rwkpq�S­ ��}Ë�kp>�K �w\�S­É��¦s¦s±sw"��pq�¿­Êr�tk�¥tkp���p �

µw<n

¥n Ó������ ��Ô)� Ð��)Ñ Ñ���gÕÖÓ�� � ��Ï�Ð �!� � Ô ��� Ô)� � � Ó�� ÓgÕ � Ð���Ï Ô �$Í �cpsw�¦<�,�|¦>���|wÛwkpÛ �tkÜ>�kp>}��Ûp>} u*�>}��>tf�,��vtk±sw���{|p>}A¬¯��}�pÞ�K{|wkpáp>} °-����tkpÞ���,�k�>tv{|p>�'�|páwk��t ��pÞ�6�¯�|r�u{|¼���pá �tkr�utf�,�K���,���|p � �6��¼)��p>�'�|pápswv�¦<�, $�,���|p��S­Êp4µ¥ ��|r�{'�kp>t´p���¦<��¦sp>�Lp>})�´�|p" $�,tf�,�'�|�>�'{|wv�Lp�¬�utf�,{'}�²�}��¥{|wv ©r�}�{'���|p"���,}�wC¦spswc�vtf�,{'�kp>�Lp>})�kw�n� �ª�L�>�Lr�{'tkp � �6��wk«�pswk�C��r�}�¦q�¥{'tkps¦>�kp>�Lp>}��%¦sr�}�}�ps¦>�k�sp�¬ª��psw´¦sr��K �rw2�,})�kw � ã m-� £ {'�'{'}¥µ � {'tv�kp4µ���k� ã tkr ��pËutf�,}���pá¦<�, $��¦>{'�k�Þ �p>tv�Lp>�v�f�,}����S­ {'�K ��6�,}��kp>t���psw�r� ©�>tf�,�kp>��tkw ��pÞ¦<�,�|¦>���"��pÞ�¥{|wv�f�,}�¦sp¦sr��K ��|p4µ¥psw"p>�C§·r�}�¦>�v{|r�}�}$�,}����,�Ëtvº��v«��Lp��¥��ß$r��%��p���r�}�}��spsw"p>}� �tkr<�*p>}$�,}�¦spI��p-�6�o�L�>�Lr�{'tkpn

� �I�L�>�Lr�{'tkp��¥{|wv �rwfp" $�,t%�,{'�'�|p>��tkw%�S­ ��}Ë�L�s¦<�,}�{|wv�Lp���p-�|ps¦>�v��tkp��,�|�<�,�kr�{'tkp��,}��v{|¦>{' ��sp�¼)��{S ©p>tv�Lp>� � wv{Èr�}¦sr�}�}$���|�%¬I�¿­É�<���,}�¦spq�|psw´r��¥¡vp>�kw\¼���{S�*r�})�\Ü>�vtkp���¦s¦s�s���sw � ��p-tkps¦sr�����tv{'t\�|p��kp>�K �w\��p-�vtf�,}�wv§·p>tv�\�S­ ��}Ûr��¥¡vp>��<�*ps¦%�|p%�kp>�K �w¸�S­É��¦s¦s±swC��p\�¿­Êr��¥¡vp>�¸wk��{'���,}��<n��"{'}�wv{ � ��¦s¦s±sw � �vtf�,}�wV§®p>tv�kw¸p>�¸�vtf�,{'�kp>�Lp>})�kwC ©p>���*p>})�Cr� ��>tkp>tCp>}tkps¦sr�����tkp>�Lp>})�<n � pq�kp>�K �w%��pq¦<�,�|¦>��� tindex

wv��t\¦sp>�v�kpª�,tk¦k«�{'�kps¦>�v��tkpIw<­É�, � �tkrsµ¥{'�Lpª�,�|r�tkw´ $�,tªä

tindex = P × max

taccess

nobj × S/BPnobj × tdist

¶#"*½

�W}Ýtkp> �tkp>}$�,})�o�¿­Êp4µ�p>�K ��|p� �tk�s¦s�s��p>}�� � �|p��kp>�K �wª�S­Êp4µ��s¦>���v{|r�} �S­ ��}�p�tkps¦f«�p>tk¦k«�p ���v{'�'{|wf�,})�I�¿­ {'}���p4µ��,�v{|r�} �wv��t\¦sp>�v�kpª�,tk¦k«�{'�kps¦>�v��tkp � pswv�´tk�s�¥��{'�"¬ tindex �

¥n �gwkps¦sr�}���pn�cp>�v�kp-�, � �tkr�¦f«�p-w<­ {'}�wv �{'tkp���psw¸ �tkr,¡vp>�kwc~%z �Vy%$'& ���( �*) ÃLÂ�Á�+-,/.6Ú2Ç &10 ( �32 Ø4+5.!6�Ä7,/.6Ú2Ç &98�� ��(Sr���:<;*+»Ä>=!=?.A@�Ä�;*+,/.6Ú2Ç & B (gr��¯�|psw�tkpswkwfr���tk¦spswq��pI¦<�,�|¦>���¨wfr�})�q¦sr�}�}�ps¦>�k�spsw��,�. ��'��w- �tk±swq��pswq�¥{|wv ©rwv{'�v{�§·w-��powv�kr�¦k¹�,u*pn � ��¥{��S�>tkp>}�¦spI���¾¡Vp>��tkpªtk�swv{|��po���,}�w��6�L ©rwkwv{'��{'�'{'�k�o�S­É��¦s¦s�s��p>t-tf�, �{|��p>�Lp>})��p>�q�,�|�<�,�kr�{'tkp>�Lp>})�I¬L�¿­ {'}¥§®r�tv���¾��v{|r�} � ¦spC¼���{$�,���kr�tv{|wkpC��}�p\�,�'u*r�tv{'�v«��K{|¼)��p\��p<�,��¦sr��� K ��'��w¨wfr� �«�{|wv�v{|¼)���spC ©r���tg���,}�{' ����|p>t¨�¿­ {'}¥§®r�tv���,�v{|r�}Ènzq�,}�w"�kr���w"�|psw�¦<��w � �¿­ {|���spo�¥{'tkps¦>�vtv{|¦spIpswk�"��p�²��'�vtkp>tq�,�á ��'��w������"�¿­ {'}¥§®r�tv���,�v{|r�} � ��p����,}�{|±>tkpK¬�}�p�§¿�,{'tkptkp>�Lr�}��kp>t"¼���p-�|psw\��r�}�}��spsw\ ©p>tv�v{'}�p>})�kpsw"�*p>tkw´�¿­É�, � ��'{|¦<�,�v{|r�}Èn

� �bwkps¦>�v{|r�}:wv��{'��,})�kpI �tk�swkp>}��kpIu�|r��$�,�|p>�Lp>})���¿­É�,tk¦f«�{'�kps¦>�v��tkp���pI~%ps¢ �»£ �,{'}�wv{W¼���p��|pswq¦f«�r�{�µÞ�kps¦f«�}�r��|r,�u{|¼���psw´p��©ps¦>�v���sw�n � �owkps¦>�v{|r�}C"I���s¦>tv{'�´�¿­Êp>})��{'tkr�}�}�p>�Lp>})�"��p� �tkr�utf�,�K���,�v{|r�}.¬� $�,tv�v{'t\�S­ ��}KÀ4ÁvÂ�Ã�Ä4Å�Æ�Á2Çr�tv{|p>}��k�"�*p>tkwc�|pswC�, � ��'{|¦<�,�v{|r�}�w´�S­ {'}���p4µ��,�v{|r�}Èn � �Iwkps¦>�v{|r�} B {'}��¥{|¼)��p"�|pswc �tkp>�K{|p>tkw¸tk�swk���'�f�,�kwcr����kp>}���w´wv��t¦sp>�v�kp��,tk¦f«�{'�kps¦>�v��tkpn

144

Page 5: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

�©Í�� ����Ñ Ô�� Õ Ð�� Ô Ð � Ñ� � ���^Î��

~%ps¢ �»£ wfp� �tk�swkp>}��kp�wkr���w��6�˧®r�tv�Lpb�S­ ��} ¦>�'��wv�kp>to��p B }�°-����wK��p ¦<�,�|¦>���C¦sr��K���,}����swo $�,tI��}�pb���¾�¦k«�{'}�pK«����kp�¶Ö}�°-���᧷tkr�})�f�,� ½4n8�¸«$��¼���pI}�°-���¯��pI¦<�,�|¦>���¨pswk�"��} ã ��p>}�tv{|¦f«�{¨��pI��p>�¥µ.¦<�,tv�kpswoÃ4ÃLÆ . ÁkÄ2ÚÁvÄkØkÆ ;���@� �ÁvÂ���=|Ä2ÚK~%¢ �¨¢��K�S­ ��}�pb¦<�, $��¦>{'�k�b��p 0B m-rÛ¦f«$��¦>��}�pbp>���¥{|wk �rwf�,}��ª��p�tkpswkwkr���tk¦spsw�tkps¦sr�}¥²�u�¥�tf�,���|pswC¦sr�}�wk�s¼)��p>}��kpswc �r���t�p��Sps¦>�v��p>tC��psw��vtf�,{'�kp>�Lp>}��kwC¬��6�q�*r��|�sp�p>}bwkr�tv�v{|p"��p\�6���L�>�Lr�{'tkpn � p"wvº¥wv�k±>�Lp¦sr��K ��|p>�"�¥{|wv ©rwkpq��r�}�¦��S­ ��}�p��L�>�Lr�{'tkp���p � ��¨m-r���wfwkr�¦>{|�sp�¬o¼���p>�|¼���psw B � � L¦sp>�'�'���|psw%�|r�u{|¼)��psw<n

� �o�L�>�Lr�{'tkp��>�f�,}��%�¿­Ê�>�|�>�Lp>}��"¦sp>})�vtf�,�X��pq¦spq �tkr,¡Vp>� � }�r���w%���>�f�,{'�'�|r�}�w\���,{'})�kp>}$�,}��"�|psw\�Lr��v{'���,�v{|r�}�w"��psw¦k«�r�{�µË�kps¦f«�}�r��|r�u{|¼)��psw���p-�6�o�L�>�Lr�{'tkp��<���,}��"�S­É�,�©r�tk��p>t\�6�K��pswk¦>tv{' ��v{|r�}Û���>�f�,{'�'�|�spª��p-�6�K¦<�,tv�kp�~"¢ �¨¢ n

�©Í·Ì$Í�� � Ô�� ÒQÕ!� Ó�� �!�.Ð�� Ô�� ÏXÒ �ÖÒ*��Õ!� �:��� Ò�Õ Ñ�

� ­Êr��¥¡vps¦>�v{�§I��pÛ~"ps¢ �¤£ pswv�b��pÛ§®r���tv}�{'tb��}�pÞ�L�>�Lr�{'tkpÞ��pÞ�vtk±swbutf�,}���pÞ�f�,{'�'�|pá�¥{|wv ©rwf�,})���S­ ��}à�kp>�K �w�S­É��¦s¦s±sw��,�|�<�,�kr�{'tkp¸�|p¨ ��'��wȧ®�,{'���|p� �rwfwv{'���|pW $�,t8tf�, � ©r�tv��¬´��}ª�¥{|wk¼���pW���,u}��>�v{|¼���pn ã �,tv�K{��|psw8�kps¦k«�}�r��|r�u{|psw�L�>�Lr�{'tkpL�¥{|wv ©r�}�{'���|psw � }�r���w��s�*r�}�wqtkp>�kp>}��:�|psw��kps¦k«�}�r��|r�u{|pswª��pI~"�"¢iwv�f�,�v{|¼)��psw � �¥º�}$�,�K{|¼���psw � p>�-�|psw�kps¦k«�}�r��|r�u{|psw���pI�L�>�Lr�{'tkp � �6��wv«Èn � p��f�,���|p<�,�¯¦>{��¤�, �tk±sw-tk�swv���Lpª�|p>��tkw� �tv{'}�¦>{' $�,�|psw�¦<�,tf��¦>�k�>tv{|wv�v{|¼���pswqp>}� � 0 n � psw�¦<�,�|¦>���|w���pC}�r�����tkp"��p\¦sr��K ©rwf�,})�kw � ��p´¦sr�â�� � ��p´�$�,}���p´ $��wkw2�,})�kp\p>����p´¦sr�}�wfr��K���,�v{|r�}bwkr�}��§®�,{'�"wv��t´�6�I�$��wkp���p-�6�otk�<�,�'{|w2�,�v{|r�}Û�S­ ��}�pq�L�>�Lr�{'tkp 0B ��{'�kw"��p 0B m-r�n

����������� �!� "$#%� &'� (*)+� ,.-���/�, &'�$0�/1(32�(*� #!4.� ���5(3)�,7698 -$���;:<, =>-���6��?)�-$,.,@-$� /.� &'�$��,@�$(3(A-B/.#!� ���2��5��,.,@-$#!4.��, "$�%�$C�-��%�

D�E1FHG I�J$K$L M<J�N'O�L$LQP O ��, K$L L3G ��R�, O J$O$LTSD�UHEVFVG O�M<J W1M$M�OQP M<L ��, JAX ��RB, N$LYS

Z[�%- ,\��]_^ F ^ U `$W MaL$N LbP J OTc , M�` L3G ��R�, W�O�L ( SZ[�d-$,@��]e^Qf E W L g$` I�JhO$L$LQP M�L L ��, N J$L3G ��R�, O O�L ( S

� �K�kps¦f«�}�r��|r�u{|p y ~"�"¢ � wv{8p>�'�|p�r �©tkp-�|pq�kp>�K �w"�S­É��¦s¦s±sw\�|pq ��'��w"¦sr���tv� � wkr�� �©tkp��S­ ��}Û¦sr�â��\ $�,t\��}�{'�k�ª��pwv�kr�¦k¹�,u*pªp4µ¥�vtkÜ>�Lp>�Lp>})�-�>�|p>�*�nQ�"{'}�wv{ � �6�o�K{|wkp�p>}á°-����tkpª�S­ ��}�p��L�>�Lr�{'tkpI��p 0B mqrb¬K�$��wfp���p y ~"�"¢}��s¦spswkwv{'�kp>tf�,{'� 8 �i� K¦sr��K �rw2�,})�kw\ ©r���t\��}˦sr�â��%��p�tkp>��{|p>}��\ �tkr�«�{'��{'�v{�§���p-�¿­Êr�tk�¥tkp���p��� " �� � kj^p>�´��}�p¦sr�}�wkr��K���,�v{|r�}.�>�|ps¦>�vtv{|¼)��p�wk�� ��>tv{|p>��tkp�¬�� $3l n

� pswg�L�>�Lr�{'tkpsw¨z-~%��¢ar �©tkp>})�¨p>}otkp>���,}�¦f«�pC��}K¦sr�â��� $�,tg��}�{'�k�´��pcwv�kr�¦k¹�,u*p¸�©p<�,��¦sr��� K ��'��w¨�,�©r�tk���,���|pn�cp>�v�kp��,�L�>�'{|r�tf�,�v{|r�}Û��p��6�I��p>}�wv{'�k�-��p�wk�kr�¦f¹��,u*p-wkp%§®�,{'�´¦sp> ©p>}����,})�%�,�¥µ����> �p>}�w´��pswC�kp>�K �w´�S­É��¦s¦s±sw´¼���{wkr�})�%u*�>}��>tf�,�|p>�Lp>})�� ��'��w\{'�K ©r�tv�f�,})�kwª¶·��p��¿­Êr�tk�¥tkp���pq�6�o�¥{nm��,{'}�p���p-}$�,}�rwfps¦sr�}���psw2½4n

y {�¦sp>�v�kpª�kps¦k«�}�r��|r�u{|pKwfp>�����|pIÜ>�vtkp � ¬� �tv{|r�tv{ � ��}.¦k«�r�{�µÞ}$�,�v��tkp>�� ©r���t%{'�K ��6�,}��kp>tq��}�p��L�>�Lr�{'tkpo��pª�vtk±swutf�,}���p%�f�,{'�'�|p � ��}�p\�kp>�'�|p%�K{|wkp\p>}b°-����tkp\ ©rwkp\��p\}�r�����tkp>�¥µ� �tkr����|±>�Lpsw<n+o8r����c�S­É�,��r�tk� � ¦spsw¨�L�>�Lr�{'tkpsw �¼)��{Qwkp´ �tk�swkp>}��kp>})�Cp>}Lu*�>}��>tf�,�Qwkr���w¨�6��§·r�tv�Lp%��p\�Lr��¥���|psw�z � ¢á¢ ¶Ö{'})�k�>utf�,})�c��}�p\¦<�, $��¦>{'�k�"��p%wv�kr�¦k¹�,u*p��p��¿­Êr�tk�¥tkp"��p �-mqr)½ � wkr�}��´�¥{A��¦>{'�|pswC¬�{'})�k�>utkp>t\p>} utf�,}��b}�r�����tkpqwv��tc��} ¦>{'tk¦>��{'�c{'�K �tv{'�L�Kä*�|p"}�r�����tkp�vtk±sw\�>�|p>�*�q��p-��tkr�¦k«�psw\�S­Êp>}��vtk�spsw2�,wkr�tv�v{|psw"tkp>}����|p-tkr����f�,u*pq�S­É�,���f�,})�% ��'��w´�¥{A��¦>{'�|p�¼)��pq¦spsw´¦sr��K ©rwf�,})�kw§·r�}�¦>�v{|r�}�}�p>}���¬%��psw8§·tk�s¼)��p>}�¦spsw��vtk±sw��>�|p>�*�spswC¶ ¡V��wk¼��ȭɬ B � g¢qpYm¸ ©r���t8�|pswg¦sr��K ©rwf�,})�kw��|pswX ��'��wXtf�, �{|��psw4½4n

� �:��p>tv}�{|±>tkpá�,�'�kp>tv}$�,�v{'�*pËtkp> ©rwkpËwv��tK�¿­ ���v{'�'{|w2�,�v{|r�} ��p��L�>�Lr�{'tkpsw p>} �kps¦k«�}�r��|r�u{|p � �6��wv«Èn¸�cp>�'�|pswV�»¦>{"wkp�¥{'��{|wfp>})�´p>}���p>�¥µL§®�,�K{'�'�|psw-ä��|psw � �6��wk«¥� � � � z^p>�¸�|psw � �6��wv«¥� � ³�~�n y {Q�6���kps¦k«�}�r��|r�u{|p � �6��wk«¥� � ³�~ r �©tkp��}��kp>�K �w´�S­É��¦s¦s±swC�,�|�<�,�kr�{'tkp�§¿�,{'���|pK¶·��p%�¿­Êr�tk�¥tkp-��p��� � �}�w2½¸p>�c��} ��w2�,u*p% �tkr�¦k«�p-��p-¦sp>�'��{S��psw¸�L�>�Lr�{'tkpswy z-~%��¢ � wf�á��p>}�wv{'�k�Û�S­ {'})�k�>utf�,�v{|r�}àtkpswk�kp��'{'�K{'�k�sp ¶���ig¢Û�Q½4nc�cr��K�Lp� �r���tK�6�á�kps¦f«�}�r��|r�u{|p y ~"�"¢ ��¿­ {'})�k�>utf�,�v{|r�}.�S­ ��}�pq�L�>�Lr�{'tkp���p��vtk±sw´utf�,}���pq�f�,{'�'�|p�pswv�\�¥{A��¦>{'�|p>�Lp>}���p>}���{|w2�,u*p<�,���|pnr ìgí3sQíut,ì8æVôVé2ò¾ñ�v<w¾è»ó5x,öÉæ¨í3sQí�é2è_y

145

Page 6: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

� psw � �6��wv«¥� � � � zN �tk�swkp>})�kp>}�� � ¼��$�,})�b¬áp>�'�|psw � ��psw���p>}�wv{'�k�swK�S­ {'})�k�>utf�,�v{|r�} wv�� ©�>tv{|p>��tkpswL¬.¦sp>�'�|pswL��psw~"�"¢ �¥º�}$�,�K{|¼)��pswo¶·r�}Û�vtkr����*pop>} � � 0 ��psw�¦sr��K �rwf�,}��kw � �6��wk«¥� � � � z ��p "�¨m��.¦sr�})�vtkp �8m��Þ ©r���t�6� y z-~"�"¢¯½4n y {\�¿­Êr�} w<­ {'}��k�>tkpswkwkpÞ�,� ¦sr�â��� $�,t ��}�{'�k�Û��pÞwv�kr�¦f¹��,u*p � {'���, � $�,tf���|��¼)��pÛ�6�¯�kps¦f«�}�r��|r�u{|p� �6��wv«¥� � � � z pswv����pÞ�vtk±swL�|r�{'} �6�¯ ��'��w��s��,})�f�,u*p>��wfpn´�cpÞ¦sr�}�wv�f�,�bpswk�b¦sr�}¥²�tv�L�Þ $�,t��|pswb�kp>}����,}�¦spsw��po¦spswq��p>tv}�{|±>tkpswª�,}�}��spsw�¼)��{Wwv��uu*±>tkp>}���¼)��pI�¿­Ê�s¦<�,tv����po¦sr�â���p>}��vtkpK�kps¦k«�}�r��|r�u{|pbz�~"�"¢ip>� � �6��wk«á��¦sr�}��v{'})��p>t�¬Lw<­É��¦s¦>tkr �|�vtkp�p>}�§¿�s�*p>��t%��pq¦sp>�v�kp���p>tv}�{|±>tkpn

� �b �tv{'}�¦>{' $�,�|pL�¥{��S�>tkp>}�¦spKp>})�vtkpo�|psw � �6��wv«¥� � � � z p>���|psw��,���vtkpsw��kps¦k«�}�r��|r�u{|psw��L�>�Lr�{'tkpsw� �r�tv�kpowv��t-�|p�Lr���pª�S­É��¦s¦s±swª�,�¥µÞ��r�}�}��spsw<nSzq�,}�w��|pI¦<��wq��psw � �6��wv«¥� � � � z � ¦sp>�'��{��»¦>{¨wfp�§¿�,{'�-wkp>�|r�}.��}á�Lr���pI $�,u{'}���<�*ps¦Þ��}�pá�6�,�kp>}�¦sp¯��p.¦k«$�,tvu*p>�Lp>}��Û��pá $�,u*p.��p �

µw � wkr�{'�  �tk±sw���p �� � � §·r�{|w  ��'��w�¼���pÞ ©r���t ��}�p

�kps¦f«�}�r��|r�u{|p y z�~"�"¢ nS�cp>�v�kpo�6�,�kp>}�¦spK�S­É��¦s¦s±sw-tkpswv�kpI���,�'utk�ª�kr����-�vtk±sw-{'}¥§®�>tv{|p>��tkpL¬�¦sp>�'�|pK�S­ ��}¯�¥{|wk¼���p���,u}��>�v{|¼���p �  ���{|wk¼���pq�¿­Êr�}Þ�o¦sp>�v�kp-§®r�{|wV�»¦>{S��}�§¿��¦>�kp>��t �� � � Kp>}�§¿�s�*p>��t"��pq�6�I�L�>�Lr�{'tkp � �6��wv«Èn

� ��wfpÛ ©rwkpÞ���,�'utk�Þ�kr������6� ¼���pswv�v{|r�} ��pÛ�¿­ {'�K $��¦>�Ë��p.¦sp>�v�kpá�6�,�kp>}�¦sp¯�S­É��¦s¦s±sw�wv��t �|pswb ©p>tV§®r�tv���,}�¦spsw�S­ ��}�p �L�>�Lr�{'tkp��S­ {'}���p4µ tk�<�,�'{|wk�sp�¬Û�$��wfp ��p�¦sr��K ©rwf�,})�kw � �6��wk«¥� � � � zIn¨�cr��K�Lp�{'�C�¿­É�Þ�>�k� �Lr�}��vtk����,}�w´�¿­ {'}��vtkr��¥��¦>�v{|r�} � �|pq�kp>�K �w\�S­É��¦s¦s±sw��,�|�<�,�kr�{'tkp taccess

¡Vr���p-��}Ët����|p- �tk�s��r��K{'}$�,}������,}�w\�6�K�¥��tk�sp���p�vtf�,{'�kp>�Lp>}��"�S­ ��}�pqtkps¼���Ü>�kp����,}�w´��}�pq�$��wfpq{'}���p4µ¥�spn

y r�}¯{'�K $��¦>�� ©p>����¦sp> ©p>}����,})�ªÜ>�vtkpotk�s�¥��{'�ªwv{W�6��¼)�$�,}��v{'�k�L��pK��r�}�}��spsw��vtf�,}�wv§·�>tk�sp�¬�¦f«$��¼)��pb��¦s¦s±sw�pswv�wv�3��w2�,�K�Lp>})��{'�K ©r�tv�f�,})�kpÞ ©r���tb�,�v�k�>})��p>t �¿­Êp��©p>�b��p��6�¯�6�,�kp>}�¦spÞ�S­É��¦s¦s±sw<n¸��­Êpswv�b�|p˦<��w����,}�w��6�.�vtk±swutf�,}���p"���¾¡Vr�tv{'�k����pswC�, � ��'{|¦<�,�v{|r�}�wqä)�S­ ��}�p" $�,tv�¸�6���f�,{'�'�|p"�S­ ��}�r��¥¡vp>��}È­Êpswv�Cp>}�u*�>}��>tf�,�© $��w¸}��>u�'{'u*p<�,���|p¶·p>}��vtkp �� .p>� �� � .r�¦>�kp>�kw2½ � �S­É�,���vtkp� $�,tv�K��}à��¦s¦s±swL¬á�¿­ {'}���p4µ wv{'u}�{�²$p�wkr����*p>})����}à��¦s¦s±swL¬Û ��'��wk{|p>��tkwr��¥¡vp>�kw�¶Ö $�,tf�,�L±>�vtkp

nobj

½4n

� �Èpswv�\ $�,t-�,{'�'�|p>��tkw\ ©rwkwv{'���|p � ���,}�w"¦sp>tv�f�,{'}�psw"wv{'�v�$�,�v{|r�}�w � ��pqtkps¦sr�����tv{'t%�6�L �«$��wkp���p�¦f«$�,tvu*p>�Lp>})�q�S­ ��}�p $�,u*pK�s�*ps¦I�6�b �«$��wkpo��pI�vtf�,}�wV§®p>tv�-��psw-��r�}�}��spsw��S­ ��}�pK�,���vtkpI $�,u*p�ä � ­É�,tk¦k«�{'�kps¦>�v��tkp�{'})�kp>tv}�pK��psw-¦sr��o� ©rwf�,})�kw � �6��wv«¥� � � � z �,���kr�tv{|wkpª�|pq§®r�}�¦>�v{|r�}�}�p>�Lp>})��¦sr�}�¦>��tvtkp>})�q��p� ��'��wv{|p>��tkw-¦sr��K �rwf�,}��kw-¦sr�}�}�ps¦>�k�sw¬b��}¯�LÜ>�LpK����w<nÈ�cpotkps¦sr�����tkp>�Lp>})�ª}È­Êpswv��¦sp> �p>}����,}��� ©rwkwv{'���|pK¼���pª�|r�tkwf¼)��po�|psw- $�,u*psw���¦s¦s�s���spswªwv��¦4�¦spswkwk{'�*p>�Lp>})�%wkr�}��"�,�'�|r����spsw"¬o��psw"¦sr��K �rw2�,})�kw\�L�>�Lr�{'tkp��¥{|wv�v{'}�¦>�kw<n~"p> �tkp>}�r�}�w¸�¿­Êp4µ�p>�K ��|p���r�}�}������,}�w¸�¿­ {'})�vtkr��¥��¦>�v{|r�} � p>}�¦sr�}�wv{|���>tf�,})�\��p>�¥µ��kps¦f«�}�r��|r�u{|pswC�L�>�Lr�{'tkpsw � �¥{|wV� ©rwf�,})�X�S­ ��}�pW�LÜ>�Lp¨�$�,}���pW $��wfwf�,})�kp

BP = 500¢ár)�,w8���,{|wX¦<�,tf��¦>�k�>tv{|wk�spsw8 $�,tX��pswS�kp>�K �w8�S­É��¦s¦s±sw��¥{��©�4�

tkp>}��kwtaccess1 �

� �}�w � p>� taccess2 ��

µw<n �W}�wfpg�$��wf�,})�8wk��tS�¿­Ê�s¼)�$�,�v{|r�} " � r�}�r����v{|p>})� � tindex1 �

¥n gwkps¦sr�}���p ©r���t´�6�I�L�>�Lr�{'tkpª¬K��¦s¦s±sw%tf�, �{|��p�p>�

tindex1 � ¥n �Swfps¦sr�}���p� ©r���t´�6�o�L�>�Lr�{'tkp�¬K��¦s¦s±sw\�|p>}��<n

³"}K¦sr�}�wv�f�,�kp\�,{'}�wv{ � ¼���pc���,�'utk�C��}K�kp>�K �w¨�S­É��¦s¦s±sw �� � � "§®r�{|wgwv�� ��>tv{|p>��t�¬-¦sp>�'��{��S­ ��}�p´�L�>�Lr�{'tkp´��pC�¤º� ©py z-~%��¢ � �|pswq ©p>tV§®r�tv���,}�¦spsw�r����kp>})��pswI¬  $�,tv�v{'t��S­ ��}�pK�L�>�Lr�{'tkpL��po�»º� ©p � �6��wv«:wfr�})�q�vtk±swq�6�,tvu*p>�Lp>}��wv�� ©�>tv{|p>��tkpsw%¬K¦sp>�'�|pªr����kp>})��psw" �r���t´��}�p�tkps¦k«�p>tk¦k«�powv��t\�¥{|wf¼)��p��¥��t � p>�\tkpswv�kp>})�-��wkwkp�mq �tkr�¦k«�pª��p�¦sp>�'�|pswr����kp>}���psw�¬  $�,tv�v{'t��S­ ��}�pÛ�L�>�Lr�{'tkp y z-~%��¢Ýn � �"}�r���w wfp>�����|pá��r�}�¦Þ¼���pË�¿­ ���v{'�'{|wf�,�v{|r�} ��pÞ�L�>�Lr�{'tkp� �6��wv«¥� � � � z w�­É�s�*±>tkp���r�}�¦�Ü>�vtkp ��} ¦k«�r�{�µ  �p>tv�v{'}�p>}��L���,}�wo�|p�¦<���¥tkp���p�~%ps¢ �»£ nW�cp�¦f«�r�{�µ {'�K ©rwkp¦sp> ©p>}����,})�%��p>�¥µË¦sr�}��vtf�,{'})�kpswIä

x ��� �*� � Ð�Õ Ò�Ï Ó�� � � �ÖÒ Ô*� Ó ��� � Ô Ð � � � � ä��|pswo¦sr��K �rwf�,}��kw � �6��wv«¥� � � � z wkr�}��or�tvu)�,}�{|wf�swKp>}Ý���|r�¦sw¼���{�§®r�tv�Lp>})�c�¿­ ��}�{'�k���K{'}�{'���,�|p"�S­É��¦s¦s±sw´¬q�6���L�>�Lr�{'tkp-p>}b�s¦>tv{'�v��tkp�p>�cp>} p��S��¦sp>�Lp>}��<n � ���kps¦f«�}�r��|r�u{|p� �6��wv« }�pËu)�,tf�,}��v{'�� $��w��6� ���,�'{|�¥{'�k�á��pÞ�kr���w��|psw ���|r�¦swb���,}�w ��} ¦sr��K �rwf�,}��<n¸�_�v{'�vtkpÞ�S­Êp4µ�p>�K ��|p ���}�po�L�>�Lr�{'tkpK��p � ��g¢ár�w<­Êr�tvu)�,}�{|wkpKp>} B �� 0 ���|r�¦sw � �s�*ps¦K��}.���¾µ¥{'����� ��p i� b���|r�¦swq���4§·ps¦>�v��p>�¥µSn� �b �tk�swkp>}�¦spo��po¦spsw����|r�¦sw-���4§®ps¦>�v��p>�¥µ.r����'{'u*pK¬����v{'�'{|wkp>t-��}¯pswv $��¦spo�S­É���¥tkpswkwf�,u*pI�|r�u{|¼)��pop>}¯wv��w-��p�¿­É���¥tkpswkw2�,u*p- �«)º¥wv{|¼)��p � �¾²�}Ë��p� ©p>tv�Lp>�v�vtkp��S­ ���v{'�'{|wkp>t\¦sp>�v�kp-�L�>�Lr�{'tkpq¦sr��K�Lpq��}�pswv $��¦spq�S­É���¥tkpswfwf�,u*p�'{'}��<�,{'tkpª��p-���|r�¦sw´��,�'{|��psw<n

x ��� Ó � Ñ � �àÓ����8Õ � �·Õ � Õ Ð � � Ó�� �!� � ��� ÒQÕÖÑ�� ä��|pswor� ©�>tf�,�v{|r�}�wL�S­Êp��S��¦sp>�Lp>}�����p ���|r�¦swK�,�'�k±>tkp>}���|pLwk�� � �r�tv����p�wv�kr�¦f¹��,u*p���po�¿­ {'}¥§·r�tv���,�v{|r�}Èn�z-pL¦spI§®�,{'� � �|psw��L�>�Lr�{'tkpsw � �6��wv« }�pLwv�� � ©r�tv�kp>})�ª¼��È­ ��}

146

Page 7: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

CTRL#0

CTRL#0

Périphériquedédié ReMIX

Périphériquedédié ReMIX

Power PC405

Power PC405

PCIPCI

NOEUD

16Go FLASH(banc 0)

16Go FLASH(banc 0)

16Go FLASH(banc 1)

16Go FLASH(banc 1)

16Go FLASH(banc 2)

16Go FLASH(banc 2)

16Go FLASH(banc 3)

16Go FLASH(banc 3)

CTRL#1

CTRL#1

FPGA XC2VP30

CTRL#2

CTRL#2

CTRL#3

CTRL#3

128 MoDDR RAM

128 MoDDR RAM

FPGA XC3S1000

160 Mo/sec

160 Mo/sec

160 Mo/sec

160 Mo/sec

640 Mo/sec

5Mo/sec

4Gbx8

Contrôleur Mémoire #0Contrôleur Mémoire #0

4Gbx8

4Gbx8

4Gbx8

4Gbx8

4Gbx8

4Gbx8

4Gbx8

CS0

CS1

CS2

CS3

32b 20MHz

CS4

CS5

CS6

CS7

32b 20MHz

32b 40MHz

CTRL#0

CTRL#0

Périphériquedédié ReMIX

Périphériquedédié ReMIX

Power PC405

Power PC405

PCIPCI

NOEUD

16Go FLASH(banc 0)

16Go FLASH(banc 0)

16Go FLASH(banc 1)

16Go FLASH(banc 1)

16Go FLASH(banc 2)

16Go FLASH(banc 2)

16Go FLASH(banc 3)

16Go FLASH(banc 3)

CTRL#1

CTRL#1

FPGA XC2VP30

CTRL#2

CTRL#2

CTRL#3

CTRL#3

128 MoDDR RAM

128 MoDDR RAM

FPGA XC3S1000

160 Mo/sec

160 Mo/sec

160 Mo/sec

160 Mo/sec

640 Mo/sec

5Mo/sec

4Gbx8

Contrôleur Mémoire #0Contrôleur Mémoire #0

4Gbx8

4Gbx8

4Gbx8

4Gbx8

4Gbx8

4Gbx8

4Gbx8

CS0

CS1

CS2

CS3

32b 20MHz

CS4

CS5

CS6

CS7

32b 20MHz

32b 40MHz

������� � x �"tk¦k«�{'�kps¦>�v��tkpI�S­ ��}�p�¦<�,tv�kp�~%¢ �¨¢

}�r�����tkp¸�'{'�K{'�k�¨��p¨¦>º¥¦>�|psw8�S­Êp��È��¦sp>�Lp>})�� $�,tÈ���|r�¦%¶·p>})��{'tkr�}105¦>º�¦>�|psw2½4n ã ��wkwf�sp¨¦sp>�v�kp¨�'{'�K{'�kp � �¿­Ê�s¦>tv{'�v��tkp

¦sr�tvtkps¦>�kpC��pswg��r�}�}��spswX}È­Êpswk�X ��'��w�u)�,tf�,})�v{|pC���,}�w��|p¸���|r�¦n � ­É���Sps¦>�f�,�v{|r�}L��pswX��r�}�}��spswW���,}�w��6�%�L�>�Lr�{'tkp�|r�tkw¨��psw¸�s¦>tv{'�v��tkpsw�p>�2�,r��L�|r�tkw¨��psw¨�Lr��¥{�²$¦<�,�v{|r�}�wc��pC���|r�¦sw���r�{'����r�}�¦\Ü>�vtkp\wkr�{'u}�p>��wfp>�Lp>})�¸¦sr�}�wk{|���>tk�sp�¾²�}b��p%���¾µ�{'�K{|wfp>t��6���¥��tk�sp"��p\��{|p\��p\�6���L�>�Lr�{'tkpn � }�p´�kps¦f«�}�{|¼)��p���p��KÄvÂ�Á� =|Ä�6,Ä�=?. ; @b���>�k�\�K{|wkp"p>} ��6��¦spq���,}�w´¦sp"������¶Ö�*r�{'tc�6�Iwkps¦>�v{|r�}�¥n1"*½4n9oXr����kp4§·r�{|w � �|p"}�r�����tkp��'{'�K{'�k����p-¦>º¥¦>�|psw´�S­Êp��S��¦sp>�Lp>}��"�ª��}{'�K $��¦>�%}��>u�'{'u*p<�,���|pª���,}�w´�|p�¦<���¥tkp��S­ ���v{'�'{|w2�,�v{|r�}Þ��pq�6�I�L�>�Lr�{'tkpª~%ps¢ �»£I� ¦­Êpswv�%¬K�¥{'tkp�p>}��L�s�¥{6����pwv�kr�¦k¹�,u*p´�S­ {'}¥§·r�tv���,�v{|r�}Þä,p>}Lwk�� � �rwf�,}��W��}�pC�K{|wkp´¬¸¡Vr���tW¼���r��v{|�¥{|p>}�}�p\��pc�¿­Êp>}�wkp>�����|p%��pC�6���L�>�Lr�{'tkp~%ps¢ �¤£I� �|psw 105

¦>º¥¦>�|psw\�S­Êp��È��¦sp>�Lp>})�"}�p�wkp>tkr�})���,�v�kp>{'})�kw�¼)�È­É�,���©r����%��p 8 "L�,}�}��spsw�

�©Í �©Í ��Ñ Ô�� Õ Ð�� Ô Ð � Ñ�ÞÓ��C� � Ô ��ѾÐ�� � ���*�

� �o¦<�,tv�kp-~%¢ �¨¢_pswv�C�|p-¦s°-��t´�¥��wvº�wk�k±>�Lp�~"ps¢ �¤£ n y �I¦sr�}�¦sp> ��v{|r�}Þ�ªp>�  ©r���t´r��¥¡Vps¦>�v{�§g�S­É��wkwkr�¦>{|p>t´wv��t��}.�LÜ>�LpKwv�� � �r�tv�-��}�pI�L�>�Lr�{'tkpK��pIutf�,}���pI�f�,{'�'�|pKp>�-��psw�tkpswkwfr���tk¦spsw-tkps¦sr�}¥²�u��tf�,���|psw����v{'�'{|wk�spsw- ©r���ttk�<�,�'{|wkp>tc��}��vtf�,{'�kp>�Lp>})�´¬q�6���*r��|�sp%��psw¸��r�}�}��spswC�,�L§Ö��tcp>�c¬-�Lpswv��tkp"��p\�|p>��t¸�|ps¦>�v��tkpn � �q²�u��tkp �"���s¦>tv{'�wkr�} �,tk¦k«�{'�kps¦>�v��tkp��,�Ý}�{'�*p<�,� wvº¥wv�k±>�Lpn � �Û¦<�,tv�kp ~%¢ �¨¢ wkpL�$��wfp�wv��tª��}�pb¦<�,tv�kp ��p����>�*p>�|r� � ©p>�Lp>})� �r���t � ã m-� � ¬K�6��¼)��p>�'�|pq}�r���w"�s�*r�}�w"��wfwkr�¦>{|�-��}�p�¦<�,tv�kp��S­Êp4µ��kp>}�wk{|r�}Ë�L�>�Lr�{'tkp � �6��wv«¥� � � � zIn

� �I¦<�,tv�kp"��p����>�*p>�|r� � ©p>�Lp>})�\pswv�c�$��wk�sp�wv��t���}�p"{'})�kp>tV§¿��¦sp ã � � p>�C�¥{|wv �rwfp"�S­ ��} � ã m-� � {'tv�kp4µ�� �f� ã tkr ���wkwkr�¦>{|��¬ ���ig¢árI��p y z-~%��¢Ýn � p � {'tv�kp4µ�� �k� ã tkrop>�ª�$�,tk¼)��p��¿­Ê�s¼���{'���,�|p>}��\��p "� � � I¦sp>�'�'���|pswc�|r�u{|¼)��psw ���" 0 ���|r�¦sw´�L�>�Lr�{'tkp���p���i $ �Ûp>�"��p>�¥µ�¦s°-��tkw"��pq �tkr�¦spswfwkp>��tkw ã r � p>t ã � B ��¥n

� �ª¦<�,tv�kp\�L�>�Lr�{'tkp�pswv�¸¦sr��K ©rwk�sp 0B ��r �|�v{|p>tkw��L�>�Lr�{'tkp"��p �8m-r � ¦f«$��¼)��p"�©r �|�v{|p>t�{'})�k±>utkp���p>�¥µ�¦sr��K ©r,�wf�,})�kw � �6��wv«Ë¼)��{8 �p>���*p>}��%Ü>�vtkpq���v{'�'{|wk�sw\��p����,}�{|±>tkp�¦sr�}�¦>��tvtkp>})�kpnS�cp>�¥µ��»¦>{Xwkr�})�\tkp>utkr��� ©�sw%p>} B �$�,}�¦sw{'}����> �p>}����,}��kwo��p � 0 m-r � ¦k«$��¼���pL�$�,}�¦��>�f�,}��Ir�tvu)�,}�{|wf��p>}:��}�p����,�vtv{|¦spb��p 8 × 4

¦sr��K ©rwf�,}��kwª���,}�w�6��¼)��p>�'�|pqr�}� ©p>���\��¦s¦s�s��p>t"¬kiI¦sr��K �rwf�,}��kw%p>}� $�,tf�,�'�|±>�|pnQ�¸«$��¼���pq¦<�,tv�kp-�L�>�Lr�{'tkpq¦sr�})�v{|p>}��"�>u)�,�|p>�Lp>})���p>�¥µ�¦>{'tk¦>��{'�kw � ã m-� ���v{'�'{|wk�sw¨ ©r���t�{'�K ��|�>�Lp>}��kp>tC�|psw¸¦sr�}��vt����|p>��tkw´��psw ���i�¦sr��K ©rwf�,}��kw � �6��wv« � p>�� ©r���tu*�>tkp>t%�¿­ {'}��kp>tV§®��¦sp�p>}��vtkp�¦f«$��¦>��}Þ��psw B �$�,}�¦sw%�L�>�Lr�{'tkp�p>�\�|pq¦>{'tk¦>��{'� � {'tv�kp4µ�� �k� ã tkr���p-�6�K¦<�,tv�kp ã � � n

� p � {'tv�kp4µ�� �k� ã tkro{'})�k±>utkp-��}�p��,tk¦f«�{'�kps¦>�v��tkp���p-�»º� �p-wvº¥wv�k±>�Lp-wv��tC ���¦sp-¦sr�}�wv�vtv��{'�kp��,���kr���t\�¥�� �tkr�¦spswV�wkp>��t ã r � p>t ã �^p>�"�S­ ��}Þ����w��cr�tkp��cr�}�}�ps¦>�<n � p�wvº¥wv�k±>�Lpq{'}��k±>utkp� ��'��wk{|p>��tkw% ©�>tv{' �«��>tv{|¼)��pswo¶·¦sr�})�vt����|p>��t�L�>�Lr�{'tkp y z-~"�"¢ � z-¢Þ� � p>�k¦n ½\¦sr�}�}�ps¦>�k�sw��,�Þ����w"wkº�wv�k±>�Lp �  $�,tv�K{X�|ps¼���p>�8��}á¦sr�})�vt����|p>��tq���s�¥{|�ª�,�¥µ�s¦k«$�,}�u*pswI��pK��r�}�}��spsw�¶Ö�|ps¦>�v��tkpLp>���s¦>tv{'�v��tkp�½-p>}��vtkpK�6��¦<�,tv�kpK�L�>�Lr�{'tkp � �6��wv«:p>�q�6� �L�>�Lr�{'tkp y z�~"�"¢��pq�6�o¦<�,tv�kp ã � � n

147

Page 8: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

��� ��� x�y ¦f«��>���L��p- �tv{'}�¦>{' ©p��¥�Ë ©�>tv{' �«��>tv{|¼)��p����s�¥{|��~%ps¢ �»£

� p-t����|p���p�¦sp- ��>tv{' �«��>tv{|¼���p��S­ {'}��kp>tV§®��¦sp � ��r�})�\�¿­É�,tk¦f«�{'�kps¦>�v��tkpªpswk�´tkp> �tk�swkp>})�k�spªp>}�²�u��tkp � p>�%¼���{Èwkp>tf����swv{'u}��qwfr���w´�|pq�kp>tv�Lp���p- ©�>tv{' �«��>tv{|¼)��pª~%ps¢ �»£ ���,}�w´�6�Kwv��{'�kpq��p�¦sp>�%�,tv�v{|¦>�|p � pswv�\��r������|pLäx � �c��wkwk��tkpL�S­ ��}�p� $�,tv�I�6��u*pswk�v{|r�}Ý��pswIr� ��>tf�,�v{|r�}�wI��p��|ps¦>�v��tkpbp>�I�S­Ê�s¦>tv{'�v��tkp ��pswI��r�}�}��spswª��p��,wv��tI�6��L�>�Lr�{'tkp � �6��wk«Èn

x � �g{'})�k±>utkpK�S­É�,���vtkpo $�,tv�q��}.���|r�¦�Æ × 4ÁVÂ�+»Ä< �Á-���,�k�>tv{|p>�¨wv ©�s¦>{6�,�'{|wk�I ©r���t-¦f«$��¼)��pL�, � ��'{|¦<�,�v{|r�} � ��r�})�q�|pt����|p�pswk�\��pq�vtf�,{'�kp>t"¬I�6�o�*r��|�spq�|psw%��r�}�}��spsw\�'��psw%¬I $�,tv�v{'t���p-�6�o�L�>�Lr�{'tkp � �6��wv«Èn

� ­Êr� ©�>tf�,�kp>��t-tkps¦sr�}¥²�u��tf�,���|po �p>���"tkps¦sp>�*r�{'tqwv{'�����'�f�,}��>�Lp>}�� B ß��¥µÛ��pI��r�}�}��spswK¶ 4 × 32��{'�kw2½\p>}Þ �tkr,�

�*p>}$�,}�¦spª��psw B �$�,}�¦sw"��p��6�K�L�>�Lr�{'tkp � �6��wk«Ûp>�% �tkr��¥��{'��p>}Þtk�swv���'�f�,�%��}Ûß��¥µÛ��p���r�}�}��spsw�wv��t 0B ��{'�kw<n� �:wvº�}�¦f«�tkr�}�{|wf�,�v{|r�} � p>}àp>})�vtk�spá¦sr��K�LpÛp>}àwfr�tv�v{|p � pswv����wkwk��tk�spË $�,t���psw��L�>�Lr�{'tkpswb��p��¤º� ©p �g��� ³In��� � � b¦sp>�'�'���|psw��|r�u{|¼)��psw�p>� �� L���|r�¦sw��L�>�Lr�{'tkpI~%��¢ ��p ��i $ �Þwkr�}����¥{|wk �r�}�{'���|psw� ©r���t%{'�K ��|�>�Lp>})�kp>t�¿­Êr� ©�>tf�,�kp>��tqwv ��s¦>{6�,�'{|wf�I~"ps¢ �¤£ª� ��r�})�q�|p�§®r�}�¦>�v{|r�}�}�p>�Lp>})��pswv�q�¥{'tkps¦>�kp>�Lp>}���¦sr�})�vt����|�o $�,t-�|p ã r � p>t ã ��,���vtf�<�*p>tkw%�¥�Ë����w\wkº�wv�k±>�Lpnm�t � ¦spª¬o�¿­É��¦s¦s±sw%p>}Þ $�,tf�,�'�|±>�|pª¬o ��'��wv{|p>��tkw"¦sr��K �rw2�,})�kw � �6��wk« � �6�o�$�,}���p� $��wfwf�,})�kp��L�>�Lr�{'tkp�p>}Ûp>}��vtk�sp��p��¿­Êr� ��>tf�,�kp>��tKpswv�I��p 0B Þ¢Þr)�,w � wkr�{'�o��p>�¥µ r�tk�¥tkpswI��p�utf�,}���p>��tK��p� ��'��wI¼)��pb¦sp>�'�|pb�¥{|wk �r�}�{'���|p wv��t�¿­ {'}��kp>tV§®��¦sp ã � � ��p��6�Û¦<�,tv�kp�~"ps¢ �¤£ n � p�����w ã � � pswv�ª��r�}�¦b��}Ýu*r����|r��K�S­Ê�>�vtf�,}�u�|p>�Lp>}�� � ¼)��{¸�'{'�K{'�kp�¿­ {'}��k�>tkÜ>�ª�S­ ��}�pL���v{'�'{|w2�,�v{|r�}Ý�¥{'tkps¦>�kp���p�¦sp>�v�kpL�L�>�Lr�{'tkpL $�,t��¿­ «����kp �  ���{|wk¼���pK�¿­Êr�} �¥{|wv ©rwkp��,�|r�tkwª�S­ ��}�p�$�,}���p� $��wkw2�,})�kp��vtk±swotk�s�¥��{'�kp:¶Ö{'}¥§®�>tv{|p>��tkp� $�,to��} r�tk�¥tkp���pbutf�,}���p>��t ¬Þ¦sp>�'�|p��S­ ��} �¥{|wf¼)��p��¥��t2½ � ¦sp¼���{Ètk�s�¥��{'�"wfp>}�wv{'���|p>�Lp>})���|psw\u)�,{'}�w%�'{|�sw"�,�Û�kp>�K �w��S­É��¦s¦s±sw"�,�|�<�,�kr�{'tkp�§¿�,{'���|p���pq�6� � �6��wv« ¶Ö�kr���¡Vr���tkw% $�,ttf�, � ©r�tv�%¬o��}Ë�¥{|wk¼���p�½4n�W}¯ �tf�,�v{|¼���p � ¦spo�¤º� ©pK�S­Ê�s¦k«$�,}�u*pbpswv��p4µ¥¦>�'� ä©�|po �tv{'}�¦>{' ©pK��po§®r�}�¦>�v{|r�}�}�p>�Lp>})�I��pK~%ps¢ �»£ ¦sr�}�wv{|wv�kpL¬���v{'�'{|wkp>tX�¿­Êr� ��>tf�,�kp>��t����,�k�>tv{|p>�� �r���t8²��'�vtkp>tX�|pswX��r�}�}��spsw��¥{'tkps¦>�kp>�Lp>}��¨¬´�6�\wfr���tk¦sp�p>���,{'}�wk{)}�p¸�vtf�,}�wv�Lp>�v�vtkp¼���p-�¿­ {'}¥§·r�tv���,�v{|r�}á���v{'�|pn$zq�,}�w"¦sp�¦sr�})�kp4µ¥�kp � p>�%p>}áwv�� � ©rwf�,})�%¼���pq�|pq�f�,�¥µË��p-²��'�vtf�,u*pª��p��¿­Êr� ©�>tf�,�kp>��tpswv�Iwv�3��wf�,}�� � �6�Ë�$�,}���p� $��wkw2�,})�kp ���>�'{'��tk�spb $�,tª�¿­ {'}��kp>tV§®��¦sp ã � � pswk�ªwv�3��wf�,}��kpn¨³"}  ©p>���ªtk�swv���Lp>tI�|p���>tkr����|p>�Lp>}��¸�S­ ��}L�vtf�,{'�kp>�Lp>}��cwv��t¨¦sp>�v�kp"�,tk¦k«�{'�kps¦>�v��tkp � ¦­Êpswv�V�¤¬q�¥{'tkp´�6�-tkps¦f«�p>tk¦k«�p�p>�W�|p´�vtf�,{'�kp>�Lp>})�c�S­ ��}r��¥¡vp>�\���,}�w´�6�o�$��wkpq�S­ {'}���p4µ � ¦sr��K�Lpªwv��{'��ä

�n � }.r��Þ ��'��wk{|p>��tkwqr�tk�¥tkpsw���pI�|ps¦>�v��tkpowkr�}��-p>}��*r<º*�sw���p> ���{|w��¿­ «����kp�¶Ö��{6���|pª �tkr�¦spswkwkp>��t ã r � p>t ã �´½

148

Page 9: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

�,�¥µ�¦sr�})�vt����|p>��tkw � �6��wv«� $�,t\�|pq ©�>tv{' �«��>tv{|¼���p��S­ {'})�kp>tV§¿��¦sp�~"ps¢ �¤£ n¥n � ­Êr� ��>tf�,�kp>��tq~%ps¢ �¤£ pswk�% $�,tf�,�L�>�vtk�I $�,t%�¿­ «����kp�¶Ö�kr���¡Vr���tkw���{6�K�|p ã r � p>t ã �´½qp>}Û����p��¥�á�vtf�,{'�kp4��Lp>}��%��psw\��r�}�}��spsw"¼)��{8wfp>tkr�})�\�'��psw%¬I $�,tv�v{'t���p-�6�o�L�>�Lr�{'tkp � �6��wv«Èn

"¥n � psw\��r�}�}��spsw%�'��psw � �¥{|wv �r�}�{'���|psw"���,}�w´�|psw �g��� ³�w%¬o�¿­Êp>}��vtk�sp���p-�¿­Êr� ©�>tf�,�kp>��t � wkr�}��"�,�|r�tkw´²��'�vtk�spsw�¬�6�I�*r��|�sp� $�,t%¦spq��p>tv}�{|p>t � ¼���{Su*�>}�±>tkpq��}�ß��¥µ���pqtk�swv���'�f�,�kw<n

B n"�cpKß��¥µátk�swv���'�f�,�ªpswv���vtf�,}�wV§®�>tk�K�*p>tkwq�6���L�>�Lr�{'tkp y z-~%��¢i $�,t��¿­ ���v{'�'{|w2�,�v{|r�} �S­ ��}Ýz-¢á� �  ©r���tÜ>�vtkpq²�}$�,�|p>�Lp>})�"p>}��*r<º*�I¬o�¿­ «����kpq $�,t\�¿­ {'}��kp>tV§®��¦sp ã � � n

�¥n � }�po§®r�{|w��|pK�vtf�,{'�kp>�Lp>}��o�kp>tv�K{'}�� � �¿­Êr� ©�>tf�,�kp>��tªwv{'u}$�,�|p��6��²�} ��pswI¦<�,�|¦>���|wª�,� ã r � p>t ã �  $�,tª��}wk{'u}$�,�È�S­ {'})�kp>tvtv�� ��v{|r�}Èn

�©Í��SÍbÎ>Ï�Ð � �$Ñ�¥Ð�ÕÖÒQÏ ���È� Ð�� � �ÛÓ�� � � Ô ��ѾÐ�� � � �Y�

�\²�}Ë�S­Êr �©tv{'t´��}�pq�,��wv�vtf��¦>�v{|r�}Û�¥� §®r�}�¦>�v{|r�}�}�p>�Lp>})�"��p��6�o¦<�,tv�kpq~"¢ �¨¢ �,�¥µ ¦sr���¦k«�psw%�|r�u{|¦>{|p>�'�|psw\wv�� ©�4�tv{|p>��tkpsw � �|p ã r � p>t ã � {'})�k±>utkpq��}Þwvº�wk�k±>�Lpq�S­Êp4µ� ��|r�{'�f�,�v{|r�}Þtk�s�¥��{'�%¼)��{Èr �©tkp���psw\wfp>tv��{|¦spsw\�S­É��¦s¦s±swªä

x ¬%�6�´�L�>�Lr�{'tkp � �6��wv«ª $�,t���psw� �tv{'�K{'�v{'�*psw��S­É��¦s¦s±sw��|r�u{|¼���psw´¶Ö�|ps¦>�v��tkpc�S­ ��}�p¸ $�,u*pc���,}�wX��}I���|r�¦¨�|r�u{|¼���p ��s¦>tv{'�v��tkp��¾�Lr��¥{�²$¦<�,�v{|r�}Q�,p��S��¦sp>�Lp>}����S­ ��}����|r�¦��|r�u{|¼)��p�½4n

x ¬ª�¿­Êr� ��>tf�,�kp>��t´tkps¦sr�}¥²�u��tf�,���|p�~%ps¢ �»£  $�,t´��pswC �tv{'�K{'�v{'�*psw´ ©p>tv�Lp>�v�f�,})�\��p� $�,tf�,�L�>�vtkp>t%p>�´��p-wv�� ©p>tV���{|wkp>t´�|p-§®r�}�¦>�v{|r�}�}�p>�Lp>})�"��p��¿­Êr� ��>tf�,�kp>��t<n

� �©��wkwv��tkp"��pC§®�,{'�¸�6�qu*pswv�v{|r�} ��psw����|r�¦swc���4§·ps¦>�v��p>�¥µ���pswc¦sr��K �rw2�,})�kw � �6��wk«bp>}����,{'}��kp>}$�,})�\p>}b�L�>�Lr�{'tkp��}�pI�f�,���|pI��pª�vtf�,}�wv�6�,�v{|r�}:�S­É���¥tkpswkwfpsw" ©p>tv�Lp>�v�f�,})����pª§¿�,{'tkp��|pª�'{|p>}¯p>})�vtkpI��}.})���L�>tkr���pª���|r�¦ª�|r�u{|¼���p¶®��wkwkr�¦>{|�Þ¬:��}�pÞ���¥tkpswkwkpÛ�|r�u{|¼)��pá���,}�wb�6�¯�L�>�Lr�{'tkpá~%ps¢ �»£ ½op>����} })���L�>tkr ��pË���|r�¦Ë �«�º�wk{|¼)��pÞwv��t��} ¶·r��  ��'��wv{|p>��tkw2½I¦sr��K ©rwf�,}��kw � �6��wv«8n ã �,t �,{'�'�|p>��tkw � �|p�wvº¥wv�k±>�Lp �Lp>�Lp>} °-����tkp���}�p��kps¦f«�}�{|¼)��pÞ��p�oÄkÂ�Á � ='Ä>6,Ä�=?.!; @:��pª �tkp>�K{|p>t-}�{'�*p<�,�:���,}�w��|pI�����q��pª�K{'}�{'�K{|wfp>t��|pI}�r��ª��tkpK�S­Êr� ��>tf�,�v{|r�}�w��S­Êp��È��¦sp>�Lp>})��|r�tkw%��pq�¿­Ê�s¦>tv{'�v��tkpªr����6�o�Lr��¥{�²$¦<�,�v{|r�}Þ��pq���|r�¦sw´�|r�u{|¼���psw<nQ�cp>�v�kpq�kps¦f«�}�{|¼)��p�tkp> �rwkpqwk��t\��}�p��,�'�|r�¦<�,�v{|r�}¦>{'tk¦>���6�,{'tkp���psw´���|r�¦sw´ �«�º�wv{|¼���psw\�'{'��tkpsw � �6��wk« & ��"�(»n

� psw ¦<�,tv�kpswb~"¢ �¨¢ wkr�}���{'}��k�>utk�spsw��,� wvº�wk�k±>�LpËwkr���wL�6�¯§·r�tv�LpÞ�S­ ��}à ©�>tv{' �«��>tv{|¼)��p ã � � n � pÛ �{'�|r��kpã � � {'})�kp>tf�,u{'���¥{'tkps¦>�kp>�Lp>})�Ë�<�*ps¦Û�6�¯¦sr���¦f«�pÞwkº�wv�k±>�LpË�K{|wkpÛp>}à°-����tkpÛwk��tL�|p ã r � p>t ã � � p>�K§®r���tv}�{'���}�pI{'})�kp>tV§¿��¦spI�S­É��¦s¦s±sw��,�.wvº¥wv�k±>�Lp���pªu*pswv�v{|r�}¯��p�²$¦k«�{|p>tkwL¶Ö�*r�{'t- $�,tf�,utf�, �«�powv��{'���,}��2½% �r���t��|pswq��¦s¦s±sw�L�>�Lr�{'tkp � p>�L�,�¯À4ÁVÂ�Ã�Ä4Å�ÆÁfÇ ¶Ö�*r�{'tK�6�.wkps¦>�v{|r�} wv��{'��,})�kp�½I ©r���tK�|p�¦sr�})�vt����|pÛp>�K�6�Þtkps¦sr�}¥²�u��tf�,�v{|r�} ��p�¿­Êr� ��>tf�,�kp>��t<n

� }Þwvº�wk�k±>�Lp���pq²$¦f«�{|p>tkw"wv ©�s¦>{�²$¼���p�¬K~%ps¢ �¤£ �o $�,t-�,{'�'�|p>��tkw"�>�k�����>�*p>�|r� � ��n©�cp>�'��{��»¦>{Xu*±>tkp��,���kr����,�v{��¼)��p>�Lp>}��"�¿­É�,�'�|r�¦<�,�v{|r�}Þ��psw"��r�}�}��spsw"wk��t\�|psw%�¥{��S�>tkp>})�kw"�$�,}�¦sw%�L�>�Lr�{'tkp � �6��wv«Èn � p������"pswv�%�S­Êr� ��v{'�K{|wfp>t�|p>��t-�f�,�¥µá�S­Êr�¦s¦>�� $�,�v{|r�}:p>�-�,{'}�wv{g���¾µ¥{'�K{|wkp>t��¿­ ��wf�,u*po��pª�6���L�>�Lr�{'tkpou�|r��$�,�|pnÈ�¸«$��¼)��po¦<�,tv�kpo~%¢ �¨¢�¥{|wv ©rwkpq��p�wkr�}� �tkr� �tkp�wkº�wv�k±>�Lpq��pq²$¦k«�{|p>tkw<n�cp>��p>}�wkp>�ª���|pL��pI§·r�}�¦>�v{|r�}�}$�,�'{'�k�swªwvº¥wv�k±>�Lpopswv��p4µ� ��|r�{'�k�o $�,tq��}:p>}���{'tkr�}�}�p>�Lp>}��ª��po �tkr�utf�,�K���,�v{|r�}¶ À2ÁvÂ�Ã�Ä4Å�Æ�Á2Ç¥½c��p�«$�,���´}�{'�*p<�,�˼���{� ©p>tv�Lp>�´��p�u*�>tkp>t\��p"���,}�{|±>tkpqwk{'�K ��'{�²$�sp-�6�ª�¥{|wk�vtv{'�����v{|r�}Ë��pswC�vtf�,{'�kp4��Lp>})�kw � p>�q�6��tk�> $�,tv�v{'�v{|r�}Ý��pswq�$��wkpswq�S­ {'}���p4µ¯wv��t-�|psw��¥{��©�>tkp>}��kwq}�°-����w�~"ps¢ �¤£ n � ��wkps¦>�v{|r�}:wk��{'���,}��kp �tk�swkp>})�kpª¦sp>�%p>})��{'tkr�}�}�p>�Lp>})�-��p- �tkr�utf�,�K���,�v{|r�}Èn

�SÍ�� ����Ï �8ÕÖѾÒ�ÏXÏ�� � ��Ï�ÐLÓ����Ñ¾Ò �$Ñ� � � �¥Ð�ÕÖÒ�Ï

� ­Êp>})��{'tkr�}�}�p>�Lp>})�I��p� �tkr�utf�,�K���,�v{|r�}Ý~%ps¢ �»£ pswv�� �tkr� ©rwk�ª���,}�w��|pª�����q��pªwv{'�K ��'{�²$p>t-�|po���>�*p>�|r� � ©p4��Lp>})���S­É�,�'u*r�tv{'�v«��Lpsw���p�tkps¦k«�p>tk¦k«�pË $�,towk{'�K{'�6�,tv{'�k�����,}�wK��pswo����wkwkpswK��p���r�}�}��spswK{'}���p4µ��spsw<n � �´�á�>�k�¦sr�}��>�á�<�*ps¦���p>�¥µ {'�K ©�>tf�,�v{�§®w\���¾¡vp>��tkw�ä�wv{'�K ��'{|¦>{'�k��p>�´tk�>���v{'�'{|w2�,��{'�'{'�k�n

149

Page 10: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

requete

résultat

sous−requetes

sous−requetes

sous−requetes résultats partiels

résultats partiels

résultats partiels

Noeud frontal ReMIX

Noeud de calcul

Noeud de calcul

Noeud de calcul

������������������������

������������������������

������������������������

������������������������

������� " x ã tv{'}�¦>{' ©p��¥�Ë�Lr���±>�|p�¦>�'{|p>})�2�,wfp>tv�*p>��t"�¥�Ûwvº¥wv�k±>�Lpq~"ps¢ �¤£

� �\wv{'�K ��'{|¦>{'�k����p¸¦sr�}�¦sp> ��v{|r�}ª���s¦sr����|pc��pW�¿­ ���v{'�'{|wf�,�v{|r�}ª�S­ ��}ª�Lr���±>�|p¸�S­Êp4µ¥�s¦>���v{|r�}I��pW�»º� ©p�¦>�'{|p>})�2�,wfp>tv�*p>��t��pátkps¼���Ü>�kpsw��¥{|wv�vtv{'�����nCz-�,}�w�¦spá�Lr���±>�|p � �6� �¥{|wv�vtv{'�����v{|r�}A��psw���r�}�}��spsw�pswv��p4µ� ��'{|¦>{'�kp.p>��wv�f�,�v{|¼���p�¿­Êp4µ��s¦>���v{|r�} � �|pswL¦sr��K�ª��}�{|¦<�,�v{|r�}�w�p>�L�|pswLwvº�}�¦k«�tkr�}�{|w2�,�v{|r�}�w wfr�})�L{'�K ��'{|¦>{'�kp>�Lp>}�� u*�>tk�spsw�n � ­Êp>}�wkp>�ª���|pw<­ {'}�wf¦>tv{'�\���,}�w´��}LÀ4ÁVÂ�Ã�Ä4Å�ÆÁfÇK¶·¦<���¥tkp���p�¦sr�}�¦sp> ��v{|r�}Q½4n

� �ªtk�>���v{'�'{|wf�,��{'�'{'�k����p"�¿­Êp>}���{'tkr�}�}�p>�Lp>}��"��p� �tkr�utf�,�K���,�v{|r�}Ûw<­ {'}�wf¦>tv{'�%¬ª��p>�¥µ }�{'�*p<�,�¥µáä��|r�u{|¦>{|p>�Èp>�C���¾��k�>tv{|p>�¿n�zo­ ��}�pb $�,tv� � �¿­Êp>}���{'tkr�}�}�p>�Lp>}��L}È­Êpswv�I $��wª�'{|��¬Û��} ��r����,{'}�p��S­É�, � ��'{|¦<�,�v{|r�}�wLp>� � �S­É�,���vtkp  $�,tv� ��¿­Êp>}���{'tkr�}�}�p>�Lp>}��I}�pb���> �p>}��  $��w��S­ ��}�p� ��6�,�kp4§·r�tv�Lp �S­Êp4µ¥�s¦>���v{|r�}  $�,tv�v{|¦>���'{|±>tkp�wf��¦sr�}¥²�u��tf�,�v{|r�} pswv� �tk�s¦>{|wk�sp"p4µ� ��'{|¦>{'�kp>�Lp>}��c���,}�w¸��}K²$¦f«�{|p>t<n � ��§¿�,���¸wv ©�s¦>{�²$p>t��|p´}�r��ª��tkp"��p%}�°-����w � �6�q}$�,�v��tkp"��p´�6�� ��6�,�kp4�§®r�tv�LpK¶·¦>�'��wv�kp>t´��p ã � � �����'�v{' �tkr�¦spswkwkp>��t\r���wv�f�,�v{|r�}Ë��p��vtf�s��,{'�S��}�{|¼)��p�½ � �|p-wv�� � ©r�tv�´��p"�L�>�Lr�tv{|w2�,�v{|r�}¶Ö�L�>�Lr�{'tkp"~%��¢ �� �6��wv« r����¥{|wk¼���p\�¥��t2½Wp>�¨�|p%wv�� � �r�tv�c�S­Êp4µ¥�s¦>���v{|r�} ��psw�r� ©�>tf�,�kp>��tkw¸��p"¦<�,�|¦>����¶ � ã m-� �¦>{'tk¦>��{'�kwI���s�¥{|�swor��Ý�v«�tkp<���$½4nW³"���vtkp�wf��u*�>}��>tv{|¦>{'�k� � ¦sp>�v�kp��, � �tkr�¦f«�p� ©p>tv�Lp>�ª��}�pb�K{|wkp��,�  ©r�{'})�I �tkr,�utkpswkwk{'�*pª��psw-�, � ��'{|¦<�,�v{|r�}�w<n8³"}á �p>���-���>�����kp>t- $�,t���psw��kpswv�kw�wv��t���}�pªwv�f�,�v{|r�}¯��pª�vtf�s��,{'�X��}�{|¼���p �  ���{|w $��wkwfp>t% �tkr�utkpswkwv{'�*p>�Lp>}���¬L�¿­Ê�s¦f«�p>�'�|pIwk��t%��}Þwkº�wv�k±>�Lp� $�,tf�,�'�|±>�|p�¶Öutf�, � �pI��p ã �´½\p>�"�kp>tv�K{'}�p>t� $�,t"��}�p�K{|wkp%p>}�°-����tkp\���,�k�>tv{|p>�'�|p"��psw¸r� ��>tf�,�kp>��tkwcwv��t¨�|p\wkº�wv�k±>�Lp´~"ps¢ �¤£ n��¸«$��¼)��p"�>�f�, �p\pswk�¨��}�tf���L}�p>�Lp>}����p-�6�o �tk�s¦s�s��p>}��kpn

� ��§¿�,���¸¦sp> ©p>}����,})�C}�r��kp>tC¼)��p"�6��¦sr�}�¦sp> ��v{|r�}Û�,���kr����,�v{|¼���p"��pswCr� ©�>tf�,�kp>��tkwCwv��t��6�ªwv�vtv��¦>�v��tkp"tkps¦sr�}¥²�u�¥�tf�,���|p"��p"~"ps¢ �¤£ }È­Êpswv�� $��w¸ �tv{|wkp�p>}b¦k«$�,tvu*poä)��}�p%{'}��kp>tV§®��¦sp�wvº¥wv�k±>�Lp"��wkwk��tkp%wv{'�K ��|p>�Lp>}��c�|pswC�s¦f«$�,}�u*pswp>}��vtkpq�|p- �tkr�¦spswfwkp>��t\�S­ ��}�}�°-���Ë��pq¦<�,�|¦>���Èp>�´�¿­Êr� ©�>tf�,�kp>��t%��pq�6�o¦<�,tv�kpq~%¢ �¨¢ n � ­Êr� ©�>tf�,�kp>��t%��r�{'�\Ü>�vtkp¦sr�}��>�Ë{'}����> ©p>}����,�K�Lp>})�<n

� pªtkpswv�kpI��pª¦sp>�v�kpowkps¦>�v{|r�}.���s¦>tv{'�qwv��¦s¦>{'}�¦>�kp>�Lp>})�q�¿­ {'�K ��6�,}��f�,�v{|r�}Ý��¦>�v��p>�'�|po¼)��{gw<­É�, � ���{|powv��t"��}á�Lr���p��p�§®r�}�¦>�v{|r�}�}�p>�Lp>})�-��p-�»º� �p�¦>�'{|p>})�2�,wkp>tv�*p>��t���pqtkps¼)��Ü>�kpsw%p>�%wv��t´�¿­Êp>})��{'tkr�}�}�p>�Lp>})���)�<���¥n

�ÈÍÖÌQÍ� � � ÒSÓ � � � Ô �·Õ ��Ï�Ð� � �)Ñ � � � Ñ Ó��ÛÑ��� ��� Ð�� �

� ��²�u��tkp "Iwk¦k«��>���,�v{|wfp-�|p"�Lr���±>�|p-��p"§·r�}�¦>�v{|r�}�}�p>�Lp>}��<n�³"}�wv�� � ©rwkp"¼���p��|psw´r��¥¡Vp>�kwCwkr�}��´tk�> $�,tv�v{|w´wv��t¦f«$��¼)��p-}�°-���Ë��pq¦<�,�|¦>���Xp>�\¼)��p-wkp>���S�|p-}�°-����§·tkr�})�f�,�8¬o¦sr�}�}$�,{|wfwf�,}�¦sp���p-�6�Itk�> $�,tv�v{'�v{|r�}Èn �¨}Ë�S­É�,���vtkpsw�kp>tv�Lpsw � {'�8 �rwkwf±s��p-�¿­ {'}���p4µ� ©p>tv�Lp>�v�f�,})����p-tkp>�vtkr����*p>t%�¿­Êp>}�wkp>�ª���|p���psw\r��¥¡vp>�kw<n

150

Page 11: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

o8r����kpªtkps¼)��Ü>�kpªwkr����K{|wkpI�,�Û}�°-����§·tkr�})�f�,��pswv�%���s¦sr��� ©�spªp>}Þwkr���wV�¿tkps¼���Ü>�kpsw<n��¸«$��¼���p�wkr���wv�¿tkps¼)��Ü>�kpªpswv�p>}�wv��{'�kp\�,{'u��{'�'�|�spC�*p>tkwg��}L��psw�}�°-����w¨��pC¦<�,�|¦>���¿n)�cpswW��p>tv}�{|p>tkwW�vtf�,{'�kp>})�¨��pc���,}�{|±>tkp´{'}����> ©p>}����,})�kp\�|p>��tkwwkr���wV�¿tkps¼���Ü>�kpsw<n��W}Ûtk±>u�|pqu*�>}��>tf�,�|p � �¿­Êr� ©�>tf�,�v{|r�}Þ¦sr�}�wv{|wk�kpqp>}Ë��}˦<�,�|¦>���X��pq�¥{|wv�f�,}�¦spn��¸«$��¼)��pq}�°-���Þ��p¦<�,�|¦>���Wtkp>})�*r�{|pKwkpsw�tk�swv���'�f�,�kw-�*p>tkw-�|pI}�°-���Þ§·tkr�})�f�,�¨¼���{X�|psw�§·��wv{|r�}�}�pop>�q���>�'{'��tkpop>}.tkp>�kr���t-�|pªtk�swk���'�f�,�²�}$�,�¿n � p�§·r�}�¦>�v{|r�}�}�p>�Lp>}�����p �¿­Êp>}�wkp>�����|p�pswv�K��wvº�}�¦k«�tkr�}�p�p>� � p>} tk�>u{'�Lp ��p�¦>tkr�{|wv{|±>tkp � ��pb�����'�v{' ��|pswtkps¼)��Ü>�kpsw% �p>���*p>}��"Ü>�vtkp-�vtf�,{'�k�spsw"wv{'�����'�f�,}��>�Lp>}��<n

�SÍ �©Í�� � � Ñ�� � ���IÒ$Ñ��

� p�¦f«�r�{�µ��S­ ��}��Lr���pq��p�§·r�}�¦>�v{|r�}�}�p>�Lp>}��"��}�{|¼���p��sº)�,}��%�>�k�-tkp>�kp>})� � ��}KÀ2ÁvÂ�Ã�Ä4Å�Æ�Á2Ç"¦sr�}��kp>}$�,})�%�kr����kpsw�|psw §·r�}�¦>�v{|r�}�}$�,�'{'�k�sw�¦sr��K�ª��}�pswÛ¬Ý�kr����kpsw��|psw��, � ��'{|¦<�,�v{|r�}�w�w<­Êpswv� {'�K �rwk�n � ­Êp>}�wfp>�����|p:� �>�k�Ûtk�<�,�'{|wf�wkp>�|r�} ��}�p��, � �tkr�¦f«�p r�tv{|p>}��k�sp�r��¥¡Vp>�o���,}�wo�¿­Êp>})��{'tkr�}�}�p>�Lp>})�b��p� �tkr�utf�,�K���,�v{|r�}àwk�f�,}����,tk� ���s��¥n � pÀ2ÁvÂ�Ã�Ä4Å�Æ�Á2Ç\¦sr�})�v{|p>}��C��r�}�¦"��p>�¥µL�»º� �psw¸��p%¦>�6��wkwfpsw%ä)¦sp>�'�|pswc¼���{�tkp>�|±>�*p>})�´�¥�L§®r�}�¦>�v{|r�}�}�p>�Lp>})�Cu*�>}��>tf�,�©�¥��Lr���±>�|pI�S­Êp4µ��s¦>���v{|r�}Þ�K{|w"p>}Û ��6��¦spIp>�"¦sp>�'�|psw�¼)��{8wfr�})�"wk ��s¦>{�²$¼���psw�¬L�¿­É�, � ��'{|¦<�,�v{|r�}Èn ã �,tv�K{W¦spsw%¦>�6��wkwfpsw ��|pq �tkr�utf�,�K�Lp>��t"��r�{'� �  $�,t%p4µ¥p>�K ��|p � wv ��s¦>{�²$p>tªä

x �6�K��pswk¦>tv{' ��v{|r�}Þ��psw\p>})�vtk�spsw���p-�¿­ {'}���p4µ x �6�otk�> $�,tv�v{'�v{|r�}á��psw\r��¥¡Vp>�kw x �6�o���,}�{|±>tkp���p����s¦sr��� �p>t\��}�p�tkps¼)��Ü>�kpqp>}Ûwfr���w´tkps¼)��Ü>�kpsw x �|pq�vtf�,{'�kp>�Lp>}��"�S­ ��}�p�wkr���wv�¿tkps¼)��Ü>�kpx �|pq ©rwv�C�vtf�,{'�kp>�Lp>})�q¬I�¿­ {|wkwv�Ë��pq�6�Itk�s¦sp> ��v{|r�}á�¥�Ëtk�swv���'�f�,�%��psw%wkr���w´tkps¼���Ü>�kpsw

� pª�vtf�,{'�kp>�Lp>})�q�S­ ��}�p�wkr���w%tkps¼)��Ü>�kpIpswv�\tkp>�6�,�v{�§C¬o�¿­Êr� ��>tf�,�kp>��t-¼���{X��r�{'�"Ü>�vtkp�{'�K ��6�,})�k�o���,}�w"�|p � ã m-�Iny ����pswf¦>tv{' ��v{|r�} wkr���w¸�6�-§®r�tv�Lp��S­ ��}�p%�L�>�v«�r���p ���s��� ©p>tv�Lp>�c��p%�kpswv�kp>tc�¿­É�, � ��'{|¦<�,�v{|r�}����,}�w¸��}�p>})��{'tkr�}¥�}�p>�Lp>})�qwv�f�,}����,tk�.�s��,})�q�S­Êp>}.¦sr�}�¦sp>�*r�{'t���}�p��*p>tkwv{|r�}á���,�k�>tv{|p>�'�|pn��"��¦>��}.¦k«$�,}�u*p>�Lp>})�q}È­Êpswk���, � ©r�tv�k�p>})�vtkp �|pswI��p>�¥µ {'�K ��6�,})�f�,�v{|r�}�w�ä����,}�w��|p ¦<��wI��pL�¿­ ���v{'�'{|wf�,�v{|r�} �S­ ��}�p ¦<�,tv�kpb~"¢ �¨¢ � �|p ��.5+ÖÚ�+·ÁkÄvÂ�à pswv�¦k«$�,tvu*���,�  �tk�<�,�6�,���|p-���,}�w¸�|p � ã m-�Ap>�c�6���L�>�v«�r���p �)�s��Ipswv�¸wv�� � ��6�,}��k��¬q�¿­Êp4µ��s¦>���v{|r�}� $�,tc��psw´�, � ©p>�|w�,�Ûwvº¥wv�k±>�Lpq�S­ {'})�kp>tV§¿��¦sp���p��6�o¦<�,tv�kp�~%¢ �¨¢ n

�SÍ��SÍbÎ>Ï�Ð � �$Ñ�¥Ð�ÕÖÒQÏ Ó�� � ��� �·Õ Ô �¥Ð�ÕÖÒQÏ �oÈtkr�{|w��, � ��'{|¦<�,�v{|r�}�w�wkr�})����¦>�v��p>�'�|p>�Lp>}����>�v���¥{|�spsw����,}�w-�|po¦<���¥tkpK�¥�. �tkr,¡Vp>�q~%ps¢ �¤£ ä���}�po�, � ��'{|¦<�,�v{|r�}��p�tkps¦f«�p>tk¦k«�po���,}�w"��}�p��$�,}�¼���p��S­ {'���,u*psw � ��}�pª�*p>tkwv{|r�}Û{'}���p4µ��spª�¥�Þ�|r�u{|¦>{|p>�X �«$�,tkpIp>}Ûu*�>}�r��K{|¼���p � �|p �tkr�utf�,�K�Lp�� � � y o & ��( & "�( � p>�q��}�pL�, � ��'{|¦<�,�v{|r�}Ý��potkps¦f«�p>tk¦k«�pb�S­ {'}¥§·r�tv���,�v{|r�} ���,}�w���pswq�$�,}�¼���psw���p��r�}�}��spsw £ ¢ � nQ�cpsw\���>�*p>�|r� � ©p>�Lp>})�kw"�6�,{|wkwkp>})�% �tk�swf�,u*p>t\ ��'��wv{|p>��tkw% �tkr,²��|w%�S­ ���v{'�'{|wf�,�kp>��tkwªä

�n´ ©r���t¨��}���r����,{'}�p"�S­É�, � ��'{|¦<�,�v{|r�} ¦sr�}�}��áä* �r�tv�kp>t¨��}�}�r����*p>���,�'u*r�tv{'�v«��Lp�¦sr�}�wv{|wv�kp%¬- �tkr�utf�,�K�Lp>t�|p ¦>�'��wv�kp>tK��p ã � p>} ���s��¯¬Ë�¿­É�,{|��p��¥�.À2ÁvÂ�Ã�Ä4Å�Æ�Á2Ç � ¬á¦k«$�,tvu*p>tLp>�K¬áp4µ� ��|r�{'�kp>tK��pswor� ��>tf�,�kp>��tkw���,�k�>tv{|p>�|w� �tk�s���4²�}�{|wÛwv��t��|p � ã mq�ªn\�cpá�»º� �p.�S­ ���v{'�'{|wf�,�v{|r�}Apswk����¦s¦spswkwk{'���|p:�,�  �tkr�utf�,�K�Lp>��twk ��s¦>{6�,�'{|wv�kpq��p�wkr�}Ë��r����,{'}�pª�, � ��'{|¦<�,�v{�§

¥n´ ©r���tI��}Ý}�r����*p<�,� ��r����,{'}�p��S­É�, � ��'{|¦<�,�v{|r�}Aä�p>}Ý ��'��wo��pswo���>�*p>�|r� � �p>�Lp>}��kwK �tk�4�»¦>{'�k�sw � {'�Cw<­É�,u{'���pb¦sr�}�¦sp>�*r�{'tI��p�}�r����*p<�,�¥µ r� ��>tf�,�kp>��tkwo��pL¦<�,�|¦>��� � ���,}�wª��}  �tkp>�K{|p>t��kp>�K �wIp>} ���s�� �  ���{|wI��p�|psw�wvº�})�v«��>�v{|wkp>tq¬K�¿­É�,{|��po��psw�r����v{'�|w"��pK�c�%³ ¦>�6��wkwv{|¼���psw<n��cpª�»º� �pª�S­ ���v{'�'{|wf�,�v{|r�}¯pswv�%tk�swfp>tv�*�I�,�¥µ�,tk¦f«�{'�kps¦>�kpsw"��p-����¦f«�{'}�p

"¥n´ ©r���t���}�pK}�r����*p>�'�|p �,tk¦k«�{'�kps¦>�v��tkpáä©�|pqÀ4ÁVÂ�Ã�Ä4Å�ÆÁfÇL���>�k�L¦sr�}��>�  ©r���t�Ü>�vtkpK ©r�tv�f�,���|pLp>���S­É�,���vtkpsw¦>{'���|psw�wkr�}���p>})��{|wf�,u*�spsw<n ã �,tËp4µ�p>�K ��|p � {'�qpswv�b ©rwkwv{'���|p � utf��¦sp¯�,� �L�s¦<�,}�{|wv�Lp.�S­ «��>tv{'�f�,u*p¯��psw�6�,}�u)�,u*pswW¬´r��¥¡vp>� � ��p¨tkp>�K ��6��¦sp>t��|p¸wv�� � ©r�tv�X�S­Êp4µ��s¦>���v{|r�}op>�X��p¨�L�>�Lr�tv{|w2�,�v{|r�}o��pswX{'}���p4µ����,}�w���psw��}�{'�k�sw��Lr���{'�|pswq���,}�w���}¯¦sr�})�kp4µ¥�kpo�S­ {'}¥§·r�tv���,�v{|¼���pK�,����{6�,})�kp�r��áp>}�¦sr�tkpo�S­ ���v{'�'{|wkp>tq��psw-�¥{|wk¼���pswwk ��s¦>{6�,�'{|wk�sw\ �r���t´ $��wkwfp>t%¬o�¿­Ê�s¦k«�p>�'�|pª�¥�� �p>�f�¾�»r�¦>�kp>�<n

151

Page 12: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

�8Í���ÒQÏ Ô � �8� ÕÖÒ�Ï

� pqwkº�wv�k±>�Lp-~"ps¢ �¤£ pswv�\r� ©�>tf�,�v{|r�}�}�p>�8��p> ���{|w´�|p- �tv{'}��kp>�K �w � � 0 n � �Spswv�%��¦>�v��p>�'�|p>�Lp>}��"¦sr��K ©rwk�q�S­ ��}¦>�'��wv�kp>t���p � ����¦k«�{'}�psw äS�¿­ ��}�pL�S­Êp>�'�|p-¡vr���po�|pKt����|pL��po�����|�vtkpbp>��¦sr�r�tk��r�}�}�p��¿­Êp4µ¥�s¦>���v{|r�} ��p B �,���vtkpsw����¦f«�{'}�psw\¼)��{Stkp>}¥§®p>tv�Lp>})�"¦k«$��¦>��}�p o¦<�,tv�kpsw\~"¢ ��¢Ýn � ­Êp>}�wkp>�ª���|p�tkp> �tk�swkp>}��kpq��}Ëpswv $��¦spq��pqwv�kr�¦k¹�,u*p¦>���ª���|�b��p � ��Þm-rË��p��L�>�Lr�{'tkp � �6��wv« �,��¼)��p>�cpswv�ª�¥{'tkps¦>�kp>�Lp>}��K¦sr�}�}�ps¦>�k����}�p� ���{|wkwf�,}�¦sp���pb¦<�,�|¦>���¦sr�}�wk�s¼���p>})�kp wkr���wI�6��§®r�tv�Lp ��p�tkpswkwfr���tk¦spswªtkps¦sr�}¥²�u��tf�,���|psw�n ã �,totf�, � �r�tv�K¬Þ��psw��vtf�<���,�¥µÝwk{'�K{'�6�,{'tkpsw �}�r��vtkpo�, � �tkr�¦f«�powkp����>���,tk¼���pI $�,t"�6�� �rwfwv{'��{'�'{'�k�ª�S­É��¦s¦s�s��p>t-tf�, �{|��p>�Lp>}����,�¥µÛ��r�}�}��spsw � ¦sr��K $�,tf�,�v{'�*p4��Lp>}��I¬���} �¥{|wk¼)��pL���,u}��>�v{|¼)��p � ¦sp�¼���{¨ ©p>tv�Lp>�ª�S­Êp>})��{|wf�,u*p>tI��pL}�r����*p>�'�|pswª�kps¦k«�}�{|¼���pswI��pLtkps¦k«�p>tk¦k«�p�$��wk�spsw%wv��t´�¿­ {'}���p4µ��,�v{|r�}Èn�W}b $�,tf�,�'�|±>�|p � ��}�p>})��{'tkr�}�}�p>�Lp>})�\��p% �tkr�utf�,�K���,�v{|r�}Ë���>�k�����>�*p>�|r� � ��n � �Qw<­É�, � ���{|p"wk��t���}�À4ÁvÂ�Ã�Ä4Å�Æ�Á2Çwv ©�s¦>{6�,�|p>�Lp>})�ª�>�v���¥{|�o �r���tq�¿­ {'}���p4µ��,�v{|r�}Ý��poutkrwkwfpsw-����wkwkpswq��pK��r�}�}��spsw<n � �g �p>����w�­Êp4µ¥�s¦>���kp>t�wv��t��¥{�§Ö�§®�>tkp>})�kpswª ��6�,�kp4§·r�tv�LpswI $�,tf�,�'�|±>�|pswI ©p>tv�Lp>�v�f�,})�K�,{'}�wv{¸�|pb���>�*p>�|r� � �p>�Lp>}��o �tkr�utkpswkwv{�§%�S­É�, � ��'{|¦<�,�v{|r�}�w � �¥� �tkr��kr��¤º� $�,u*po¡V��wk¼��ȭɬÞ�¿­ {'})�k�>utf�,�v{|r�} p��©ps¦>�v{'�*p��S­Êr� ©�>tf�,�kp>��tkwLtkps¦sr�}¥²�u��tf�,���|psw wv ©�s¦>{6�,�'{|wk�sw<n � p�wvº¥wv�k±>�Lppswv�o��¦>�v��p>�'�|p>�Lp>})�Kp>}  �«$��wkp���pb�kpswv� � ¬Ë�6��§®r�{|w�wk��t��|pswo��wv �ps¦>�kwª���,�k�>tv{|p>�´p>���|r�u{|¦>{|p>�¿n�zq�,}�wI¦spb¦<���¥tkp �}�r���w´�vtf�<���,{'�'�|r�}�w% ��'��w\ �tk�s¦>{|wk�>�Lp>}��"wv��t\��p>�¥µË��r����,{'}�psw��, � ��'{|¦<�,�v{�§·wªä¥�¿­ {'���,u*p�p>�\�6�Iu*�>}�r��K{|¼���pn

� ­Êp>}���{'tkr�}�}�p>�Lp>}�� ��p  �tkr�utf�,�K���,�v{|r�} �.�>�k��p>})�v{|±>tkp>�Lp>})�b���,�'{|����wk��tK�6�Ûtkps¦f«�p>tk¦k«�pÞ�S­ {'���,u*pswL $�,tK�|p¦sr�}��kp>})� & ����(»n � }�pLtkps¼���Ü>�kpbpswk����}�pL{'���,u*p p>�ªr�} �*p>����tk�s¦>�� ©�>tkp>tI�kr����kpswª�|psw�{'���,u*pswbÚ<.Öà . =' . ÁkÄ2ÚL¶·r�� $�,tv�v{|psw��S­ {'���,u*pswIwv{'�K{'�6�,{'tkpsw2½- $�,tv�K{���pswq�K{'�'�'{|r�}�w��S­ {'���,u*pswI�S­ ��}�pK�$��wkpK��p���r�}�}��spsw<n � psw�{'���,u*psw���p�6�.�$��wfpËwv����{|wkwkp>}����S­É�,�©r�tk� ��}à�vtf�,{'�kp>�Lp>}��b ©r���t�p4µ¥«�{'��p>t�¦sp>tv�f�,{'}�pswb �tkr� �tv{|�>�k�sw ¼)��{ � �S­ ��}  �r�{'}��b��p����p\ ���tkp>�Lp>}��´{'}¥§·r�tv���,�v{|¼���p � w<­Êp4µ� �tv{'�Lp>}��C $�,t¸��}�p�¦sr��'�|ps¦>�v{|r�}���p%�*ps¦>�kp>��tkw\�,�v�f��¦f«��swC¬ª¦k«$��¼���p�{'���,u*pn� } ¦<�,�|¦>���¸��pb�¥{|wv�f�,}�¦sp�p>}��vtkp�{'���,u*pswªtkp>��{|p>})�K�,�|r�tkwª¬Ë¦<�,�|¦>���|p>to��psw��¥{|wk�f�,}�¦spswªp>}��vtkp��*ps¦>�kp>��tkw<ng�cp>�v�kp�, � ��'{|¦<�,�v{|r�} �.�>�k��¦sr��K ��|±>�kp>�Lp>}��b{'}��k�>utk�spÛ���,}�wK�|poÀ4ÁvÂ�Ã�Ä4Å�Æ�Á2Çbp>�Þ¶®�,���kr����,�v{|¼���p>�Lp>})�2½L $�,tf�,�'�|�>�'{|wk�spwv��t´�|p�¦>�'��wv�kp>t"~"ps¢ �¤£ n � �K��p>tv}�{|±>tkp��>�f�, ©p�¦sr�}�wv{|wk�kp�¬Kwvº�})�v«��>�v{|wkp>t"�¿­Êr� ��>tf�,�kp>��t���p��¥{|wv�f�,}�¦spª¼)��{ �  ©r���t�¿­ {'}�wv�f�,}�� � pswv�\p4µ��s¦>���k�q $�,t\�|r�u{|¦>{|p>�¿n

� ����,�'{|���,�v{|r�} ���,�k�>tv{|p>�'�|p-��pswC¦<�,tv�kpswC~%¢ �¨¢ w<­É�, � ���{|p � ¼��$�,})�´¬�p>�'�|p � wv��tc��}�p��, � ��'{|¦<�,�v{|r�}�u*�>}�r��K{|¼���pp>}� $�,tv�kp>}$�,tv{6�,�%�s�*ps¦-�¿­Ê�s¼���{' ©p �¤�qy �¨~%¢ � 0 � B �¥�Û�?p � �S­Ê�%}�u*p>tkw�n��cp>�v�kpq�s¼���{' ©p�¦f«�p>tk¦k«�p�¬ª{|��p>}��v{�²$p>t��pb}�r����*p>�'�|pswK �tkr��k�>{'}�pswo�K{'�kr�¦k«�r�}��¥tv{6�,�|psw�¼���{c �p>���*p>}��LÜ>�vtkpb{'�K ��'{|¼����spswK���,}�wI��} utf�,}�� }�r�����tkp���p �tkr�¦spswkwv��wC $�,�v«�r��|r�u{|¼���psw%�kp>�|w%¼)��pLä�¦<�,}�¦sp>t � �¥{6�,��±>�kp � r����swv{'�k� � ���,�6���¥{|psw"u*�>}��>�v{|¼���psw%p>�´}�p>��tkr����>u*�>}��4�tf�,�v{'�*psw<n¥³"}bp>}�¦sr�}�}$���|�Cp>})��{'tkr�} �� � �wv��t¨�|psw ���� � �pswk�v{'�L�spsw<n)~"p> ��>tkp>t���p%}�r����*p>�'�|pswc{'}�wv�f�,}�¦spsw¸pswk����r�}�¦ �tv{'�Lr�tk�¥{6�,�W ©r���t-�,�L�>�'{|r�tkp>tq�6�b¦sr��K �tk�>«�p>}�wv{|r�} ��pª�6�b �«)º¥wv{|r� $�,�v«�r��|r�u{|po�K{'�kr�¦k«�r�}��¥tv{6�,�|pnÈzo­ ��}. �r�{'}����p"����p���{|r�{'}¥§®r�tv���,�v{|¼)��p � {'��w<­É�,u{'�´��p�tkp>�vtkr����*p>t\���,}�wC�|p�u*�>}�r��Lp-«)�����,{'}Ë��pswCu*±>}�psw\�,}�¦spswv�vtf�,�¥µ�¦sr��o��ª��}�w%�s�*ps¦q�¿­Êp>}�wfp>�����|p���psw´�$��¦>�k�>tv{|psw"wk�s¼���p>}�¦s�spsw%¬o¦spc¡Vr���t<n�z-psw´wv{'�K{'�'{'�v����psw"p>})�vtkp B � � � K �tkr��k�>{'}�psw�$��¦>�k�>tv{|p>}�}�pswCp>���|psw "q�K{'�'�'{6�,tk��wc��p\}���¦>�|�sr��v{|��psw´¼)��{�¦sr�}�wv�v{'�v��p>})�c�|p\u*�>}�r��Lp"«)�����,{'}�wkr�}��c¬�tkps¦k«�p>tk¦k«�p>twvº¥wv�k�>���,�v{|¼���p>�Lp>})�<n � �K�L�>�Lr�{'tkpo��pª~%ps¢ �»£ ¦sr�})�v{|p>}����¿­ {'}���p4µ��,�v{|r�}¯�¥�Ûu*�>}�r��LpIp>�%�|p��vtf�,{'�kp>�Lp>})�qpswv����s¦sr��� ©��p>} ��p>�¥µÝ �«$��wkpswL¼���{´¦sr�tvtkpswv ©r�}���p>})�b¬á��p>�¥µ ²��'�vtf�,u*pswL�¥{��©�>tkp>}��kw<n ã r���t�¦k«$��¼���p� �«$��wkp � ��}r� ©�>tf�,�kp>��t-tkps¦sr�}¥²�u��tf�,���|pKwv ��s¦>{�²$¼���pI�>�k�I���>�*p>�|r� � ©�n � ­Êp>}�wkp>�ª���|pLpswv�-p>}á¦sr���tkw-��pI���,�'{|���,�v{|r�}¯p>����}�ppswv�v{'���,�v{|r�}Ûtf�,{|wkr�}�}$�,���|pq{'}��¥{|¼���pq��}��kp>�K �w\��pq¦<�,�|¦>���È���¾µ¥{'���,�8��p/""¡vr���tkw<n$�cps¦>{8pswv�\¬K¦sr��K $�,tkp>t"�,�¥µ¼���p>�|¼)��psw\�Lr�{|w\wv��t´��}Û¦>�'��wv�kp>t"��p ã � ��pq�f�,{'�'�|p��s¼���{'��,�|p>})�kp��<�*ps¦��|p-�|r�u{|¦>{|p>�8� � � y o & �>( & "�(»n�cpswC��p>�¥µ��, � ��'{|¦<�,�v{|r�}�w´¦sr�}�wk�v{'�v��p>})�\��}�p��$��wkp���p��vtf�s��,{'�� ©p>tv�v{'}�p>})�kpn �¨�'�|pswCtk�> �r�}���p>}��%¬ª��pswc �tk�sr�¦s¦>�¥� $�,�v{|r�}�wWtk�sp>�'�|psw¸p>�W �p>tv�Lp>�v�kp>}��¸��pC�kpswv�kp>tW�|pC �tkr��kr��¤º� ©p\p>}�¦sr�}�wf�s¼)��p>}�¦spn � �� �tkp>�K{|±>tkp%p4µ¥ ��>tv{'�Lp>}��f�,�v{|r�}{'�'�'��wv�vtkpª��{|p>}á�¿­É�, � �tkr�¦f«�pK��pswk¦sp>}����,})�kpo¼���p�}�r���w-wkr���«$�,{'�kr�}�w-�Lp>�v�vtkpIp>}Þ ��6��¦spo���,}�w��¿­Êp>})��{'tkr�}�}�p>�Lp>})�~"ps¢ �¤£ ä��}�p��, � ��'{|¦<�,�v{|r�} pswk���S­É�,��r�tk���K{|wkp%�,�L ©r�{'})�C¬q�¿­É�,{|��p\�S­ ��} ¦<���¥tkp\�|r�u{|¦>{|p>��wv ��s¦>{�²$¼���pn � p´ �tkr,�utf�,�K�Lp>��t¨pswv�Wu��{|���´���,}�wWw2�"���>���,tk¦f«�p\ ©r���t¨�,��r����v{'t�¬"��}�p´wv ©�s¦>{�²$¦<�,�v{|r�}L �tk�s¦>{|wkp´��pC¦sp´¼���{� ©p>���WÜ>�vtkpwv�� � ©r�tv�k�- $�,t\�|psw"¦<�,tv�kpsw%~%¢ �¨¢ n�zq�,}�w´�|p´À4ÁVÂ�Ã�Ä4Å�ÆÁfÇ � �¿­Êr� ��>tf�,�kp>��t%tkps¦sr�}¥²�u��tf�,���|pªpswv�"p4µ� ��'{|¦>{'�kp>�Lp>}��wv ©�s¦>{�²$�q���,}�w´��}�pq �tkr�¦s�s�¥��tkp �*� � �ªn

152

Page 13: Remix : une architecture pour la recherche dans les masses ... · Remix : une architecture pour la recherche dans les ... une architecture pour la recherche dans les masses de donn

� ­Ê�>�f�, ©pªwv��{'��,})�kpªpswv�%��pq�vtf���¥��{'tkpI¦sp>�v�kp�wk ��s¦>{�²$¦<�,�v{|r�}áp>}Û��}�pª�,tk¦f«�{'�kps¦>�v��tkp����,�k�>tv{|p>�'�|pn �W}Û§®�,{'� � ���,}�w~%ps¢ �»£ �|pswW�vtf�,{'�kp>�Lp>}��kwc¬�tk�<�,�'{|wkp>t¸wv��tW�|psw¨¦<�,tv�kpsw�~"¢ ��¢  ©p>���*p>})��Ü>�vtkp%¦sr�}�wv{|���>tk�sw�¦sr��K�Lp´��}L²��'�vtf�,u*pwv��t���}Ëß$r��-��pª��r�}�}��spsw-¦sr�})�v{'}��Èn8��­Êpswv�"��r�}�¦ª��}.¦<���¥tkp�tkp>�6�,�v{'�*p>�Lp>}��q��{|p>}á���4²�}�{gwv��t%�|ps¼���p>�gr�}Þ ©p>���w<­É�, � ���º*p>t� �r���t�u��{|��p>t%��}�pIwvº�})�v«�±swkpI�,tk¦k«�{'�kps¦>�v��tf�,�|pKp>�"¼���{Xw�­ {'}�wkp>tkp���{|p>}.���,}�w%��}�p�u)�,�K�Lpª�S­Êr����v{'�|w����¡v¬o�¥{|wk �r�}�{'���|psw & ��( & �� ( & i�(»n � �I �{|wk�kp�¼���p-}�r���wC ©r���tkwv��{'�*r�}�w\¦sr�}�wv{|wv�kp�¬o�����, ��kp>t\�¿­Êr����v{'�È��pqwkº�}��v«�±swkpm-� � o & �($���,}�wg�¿­Êp>})��{'tkr�}�}�p>�Lp>})�C~%ps¢ �»£ n)mq� � o pswv�W���>�*p>�|r� � ©�%�,� � � y o �¨~ � ¬ � r�tv{|p>})� � p>����¦s¦sp> ��kp��} ¦sr���p:� ¦sr��K�Lp¯wv ��s¦>{�²$¦<�,�v{|r�} ¸{'��u*�>}�±>tkp.��}�p.��pswk¦>tv{' ��v{|r�} � p�z � ¼)��pÞ}�r���w� ©r����*r�}�w p>}�wk��{'�kp{'})�k�>utkp>t����,}�w\�|p- ©�>tv{' �«��>tv{|¼)��pª��pq¦sr�})�vt����|p����s�¥{|��~%ps¢ �»£ n�W}ª¦sr�}�¦>�'��wk{|r�} � �|pW �tkr,¡vp>�8~%ps¢ �¤£ pswv�Èp>}�¦sr�tkp¸p>}� ��|p>{'}�p¨ �«$��wfp¨��pW��,�'{|���,�v{|r�}Èn � �C�kps¦f«�}�r��|r�u{|p � �6��wv«ª¦sr��¥� ��|�sp¨�vtk±sw��>�vtkr�{'�kp>�Lp>})�¨¬´��pswXtkpswkwkr���tk¦spsw8tkps¦sr�}¥²�u��tf�,���|pswg�6�,{|wkwkp>})�X �tk�swf�,u*p>tX�S­Êp4µ�¦sp>�'�|p>})�kpsw� ©p>tV§·r�tv���,}�¦spsw�n� ­Êp4µ¥ ��>tv{|p>}�¦spª�Lr�})�vtkpª¦sp> �p>}����,}���¼��È­ ��}Þ��psw% �r�{'}��kw\���|r�¼)�$�,}��kw%tkpswv�kp�wkr����*p>})�"�6�o �tkr�utf�,�K���,�v{|r�}¯��psw�,tk¦k«�{'�kps¦>�v��tkpsw�tkps¦sr�}¥²�u��tf�,���|psw<n � r���w�pswkwf�<º*r�}�w � ���,}�wb¦spË �tkr,¡vp>� � ��pË���>�*p>�|r� � ©p>t�¦sr�}�¡Vr�{'}��kp>�Lp>})����}p>})��{'tkr�}�}�p>�Lp>})�q¼���{S �p>tv�Lp>�v�kp��S­É�,��u�Lp>}��kp>t"�|pq¦sp>tk¦>�|p���psw\ �tkr�utf�,�K�Lp>��tkw" �r��kp>}��v{|p>�|w<n

� Õ � �·ÕÖÒ*�$Ñ�� � Õ ��n y n � n�%�'�kwf¦k«)��� ��l n*m�{|wv« le� l n�¢Û{'�'�|p>t � �%n l n¢Þº*p>tkw � zon ��n � {' ����,} � �´��wv{|¦c�|r�¦<�,�$�,�'{'u}��Lp>}���wkp<�,tk¦f«�kr�r�� � �L¢ár��8�c{|r��¿n� ����¶#"*½qä B "¾� �� � � ���� ¥n

¥n �\n�¢á�,tv�v{'} � ³In y p>})�v{|p>º¥w � pIn*z����©r�{|w � ��n � n ã «�{'�'{' � ©p � m-� � oAä)�,} �%tk¦f«�{'�kps¦>�v��tkp y º�})�v«�pswv{|wHo8r�r���§®r�tz-ps�¥{|¦<�,�kps� y {'u}$�,� ã tkr�¦spswkwfr�tkw ��� }� �tkr�¦spsps�¥{'}�u*w"r,§ � � ~\³%�»z\�%� � " �  � Èn � B � � � � � ��� "¥n

"¥n y n � ng�%�'�kwk¦f«)��� �¨� nÊ¢Ýn>oC«�r�����w � �InÊ�ªn y ¦k«����Sp>t � ��n��Q«$�,}�u � ��n��Q«$�,}�u � l ng¢Þ{'�'�|p>t � zon ��n � {' ����,} �mq�, � ©ps�:� � � y o �,}�� ã y�� �»� � � y oZäÈ� }�p � u*p>}�p>tf�,�v{|r�} r,§¸ �tkr��kp>{'} ���,�f�,�$��wkp�wkp<�,tk¦k«: �tkr�utf�,�Lw �� ��¦>�|p>{|¦��´¦>{|��w%~"psw<n����ä1" "�i��¾� " B � � � ��� 8 n

B n $ n $ psp>�kr�} � zonQ�In ã �,�v�kp>tkwkr�} � ��n©¢ n�p�p>�'�|p>tkwv�kp>{'} � � �C��wkpª§®r�t � })�kp>�'�'{'u*p>}���z�{|wv¹¥wI¶ � z �Vy%$ w2½ �Sy�� m"�¢¯³�z ~%ps¦sr�tk� �¥� r��¿n 8���� r�n�" � � ����i¥n

�¥n �In��´¦f«$�,tvº)� � ¢ n � º¥wf�,� � ��n y �,�'� m � �´¦>�v{'�*p�z�{|wv¹¥w%ä ã tkr�utf�,�K�K{'}�uK¢ár���p>� � �%�'u*r�tv{'�v«��Lw´�,}�� �W��,�'�$�¾��v{|r�} � � y ã � ³ y � �-�k�k�4�$y �,} �*rwkp � �C�,�'{�§®r�tv}�{6� � � ����i¥n

0 n monQ¢Þp>�K{'¹ � ¢ n oqn $ �,}���p>�K{'t � �In��¸«�r����¥«$�,tvº � z-pswv{'u}á�,}�� �W���,�'�$�,�v{|r�}¯r,§ y ���,tv�-z"{|wk¹��"tk¦k«�{'�kps¦4��v��tkp"§·r�tCz y�y �cr��K�Lp>tk¦>{6�,� l r�tv¹��|r*����w �¥� } ã tkr�¦spsps�¥{'}�u*w\r,§ � })�kp>tv}$�,�v{|r�}$�,�g�cr�}¥§·p>tkp>}�¦sp-r�} ã �,tf�,�'�|p>�ã tkr�¦spswkwv{'}�uÞ¶ � � ã¨ã ½ � o8r�tkr�}��kr � �C�,}$����� � � � � ¥n

8 n ¢ n � º�wf�,�%�,}�� �ªn¸�´¦k«$�,tvº)� �,}�� ��n y �,�'� m � �W��,�'�$�,�v{|r�} r,§q�´¦>�v{'�*pÞz�{|wv¹�wL§·r�tbz�ps¦>{|wk{|r�} y �� � ©r�tv�zq�,�f�,�$��wkpsw � p ã �c�%� � � � � oXr����|r���wkp ��� tf�,}�¦sp � � � � ¥n

i¥n oqn ��n´�C�,�'�6�,«$�,} � ��nHp-�,��wkp>t � ��n l � � t msº�}�p>¹ � oC«�p.mq�,tv  �%tk¦f«�{'�kps¦>�v��tkp¯�,}�� �N�cr��K �{'�|p>t �c� � � ��cr��K ����kp>t � �" �tv{'� � � � ¥n

�¥n ��n � tv{'u*r � ¢ÝnQmqr�¹�«$�,�|p � zon � �s�*p>}�{|p>t � �W��,�'�$�,�v{|r�}¯r,§W�v«�p y �vtkp<�,�LwV�������¿�kr,� � ã m-� �cr��K �{'�|p>toä$�"}�" � ��'{|¦<�,�v{|r�} ã p>tkwv ©ps¦>�v{'�*p � �,�v«Ý�%�c¢ � })�kp>tv}$�,�v{|r�}$�,� y º��K ©rwv{'��� r�} � {|p>�|��� ã tkr�utf�,�K���,���|pÛmq�,�kp�"tvtf�sº¥w � ¢ár�})�kp>tkp>º � �c� � � y � � � � �n

�� ¥nÈ�-n¸z�tf�, ©p>t �Vl n��Cr�«�� � ��n?p��,�K�Lpsw �Hl n � �¾¡ ¡k�,t � ~ªn¨�Cp>�*p>tv{|�¥u*p � ��n¸~"rwkw � ¢ nc�¸«$� � �,�v«�p � ¢ nz-pswf�,{ � �cr��K �{'�'{'}�u y �%��� ã tkr�utf�,�Lwb�kr � ã m-��wËä ã p>tV§®r�tv���,}�¦spÞ~"pswv���'�kw � ��n¨�c{'}�w<n � })�kp>tv}$�,�v{|r�}$�,��cr�}¥§®p>tkp>}�¦sp�r�} � {|wv{|r�} y º¥wv�kp>�Lw �¥� �,}�¦sr����*p>t � �*���'º 8 �@i � � � �n

���n � nC�"�Lwf�,�|p>u � ã n\m�tkrw �´y �»�ªn¸�Cp>tvtf�,}�{ � ~"r�����wv�˳"�¥¡Vps¦>��~%ps¦sr�u}�{'�v{|r�} {'} � ���,u*psw��,}�� �v«�pÞ~"p>�6�¾��kps�Ûzq�,�f�,�$��wkp ã tkr����|p>�Lw �Sy  ©ps¦>{6�,�8{|wkwv��p�r,§g�v«�p �*r���tv}$�,�gr,§¨¢Û���'�v{'�Lps�¥{6��o8r�r��|w��,}��Þ�% � ��'{|¦<�,�v{|r�}�w � "�ä � �4� "�� � � � B n

��¥n y n,m-��º*p>�f�,})� � ¢Ýn¾m-{'tf�,��� ��� n � ­ p"r���tkw �,y n�z-p>tvtv{|p>} ��y n<~\����{'}�{ � zIn � �s�*p>}�{|p>t �,� n<~"�,{'�ª�$�,���'� � �¸�'��wk�kp>tr,§gtkp4�»¦sr�}¥²�u��tf�,���|p�}�r���pswC§®r�tCwf¦<�,}�}�{'}�uL�6�,tvu*pqu*p>}�r��K{|¦q�$�,}�¹¥w � ã �,tf�,�'�|p>�g�cr��K ����v{'}�u � " �*¶��½ � � � ��¥n

��"¥n �\n$mq�,� ��y n o8r��|ps��r�ä¥�"�'u*r�tv{'�v«��Lw%�,}������,�f�owv�vtv��¦>�v��tkpswc§®r�t¸ßQ��wk« �Lp>�Lr�tv{|psw�n��%�c¢ �cr��K ����<n y ��tv�©n" 8 ¶�*½-ä ��"�i¾� � 0 " � � � ��¥n

153