COMP9315 week07课堂笔记_bit-sliced index

Signature-based Selection

Descriptor 也叫signature。
从individual attributes里提取并合并信息去组成单个bitstream，捕获tuple的内容。
signature存储在signature file中。每个tuple都有自己的signature。

但signature不会决定record的位置。signature file比data file 更小。

一个signature从一个tuple中“总结”数据。
(codeword是)tuple的每个attribute用m bit长的bitstream，其中k bits设为1。
tuple descriptor(signature)是指把codewords结合起来，比如通过overlaying方式结合(bitwise-OR)。目的是大约一半的bits被置为1。

创建对于attribute A 的k-in-m codeword

//m is length of codeword，k is the number of bits we set to 1
bits codeword(char *attr_value, int m, int k)
{
   
	int nbits=0; //count of set bits
	bits cword =0;
	srandom(hash(attr_value));
	while (nbits < k){
   
		//generate random bit positions 0 to m-1
		int i = random() % m;
		// if cword does not have this set bit 
		if (((1 << i) & cword)	== 0) {
   
		// i<<i--> ith position in 32 bits is 1, and it does bitwise "OR" into codeword.
			cword |= (1 << i);
			nbits++;
		}
	}
	return cword; // m-bits with k 1-bits and m-k 0-bits
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

以上程序将随机的bit position置为1，直到其中k个bits被置为1.

对于每个attribute，我们根据他的值生成codeword。并把这些codewords “or”在一起，获得signature。

bits desc=0
for (i=1li<=n;i++){
   
	bits cw = codeword(A[i])
	desc = desc | cw
1
2
3
4
5