Class / Patent application number | Description | Number of patent applications / Date published |
711216000 | Hashing | 71 |
20080215849 | HASH TABLE OPERATIONS WITH IMPROVED CACHE UTILIZATION - Method and apparatus for building large memory-resident hash tables on general purpose processors. The hash table is broken into bands that are small enough to fit within the processor cache. A log is associated with each band and updates to the hash table are written to the appropriate memory-resident log rather than being directly applied to the hash table. When a log is sufficiently full, updates from the log are applied to the hash table insuring good cache reuse by virtue of false sharing of cache lines. Despite the increased overhead in writing and reading the logs, overall performance is improved due to improved cache line reuse. | 09-04-2008 |
20080222386 | COMPRESSION OF IPV6 ADDRESSES IN A NETFLOW DIRECTORY - Modified flow keys holding compressed IPv6 addresses are stored in a flow table to improve memory utilization. The compressed IPv6 addresses are utilized to access a compression table holding the full IPv6 address, and full IPv6 address are substituted into the modified flow key to form an unmodified flow key. | 09-11-2008 |
20080222387 | Correction of incorrect cache accesses - The application describes a data processor operable to process data, and comprising: a cache in which a storage location of a data item within said cache is identified by an address, said cache comprising a plurality of storage locations and said data processor comprising a cache directory operable to store a physical address indicator for each storage location comprising stored data; a hash value generator operable to generate a generated hash value from at least some of said bits of said address said generated hash value having fewer bits than said address; a buffer operable to store a plurality of hash values relating to said plurality of storage locations within said cache; wherein in response to a request to access said data item said data processor is operable to compare said generated hash value with at least some of said plurality of hash values stored within said buffer and in response to a match to indicate a indicated storage location of said data item; and said data processor is operable to access one of said physical address indicators stored within said cache directory corresponding to said indicated storage location and in response to said accessed physical address indicator not indicating said address said data processor is operable to invalidate said indicated storage location within said cache. | 09-11-2008 |
20080229055 | Hardware-Based Secure Code Authentication - The present invention provides for authentication of code, such as boot code. A memory addressing engine is employable to select a portion of a memory, as a function of a step value, as a first input hash value. The step value allows for the non-commutative cumulative hashing of a plurality of memory portions with a second input hash value, such as a previous hash value that has been rotated left. An authenticator circuit is employable to perform a hash upon the portion of memory and the second input hash value. A comparison circuit is then employable to compare an output of the authenticator circuit to an expected value. | 09-18-2008 |
20080229056 | METHOD AND APPARATUS FOR DUAL-HASHING TABLES - Methods and apparatus for dual hash tables are disclosed. An example method includes logically dividing a hash table data structure into a first hash table and a second hash table, where the first hash table and the second hash table are substantially logically equivalent. The example method further includes receiving a key and a corresponding data value, applying a first hash function to the key to produce a first index to a first bucket in the first hash table, and applying a second hash function to the key to produce a second index to a second bucket in the second hash table. In the example method the key and the data value are inserted in one of the first hash table and the second hash table based on the first index and the second index. | 09-18-2008 |
20080235488 | Splash Tables: An Efficient Hash Scheme for Processors - A computer implemented method, data processing system, and computer usable program code are provided for storing data items in a computer. A plurality of hash functions of data values in a data item are computed. A corresponding memory location is determined for one of the plurality of hash functions. The data item and a key portion and a payload portion of all data items are stored contiguously within the memory location. | 09-25-2008 |
20080263316 | Splash Tables: An Efficient Hash Scheme for Processors - A computer implemented method, data processing system, and computer usable program code are provided for storing data items in a computer. A plurality of hash functions of data values in a data item are computed. A corresponding memory location is determined for one of the plurality of hash functions. The data item and a key portion and a payload portion of all data items are stored contiguously within the memory location. | 10-23-2008 |
20090024826 | GALOIS-BASED INCREMENTAL HASH MODULE - Various systems and methods for implementing a Galois-based incremental hash module are disclosed. For example, a method involves computing a first hash of a first string of an input stream. The first hash is computed by performing one or more Galois mathematical operations upon portions of the first string. A second hash of a second string, which overlaps the first string, can then be computed by processing the first hash. | 01-22-2009 |
20090024827 | METHOD AND SYSTEM FOR DYNAMICALLY DETERMINING HASH FUNCTION VALUES FOR FILE TRANSFER INTEGRITY VALIDATION - A method and system for dynamically determining hash values for file transfer integrity validation. In response to a request for a transfer of a data file between a first computing system and a second computing system, the first computing system loads a first portion of the data file to a buffer. The first computing system determines a first hash function value based on the first portion. The first computing system loads a second portion of the data file portion to the buffer and determines a second hash function value incrementally based on the first and second data file portions. The first and second data file portions are non-overlapping portions of the data file being transferred. | 01-22-2009 |
20090089539 | SYSTEM AND METHOD FOR DETECTING EMAIL CONTENT CONTAINMENT - Systems and methods for detecting email content containment are disclosed. In one embodiment, a method comprises generating a first set of hash values corresponding to a first email document, wherein the first set includes a respective hash value corresponding to each of a plurality of character sequences of the first email document. The method further comprises generating a second set of hash values corresponding to a second email document, wherein the second set include a respective hash value corresponding to each of a plurality of character sequences of the second email document, and determining whether the first set of hash values is a subset of the second set of hash values. | 04-02-2009 |
20090094435 | SYSTEM AND METHOD FOR CACHE ACCESS PREDICTION - A cache system includes a cache having a plurality of cache units, a prediction table and a hashing module. The prediction table is utilized to store way information of at least one cache unit corresponding to at least one accessing address, and the hashing module generates a hashing value corresponding to a target accessing address and reads way information from the prediction table or writes the way information to the prediction table by using the hashing value as an index. | 04-09-2009 |
20090100246 | INFORMATION RETRIEVING APPARATUS AND METHOD - The present invention provides an information retrieving apparatus and method each of which stores predetermined information at addresses of a Main Table RAM associated with retrieval key data by substituting data indicative of each specific position of the retrieval key data in retrieval range defining data in which a range targeted for retrieval is defined by setting the retrieval range defining data as information indicative of the data being arbitrary data, with a fixed value defined in advance and performing conversion on the retrieval key data by predetermined hash functions; allows a mask Table to store position information indicative of the specific position; when retrieval key data targeted for retrieval is inputted, reads the position information from the mask Table and reads from the Main Table RAM through a data selector, the information stored at the addresses associated therewith by substituting the data indicative of each specific position indicated by the position information of the retrieval key data with the fixed value and converting the same by the hash functions, and determines whether each read information is of the predetermined information. | 04-16-2009 |
20090113166 | HASHING METHOD FOR NAND FLASH MEMORY - In accordance with exemplary embodiments, a flash memory, such as a NAND flash memory, selectively updates blocks based on hash values associated with the blocks, wherein the hashing codes are generated for each block from the software image to be programmed into the flash memory. Selectively updating blocks in accordance with an embodiment of the present invention might reduce re-programming time and potentially destructive pre-mature aging of cells in the flash memory. | 04-30-2009 |
20090113167 | DATA PROCESSING APPARATUS AND METHOD OF PROCESSING DATA - Data processing apparatus comprising: a chunk store containing specimen data chunks, a manifest store containing at least one manifest that represents at least a part of a data set and that comprises at least one reference to at least one of said specimen data chunks, a sparse chunk index containing information on only those specimen data chunks having a predetermined characteristic, the processing apparatus being operable to process input data into input data chunks and to use the sparse chunk index to identify at least one of said at least one manifest that includes at least one reference to one of said specimen data chunks that corresponds to one of said input data chunks having the predetermined characteristic. | 04-30-2009 |
20090125701 | AGGREGATING DATA FROM DIFFERENT SOURCES - A method and system that aggregates data associated with one or more entities from different data sources are provided. The data sources include documents, web pages, or images that have information about one or more entities. The information is extracted from the data sources based on criteria that define the entities. The extracted information is utilized to generate a hash identifier that corresponds to each entity and one or more storage locations. The one or more storage locations and associated hash identifiers are utilized to store the extracted information corresponding to the entities, and the extracted information for each entity is structured as a virtual page that is stored in an index having references to the data sources. The index storing the virtual pages is notified or updated when the associated data sources are modified. | 05-14-2009 |
20090132784 | CACHE MEMORY AND METHOD OF OPERATING THE SAME - Provided are a cache memory using a linear hash function and a method of operating the same. The cache memory includes: a first hash function module for converting a main memory address received from a central processing unit (CPU) into a first index value using a first hash function; a second hash function module for converting the main memory address into a second index value using a second hash function; a first comparator for comparing a tag value of a data block located at the first index value in the first bank with a tag value of the main memory address; and a second comparator for comparing a tag value of a data block located at the second index value in the second bank with the tag value of the main memory address. In a pair of linear hash functions according to the present invention, each constructed with a 2m×m binary matrix, even if m is an odd number, each of the linear hash functions has the highest degree of interbank dispersion and avoids conflicts in row, column, diagonal, anti-diagonal, and rectangular patterns, so that a 2-way skewed associative cache can be constructed in relatively wide ranges. | 05-21-2009 |
20090158006 | Facilitating management of layer 2 hardware address table based on packet priority information - A network switching device comprises hardware address table storage space, a priority comparison mechanism, and an address table management mechanism. The hardware address table storage space having a number of entries therein. Each one of the entries within the hardware address table storage space includes respective information designating a priority of a respective source network address. The priority comparison mechanism is configured for comparing the priority designating information of the received packet with the priority designating information of at least a portion of the entries within the hardware address table storage space in response to determining that a number of entries within the hardware address table storage space is equal to a capacity of the hardware address table storage space. The address table management mechanism is configured for replacing an entry within the hardware address table storage space with an entry having contents corresponding to the received packet in response to determining that a priority level corresponding to the priority designating information of the received packet is higher than a priority level corresponding to the priority designating information of the replaced entry. | 06-18-2009 |
20090193223 | METHODS AND SYSTEMS FOR VECTORED DATA DE-DUPLICATION - The present invention is directed toward methods and systems for data de-duplication. More particularly, in various embodiments, the present invention provides systems and methods for data de-duplication that may utilize a vectoring method for data de-duplication wherein a stream of data is divided into “data sets” or blocks. For each block, a code, such as a hash or cyclic redundancy code may be calculated and stored. The first block of the set may be written normally and its address and hash can be stored and noted. Subsequent block hashes may be compared with previously written block hashes. | 07-30-2009 |
20090193224 | TECHNIQUES FOR REDUCING STORAGE SPACE AND DETECTING CORRUPTION IN HASH-BASED APPLICATION - Techniques for reducing storage space and detecting corruption in hash-based applications are presented. Data strings are hashed or transformed into numerically represented strings. Groupings of the numeric strings form a set. Each numeric string of a particular set is associated with a unique co-prime number. All the numeric strings and their corresponding co-prime numbers for a particular set are processed using a Chinese Remainder Theorem algorithm (CRT) to produce a single storage value. The single storage value is retained in place of the original numeric strings. The original numeric strings can be subsequently reproduced and verified using the single storage value and the co-prime numbers. | 07-30-2009 |
20090240913 | UNIVERSAL-HASH-FUNCTION-FAMILY CALCULATION UNIT AND SHARED-KEY GENERATION SYSTEM - An input data enlarging unit ( | 09-24-2009 |
20090249023 | APPLYING VARIOUS HASH METHODS USED IN CONJUNCTION WITH A QUERY WITH A GROUP BY CLAUSE - A novel method is described for applying various hash methods used in conjunction with a query with a Group By clause. A plurality of drawers are identified, wherein each of the drawers is made up of a collection of cells from a single partition of a Group By column and each of the drawers being defined for a specific query. A separate hash table is independently computed for each of the drawers and a hashing scheme (picked from among a plurality of hashing schemes) is independently applied for each of the drawers. | 10-01-2009 |
20090287904 | SYSTEM AND METHOD TO ENFORCE ALLOWABLE HARDWARE CONFIGURATIONS - The present invention comprise methods and systems for enforcing allowable hardware configurations. The present invention utilizes shadow registers, which act as gatekeepers for actual sensitive configuration registers. An attempted write to the actual sensitive configuration registers is first stored in a corresponding shadow register and is subsequently validated via a cryptographic hash register before the values are passed to the actual configuration register. | 11-19-2009 |
20090300321 | METHOD AND APPARATUS TO MINIMIZE METADATA IN DE-DUPLICATION - The invention provides a method for reducing identification of chunk portions in data de-duplication. The method includes detecting sequences of stored identification of chunk portions of at least one data object, indexing the detected stored identification of chunk portions based on a sequence type, encoding first repeated sequences of the stored identifications with a first encoding, encoding second repeated sequences of the stored identifications with a second encoding, and avoiding repeated stored identifications of chunk portions. | 12-03-2009 |
20100023726 | Dual Hash Indexing System and Methodology - A method, system and program are disclosed for accelerating data storage in a cache appliance that transparently monitors NFS and CIFS traffic between clients and NAS subsystems and caches files in a cache memory by using a dual hash technique to rapidly store and/or retrieve connection state information for cached connections in a plurality of index tables that are indexed by hashing network protocol address information with a pair of irreducible CRC hash algorithms to obtain an index to the memory location of the connection state information. | 01-28-2010 |
20100023727 | IP ADDRESS LOOKUP METHOD AND APPARATUS BY USING BLOOM FILTER AND MULTI-HASHING ARCHITECTURE - The present invention relates to an IF address lookup apparatus using a Bloom filter and a multi-hashing architecture that includes a buffering means that outputs a prefix of an inputted address having the number of bits reduced by one bit whenever a control signal is received at the time of outputting the prefix of the inputted address; a hashing hardware that generates a plurality of hashing indexes by hashing the prefix (hereinafter, referred to as “output prefix”) outputted from the buffering means; a Bloom filter that determines whether or not the output prefix is an entry of the hash table by using the plurality of hashing indexes; and a processor that includes the hash table and an overflow table and outputs a prefix that matches the output prefix by searching entries of locations of the hash table indicated by the plurality of hashing indexes and entries stored in the overflow table when a Bloom filter's determination result is positive and outputs the control signal to the buffering means when the matched prefix is not provided or the Bloom filter's determination result is negative. | 01-28-2010 |
20100031000 | APPARATUS, SYSTEM, AND METHOD FOR VALIDATING THAT A CORRECT DATA SEGMENT IS READ FROM A DATA STORAGE DEVICE - An apparatus, system, and method are disclosed for validating that correct data is read from a storage device. A read request receiver module receives a read storage request to read a data segment of a file or object stored on a data storage device. The storage request includes one or more source parameters for the data segment. The source parameters include one or more virtual addresses that identify the data segment. A hash generation module generates one or more hash values from the virtual addresses. A read data module reads the requested data segment and returns one or more data packets and corresponding stored hash values stored with the data packets. The stored hash values were generated from a data segment written to the data storage device that contains data of the data packets. A hash check module verifies that the generated hash values match the respective stored hash values. | 02-04-2010 |
20100058027 | METHOD FOR SELECTING HASH FUNCTION, METHOD FOR STORING AND SEARCHING ROUTING TABLE AND DEVICES THEREOF - A method for selecting a hash function, a method for storing and searching a routing table and devices thereof are provided. The method for selecting a hash function includes: hashing data to be hashed by using a current alternative hash function; decoding a hash result; accumulating decoded results until no carry occurs during the accumulation; and selecting a current alternative hash function with no carry generated as a formal hash function. The method for storing a routing table includes: dividing the routing table into a next-level node pointer portion and a prefix portion for being stored; and selecting a hash function by using the above method for selecting a hash function. The method for searching a routing table includes: directly searching an IP address to be searched according to a directly stored length of a next-level node pointer portion for storing the routing table; and reading a prefix node according to a searched result. Thus, hash collision can be avoided, and memory resources occupied by the routing table can be effectively reduced. | 03-04-2010 |
20100070736 | INFORMATION PROCESSING SYSTEM, INFORMATION PROCESSING METHOD, AND PROGRAM - An information processing system includes: a data processing unit that executes verification processing for a content recorded in a disk and reproduces the disk-recorded content under a condition that the verification succeeds, wherein the data processing unit randomly selects hash units, which are objects of collation, from among a plurality of hash units formed with component data items of the content, reads the selected hash units sequentially from the disk, calculates hash values, and collates the calculated hash values with collation hash values; and the data processing unit executes reading sequence determination processing so as to determine a reading sequence in which the selected hash units are sorted according to recording positions in a disk, and reads the selected hash units according to the determined reading sequence. | 03-18-2010 |
20100115230 | HASH FUNCTIONS USING RECURRENCY AND ARITHMETIC - Aspects relate to systems and methods for implementing a hash function using a stochastic and recurrent process, and performing arithmetic operations during the recurrence on portions of a message being hashed. In an example method, the stochastic process is a Galton-Watson process, the message is decomposed into blocks, and the method involves looping for a number of blocks in the message. In each loop, a current hash value is determined based on arithmetic performed on a previous hash value and some aspect of a current block. The arithmetic performed can involve modular arithmetic, such as modular addition and exponentiation. The algorithm can be adjusted to achieve qualities including a variable length output, or to perform fewer or more computations for a given hash. Also, randomizing elements can be introduced into the arithmetic, avoiding a modular reduction until final hash output production. | 05-06-2010 |
20100199066 | GENERATING A LOG-LOG HASH-BASED HIERARCHICAL DATA STRUCTURE ASSOCIATED WITH A PLURALITY OF KNOWN ARBITRARY-LENGTH BIT STRINGS USED FOR DETECTING WHETHER AN ARBITRARY-LENGTH BIT STRING INPUT MATCHES ONE OF A PLURALITY OF KNOWN ARBITRARY-LENGTH BIT STRINGS - Generating and using a high-speed, scalable and easily updateable data structures are described. The proposed data structure provides minimal perfect hashing functionality while intrinsically supporting low-cost set-membership queries. In other words, in some embodiments, it provides at most one match candidate in a set of known arbitrary-length bit strings that is used to match the query. | 08-05-2010 |
20100217953 | HYBRID HASH TABLES - A hash table system having a first hash table and a second hash table is provided. The first hash table may be in-memory and the second hash table may be on-disk. Inserting an entry to the hash table system comprises inserting the entry into the first hash table, and, when the first hash table reaches a threshold load factor, flushing entries into the second hash table. Flushing the first hash table into the second hash table may comprise sequentially flushing the first hash table segments into corresponding second hash table segments. When looking up a key/value pair corresponding to a selected key in the hash table system, the system checks both the first and second hash tables for values corresponding to the selected key. The first and second hash tables may be divided into hash table segments and collision policies may be implemented within the hash table segments. | 08-26-2010 |
20100228947 | ADDRESS GENERATOR - The address generator has a hash network for producing hashed Y | 09-09-2010 |
20100250896 | SYSTEM AND METHOD FOR DATA DEDUPLICATION - A system for deduplicating data comprises a card operable to receive at least one data block and a processor on the card that generates a hash for each data block. The system further comprises a first module that determines a processing status for the hash and a second module that discards duplicate hashes and their data blocks and writes unique hashes and their data blocks to a computer readable medium. In one embodiment, the processor also compresses each data block using a compression algorithm. | 09-30-2010 |
20100312986 | SEMICONDUCTOR INTEGRATED CIRCUIT - A semiconductor integrated circuit includes: a data path configured to transmit data from a first region to a second region; a first hash value calculator configured to read first data being transmitted through the data path within the first region and to calculate a first hash value from the first data; a register being disposed on the data path within the second region and configured to read second data transmitted through the data path; a second hash value calculator configured to read the second data output from the register and to calculate a second hash value from the second data; and a comparator configured to compare the first hash value and the second hash value and to determine whether the first hash value and the second hash value coincide with each other. | 12-09-2010 |
20100332791 | SYSTEM, METHOD, AND COMPUTER-READABLE MEDIUM FOR OPTIMIZING PROCESSING OF GROUP-BY QUERIES FEATURING MAXIMUM OR MINIMUM EQUALITY CONDITIONS IN A PARALLEL PROCESSING SYSTEM - A system, method, and computer-readable medium for optimized processing of queries that feature maximum or minimum equality conditions are provided. The disclosed mechanisms provide for a single-scan of the table on which the group-by query is applied. When the table is scanned, each processing module dynamically keeps track of the row(s) having a value of the attribute on which the equality condition is applied that equals or exceeds the maximum attribute value (assuming a maximum equality condition is applied) previously encountered by the processing module. Subsequently, a global aggregation process is then performed to compute the query's result without rescanning the table. Queries featuring a minimum equality condition are similarly processed in accordance with the disclosed embodiments. | 12-30-2010 |
20110078408 | Method for Protecting a Privilege Level of System Management Mode of a Computer System - A method for protecting a privilege level of a system management mode (SMM) of a computer system is disclosed. A SMM program is loaded into a special memory (SMRAM) area within a system memory of a computer. A first program, a second program, and a vector table are loaded into a general area of the system memory. Before the booting process of the computer has been completed, a reference hash value of the first program is determined by the SMM program, and the reference hash value is stored in the SMRAM area. A hash value of the first program is the computed by the SMM program. After the computer has been operating under an operating environment of an operating system, the computed hash value is compared to the reference hash value. When the computed hash value matches the reference hash value, the first program is called by the SMM program. | 03-31-2011 |
20110099351 | Use of Similarity Hash to Route Data for Improved Deduplication in a Storage Server Cluster - A technique for routing data for improved deduplication in a storage server cluster includes computing, for each node in the cluster, a value collectively representative of the data stored on the node, such as a “geometric center” of the node. New or modified data is routed to the node which has stored data identical or most similar to the new or modified data, as determined based on those values. Each node stores a plurality of chunks of data, where each chunk includes multiple deduplication segments. A content hash is computed for each deduplication segment in each node, and a similarity hash is computed for each chunk from the content hashes of all segments in the chunk. A geometric center of a node is computed from the similarity hashes of the chunks stored in the node. | 04-28-2011 |
20110202744 | HASHING WITH HARDWARE-BASED REORDER USING DUPLICATE VALUES - A hash table controller may include a hash calculator configured to receive a key and to determine, based thereon, a first entry in a first bank of a hash table for a value associated with the key and determine a second entry in a second bank of the hash table for the value. The hash table controller also may include a table operations manager configured to determine that the first entry and the second entry are empty, and to store the value and a duplicate of the value at both the first entry and the second entry, respectively. | 08-18-2011 |
20110225391 | HASH PROCESSING IN A NETWORK COMMUNICATIONS PROCESSOR ARCHITECTURE - Described embodiments provide a hash processor for a system having multiple processing modules and a shared memory. The hash processor includes a descriptor table with N entries, each entry corresponding to a hash table of the hash processor. A direct mapped table in the shared memory includes at least one memory block including N hash buckets. The direct mapped table includes a predetermined number of hash buckets for each hash table. Each hash bucket includes one or more hash key and value pairs, and a link value. Memory blocks in the shared memory include dynamic hash buckets available for allocation to a hash table. A dynamic hash bucket is allocated to a hash table when the hash buckets in the direct mapped table are filled beyond a threshold. The link value in the hash bucket is set to the address of the dynamic hash bucket allocated to the hash table. | 09-15-2011 |
20110276780 | Fast and Low-RAM-Footprint Indexing for Data Deduplication - The subject disclosure is directed towards a data deduplication technology in which a hash index service's index maintains a hash index in a secondary storage device such as a hard drive, along with a compact index table and look-ahead cache in RAM that operate to reduce the I/O to access the secondary storage device during deduplication operations. Also described is a session cache for maintaining data during a deduplication session, and encoding of a read-only compact index table for efficiency. | 11-10-2011 |
20110276781 | Fast and Low-RAM-Footprint Indexing for Data Deduplication - The subject disclosure is directed towards a data deduplication technology in which a hash index service's index maintains a hash index in a secondary storage device such as a hard drive, along with a compact index table and look-ahead cache in RAM that operate to reduce the I/O to access the secondary storage device during deduplication operations. Also described is a session cache for maintaining data during a deduplication session, and encoding of a read-only compact index table for efficiency. | 11-10-2011 |
20110283085 | SYSTEM AND METHOD FOR END-TO-END DATA INTEGRITY IN A NETWORK FILE SYSTEM - A computer readable storage medium, embodying instructions executable by a computer to perform a method, the method including: validating a memory write of data segments using a first number of leaf hashes of a first hash tree, where each of the first number of leaf hashes is associated with one of the data segments of a first block size, generating interior node hashes based on the first number of leaf hashes, where each of the interior node hashes is associated with a second block size, generating a first root hash using the interior node hashes, where the first root hash is associated with a remote procedure call size, transmitting the first root rash and the data segments to a network file system, where the transmission is performed using the remote procedure call size, and validating the transmission of the data segments using the first root hash. | 11-17-2011 |
20110307683 | INDEX ENTRY EVICTION - Systems, methods embodied on computer-readable media, and other embodiments associated with index entry eviction are described. One example method includes selecting an index entry for eviction from a bucket of index entries based on a time value, a utility value, and a precedence value. A precedence value may be a value associated with an index entry that is static over time. Additionally, results of a function that compares two precedence values may be static over time. The example method may also include providing an index entry identifier that identifies the index entry. | 12-15-2011 |
20120030446 | METHOD AND SYSTEM FOR PROVIDING DISTRIBUTED PROGRAMMING ENVIRONMENT USING DISTRIBUTED SPACES, AND COMPUTER READABLE RECORDING MEDIUM - Disclosed herein are a method, a system, and a computer-readable recording medium for providing distributed programming environment by using a distributed space. | 02-02-2012 |
20120060014 | ELECTRONIC DEVICE AND METHOD FOR PROTECTING ELECTRONIC KEYS USING THE SAME - A method for protecting electronic keys sets a plurality of hash functions, divides an electronic key into a plurality of key segments, creates a data storage structure for each of the key segments, and calculates a hash address for each of the key segments of the electronic key using each of the hash functions. The method further obtains a plurality of hash addresses of the plurality of key segments corresponding to the plurality of hash functions, stores information of the data storage structure of each key segment in a hash table according to the hash address of the key segment corresponding to one of the hash functions. | 03-08-2012 |
20120102298 | Low RAM Space, High-Throughput Persistent Key-Value Store using Secondary Memory - Described is using flash memory (or other secondary storage), RAM-based data structures and mechanisms to access key-value pairs stored in the flash memory using only a low RAM space footprint. A mapping (e.g. hash) function maps key-value pairs to a slot in a RAM-based index. The slot includes a pointer that points to a bucket of records on flash memory that each had keys that mapped to the slot. The bucket of records is arranged as a linear-chained linked list, e.g., with pointers from the most-recently written record to the earliest written record. Also described are compacting non-contiguous records of a bucket onto a single flash page, and garbage collection. Still further described is load balancing to reduce variation in bucket sizes, using a bloom filter per slot to avoid unnecessary searching, and splitting a slot into sub-slots. | 04-26-2012 |
20120173844 | APPARATUS AND METHOD FOR DETERMINING A CACHE LINE IN AN N-WAY SET ASSOCIATIVE CACHE - A method and apparatus for determining a cache line in an N-way set associative cache are disclosed. In one example embodiment, a key associated with a cache line is obtained. A main hash is generated using a main hash function on the key. An auxiliary hash is generated using an auxiliary hash function on the key. A bucket in a main hash table residing in an external memory is determined using the main hash. An entry in a bucket in an auxiliary hash table residing in an internal memory is determined using the determined bucket and the auxiliary hash. The cache line in the main hash table is determined using the determined entry in the auxiliary hash table. | 07-05-2012 |
20120173845 | Distributed Cache for Graph Data - A distributed caching system for storing and serving information modeled as a graph that includes nodes and edges that define associations or relationships between nodes that the edges connect in the graph. | 07-05-2012 |
20120226889 | SYSTEM AND METHOD FOR DETERMINING EXACT LOCATION RESULTS USING HASH ENCODING OF MULTI-DIMENSIONED DATA - Aspects of the present invention are directed to system and methods for optimizing identification of locations within a search area using hash values. A hash value represents location information in a single dimension format. Computing points around some location includes calculating an identification boundary that surrounds the location of interest based on the location's hash value. The identification boundary is expanded until it exceeds a search area defined by the location and a distance. Points around the location can be identified based on having associated hash values that fall within the identification boundary. Hashing operations let a system reduce the geometric work (i.e. searching inside boundaries) and processing required, by computing straightforward operations on hash quantities (e.g. searching a linear range of geohashes), instead of, for example, point to point comparisons. | 09-06-2012 |
20120260060 | MEMORY DEVICE, COMPUTER SYSTEM INCLUDING THE SAME, AND OPERATING METHODS THEREOF - A memory device includes a hash table storing a hash value, a bit value, and a page address for each of a plurality of pages, a memory cell unit configured to store the pages and output contents corresponding to the page addresses of the pages having a same hash value, and a controller including a comparator configured to compare the contents output from the memory cell unit and change at least one bit value associated with a respective one of the pages upon determining that the contents of the pages are the same. | 10-11-2012 |
20120317395 | LOW LATENCY REPLICATION TECHNIQUES WITH CONTENT ADDRESSABLE STORAGE - A CAS data storage method and apparatus comprising: receiving input data including a succession of data items with corresponding logical addresses at a source CAS data storage space for storage therein and for replication at a destination CAS data storage space, generating a hash key for each data item at the source storage space, comparing respective hash keys with hash keys stored at a hash key storage table, to determine whether respective further data items are already present at the destination storage device; transferring respective data items to the destination storage space if no match is made to a hash key stored at the hash key storage table, but not transferring respective further data items if a match is made to a hash key stored at the hash key storage table, thereby transferring to the destination storage space only unique data items. | 12-13-2012 |
20130036292 | MEMORY CONFIGURATION APPARATUS FOR SUPPORTING ARBITRARY MEMORY SET AND METHOD THEREOF - An apparatus and a method for supporting a memory set of an arbitrary number are provided. The apparatus includes a storage, a memory manager, and a controller. The storage is configured with the memory set of the arbitrary number. The memory manager indexes the memory set of the arbitrary number based on a Hash function and an index. The controller controls the memory manager. | 02-07-2013 |
20130097405 | APPARATUS AND METHOD FOR ABSTRACT MEMORY ADDRESSING - An apparatus for abstract memory addressing. A processor for generating an abstract memory address. A base register for storing a base memory address. An adder for adding the base memory address to the abstract memory address and generating a physical address for a device memory. A pointer register for storing the physical address, wherein the pointer register is directly coupled to the device memory. | 04-18-2013 |
20130111187 | DATA READ AND WRITE METHOD AND APPARATUS, AND STORAGE SYSTEM | 05-02-2013 |
20130151810 | HYBRID HASH TABLES - A hash table system having a first hash table and a second hash table is provided. The first hash table may be in-memory and the second hash table may be on-disk. Inserting an entry to the hash table system comprises inserting the entry into the first hash table, and, when the first hash table reaches a threshold load factor, flushing entries into the second hash table. Flushing the first hash table into the second hash table may comprise sequentially flushing the first hash table segments into corresponding second hash table segments. When looking up a key/value pair corresponding to a selected key in the hash table system, the system checks both the first and second hash tables for values corresponding to the selected key. The first and second hash tables may be divided into hash table segments and collision policies may be implemented within the hash table segments. | 06-13-2013 |
20130185536 | HASH-BASED MANAGING OF STORAGE IDENTIFIERS - Managing storage identifiers in a pool is facilitated by providing a hashing-based management protocol in association with a stack which accommodates storage identifiers of the pool. The hashing-based management protocol includes: based on a request, popping a storage identifier from the stack without evaluating for update of a hash link associated with the stack, potentially allowing the hash link to become inconsistent with storage identifiers remaining in the stack; and based on return of a freed storage identifier to the stack, hashing the freed storage identifier and identifying whether there is an inconsistency in the hash link related to return of the freed storage identifier, and based on identifying the inconsistency, one of updating the hash link to remove the inconsistency, or indicating, where ascertained, that the freed storage identifier is a duplicate storage identifier. | 07-18-2013 |
20130185537 | HASH TABLE USING HASH TABLE BANKS - A hash table method and structure comprises a processor that receives a plurality of access requests for access to a storage device. The processor performs a plurality of hash processes on the access requests to generate a first number of addresses for each access request. Such addresses are within a full address range. Hash table banks are operatively connected to the processor. The hash table banks form the storage device. Each of the hash table banks has a plurality of input ports. Specifically, each of the hash table banks has less input ports than the first number of addresses for each access request. The processor provides the addresses to the hash table banks, and each of the hash table banks stores pointers corresponding to a different limited range of addresses within the full address range (each of the different limited range of addresses is less than the full address range). | 07-18-2013 |
20130238876 | Efficient Inline Data De-Duplication on a Storage System - A mechanism is provided in a storage system for efficient inline data de-duplication. The mechanism receives a write command and a hash key for a portion of data to be written from an application host to a write address. The write command indicates whether the application host is tolerant or intolerant to data loss. Responsive to the write command indicating the application host is tolerant to data loss, the mechanism performs a hash key lookup in a hash index. The mechanism determines whether the portion of data has previously been written to the storage system. Responsive to determining the portion of data has previously been written to the storage system, the mechanism stores a pointer to the previously written data at the write address. | 09-12-2013 |
20140136813 | TRANSACTIONAL MEMORY THAT PERFORMS A TCAM 32-BIT LOOKUP OPERATION - A transactional memory (TM) receives a lookup command across a bus from a processor. The command includes a memory address. In response to the command, the TM pulls an input value (IV). The memory address is used to read a word containing multiple result values (RVs), multiple reference values, and multiple mask values from memory. A selecting circuit within the TM uses a starting bit position and a mask size to select a portion of the IV. The portion of the IV is a lookup key value (LKV). The LKV is masked by each mask value thereby generating multiple masked values. Each masked value is compared to a reference value thereby generating multiple comparison values. A lookup table generates a selector value based upon the comparison values. A result value is selected based on the selector value. The selected result value is then communicated to the processor via the bus. | 05-15-2014 |
20140181465 | INCREASED IN-LINE DEDUPLICATION EFFICIENCY - Exemplary embodiments for increased in-line deduplication efficiency in a computing environment are provided. Embodiments include incrementing the size of data samples from fixed size data chunks for each nth iteration for reaching a full size of an object requested for in-line deduplication, calculating in nth iterations hash values on data samples from fixed size data chunks extracted from the object, and matching in a nth hash index table the calculated nth iteration hash values for the data samples from the fixed size data chunks with a corresponding hash value of existing objects in storage, wherein the nth hash index table is built for each nth iteration of the data samples belonging to the fixed data chunks. | 06-26-2014 |
20140215181 | QUEUE REQUEST ORDERING SYSTEMS AND METHODS - The described systems and methods can facilitate efficient and effective information storage. In one embodiment a system includes a hash component, a queue request order component and a request queue component. The hash component is operable to hash a request indication. The queue request order component is operable to track a queue request order. The request queue component is operable to queue and forward requests in accordance with direction from the queue request order component. In one embodiment, the storage component maintains a request without stalling a request in an aliasing condition. | 07-31-2014 |
20150032989 | Methods, Systems, and Products for Hashing Using Twisted Tabulation - Methods, systems, and products describe a robust solution for the dictionary problem of data structures. A hash function based on tabulation is twisted to utilize an additional xoring operation and a shift. This twisted tabulation offers strong robustness guarantees over a set of queries in both linear probing and chaining. | 01-29-2015 |
20150074372 | Apparatus and Method for Hash Table Access - A system and method for accessing a hash table are provided. A hash table includes buckets where each bucket includes multiple chains. When a single instruction multiple data (SIMD) processor receives a group of threads configured to execute a key look-up instruction that accesses an element in the hash table, the threads executing on the SIMD processor identify a bucket that stores a key in the key look-up instruction. Once identified, the threads in the group traverse the multiple chains in the bucket, such that the elements at a chain level in the multiple chains are traversed in parallel. The traversal continues until a key look-up succeeds or fails. | 03-12-2015 |
20150082002 | DYNAMIC HETEROGENEOUS HASHING FUNCTIONS IN RANGES OF SYSTEM MEMORY ADDRESSING SPACE - Dynamic heterogeneous hashing function technology for balancing memory requests between multiple memory channels is described. A processor includes functional units and multiple memory channels, and a memory controller unit (MCU) coupled between them. The MCU includes a dynamic heterogeneous hashing module (DHHM) that includes multiple specific-purpose hashing function blocks that define different interleaving sequences for memory requests to alternately access the multiple memory channels. The DHHM also includes a hashing-function selection block. The hashing-function selection block is operable to identify a requesting functional unit originating a current memory request and to select one of the specific-purpose hashing function blocks for the current memory request in view of the requesting functional unit. | 03-19-2015 |
20150121034 | Systems and Methods for Implementing Low-Latency Lookup Circuits Using Multiple Hash Functions - A lookup circuit evaluates hash functions that map keys to addresses in lookup tables. The circuit may include multiple hash function sub-circuits, each of which applies a respective hash function to an input key value, producing a hash value. Each hash function sub-circuit (which may include a programmable hash table) may multiply bit vectors representing key values by a bit matrix and add a constant bit vector to the results. Each hash value may be used to access a location in a lookup table in memory to obtain its contents (e.g., a key and associated data). The circuit may include a selection sub-circuit that selects the data of one of the identified locations as an output of the lookup circuit (e.g., one whose key matches the input key). The circuit may modify obtained data prior to its selection and may output a signal indicating the validity of input keys. | 04-30-2015 |
20150121035 | Systems and Methods for Implementing Low-Latency Lookup Circuits Using Sparse Hash Functions - A lookup circuit evaluates hash functions that map keys to addresses in lookup tables. The circuit may include multiple hash function sub-circuits, each of which applies a respective hash function to an input key value, producing a hash value. Each hash function sub-circuit may multiply bit vectors representing key values by a sparse bit matrix and may add a constant bit vector to the results. The hash function sub-circuits may be constructed using odd-parity circuits that accept as inputs subsets of the bits of the bit vectors representing the key values. The sparse bit matrices may be chosen or generated so that there are at least twice as many 0-bits per row as 1-bits or there is an upper bound on the number of 1-bits per row. Using sparse bit matrices in the hash function sub-circuits may allow the lookup circuit to perform lookup operations with very low latency. | 04-30-2015 |
20150363328 | METHODS AND APPARATUS FOR DATA PROCESSING - Data processing methods and apparatus for efficiently storing and retrieving data, e.g., blocks of data, to and from memory. The data processing including, e.g., techniques such as using linked lists and/or tables for tracking duplicate data blocks received for storage, the use of lossless data compression, and de-duplication based on comparing hash values, compressed data block sizes, and/or bit by bit comparisons of the block of data to be stored and previously stored blocks of data. For example, one embodiment of a method in accordance with the present invention includes generating a hash value from a block of data to be stored and a hash function; compressing the block of data to be stored to generate a compressed block of data, said compressed block of data being of a first size; comparing said generated hash value to hash values corresponding to previously stored blocks of data; and when said generated hash value matches a hash value of a previously stored block of data, determining if the block of data to be stored matches the previously stored block of data with the matching hash value. In some embodiments of the present invention, the aforementioned determining step includes comparing said first size to the size of said previously stored block of data with the matching hash value; and determining that said block of data to be stored does not match said previously stored block of data when said first size does not match the size of said stored block of data. | 12-17-2015 |
20160124864 | MEMORY ADDRESSING MECHANISM USING A BUFFER OF A HIERARCHY OF COLLISION FREE HASH TABLES - Methods and apparatuses for insertion, searching, deletion, and load balancing using a hierarchical series of hash tables are described herein. The techniques disclosed provide nearly collision free or deterministic hash functions using a bitmap as a pre-filter. The hash functions have different priorities and one hashing result will be used to perform main memory access. For the hash functions, two hash bitmaps are used to store valid data and collision information. There is no collision allowed in the hash tables except for the hash table with the lowest priority. The hash tables and bitmaps may be stored in one or more caches in (e.g., a cache of a CPU, Block RAMs in FPGAs, etc.) which perform much faster than main memory. | 05-05-2016 |
20160124865 | DYNAMIC EVALUATION AND ADAPTION OF HARDWARE HASH FUNCTIONS - Creating hash values based on bit values of an input vector. An apparatus includes a first and a second hash table, a first and second hash function generator adapted to configure a respective hash function for a creation of a first and second hash value based on the bit values of the input vector. The hash values are stored in the respective hash tables. An evaluation unit includes a comparison unit to compare a respective effectiveness of the first hash function and the second hash function, and an exchanging unit responsive to the comparison unit adapted to replace the first hash function by the second hash function. | 05-05-2016 |
20160147450 | HIGH-PERFORMANCE HASH JOINS USING MEMORY WITH EXTENSIVE INTERNAL PARALLELISM - In one embodiment, a computer-implemented method includes issuing, to a DRAM with EIP, a first group of two or more load requests to load data from a hash table constructed from hashed join-key values of a dimension table for a hash-join procedure. A second group of two or more load requests is issued. First response data is received, responsive to the first group of load requests. The first response data is processed while awaiting second response data responsive to the second group. Processing the first response data includes identifying matches between the join-key values corresponding to entries in the load requests of the first group and one or more hash buckets in the first response data. The size of the second group of load requests is selected such that a time for processing the first response data is approximately equal to the latency in receiving the second response data. | 05-26-2016 |
20160147451 | HIGH-PERFORMANCE HASH JOINS USING MEMORY WITH EXTENSIVE INTERNAL PARALLELISM - In one embodiment, a computer-implemented method includes issuing, to a DRAM with EIP, a first group of two or more load requests to load data from a hash table constructed from hashed join-key values of a dimension table for a hash-join procedure. A second group of two or more load requests is issued. First response data is received, responsive to the first group of load requests. The first response data is processed while awaiting second response data responsive to the second group. Processing the first response data includes identifying matches between the join-key values corresponding to entries in the load requests of the first group and one or more hash buckets in the first response data. The size of the second group of load requests is selected such that a time for processing the first response data is approximately equal to the latency in receiving the second response data. | 05-26-2016 |