Yioop - PHP Search Engine

-- Feb 26 In-Class Exercise

Resource Description for EFCF4804-4862-49C0-9942-CD1A66B35766.png

((resource:EFCF4804-4862-49C0-9942-CD1A66B35766.png|Resource Description for EFCF4804-4862-49C0-9942-CD1A66B35766.png))

-- Feb 26 In-Class Exercise

Number of blocks to index EyeColor and HairColor = ?

Number of bytes to index EyeColor and HairColor = ?

Number of bytes to index EyeColor = ?

Number of bytes for indirection = 1,000,000 * 6 bytes = 6000000 bytes

Number of bytes for keys = 3 * (4 bytes + 6 bytes) = 30 bytes

Number of bytes to index EyeColor = 6000000 + 30 = 6000030 bytes

Number of bytes to index HairColor = ?

Number of bytes for indirection = 1,000,000 * 6 bytes = 6000000 bytes

Number of bytes for keys = 5 * (4 bytes + 6 bytes) = 50 bytes

Number of bytes to index HairColor = 6000000 + 50 = 6000050 bytes

Number of bytes to index EyeColor and HairColor = 6000030 + 6000050 = 12000080 bytes

Number of blocks to index EyeColor and HairColor = 12000080 / 4096 bytes = 2930 blocks

Size of bitmapped index of EyeColor and HairColor = ?

Size of bitmapped index of EyeColor = 1000000 rows * 3 values * 1 byte / 8 bits * 1 block / 4096 bytes = 92 blocks

Size of bitmapped index of HairColor = 1000000 rows * 5 values * 1 byte / 8 bits * 1 block / 4096 bytes = 153 blocks

Size of bitmapped index of EyeColor and HairColor = 92 + 153 = 245 blocks

(Edited: 2020-02-26)

Number of blocks to index EyeColor and HairColor = ? Number of bytes to index EyeColor and HairColor = ? Number of bytes to index EyeColor = ? Number of bytes for indirection = 1,000,000 * 6 bytes = 6000000 bytes Number of bytes for keys = 3 * (4 bytes + 6 bytes) = 30 bytes Number of bytes to index EyeColor = 6000000 + 30 = 6000030 bytes Number of bytes to index HairColor = ? Number of bytes for indirection = 1,000,000 * 6 bytes = 6000000 bytes Number of bytes for keys = 5 * (4 bytes + 6 bytes) = 50 bytes Number of bytes to index HairColor = 6000000 + 50 = 6000050 bytes Number of bytes to index EyeColor and HairColor = 6000030 + 6000050 = 12000080 bytes Number of blocks to index EyeColor and HairColor = 12000080 / 4096 bytes = 2930 blocks Size of bitmapped index of EyeColor and HairColor = ? Size of bitmapped index of EyeColor = 1000000 rows * 3 values * 1 byte / 8 bits * 1 block / 4096 bytes = 92 blocks Size of bitmapped index of HairColor = 1000000 rows * 5 values * 1 byte / 8 bits * 1 block / 4096 bytes = 153 blocks Size of bitmapped index of EyeColor and HairColor = 92 + 153 = 245 blocks

-- Feb 26 In-Class Exercise

1) # of blocks on both eye color & hair color

1,000,000 bits for each eye color Convert to bytes: 1,000,000 bits * 1 byte / 8 bits = 125,000 bytes Calculate # of blocks: 125,000 bytes / 4096 bytes = 30.5175781 ~ 30 blocks

2) secondary index w/ indirection

Eye color: 1,000,000 bits for each eye color * 3 possible eye colors = 3,000,000 bits Convert to bytes: 3,000,000 bits / 8 bits = 375,000 bytes Calculate # of blocks: 375,000 bytes / 4096 bytes = 91.55 blocks ~ 92 blocks

