text: This paper is concerned with practical implementations of approximate string dictionaries that allow edit errors. In this problem, we have as input a dictionary @math of @math strings of total length @math over an alphabet of size @math . Given a bound @math and a pattern @math of length @math , a query has to return all the strings of the dictionary which are at edit distance at most @math from @math , where the edit distance between two strings @math and @math is defined as the minimum-cost sequence of edit operations that transform @math into @math . The cost of a sequence of operations is defined as the sum of the costs of the operations involved in the sequence. In this paper, we assume that each of these operations has unit cost and consider only three operations: deletion of one character, insertion of one character and substitution of a character by another. We present a practical implementation of the data structure we recently proposed and which works only for one error. We extend the scheme to @math . Our implementation has many desirable properties: it has a very fast and space-efficient building algorithm. The dictionary data structure is compact and has fast and robust query time. Finally our data structure is simple to implement as it only uses basic techniques from the literature, mainly hashing (linear probing and hash signatures) and succinct data structures (bitvectors supporting rank queries).
  @cite_0: Peer-to-peer (P2P) systems show numerous advantages over centralized systems, such as load balancing, scalability, and fault tolerance, and they require certain functionality, such as search, repair, and message and data transfer. In particular, structured P2P networks perform an exact search in logarithmic time proportional to the number of peers. However, keyword similarity search in a structured P2P network remains a challenge. Similarity search for service discovery can significantly improve service management in a distributed environment. As services are often described informally in text form, keyword similarity search can find the required services or data items more reliably. This paper presents a fast similarity search algorithm for structured P2P systems. The new algorithm, called P2P fast similarity search (P2PFastSS), finds similar keys in any distributed hash table (DHT) using the edit distance metric, and is independent of the underlying P2P routing algorithm. Performance analysis shows that P2PFastSS carries out a similarity search in time proportional to the logarithm of the number of peers. Simulations on PlanetLab confirm these results and show that a similarity search with 34,000 peers performs in less than three seconds on average. Thus, P2PFastSS is suitable for similarity search in large-scale network infrastructures, such as service description matching in service discovery or searching for similar terms in P2P storage networks.
  @cite_4: We engineer an algorithm to solve the approximate dictionary matching problem. Given a list of words @math , maximum distance @math fixed at preprocessing time and a query word @math , we would like to retrieve all words from @math that can be transformed into @math with @math or less edit operations. We present data structures that support fault tolerant queries by generating an index. On top of that, we present a generalization of the method that eases memory consumption and preprocessing time significantly. At the same time, running times of queries are virtually unaffected. We are able to match in lists of hundreds of thousands of words and beyond within microseconds for reasonable distances.
  @cite_6: 
  @cite_23: We present experimental analysis of approximate search algorithms that involve indexing of deletion neighborhoods. These methods require huge indices whose sizes grow exponentially with respect to the maximum allowable number of errors k. Despite extraordinary space requirements, the super-linear indices are of great interest, because they provide some of the shortest retrieval times. A straightforward implementation that creates a hash index directly over residual strings (obtained by deletions from dictionary words) is not space efficient. Rather than memorizing complete residual strings, we record only deleted characters and their respective positions. These data are indexed using a perfect hash function computed for a set of residual dictionary strings [2]. We carry out an experimental evaluation of this approach against several well-known benchmarks (including FastSS, which stores residual strings directly [3]). Experiments show that our implementation has a comparable or superior performance to that of the fastest benchmarks. At the same time, our implementation requires 4-8 times less space as compared to FastSS.
summary: Our algorithm is in a sense similar to the FASTSS algorithm introduced in @cite_0 . In this algorithm, a hash table stores all the strings that can be obtained by deleting (at most) @math characters from any string in the dictionary. Then at query time the hash table is queried for all the strings that can be obtained by deleting (at most) @math characters from the string. Then, it can be proved that all the strings at edit distance at most @math will be contained in the resulting set and the remaining task will be to test all the candidates. A clever improvement to FASTSS was achieved in @cite_4 , where instead of storing all the strings obtained by deleting one character, the dictionary stores pointers to the strings. Following this, @cite_23 compresses the strings in a different way: instead of storing the strings, only deleted characters along with their positions are stored. Space-efficient perfect hashing methods @cite_6 are then used to store the lists of positions and characters.