Indexing methods for approximate dictionary searching, comparative analysis

DOI10.1145/1963190.1963191MaRDI QIDQ5406235zbMATH OpenOpenAlexWikidataFDO

Authors Leonid Boytsov

Publication date 1 April 2014

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1963190.1963191

zbMATH Keywords

Agrepapproximate searchingDamerau-Levenshtein distancefrequency distancefrequency vector trieLevenshtein distancemetric treesneighborhood generationNR-greptrie

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20) Pattern recognition, speech recognition (68T10) Algorithms on strings (68W32) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Recommendations

• Using signature hashing for approximate string matching
• A new method for approximate indexing and dictionary lookup with one error
• scientific article; zbMATH DE number 2185640
• Cache-Oblivious Index for Approximate String Matching
• Faster and Space-Optimal Edit Distance “1” Dictionary

Cited in

(10)

• Using signature hashing for approximate string matching
• Index structures for fast similarity search for symbol strings
• Compressing dictionary matching index via sparsification technique
• Dictionary compression and information source correction
• Upper and lower bounds for dynamic data structures on strings
• Indexing a Dictionary for Subset Matching Queries
• Simple, compact and robust approximate string dictionary
• Fuzzy \(k\)-minpen clustering and \(k\)-nearest-minpen classification procedures incorporating generic distance-based penalty minimizers
• Approximate similarity search under edit distance using locality-sensitive hashing
• Finding all stable matchings with couples

This page was built for publication: Indexing methods for approximate dictionary searching, comparative analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5406235)