Finding Content in File-Sharing Networks When You Can't Even Spell.
Matei Zaharia, Amit Chandel, Stefan Saroiu, Srinivasan Keshav · 2007
Abstract: The query success rate in current filesharing systems is low, for example, only 7-10 % in Gnutella. An often-overlooked cause for this low recall is simply that keywords in queries and document descriptions are misspelled. Although many sophisticated approximate matching techniques have been developed by the Information Retrieval community, to our knowledge, they have not been used in popular P2P systems. We propose two approaches to improving query recall in file-sharing systems. For unstructured P2P networks, we show that “q-gram”-based approaches nearly double recall with little loss in precision. Unfortunately, such techniques cannot be used in structured P2P networks. Instead, we propose a simple alternative: encoding keywords using Soundex, a century-old phonetic algorithm for indexing names by their sound. We evaluate both approaches on a trace of all queries and files in Gnutella over a period of a month. We find that misspellings are common in this trace, with 20 % of file descriptions and 25 % of queries containing at least one spelling error. We find that our approaches improve recall by 20-88 % with little loss in precision when compared to a standard prefix-match approach. Given the endemic nature of misspellings, our findings suggest that techniques such as those described here ought to be part of any file-sharing system. 1