Source: http://www.google.com/patents/US7664731?dq=7,444,563
Timestamp: 2016-06-28 06:17:20
Document Index: 210128663

Matched Legal Cases: ['Application No. 60', 'Application No. 03824536', 'Application No. 577', 'Application No. 2004', 'Application No. 03824536', 'Application No. 03739087']

Patent US7664731 - Method and system for storing and retrieving data using hash-accessed ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA method and system for storing and retrieving data using hash-accessed multiple data stores, provides data protection while requiring low computational overhead and further provides storage and retrieval access based on only a single piece of access information, which is generally public. The algorithms...http://www.google.com/patents/US7664731?utm_source=gb-gplus-sharePatent US7664731 - Method and system for storing and retrieving data using hash-accessed multiple data storesAdvanced Patent SearchPublication numberUS7664731 B2Publication typeGrantApplication numberUS 11/231,989Publication dateFeb 16, 2010Filing dateSep 22, 2005Priority dateMar 21, 2002Fee statusPaidAlso published asUS20060020575Publication number11231989, 231989, US 7664731 B2, US 7664731B2, US-B2-7664731, US7664731 B2, US7664731B2InventorsRobert F. Snapp, David J. Payne, James D. WilsonOriginal AssigneeUnited States Postal ServiceExport CitationBiBTeX, EndNote, RefManPatent Citations (41), Non-Patent Citations (41), Referenced by (3), Classifications (12), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMethod and system for storing and retrieving data using hash-accessed multiple data stores
US 7664731 B2Abstract
1. A method, implemented using a computer system, for processing data comprising:
receiving an access record having a plurality of identifiers, the access record corresponding to an entity;
transforming, using the computer system, at least one of the plurality of identifiers in the access record into a pre-determined standard representation of the at least one of the plurality of identifiers;
utilizing a cryptographic algorithm to process, using the computer system, at least two of the plurality of identifiers in the access record, including the pre-determined standard representation, to form a cryptographic algorithm result corresponding to previously stored data related to the entity, wherein the previously stored data related to the entity was stored according to an output of the cryptographic algorithm;
matching, using the computer system, the cryptographic algorithm result with the previously stored data related to the entity;
if the cryptographic algorithm result matches the previously stored data related to the entity, outputting, using the computer system, a result indicating a match; and
if the cryptographic algorithm result does not match the previously stored data related to the entity, outputting, using the computer system, an empty result.
2. The method of claim 1, wherein the at least two of the plurality of identifiers comprises at least one from the group comprising: rural address information, city-style address information, hint information, name information, gender information, and moving date information.
3. The method of claim 1, wherein the previously stored data related to the entity comprises a delivery point code.
determining, using the computer system, whether a format of the access record matches a format used to store the previously stored data related to the entity, prior to utilizing the cryptographic algorithm to process at least two of the plurality of identifiers in the access record.
5. The method of claim 4, further comprising enhancing the access record, using the computer system.
6. The method of claim 5, wherein enhancing the access record includes:
formatting at least one of the plurality of identifiers in accordance with a standard.
7. The method of claim 6, wherein the standard comprises one of a group comprising: a name formatting standard, an address formatting standard, and a number formatting standard.
8. The method of claim 5, wherein enhancing the record includes:
generating a variant to at least one of the plurality of identifiers; and
associating the variant with the record.
retrieving, using the computer system, previously stored secondary data reflecting the entity; and
if the cryptographic algorithm result matches the previously stored data related to the entity, outputting, using the computer system, the secondary data with the result indicating the match.
10. A system for processing data comprising:
a receiver for receiving an access record having a plurality of identifiers, the access record corresponding to an entity;
a processor, communicatively connected to the receiver, adapted for:
transforming an identifier from the access record into a pre-determined standard representation;
utilizing a cryptographic algorithm to process at least two of the plurality of identifiers in the access record to form a cryptographic algorithm result corresponding to previously stored data related to the entity, wherein the previously stored data related to the entity was stored according to an output of the cryptographic algorithm;
matching the cryptographic algorithm result with the previously stored data related to the entity;
if the cryptographic algorithm result matches the previously stored data related to the entity, outputting a result indicating a match; and
a preprocessing module for determining whether a format of the access record matches a format used to store the previously stored data, prior to utilizing the cryptographic algorithm to process at least two of the plurality of identifiers in the access record.
12. The system of claim 11, wherein the preprocessing module is further adapted for enhancing the access record.
13. A computer system implemented method for storing entity data comprising:
receiving a record having a plurality of identifiers, the record corresponding to an entity;
transforming, using the computer system, at least one of the plurality of identifiers in the record into a pre-determined standard representation of the at least one of the plurality of identifiers;
utilizing a cryptographic algorithm to process, using the computer system, at least two of the plurality of identifiers in the record, including the pre-determined standard representation, to form a cryptographic algorithm result;
deriving, using the computer system, an index from the cryptographic algorithm result to indicate a location in a secure database; and
storing the entity data, using the computer system, in the secure database at the location determined by the index derived from the cryptographic algorithm result.
14. The method of claim 13, wherein storing comprises:
storing a plurality of portions of the entity data at multiple locations determined by multiple indices derived from the cryptographic algorithm result.
15. The method of claim 13, wherein the record comprises a name identifier and an address identifier.
16. The method of claim 13, wherein the entity data comprises an address of the entity.
17. The method of claim 16, wherein the address comprises an address of the entity expressed in an alternative format.
enhancing, using the computer system, the record prior to utilizing a cryptographic algorithm to process at least two of the plurality of identifiers in the record.
19. The method of claim 9, wherein the previously stored data comprises delivery information, and the secondary data comprises a hint to resolve ambiguity related to the delivery information.
20. The method of claim 1, wherein the empty result comprises result indicating that no previously stored data corresponding to the cryptographic algorithm result was found.
21. The method of claim 1, wherein the cryptographic algorithm comprises a hash algorithm.
22. The method of claim 8, wherein the at least one of the plurality of identifiers comprises a number expressed as a word, and the variant comprises a numeral.
23. The system of claim 10, wherein the empty result comprises a result indicating that no previously stored data corresponding to the cryptographic algorithm result was found.
24. The system of claim 12, wherein enhancing the access record includes:
generating a variant for at least one of the plurality of identifiers; and
including the variant with the access record.
25. The method of claim 16, wherein the address comprises a relocation address for the entity.
26. The method of claim 18, wherein enhancing the record includes formatting at least one of the plurality of identifiers in accordance with a standard.
27. The method of claim 18, wherein enhancing the record includes:
identifying a variant to at least one of the plurality of identifiers; and
28. The method of claim 18, wherein enhancing the record includes normalizing the record.
outputting the previously stored data.
This is a continuation of, and claims the benefit of, U.S. application Ser. No. 10/377,989, filed Feb. 28, 2003, which claims the benefit of U.S. Provisional Application No. 60/366,805, filed Mar. 21, 2002, both of which are incorporated herein by reference.
For the above reason, rural addresses that have been converted to a city-style address present an inconvenience in managing delivery operations. When using standard address matching software (known as a ZIP+4 engine) to standardize addresses, when a rural address is encountered, a cross-reference table: the Locatable Address Conversion System (LACS), must be used to convert the rural address to a city-style address. The ZIP+4 engine provides a full 11-digit ZIP code for a newer city-style address, but older rural addresses must be first converted to a newer city-style address using the LACS before an 11-digit ZIP code can be assigned. Since the LACS comprises an address lists the LACS cannot be generally distributed.
FIG. 2 is a pictorial diagram depicting the structure of database information located in multiple data stores in accordance with an embodiment of the present invention.
FIG. 3 is a flowchart depicting operation of the system executing a storage method in accordance with an embodiment of the present invention.
FIG. 4 is a flowchart depicting operation of the system executing a retrieval method in accordance with an embodiment of the present invention.
Data values 35 stored at the offsets determined by the first 8 offsets correspond to digits of a number of a particular numeric base. However, to further secure the stored data from any possible mining or discovery and also to realize an even usage of individual data stores 34, the data is “striped” across data stores 34 when data stores 34 are populated, so the extracted data must be un-striped in order reconstruct the original data.
Striping look-up table and reordering 38 represents a process that uses the top eight bytes of hashed result 32 as an entry pointer to a look-up table. The look-up table contains all of the possible combinations of reordering of data values 35 amongst data stores 34. Data store 8 34D is depicted as being outside of the striping algorithm in FIG. 2, but may be included as well.
The top 8-bytes of the 20 byte SHA-1 result (hashed access information 32 shifted right by 12 bytes) is divided by 5040 and the resulting modulo 5040 result (the remainder) is used to access a striping look-up table 38, provided as a file. However, any portion of hashed access information 32 could be used as an entry to striping look-up table 38, since access information 32 is quasi-random. Look-up table 38 provides 5040 combinations (7! combinations, where “!”, is the factorial operator and 7! is the number of possible combinations of the 7 tables). If eight tables are used, the divisor use is 40320=8! and the look-up table expanded to include 40320 combination patterns. Look-up table 38 is provided in the software that retrieves data from data stores 34, so that extracted data can be re-ordered at the time of retrieval. The result of the look-up operation is a re-ordering of the positions of the data values extracted by hashed access information 32 in the computation of the final data output. Once the order of the original stored data pattern across data stores 34 has been determined, they are assigned in the re-ordered pattern as values for computing the retrieved element (11-digit DPC).
Data store 8 is a special data store for storing codes corresponding to “hint” information. Hint information is used for resolving ambiguities between some addresses located at the same 11-digit bar code location (such as addresses containing designators such as the 1/2 in some dual-unit street addresses, apartment designations in small un-coded multiple residence units, and other designations such as trailer, lobby, lot, penthouse, suite, upper/lower, etc.). Other information can be coded in data stores 34 (data stores 1-7) such as middle initial of addressee (for tie-breaker determinations when multiple addresses match or for verification of correct address) and information such as effective move-in date (for the change of address application) is inserted in and retrieved from the remaining data store locations for the change of address application. Data store 9 can be optionally incorporated to extend the amount of data or provide a location for storing information about a type of date.
Referring now to FIG. 4, a method for retrieving data is illustrated in accordance with an embodiment of the present invention. First, access information is received and pre-processed to ensure a match to the access information used to store information in the data stores (step 61). Next the access information is hashed using a SHA-1 algorithm to produce a hashed element (step 62) and the hashed access information is divided into a number of non-overlapping fields equal to the number of data stores and ANDed with the size of the corresponding data store minus one to generate an offset for each data store (step 63). Then, the data values within each data store are retrieved with the corresponding offset (step 64). If a marker is found that indicates that a storage conflict occurred during storage (decision 65) the offset is shifted one byte to produce a new offset for that data store (step 66). Step 65 and step 66 are repeated until all of the offsets return valid data values. If any of the data values retrieved are null (indicating that data was never stored at that location), an empty result is returned (step 68) indicating that no stored database element corresponds to the access information provided. If all of the data values are non-null, the data values are re-ordered according to the striping table entry selected by the top 8 bytes of the hashed access information (step 70). Finally, the database element is assembled from the data values by multiplying by the numeric base used to generate the data store information (step 70) and the database element is thus returned in response to the provided access information.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4871903Jul 31, 1987Oct 3, 1989General Electric CompanyApparatus for rapidly accessing a large data base employing an optical disc reading system with multiple heads and track position compensation meansUS5204966 *Mar 9, 1990Apr 20, 1993Digital Equipment CorporationSystem for controlling access to a secure system by verifying acceptability of proposed password by using hashing and group of unacceptable passwordsUS5343529Sep 28, 1993Aug 30, 1994Milton GoldfineTransaction authentication using a centrally generated transaction identifierUS5420403May 26, 1992May 30, 1995Canada Post CorporationMail encoding and processing systemUS5491752Sep 2, 1994Feb 13, 1996Digital Equipment Corporation, Patent Law GroupSystem for increasing the difficulty of password guessing attacks in a distributed authentication scheme employing authentication tokensUS5742807May 31, 1995Apr 21, 1998Xerox CorporationIndexing system using one-way hash for document serviceUS5819291Aug 23, 1996Oct 6, 1998General Electric CompanyMatching new customer records to existing customer records in a large business database using hash keyUS5893120Jan 2, 1997Apr 6, 1999Nemes; Richard MichaelMethods and apparatus for information storage and retrieval using a hashing technique with external chaining and on-the-fly removal of expired dataUS5903651May 14, 1996May 11, 1999Valicert, Inc.Apparatus and method for demonstrating and confirming the status of a digital certificates and other dataUS5933604Nov 5, 1996Aug 3, 1999Fujitsu LimitedNetwork resource monitoring system and method for providing notice of changes in resources in a networkUS5966542Aug 10, 1998Oct 12, 1999Sun Microsystems, Inc.Method and system for loading classes in read-only memoryUS6006200May 22, 1998Dec 21, 1999International Business Machines CorporationMethod of providing an identifier for transactionsUS6289334Jan 31, 1997Sep 11, 2001Sun Microsystems, Inc.Apparatus and method for decomposing database queries for database management system including multiprocessor digital data processing systemUS6289450May 28, 1999Sep 11, 2001Authentica, Inc.Information security architecture for encrypting documents for remote access while maintaining access controlUS6308247May 22, 1997Oct 23, 2001International Business Machines CorporationPage table entry management method and apparatus for a microkernel data processing systemUS6347376Aug 12, 1999Feb 12, 2002International Business Machines Corp.Security rule database searching in a network security environmentUS6457012 *Jun 10, 1997Sep 24, 2002Pitney Bowes Inc.Method and system of updating address records utilizing a clientserver interfaceUS6516320Mar 8, 1999Feb 4, 2003Pliant Technologies, Inc.Tiered hashing for data accessUS6754785Nov 30, 2001Jun 22, 2004Yan Chiew ChowSwitched multi-channel network interfaces and real-time streaming backupUS6763344Apr 14, 2000Jul 13, 2004International Business Machines CorporationMethod of and system for dynamically controlling access to data recordsUS7124408 *Jun 28, 2000Oct 17, 2006Microsoft CorporationBinding by hashUS7159119Jun 11, 2003Jan 2, 2007United States Postal ServiceMethod and system for efficiently retrieving secured data by securely pre-processing provided access informationUS7302582Aug 21, 2001Nov 27, 2007United States Postal ServiceDelivery point validation systemUS20010044783Feb 16, 2001Nov 22, 2001Seth WeisbergOn-line value-bearing indicium printing using DSAUS20020049670Mar 9, 2001Apr 25, 2002Hitachi, Ltd.Electronic payment method and systemUS20030028783Jul 19, 2002Feb 6, 2003Mark CollinsSecurity systemUS20030177021Dec 4, 2002Sep 18, 2003Rana DuttaTraceable business reply envelopesUS20040065598Jun 16, 2003Apr 8, 2004Ross David JustinAddress disambiguation for mail-piece routingUS20040111443May 3, 2002Jun 10, 2004Wong Thomas K.Apparatus and methods for caching objects using main memory and persistent memoryUS20040128247Dec 16, 2003Jul 1, 2004Hitachi., Ltd.Bank system program, credit service program and IC cardUS20040181670Mar 10, 2003Sep 16, 2004Carl ThuneSystem and method for disguising dataUS20040210763Nov 6, 2003Oct 21, 2004Systems Research & DevelopmentConfidential data sharing and anonymous entity resolutionUS20050060556Dec 31, 2003Mar 17, 2005Jonas Jeffrey J.Authorized anonymous authenticationUS20050066182Mar 24, 2004Mar 24, 2005Systems Research & DevelopmentSecure coordinate identification method, system and programCN1311486AFeb 28, 2000Sep 5, 2001金容杰Comprehensive search method for intermediat station information in electronic trade businessDE4421640C1Jun 21, 1994Aug 3, 1995Siemens AgHash addressing and storage for distribution and recovery of dataEP0381418A2Jan 29, 1990Aug 8, 1990International Business Machines CorporationA small fast lookup table for use in a data processing systemJP2001043135A Title not availableJP2002202938A Title not availableJPH08235040A Title not availableJPH11306676A Title not available* Cited by examinerNon-Patent CitationsReference1"Application of DB2 Anonymous Resolution to the Financial Services Industry," Whitepaper of IBM Corporation, USA, May 2005 (17 pages).2"DB2 Anonymous Resolution for Public Safety, Corrections, & Criminal Intelligence," Publication of IBM Corporation, USA, Feb. 2005 (2 pages).3"DB2 Anonymous Resolution," Publication of IBM Corporation, USA, May 2005 (2 pages).4"IBM DB2 Anonymous Resolution Version 3.8 Technical Information," Publication of IBM Corporation, USA, May 2005 (2 pages).5Bellare at al., "Collision-Resistant Hashing: Towards Making UOWHFs Practical," Advances in Cryptology Conference (CRYPTO); Germany; vol. Conf. 17, pp. 470-484, (1997).6Carter et al., "Exact and Approximate Membership Testers," ACM 10th STOC, pp. 59-65, (1978).7Chinese Office Action, dated Nov. 21, 2008, for Chinese Application No. 03824536.1 (14 pages).8First Examination Report from the Government of India Patent Office, dated Dec. 1, 2006 for Patent Application No. 577/KOLNP/2005 (3 pages).9Friedrich, Andrew, "IBM DB2 Anonymous Resolution: Knowledge Discovery Without Knowledge Disclosure," Whitepaper of IBM Corporation, USA, May 2005 (23 pages).10International Search Report for PCT/US01/26125, 3 pages mailed Mar. 26, 2002.11Interview Summary, dated Nov. 30, 2004, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (2 pages).12Interview Summary, dated Sep. 21, 2005, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (2 pages).13Lohr, Steve, "I.B.M. Software Aims to Provide Security Without Sacrificing Privacy," The New York Times, May 24, 2005 (2 pages).14Notice of Allowance and Allowability, dated Jan. 13, 2009, for U.S. Appl. No. 11/235,243 (6 pages) with Response to Office Action, filed Nov. 12, 2008, including listing of allowed claims (18 pages).15Notice of Allowance and Allowability, dated Jul. 1, 2008, for U.S. Appl. No. 10/377,989 (5 pages), with Response to Office Action, filed Aug. 15, 2005, including listing of allowed claims (10 pages).16Notice of Allowance and Allowability, dated Jul. 15, 2009, for U.S. Appl. No. 11/368,445 (6 pages), with Reply to Office Action, filed Nov. 14, 2008, including listing of allowed claims (19 pages).17Notice of Allowance and Allowability, dated Jul. 17, 2007, for U.S. Appl. No. 10/344,990 (6 pages), with Response to Office Action, filed May 29, 2007, including listing of allowed claims (22 pages).18Notice of Allowance and Allowability, dated Jul. 17, 2007, for U.S. Appl. No. 10/344,990 (6 pages).19Notice of Allowance and Allowability, dated May 17, 2006, for U.S. Appl. No. 10/459,013 (16 pages), with Reply Under 37 C.F.R. � 1.111, filed Apr. 27, 2006, including listing of allowed claims (9 pages).20Notice of Allowance and Allowability, dated May 4, 2009, for U.S. Appl. No. 10/377,989 (4 pages), with Response to Office Action, filed Aug. 15, 2005, including listing of allowed claims (10 pages).21Office Action, dated Apr. 15, 2005, for U.S. Appl. No. 10/377,989, filed Feb. 28, 2003 (4 pages).22Office Action, dated Apr. 4, 2006, for U.S. Appl. No. 10/344,990, filed Feb. 20, 2003 (8 pages).23Office Action, dated Jul. 16, 2008, for U.S. Appl. No. 11/638,445, filed Dec. 14, 2006 (8 pages).24Office Action, dated Jun. 26, 2009, for U.S. Appl. No. 11/231,787, filed Sep. 22, 2005 (7 pages).25Office Action, dated Jun. 3, 2008, for U.S. Appl. No. 11/235,243, filed Sep. 27, 2005 (8 pages).26Office Action, dated Mar. 24, 2005, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (14 pages).27Office Action, dated May 26, 2009, for Japanese Application No. 2004-534223, filed Jun. 11, 2003 (9 pages).28Office Action, dated May 8, 2009, for Chinese Application No. 03824536.1, filed Jun. 11, 2003 (8 pages).29Office Action, dated Nov. 28, 2006, for U.S. Appl. No. 10/344,990, filed Feb. 20, 2003 (4 pages).30Office Action, dated Oct. 27, 2005, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (12 pages).31Office Action, dated Sep. 20, 2004, for U.S. Appl. No. 10/377,989, filed Feb. 28, 2003 (4 pages).32Office Action, dated Sep. 3, 2004, for U.S. Appl. No. 10/459,013, filed Jun. 11, 2003 (12 pages).33PCT International Preliminary Examination Report, completed May 6, 2003, for International Application No. PCT/US01/26125 (4 pages).34PCT International Preliminary Examination Report, mailed Nov. 12, 2003 for International Application No. PCT/US03/06672 (4 pages).35PCT International Search Report, dated Mar. 26, 2002, for International Application No. PCT/US01/26125 (4 pages).36PCT International Search Report, dated May 23, 2003, for International Application No. PCT/US03/06672 (5 pages).37PCT International Search Report, dated Oct. 17, 2003, for International Application No. PCT/US03/18412 (7 pages).38PCT Written Opinion, dated Aug. 2, 2004, for International Application No. PCT/US03/18412 (5 pages).39PCT Written Opinion, dated Feb. 13, 2003, for International Application No. PCT/US01/26125 (4 pages).40PCT Written Opinion, dated Sep. 7, 2006, for International Application No. PCT/US03/12711 (8 pages).41Supplementary European Search Report, dated Feb. 17, 2009, for European Application No. 03739087.9-1525 (3 pages).Referenced byCiting PatentFiling datePublication dateApplicantTitleUS9081672May 30, 2013Jul 14, 2015Richard Michael NemesMethods and apparatus for information storage and retrieval using a caching technique with external-chain hashing and dynamic resource-dependent data sheddingUS9117502 *Feb 6, 2013Aug 25, 2015Fixnetix Ltd.System and method for memory management of unique alpha-numeric order identifiers subjected to hashing and truncation for mapping to limited memory spaceUS20140223091 *Feb 6, 2013Aug 7, 2014Fixnetix Ltd.System and method for management of unique alpha-numeric order message identifiers within ddr memory space* Cited by examinerClassifications U.S. Classification707/747, 713/190, 715/205, 713/171, 709/203, 709/201, 707/781International ClassificationG06F17/30Cooperative ClassificationG06F17/30949, G06F21/62European ClassificationG06F17/30Z1C, G06F21/62Legal EventsDateCodeEventDescriptionApr 20, 2010CCCertificate of correctionMar 14, 2013FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services