Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-09-03
1999-12-28
Amsbury, Wayne
Data processing: database and file management or data structures
Database design
Data structure types
707 5, 707104, G06F 1730
Patent
active
060094249
ABSTRACT:
Provided is a similarity search apparatus for searching data at a higher speed than that of the prior art without limiting the types of letter of a search key. A unit position correspondence memory stores therein a table that expresses the ordinal number among units at which each unit in a search key inputted by means of a keyboard has appeared within the search key. A search section refers to the table stored in the unit position correspondence memory and operates every time units are read out one by one from a database memory including a plurality of units to generate a plurality of status parameters each of which includes a similarity, a position of coincidence and a skip number, which express with what number of units from the top of the search key the units read out from the database have coincided at what degree of similarity, and express how many units in the database have been skipped over subsequently. Through the above process, the search section updates each status parameter stored in a status parameter memory and operates upon detecting a unit string coincident at a similarity equal to or lower than an inputted similarity, to output the detected unit string as a unit string of a similarity.
REFERENCES:
patent: 5265242 (1993-11-01), Fujisawa et al.
patent: 5577249 (1996-11-01), Califano
patent: 5628003 (1997-05-01), Fujisawa et al.
patent: 5680511 (1997-10-01), Baker et al.
patent: 5752051 (1998-05-01), Cohen
patent: 5787425 (1998-07-01), Bigus
patent: 5799301 (1998-08-01), Castelli et al.
patent: 5799325 (1998-08-01), Rivette et al.
patent: 5884305 (1999-03-01), Kleinberg et al.
H.D. Cheng; "VLSI Architectures for String Matching and Pattern Matching"; Pattern Recognition, vol. 20. No. 1, 1987; pp. 125-141.
W.I. Chang et al.; "Sublinear Approximate String Matching and Biological Applications"; Algorithmica, vol. 12, No. 4/05, Oct. 1994; pp. 327-344.
Nadia El-Mabrouk; "Boyer-Moore Strategy to Efficient Approximate String Matching"; Combinatorial Pattern Matching Annual Symposium Proceedings, Jun. 1996; pp. 24-38.
William I. Chang et al.; "Approximate String Matching in Sublinear Expected Time"; Proceedings of the Annual Symposium on Foundations of Computer Scie, St. Louis, Oct. 22-24, 1990, vol. 1, pp. 116-124.
Raghu Sastry et al.; "CASM: A VLSI Chip for Approximate String Matching"; IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, No. 8, Aug. 1, 1995; pp. 824-830.
Sun Wu et al.; "Text Searching Allowing Errors"; Communications of the Ass'n. for Computing Machinery, vol. 35, No. 10, Oct. 1, 1992; pp. 83-91.
Robert A. Wagner et al.; "The String-to-String Correction Problem", Journal of the Association for Computing Machinery, vol. 21, No. 1, Jan. 1974; pp. 168-173.
Stanley M. Selkow; "The Tree-to-Tree Editing Problem", Information Processing Letters; vol. 6, No. 6; Dec. 1977; pp. 184-186.
Yves Lepage et al.; "A First Quantitative Analysis of Approximate Pattern-Matching"; Proceedings of Japanese Society for Artificial Intelligence, The Special Interest Group (SIG)-J-9501-4; Dec. 8, 1995; pp. 17-23.
Ando Shinichi
Lepage Yves
Amsbury Wayne
ATR Interpreting Telecommunications Research Laboratories
Fleurantin Jean Bolte
LandOfFree
Similarity search apparatus for searching unit string based on s does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Similarity search apparatus for searching unit string based on s, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Similarity search apparatus for searching unit string based on s will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2389675