Hair color: 1,000,000 bits for each hair color * 5 possible hair colors = 5,000,000 bits Convert to bytes: 5,000,000 bits / 8 bits = 625,000 bytes Calculate # of blocks: 625,000 bytes / 4096 bytes = 152.58 ~ 153 blocks

Size of bitmapped index of eye color + hair color = 92 + 153 = 245 blocks

1) # of blocks on both eye color & hair color 1,000,000 bits for each eye color Convert to bytes: 1,000,000 bits * 1 byte / 8 bits = 125,000 bytes Calculate # of blocks: 125,000 bytes / 4096 bytes = 30.5175781 ~ 30 blocks 2) secondary index w/ indirection Eye color: 1,000,000 bits for each eye color * 3 possible eye colors = 3,000,000 bits Convert to bytes: 3,000,000 bits / 8 bits = 375,000 bytes Calculate # of blocks: 375,000 bytes / 4096 bytes = 91.55 blocks ~ 92 blocks Hair color: 1,000,000 bits for each hair color * 5 possible hair colors = 5,000,000 bits Convert to bytes: 5,000,000 bits / 8 bits = 625,000 bytes Calculate # of blocks: 625,000 bytes / 4096 bytes = 152.58 ~ 153 blocks Size of bitmapped index of eye color + hair color = 92 + 153 = 245 blocks

-- Feb 26 In-Class Exercise

Eyecolor:

There are 1,000,000 records and record pointer is 6 bytes => 1,000,000 * 6 = 6,000,000 bytes

There are three possible values for eyecolor and each consists of an integer (4 bytes) and a record pointer (6 bytes) => (4 + 6) * 3 = 30 bytes

Therefore, total is 6,000,000 + 30 = 60,000,030 bytes

One block is 4096 bytes => 60,000,030 bytes / 4096 bytes = 1,465 blocks

Haircolor:

Same as eyecolor, there is a total of 6,000,000 bytes for 1,000,000 records.

There are 5 possible values for haircolor and each consists of an integer (4 bytes) and a record pointer (6 bytes) => (4 + 6) * 5 = 50 bytes

Therefore, total is 6,000,000 + 50 = 60,000,050 bytes

One block is 4096 bytes => 60,000,050 bytes / 4096 bytes = 1,465 blocks

Combine both eyecolor and haircolor together, then the total of blocks needed = 1,465 + 1,465 = 2,930 blocks

Bitmap Index:

Eyecolor:

There are 1,000,000 bits for each eyecolor => 1,000,000 * 3 = 3,000,000 bits = 375,000 bytes for three possible values of eyecolor.

One block is 4096 bytes => 375,000 bytes / 4096 bytes = 92 blocks

Haircolor:

There are 1,000,000 bits for each haircolor => 1,000,000 * 5 = 5,000,000 bits = 625,000 bytes for five possible values of haircolor.

One block is 4096 bytes => 625,000 bytes / 4096 bytes = 153 blocks

Therefore, number of blocks needed for bitmap index on both eyecolor and haircolor = 92 + 153 = 245 blocks

(Edited: 2020-02-26)

Eyecolor: There are 1,000,000 records and record pointer is 6 bytes => 1,000,000 * 6 = 6,000,000 bytes There are three possible values for eyecolor and each consists of an integer (4 bytes) and a record pointer (6 bytes) => (4 + 6) * 3 = 30 bytes Therefore, total is 6,000,000 + 30 = 60,000,030 bytes One block is 4096 bytes => 60,000,030 bytes / 4096 bytes = 1,465 blocks Haircolor: Same as eyecolor, there is a total of 6,000,000 bytes for 1,000,000 records. There are 5 possible values for haircolor and each consists of an integer (4 bytes) and a record pointer (6 bytes) => (4 + 6) * 5 = 50 bytes Therefore, total is 6,000,000 + 50 = 60,000,050 bytes One block is 4096 bytes => 60,000,050 bytes / 4096 bytes = 1,465 blocks Combine both eyecolor and haircolor together, then the total of blocks needed = 1,465 + 1,465 = 2,930 blocks Bitmap Index: Eyecolor: There are 1,000,000 bits for each eyecolor => 1,000,000 * 3 = 3,000,000 bits = 375,000 bytes for three possible values of eyecolor. One block is 4096 bytes => 375,000 bytes / 4096 bytes = 92 blocks Haircolor: There are 1,000,000 bits for each haircolor => 1,000,000 * 5 = 5,000,000 bits = 625,000 bytes for five possible values of haircolor. One block is 4096 bytes => 625,000 bytes / 4096 bytes = 153 blocks Therefore, number of blocks needed for bitmap index on both eyecolor and haircolor = 92 + 153 = 245 blocks

