Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-01-19
2003-04-29
Feild, Joseph H. (Department: 2176)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C715S252000
Reexamination Certificate
active
06556984
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and method for hierarchical string matching using multi-path dynamic programming.
2. Description of Related Art
Modern human-computer interfaces provide many mechanisms that attempt to help in navigating paths through the World Wide Web. Bookmarks can be used to identify frequently visited Web sites, while portals or search engines can be used to identify new Web sites. Nevertheless, the sheer volume of information available today on the Internet inevitably leads to problems in such navigation.
One place where navigation problems arise is in missing URLs (Uniform Resource Locators). For example, one of the most common errors seen when accessing Web servers is the “
404
Error”, which occurs when a URL cannot be found because the associated page or document has been renamed, removed, moved or deleted from the Web server, causing the link to become broken. This error arises quite often due to the dynamic and changing nature of the Internet, and the fact that bookmarks and search engines often have outdated links to URLs. The error also occurs when a user mistypes the URL.
Thus, there is a need in the art for new approaches to the management of links and pages, especially mechanisms that can apply increased intelligence to the problem of unknown, missing, or mistyped URLs on the Internet. More specifically, there is a need in the art for approaches that simplify the steps a user must go through to obtain access to a URL on the Internet.
By increasing the intelligence of the Web server, a better, user-friendlier way of dealing with these errors is provided by presenting a list of matches similar to the URL that was desired. Since errors (should) occur relatively infrequently, the increased computational needs for handling these error cases should not significantly affect the overall server performance for all but the largest Web sites.
Hierarchical string-matching is useful here, because when an unknown URL is requested, the Web server can then select from a list of similar candidate URLs based on the new method. Moreover, the method of the present invention is very general, and can be additionally applied to a wide range of applications, such as Web servers, proxy servers, email addresses, spelling checkers, file systems and operating systems, and file browsers (command-line or graphical).
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, system, and article of manufacture for generating a list of candidate objects for a requested object. An identifier for the requested object is accepted, wherein the identifier comprises a target string. A list of candidate objects is generated when the requested object cannot be found by performing a hierarchical string match for the target string against a set of source strings using multi-path dynamic programming, wherein the set of source strings represent a set of objects from which the list of candidate objects is generated.
REFERENCES:
patent: 3568156 (1971-03-01), Thompson
patent: 4319357 (1982-03-01), Bossen
patent: 5168533 (1992-12-01), Kato et al.
patent: 5220567 (1993-06-01), Dooley et al.
patent: 5576955 (1996-11-01), Newbold et al.
patent: 5608874 (1997-03-01), Ogawa et al.
patent: 5689626 (1997-11-01), Conley
patent: 5706498 (1998-01-01), Fujimiya et al.
patent: 5710916 (1998-01-01), Barbara et al.
patent: 5751898 (1998-05-01), Kosaka et al.
patent: 5761538 (1998-06-01), Hull
patent: 5978797 (1999-11-01), Yianilos
patent: 6144962 (2000-11-01), Weinberg et al.
patent: 6178461 (2001-01-01), Chan et al.
patent: 6311179 (2001-10-01), Agarwal et al.
patent: 6321224 (2001-11-01), Beall et al.
patent: 0 814 582 (1997-12-01), None
patent: WO 97/18519 (1997-05-01), None
patent: WO 97/22947 (1997-06-01), None
patent: WO 98/18070 (1998-04-01), None
Levenshtein, V.I., “Binary Codes Capable of Correcting Deletions, Insertions, and Reversals”, Soviet Physics-Doklady, vol. 10, No. 8, Feb. 1966, pp. 707-710.
Sellers, Peter H., “On the Theory and Computation of Evolutionary Distances”, SIAM Journal o f Applied Mathematics, vol. 26, No. 4, Jun. 1974, pp. 787-793.
(Abstract) Garrow, GSD, Xydeas, CS, Oakley JP, Divisional of Electrical Engineering, Manchester University , UK, “Model Matching in Intelligent Document Understanding”, Proceedings of the Third International Conference on Document Analysis and Recognition, Pt. vol. 1, pp. 293-296 vol. 1, IEEE Computer Soc. Press.
(Abstract) Szanser, AJ, “Bracketing Technique in Elastic Matching”, Nat. Phys. Lab., Teddington, U.K., Computer Journal, vol. 16, No. 2, pp. 132-134, May 1973.
(Abstract in English) Corresponding to German Patent Reference DE 19622478 above.
Feild Joseph H.
Gates & Cooper LLP
Singh Rachna
LandOfFree
Hierarchical string matching using multi-path dynamic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical string matching using multi-path dynamic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical string matching using multi-path dynamic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3066747