Yioop - PHP Search Engine

Feb 26 In-Class Exercise.

Post your solutions to the Feb 26 In-Class Exercise to this thread.

Best,

Chris

Post your solutions to the Feb 26 In-Class Exercise to this thread. Best, Chris

-- Feb 26 In-Class Exercise

indirection layer contains 1 pointer for each of 1mil records = 6mil bytes for eye color: 1 pointer + 1 integer for each of 3 possible eye colors = (4+6)*3 = 30 bytes total for eye color: 6,000,030 bytes

second indirection layer: 6 mil bytes for hair color: 1 pointer + 1 integer for each of 5 possible hair colors = (4+6)*5 = 50 bytes total for hair color = 6,000,050 bytes

total blocks = 12,000,080/4096 = 2930 blocks

(Edited: 2020-02-26)

indirection layer contains 1 pointer for each of 1mil records = 6mil bytes for eye color: 1 pointer + 1 integer for each of 3 possible eye colors = (4+6)*3 = 30 bytes total for eye color: 6,000,030 bytes second indirection layer: 6 mil bytes for hair color: 1 pointer + 1 integer for each of 5 possible hair colors = (4+6)*5 = 50 bytes total for hair color = 6,000,050 bytes total blocks = 12,000,080/4096 = 2930 blocks

-- Feb 26 In-Class Exercise

(Edited: 2020-02-26)

((resource:IMG_7900.jpg|Resource Description for IMG_7900.jpg))

-- Feb 26 In-Class Exercise

EyeColor:

6 bytes record pointer * 1,000,000 records = 6,000,000 bytes

3 possible values * (4 bytes integer + 6 bytes record pointer) = 30 bytes

6,000,030 bytes / 4096 bytes/block = 1,465 blocks

HairColor:

Same as EyeColor for record pointers + 5 possible values * (4 bytes integer + 6 bytes record pointer) = 50 bytes

6,000,050 bytes / 4096 bytes/block = 1,465 blocks

1,465 blocks * 2 = 2,930 blocks

2,930 blocks for 1,000,000 records with 2 indexes on EyeColor & HairColor

Bitmap Index:

	EyeColor
		We need 1,000,000 bits * 3 possible values = 3,000,000 bits
		3,000,000 bits * 1 byte/8 bits = 375,000 bytes
		375,000 bytes / 4096 bytes/block = 92 blocks
	HairColor
		We need 1,000,000 bits * 5 possible values = 5,000,000 bits
		5,000,000 bits * 1 byte/8 bits = 625,000 bytes
		625,000 bytes / 4096 bytes/block = 153 blocks

In total, we need 92 + 153 blocks = 245 blocks for a bitmap index

(Edited: 2020-02-26)

EyeColor: 6 bytes record pointer * 1,000,000 records = 6,000,000 bytes 3 possible values * (4 bytes integer + 6 bytes record pointer) = 30 bytes 6,000,030 bytes / 4096 bytes/block = 1,465 blocks HairColor: Same as EyeColor for record pointers + 5 possible values * (4 bytes integer + 6 bytes record pointer) = 50 bytes 6,000,050 bytes / 4096 bytes/block = 1,465 blocks 1,465 blocks * 2 = 2,930 blocks 2,930 blocks for 1,000,000 records with 2 indexes on EyeColor & HairColor Bitmap Index: EyeColor We need 1,000,000 bits * 3 possible values = 3,000,000 bits 3,000,000 bits * 1 byte/8 bits = 375,000 bytes 375,000 bytes / 4096 bytes/block = 92 blocks HairColor We need 1,000,000 bits * 5 possible values = 5,000,000 bits 5,000,000 bits * 1 byte/8 bits = 625,000 bytes 625,000 bytes / 4096 bytes/block = 153 blocks In total, we need 92 + 153 blocks = 245 blocks for a bitmap index

-- Feb 26 In-Class Exercise

Resource Description for 2-26InClassExercise3.PNG

((resource:2-26InClassExercise3.PNG|Resource Description for 2-26InClassExercise3.PNG))

-- Feb 26 In-Class Exercise

Eye Color Secondary Index Size =

(4 bytes * 3) + (6 bytes * 3) + (1,000,000 * 6) = 6,000,030B

Hair Color Secondary Index Size =

(4 bytes * 5) + (6 bytes * 5) + (1,000,000 * 6) = 6,000,050B

Sum of Index =

12,000,080 bytes/ 4096 bytes per block = about 2,930 blocks for secondary indexes.

Using Bitmapped Indexes:

Eye Color = (1,000,000 * 3)/8 bits per byte = 375,000 bytes
Hair Color = (1,000,000 * 5)/8 bits per byte = 625,000 bytes
Total bytes = (375,000+625,000)/4096 bytes per block = about 245 blocks .

(Edited: 2020-02-26)

