Regular Paper

DBSJ Journal,Vol.8, No.2
September 2009―7―日本データベース学会論文誌 Vol.8, No.2
2009年 9月

Regular Paper

DBSJ Journal,Vol.8, No.2
September 2009―8―日本データベース学会論文誌 Vol.8, No.2
2009年 9月

Regular����Paper                    DBSJJournal, Vol.8, No.2
DBSJ Journal,Vol.8,No.2
                                                 September
September 20092009

number using d-left hashing, and then check thecandidates in a constant time. More formally describing,given � � �0,1�� , we calculate � � � � which includes� � � �� ��� for given � � �0,1�� using d-left hashing,where |��| is almost a constant. Then, we check at most�� elements of �� if each of them matches � �� ���. If thematch exists, the server returns the value as �� ���������,the function returns � since there are no matches.

3.3

Fig.1

Example of d-Left Hash Table (d=2, m=8, n=5)

To add a record, feed it to each of the � hash functions
to get the � bucket positions. The incoming record isplaced in the bucket containing the smallest number ofrecords; in case of a tie, the record is the placed into theleft-most bucket. The asymmetry introduced by breaking
ties toward the left actually improves performance, inthat the maximum number of items placed in a bucket issmaller (in a probabilistic sense) when one breaks ties inthis manner [5]. In Fig.1, hash functions generate twobucket position �� ��� � 8 and �� ��� � 1. The number ofthe records of the 1st bucket |��1�| � 1 is smaller thanthat of the 8th bucket |��8�| � �. Therefore, � is inserted
into the 1st bucket ��1�.
In order to retrieve a record in the hash table, feed it toeach of the � hash functions to get � bucket positions.
Then, the contents of � buckets are checked. Since thed-left hashing balances the bucket load, the table canachieve lookup speed with better worst-case performancein practice [7]. To delete a record from the hash table,
search the record to determine which bucket stores therecord. Then, delete the record from the bucket.
To avoid using pointers to reduce memory size, thebucket size � is fixed. The fixed bucket size may result
overflow; however, the probability of overflow is quite low
since the d-left hashing balances the bucket load [6].

3.2

d-left Pre-computation Scheme

The proposed d-left pre-computation scheme has threephases, 1) pre-computing phase, 2) identification phase,and 3) update phase. The pre-computing phase is done
only once. The identification phase and the update phaseare executed for each identification process.
Our scheme is similar to a Bloom pre-computation
scheme [8]. The Bloom pre-computation scheme uses aBloom filter [9]. Since the Bloom filter cannot erase arecord, an update phase of our scheme is quite different
from that of the Bloom pre-computation scheme.
In the proposed scheme, the hash table � and the lastindex �� of a tag � are stored in a memory on the server.

3.3.1

Pre-computing Phase

In pre-computing phase, the server stores an initial
output set ���,� , � , ��,� � for each tag in the d-left hashtable. When a new record is stored in the d-left hash table,
the record is inserted into the least loaded bucket. The
server stores only a pair of ��, �� and � is not stored in
the hash table. Since record insertions of the d-left hashtable may fail, we discuss this problem in the Section 4.1.
Algorithm 1 shows the procedure of pre-computing
phase. ����������, �� is an algorithm which stores ��,� inthe d-left hash table, and described in Algorithm 2.
������������, �� is a function to obtain ��,� .

d-left Hashing for Hash Inverse Calculation

In this subsection, we describe a novel idea to reduce a
memory usage of the d-left hash table. A usually lookup
table, including a d-left hash table must store a pair of akey � and a value � as a record. However, there exists arelation � � ���� for hash inverse calculation � � � �� ���.
Thus, the key � can be calculated from the value �.
In our method, a set of indexes � that can be identified
by the server is given as:� � ���, ��|1 � � � �, �� � 1 � � � �� � ��
The stored data are modified from the pair of ��, �� to �,
where � � � and � � �0,1�� . Since � � �� as mentioned,
it is log|�| � � , and stopping storing makes a large
reduction of memory usage. Since our scheme does notstore � in the table, we need to calculate � from � forevery identification process. However, we only calculate at
most �� records in the � buckets. We can explain theabove idea as follows.
We firstly reduce the candidates to a small constant―9―

Algorithm 1 Pre-computing Phase
1:
2:
3:
4:
5:
6:

��� � � 1 �o � ���� � 0��� � � 1 �o � ������������, ����� ������ ���Algorithm 2 ����������, �������� � � �1, � , ��, � � �1, � , ���� �
1:

2:
3:
4:
5:
6:
7:

� � ������������, ��� � ��g ��� �|���� ����|����,�,��� |���� ����| � � ���������� ��, �� �� ���� ��������

������ ��������o� ���l����� ��������������� Vol.8, No.2
日本データベース学会論文誌 2009Vol.8,
年 No.29月
2009年 9月

Regular Paper

DBSJ Journal,Vol.8, No.2
September 2009― 10 ―

日本データベース学会論文誌 Vol.8, No.2
2009年 9月

Regular Paper

DBSJ Journal,Vol.8, No.2
September 2009― 11 ―

日本データベース学会論文誌 Vol.8, No.2
2009年 9月

Regular PaperDBSJ Journal,Vol.8, No.2
September 2009― 12 ―

日本データベース学会論文誌 Vol.8, No.2
2009年 9月