Browse Prior Art Database

Performance Improvements to Adaptive Query System for Small Storage Cpus

IP.com Disclosure Number: IPCOM000061304D
Original Publication Date: 1986-Jul-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Kuehn, SJ: AUTHOR

Abstract

A performance improvement to an adaptive query system for small or limited storage central processing units (CPUs) decreases the delay time (response time) to receive answers from users' questions. By combining and redefining steps which compare character strings, storage required is reduced by not using a matrix. The matrix is no longer needed when processing matching character locations directly. The heart of the adaptive query system is an algorithm for evaluating the similarity of two character strings. The algorithm is implemented in four steps: . Form a matrix by assigning a 1 to the location I:J, where the Ith character of the first string equals the Jth character of the second string. . If a row or a column contains more than one 1, then retain only the one closest to the main diagonal.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Performance Improvements to Adaptive Query System for Small Storage Cpus

A performance improvement to an adaptive query system for small or limited storage central processing units (CPUs) decreases the delay time (response time) to receive answers from users' questions. By combining and redefining steps which compare character strings, storage required is reduced by not using a matrix. The matrix is no longer needed when processing matching character locations directly. The heart of the adaptive query system is an algorithm for evaluating the similarity of two character strings. The algorithm is implemented in four steps: . Form a matrix by assigning a 1 to the location I:J, where the Ith character of the first string equals the Jth character of the second string. . If a row or a column contains more than one 1, then retain only the one closest to the main diagonal. Note: If two 1s are equally distant from the diagonal, then retain both 1s. . Consider the 1s in the matrix as points on an X-Y coordinate system.

If the I:J location contains a 1, then define a point where the X-coordinate equals I and the Y-coordinate equals J. . Using the X-Y coordinates, evaluate the standard correlation coefficient. The algorithm is a pattern-matching algorithm for sentences or phrases. The algorithm does not parse the sentence and misspellings are ignored. The algorithm can be used for different domains without modification (no language or knowledge base needed). By combining the first three steps of the algorithm and then redefining the steps, the following improved algorithm was produced: . The character scan is first performed on the same character position on both strings. This is where I equals J; if the characters are the same, then assign X the value of I and Y the value of J and call the subroutine "Process X and Y". . The "Process X and Y" subroutine calculates: - count of X-Y coordinates. - sum of X coordinate. - sum of Y coordinate. - sum of X coordinate squared. - sum of Y coordinate squared. - sum of the product of the X coordinate and the Y coordinate. . If the characters are not the same, the following is done: Compare the Ith character with the Jth - 1 character; if the char...