Eye Color Secondary Index Size = * (4 bytes * 3) + (6 bytes * 3) + (1,000,000 * 6) = 6,000,030B Hair Color Secondary Index Size = * (4 bytes * 5) + (6 bytes * 5) + (1,000,000 * 6) = 6,000,050B Sum of Index = * 12,000,080 bytes/ 4096 bytes per block = '''about 2,930 blocks''' for secondary indexes. Using Bitmapped Indexes: * Eye Color = (1,000,000 * 3)/8 bits per byte = 375,000 bytes * Hair Color = (1,000,000 * 5)/8 bits per byte = 625,000 bytes * Total bytes = (375,000+625,000)/4096 bytes per block = '''about 245 blocks'''.

-- Feb 26 In-Class Exercise

EyeColor: 1,000,000 records * 6 bytes record pointer = 6,000,000 bytes. 6000000 + 10 + 10 + 10 = 6,000,030 bytes, where 10 = 4byte + 6byte. 6,000,030 bytes / 4096 bytes/block = 1,465 blocks

HairColor: Same as EyeColor for record pointers + 5 possible values * (4 bytes integer + 6 bytes record pointer) = 50 bytes 6,000,050 bytes / 4096 bytes/block = 1,465 blocks 1,465 blocks * 2 = 2,930 blocks

Bitmap Index:

	EyeColor
		1,000,000 bits * 3 color values = 3,000,000 bits =  375,000 bytes
               since each blcok is 4096bytes, the number of blocks are: 375,000 bytes / 4096 = 92 blocks
	HairColor
		1,000,000 bits * 5 possible values = 5,000,000 bits = 625,000 bytes
		625,000 bytes / 4096 bytes/block = 153 blocks
       Total, 92 + 153 = 245 blocks for a bitmap index

(Edited: 2020-02-26)

EyeColor: 1,000,000 records * 6 bytes record pointer = 6,000,000 bytes. 6000000 + 10 + 10 + 10 = 6,000,030 bytes, where 10 = 4byte + 6byte. 6,000,030 bytes / 4096 bytes/block = 1,465 blocks HairColor: Same as EyeColor for record pointers + 5 possible values * (4 bytes integer + 6 bytes record pointer) = 50 bytes 6,000,050 bytes / 4096 bytes/block = 1,465 blocks 1,465 blocks * 2 = 2,930 blocks Bitmap Index: EyeColor 1,000,000 bits * 3 color values = 3,000,000 bits = 375,000 bytes since each blcok is 4096bytes, the number of blocks are: 375,000 bytes / 4096 = 92 blocks HairColor 1,000,000 bits * 5 possible values = 5,000,000 bits = 625,000 bytes 625,000 bytes / 4096 bytes/block = 153 blocks Total, 92 + 153 = 245 blocks for a bitmap index

-- Feb 26 In-Class Exercise

Given: Ints are 4 bytes, record pointeres are 6 bytes. Eye color can be 0, 1, or 2 Hair color can be 0, 1, 2, 3, 4 We have 1,000,000 records.

Secondary Index with Indirection Eye Color: For eye color, we’ll need 3 ”level-1” indirection pointers at 10 bytes each. Then we’ll need 1, 000, 000 ”level-2” indirection pointers (pointers to the actual records). So we need 6 × 1, 000, 003 bytes for the indirection pointers for eye color. Hair Color : For hair color, we’ll need 5 ”level-1” indirection pointers at 10 bytes each. Then we’ll need 1, 000, 000 ”level-2” indirection pointers (pointers to the actual records). So we need 6 × 1, 000, 005 bytes for the indirection pointers for hair color. Total In total, we’ll need 2929 blocks.

Bitmap Index

 We’ll need 1, 000, 000 × 3 bits for each eye color

We’ll need 1, 000, 000 × 5 bits for each hair color In total, we’ll need 8, 000, 000 bits, which is about 255 blocks.

'''Given:''' Ints are 4 bytes, record pointeres are 6 bytes. Eye color can be 0, 1, or 2 Hair color can be 0, 1, 2, 3, 4 We have 1,000,000 records. ---- '''Secondary Index with Indirection''' '' Eye Color:'' For eye color, we’ll need 3 ”level-1” indirection pointers at 10 bytes each. Then we’ll need 1, 000, 000 ”level-2” indirection pointers (pointers to the actual records). So we need 6 × 1, 000, 003 bytes for the indirection pointers for eye color. '' Hair Color'': For hair color, we’ll need 5 ”level-1” indirection pointers at 10 bytes each. Then we’ll need 1, 000, 000 ”level-2” indirection pointers (pointers to the actual records). So we need 6 × 1, 000, 005 bytes for the indirection pointers for hair color. '' Total'' In total, we’ll need 2929 blocks. ---- '''Bitmap Index''' We’ll need 1, 000, 000 × 3 bits for each eye color We’ll need 1, 000, 000 × 5 bits for each hair color In total, we’ll need 8, 000, 000 bits, which is about 255 blocks.

-- Feb 26 In-Class Exercise

(Edited: 2020-02-27)

((resource:IMG_1822.JPG|Resource Description for IMG_1822.JPG))

-- Feb 26 In-Class Exercise

Resource Description for 01ae74c0c4c7d47205e2998dd9fcce514060127fd5.jpg

((resource:01ae74c0c4c7d47205e2998dd9fcce514060127fd5.jpg|Resource Description for 01ae74c0c4c7d47205e2998dd9fcce514060127fd5.jpg))