The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Aug. 09, 2011
Filed:
Dec. 14, 2008
Chen LI, Irvine, CA (US);
Bin Wang, Shenyang, CN;
Xaochun Yang, Shenyang, CN;
Alexander Behm, Irvine, CA (US);
Shengyue Ji, Irvine, CA (US);
Jiaheng LU, Beijing, CN;
Chen Li, Irvine, CA (US);
Bin Wang, Shenyang, CN;
Xaochun Yang, Shenyang, CN;
Alexander Behm, Irvine, CA (US);
Shengyue Ji, Irvine, CA (US);
Jiaheng Lu, Beijing, CN;
The Regents of the University of California, Oakland, CA (US);
Abstract
A computer process, called VGRAM, improves the performance of these string search algorithms in computers by using a carefully chosen dictionary of variable-length grams based on their frequencies in the string collection. A dynamic programming algorithm for computing a tight lower bound on the number of common grams shared by two similar strings in order to improve query performance is disclosed. A method for automatically computing a dictionary of high-quality grams for a workload of queries. Improvement on query performance is achieved by these techniques by a cost-based quantitative approach to deciding good grams for approximate string queries. An approach for answering approximate queries efficiently based on discarding gram lists, and another is based on combining correlated lists. An indexing structure is reduced to a given amount of space, while retaining efficient query processing by using algorithms in a computer based on discarding gram lists and combining correlated lists.