Browse Prior Art Database

Fast and Dynamic Data Structure for Storing ID Value Pairs

IP.com Disclosure Number: IPCOM000200617D
Original Publication Date: 2010-Oct-21
Included in the Prior Art Database: 2010-Oct-26
Document File: 2 page(s) / 73K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

In multithreaded software environments objects have to be stored and shared or accessed by multiple threads. A shared object is stored at one location only and the worker threads get the objects or pointers to the objects from this central location. In order to have the full control over the stored objects it is a common practice to identify such objects via a unique ID (IDentification) string created by the central location. Typically such a central location is nothing more than a hash or binary tree. Both techniques - using hash functions or binary code - have problems when huge numbers of objects have to be stored. Thus, a tree becomes large and to traverse the tree a lot of checks are involved. A hash table is only fast if the hash table size is close to the actual number of stored objects. In the most cases during the creation of the hash table it is not known how many objects will be stored. A dynamic hash resizes the hash table but during this operation the lookup will be affected dramatically. Both the tree and the hash algorithm can only store comparable values. Looking up an object within the above mentioned multithreaded software environment does therefore obviously affect the system performance.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 01 of 2

(This page contains 01 pictures or other non-text object)

(This page contains 00 pictures or other non-text object)

Fast and Dynamic Data Structure for Storing ID Value Pairs

Idea: Frank Wigger, IN-Bangalore

In multithreaded software environments objects have to be stored and shared or accessed by multiple threads. A shared object is stored at one location only and the worker threads get the objects or pointers to the objects from this central location. In order to have the full control over the stored objects it is a common practice to identify such objects via a unique ID (IDentification) string created by the central location. Typically such a central location is nothing more than a hash or binary tree. Both techniques - using hash functions or binary code - have problems when huge numbers of objects have to be stored. Thus, a tree becomes large and to traverse the tree a lot of checks are involved. A hash table is only fast if the hash table size is close to the actual number of stored objects. In the most cases during the creation of the hash table it is not known how many objects will be stored. A dynamic hash resizes the hash table but during this operation the lookup will be affected dramatically. Both the tree and the hash algorithm can only store comparable values. Looking up an object within the above mentioned multithreaded software environment does therefore obviously affect the system performance.

The following proposed solution describes an algorithm that overcomes these limitations. The proposed algorithm stores the objects in a set of blocks (see Figure 1). There are two types of blocks. A data block that stores the data and an address block storing pointers to the sub blocks. A data block has a size of 251 pointers. The address blocks are organized in a tree. The maximum depth of the tree is 3 and a node contains an address block that can store 256 pointers to sub blocks. The data blocks are stored only in the last layer (layer 0). Furthermore, the proposed algorithm creates a unique ID, which has a size of 32 bit. The first byte is used for addressing the address blocks of layer 2. The second byte is than used for addressing the address blocks of layer 1, and the third byte for addressing the data blocks of layer 0. The last byte is the index of the data within the data block. For instance, the generated ID of Object A in Figure 1 is 0x00000002 and for Objec...