-- Feb 26 In-Class Exercise

Resource Description for IMG_3903.HEIC

((resource:IMG_3903.HEIC|Resource Description for IMG_3903.HEIC))

-- Feb 26 In-Class Exercise

 1) We need 2 sets of record pointers, one for the EyeColor and one for the HairColor. That is 2,000,000 records and each is 6 bytes which gives 12,000,000 bytes. Then we 
 have each EyeColor and HairColor which will each take 4 bytes + 6 bytes (for the record pointers). That is an extra 8 * (10 
 bytes) = 80 bytes. So 12,000,080 bytes / 
 4096 bytes = 2930 blocks.

 2) We need 1,000,000 bits for each EyeColor and HairColor. That means we have a total of 8 * (1,000,000 bits) = 1,000,000 
 bytes. So 1,000,000 bytes / 4096 bytes 
 = 245 blocks

(Edited: 2020-02-26)

1) We need 2 sets of record pointers, one for the EyeColor and one for the HairColor. That is 2,000,000 records and each is 6 bytes which gives 12,000,000 bytes. Then we have each EyeColor and HairColor which will each take 4 bytes + 6 bytes (for the record pointers). That is an extra 8 * (10 bytes) = 80 bytes. So 12,000,080 bytes / 4096 bytes = 2930 blocks. 2) We need 1,000,000 bits for each EyeColor and HairColor. That means we have a total of 8 * (1,000,000 bits) = 1,000,000 bytes. So 1,000,000 bytes / 4096 bytes = 245 blocks

-- Feb 26 In-Class Exercise

Secondary Index: Eye Color (4 bytes*3) + (6 bytes*3) + (1,000,000*6) = 6,000,030 Hair Color = (4 bytes * 5) + (6 bytes*5) + (1,000,000*6) = 6,000,050

of blocks = 12,000,080 bytes/ 4096 bytes = about 2,930 blocks

Bitmap Index: 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 = about 245 blocks

'''Secondary Index:''' Eye Color (4 bytes*3) + (6 bytes*3) + (1,000,000*6) = 6,000,030 Hair Color = (4 bytes * 5) + (6 bytes*5) + (1,000,000*6) = 6,000,050 # of blocks = 12,000,080 bytes/ 4096 bytes = about '''2,930 blocks''' '''Bitmap Index:''' 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 = about '''245 blocks'''

-- Feb 26 In-Class Exercise

The number of blocks needed to support an index on hair and eye color using:

A secondary index with indirection -

3 unique values for eye color * 4 bytes to represent int + 1000000 records * 6 bytes to represent record pointers = 6,000,012 bytes to represent index on eye color 5 unique values for hair color * 4 bytes to represent int + 1000000 records * 6 bytes to represent record pointers = 6,000,020 bytes to represent index on hair color -> total 12,000,032 bytes to represent index on hair and eye color / 4096 bytes per block -> 2929.69 ~> 2930 blocks

A bit mapped index -

