论文标题
Minhashing方法的近似相似性的确切概率定律
The exact probability law for the approximated similarity from the Minhashing method
论文作者
论文摘要
我们提出了一个概率设置，其中我们研究了Rajaraman和Ullman \ textIt {ru}算法的概率定律，以及由\ textit {rum}表示的修改版本。这些算法旨在估计网络上下文中巨大文本之间的相似性索引。我们通过在仔细选择的概率定律的理想情况下显示出这种方法的基础，确切的相似性是算法提供的随机相似性的数学期望。给出了一些扩展。 \noindent \textbf{Résumé.} Nous proposons un cadre probabilistique dans lequel nous étudions la loi de probabilité de l'algorithme de Rajaraman et Ullman \textit{RU} ainsi qu'une version modifiée de cet algorithme notée \textit{RUM}. CES ALOGRITHMES VISENT - ENDER L'Indice de laeensitéentre des textes de Grandes tailles dan dans dan le contectione du web。 Nous Donnons une Base devicalitédecetteMéthodeen Montrant Que pour des lois des lois deprobabilités细节Choisies，Laselliplyitéexperteexpérancel'EspéranceMathématiquede la la la la laealitealéaléatoIreireDonnéeDonnéeParl'Algorithme\ textit \ textit \ textit \ textit {rum}。 desgénémarisationssontabées。
We propose a probabilistic setting in which we study the probability law of the Rajaraman and Ullman \textit{RU} algorithm and a modified version of it denoted by \textit{RUM}. These algorithms aim at estimating the similarity index between huge texts in the context of the web. We give a foundation of this method by showing, in the ideal case of carefully chosen probability laws, the exact similarity is the mathematical expectation of the random similarity provided by the algorithm. Some extensions are given. \noindent \textbf{Résumé.} Nous proposons un cadre probabilistique dans lequel nous étudions la loi de probabilité de l'algorithme de Rajaraman et Ullman \textit{RU} ainsi qu'une version modifiée de cet algorithme notée \textit{RUM}. Ces alogrithmes visent à estimer l'indice de la similarité entre des textes de grandes tailles dans le contexte du Web. Nous donnons une base de validité de cette méthode en montrant que pour des lois de probabilités minutieusement choisies, la similarité exacte est l'espérance mathématique de la similarité aléatoire donnée par l'algorithme \textit{RUM}. Des généralisations sont abordées.
