Approximate Keyword Search in Web Search Engines

We present a new index method to provide approximate keyword search in search engines. Our approximate keyword matching adopts a new similarity measurement called Listance model, which is a variation of the LCS (longest common subsequence) model. Two keywords are considered approximately matched, if their Listance is no more than a predefined parameter k. Suppose the length of keywords A and B are m and n respectively, the Listance between A and B is defined to be max(m, n) - LCS(A, B). The index method uses a new data structure called LBS index (listance bounded subsequence index), which was designed to allow for very fast approximate keyword matching. In the index phase, a collection of keywords is used as a reference dictionary. We transform keywords in the Web pages into a special form to be indexed if they match one of the keywords approximately in the reference dictionary. During the query processing, a similar keyword transformation is conducted to search the approximate index. The experimental result shows that our approach is efficient and can provide approximate keyword search capability that could be practically interesting.