1000000 rows * 3 unique values for eye color + 3 unique values for eye color * 4 bytes to represent int = 3000012 bits / 8 bits per byte = 375001.5 bytes to represent bitmap index for eye color 1000000 rows * 5 unique values for hair color + 5 unique values for hair color * 4 bytes to represent int = 5000020 bites / 8 bits per byte = 625002.5 bytes to represent bitmap index for hair color -> total 1,000,004 bytes to represent bit map index for eye and hair color / 4096 bytes per block -> 244.14 ~> 245 blocks

(Edited: 2020-03-01)

The number of blocks needed to support an index on hair and eye color using: A secondary index with indirection - 3 unique values for eye color * 4 bytes to represent int + 1000000 records * 6 bytes to represent record pointers = 6,000,012 bytes to represent index on eye color 5 unique values for hair color * 4 bytes to represent int + 1000000 records * 6 bytes to represent record pointers = 6,000,020 bytes to represent index on hair color -> total 12,000,032 bytes to represent index on hair and eye color / 4096 bytes per block -> 2929.69 ~> 2930 blocks A bit mapped index - 1000000 rows * 3 unique values for eye color + 3 unique values for eye color * 4 bytes to represent int = 3000012 bits / 8 bits per byte = 375001.5 bytes to represent bitmap index for eye color 1000000 rows * 5 unique values for hair color + 5 unique values for hair color * 4 bytes to represent int = 5000020 bites / 8 bits per byte = 625002.5 bytes to represent bitmap index for hair color -> total 1,000,004 bytes to represent bit map index for eye and hair color / 4096 bytes per block -> 244.14 ~> 245 blocks

-- Feb 26 In-Class Exercise

 1) Secondary Index with Indirection
 eye color: An integer is 4 bytes and a record pointer is 6 bytes. 
            4 + 6 = 10 bytes
            There are three possible eye color values.
            3 * 10 bytes = 30 bytes
            There are 1,000,000 records.
            6 bytes * 1,000,000 = 6,000,000
            Total: 6,000,000 + 30 = 6,000,030 bytes
            There are 4096 bytes/block.
            6,000,030/ 4096 = 1,464.8 -> 1, 465 blocks
 hair color:There are five possible hair color values.
            5 * 10 bytes = 50 bytes.
            Total: 6,000,000 + 50 = 6,000,050 bytes
            6,000,050/4096 = 1,464.8 --> 1,465 blocks
 Total: 2,929 blocks
 
 2) Bitmap Index
 eye color: There are 3 possible eye color values.
            3 * 1,000,000 bits = 3,000,000 bits -> 375,000 bytes
            375,000/4096 = 91.5 -> 92 blocks
 hair color: There are 5 possible hair color values.
             5 * 1,000,000 bits = 5,000,000 bits -> 625,000 bytes
             625,000/4096 = 152.5 -> 153 blocks
 Total: 245 blocks

1) Secondary Index with Indirection eye color: An integer is 4 bytes and a record pointer is 6 bytes. 4 + 6 = 10 bytes There are three possible eye color values. 3 * 10 bytes = 30 bytes There are 1,000,000 records. 6 bytes * 1,000,000 = 6,000,000 Total: 6,000,000 + 30 = 6,000,030 bytes There are 4096 bytes/block. 6,000,030/ 4096 = 1,464.8 -> 1, 465 blocks hair color:There are five possible hair color values. 5 * 10 bytes = 50 bytes. Total: 6,000,000 + 50 = 6,000,050 bytes 6,000,050/4096 = 1,464.8 --> 1,465 blocks Total: 2,929 blocks 2) Bitmap Index eye color: There are 3 possible eye color values. 3 * 1,000,000 bits = 3,000,000 bits -> 375,000 bytes 375,000/4096 = 91.5 -> 92 blocks hair color: There are 5 possible hair color values. 5 * 1,000,000 bits = 5,000,000 bits -> 625,000 bytes 625,000/4096 = 152.5 -> 153 blocks Total: 245 blocks

-- Feb 26 In-Class Exercise

(Edited: 2020-03-02)

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