Open AccessWEB APP: String Similarity Search - A Hash-based Approach
Author(s) -
Snehal Bobhate
Publication year - 2021
Publication title -
international journal for research in applied science and engineering technology
Language(s) - English
Resource type - Journals
ISSN - 2321-9653
DOI - 10.22214/ijraset.2021.34561
Subject(s) - hash function , string (physics) , string metric , computer science , double hashing , edit distance , rolling hash , hash table , oracle , dynamic perfect hashing , filter (signal processing) , string kernel , theoretical computer science , similarity (geometry) , string searching algorithm , data mining , mathematics , data structure , algorithm , artificial intelligence , programming language , kernel method , image (mathematics) , polynomial kernel , support vector machine , mathematical physics , computer vision
During this Project, we study string similarity search based on edit distance that is supported by many database management systems like Oracle and PostgreSQL. Given the edit distance, ed(s, t), between two strings, s and t, the string similarity search is to search out each string t in a string database D which is almost like a query string s such that ed(s, t) = t for a given threshold t. Within the literature, most existing work takes a filter-and-verify approach, where the filter step is introduced to reduce the high verification cost of 2 strings by utilizing an index engineered offline for D. The two up-to-date approaches are prefix filtering and native filtering. We have a tendency to propose 2 new hash- primarily based labeling techniques, named OX label and XX label, for string similarity search. We have a tendency to assign a hash-label, H s , to a string s, and prune the dissimilar strings by comparing 2 hash-labels, H s and H t , for two strings s and t within the filter step. The key idea is to take the dissimilar bit- patterns between 2 hash-labels.Our hash-based mostly approaches achieve high efficiency, and keep its index size and index construction time one order of magnitude smaller than the present approaches in our experiment at the same time.