logging in or signing up about the file organization presentation alanruiz Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 839 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: November 17, 2008 This Presentation is Public Favorites: 0 Presentation Description hi to all this is my presentation!!!!!!!!!!!!!!!! Comments Posting comment... By: ganeshindian (26 month(s) ago) thanks sir!great upload Saving..... Post Reply Close Saving..... Edit Comment Close By: amjadusman (42 month(s) ago) Respected Sir Ruiz Sir I Am a student of MS IT at NUST Pakistan. i have registered in a course titled as "Advance Database Systems". i need ur ppt presentation. pliz forward it to mw . i will be very thankful to u Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript EXTENDIBLE HASHING : EXTENDIBLE HASHING A hash table in which the hash function is the last few bits of the key and the table refers to buckets. Table entries with the same final bits may use the same bucket. If a bucket overflows, it splits, and if only one entry referred to it, the table doubles in size. If a bucket is emptied by deletion, entries using it are changed to refer to an adjoining bucket, and the table may be halved. Extendible hashing is a type of hash system which treats a hash as a bit string, and uses a trie for bucket lookup. Because of the hierarchal nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes. Extendible hashing is a kind of fast indexing technology; it provides with a way of storing structural data records so that each of them can be gotten very quickly. Ruiz, Alan R. CS-304 bucket : bucket An area of storage where items with a common property are stored. Typically tree data structures and sort algorithms use many buckets, one for each group of items. Usually buckets are kept on disk. A bucket is a structure containing an array of records, a count of the number of records actually occupied, and a bucket depth, which indicates the number of significant bits used to address into this bucket. TRIE : TRIE In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. The term trie comes from "retrieval." Following the etymology, the inventor, Edward Fredkin, pronounces it [tri] ("tree") . However, it is usually pronounced [traɪ] ("try"). A trie for keys "t", "to", "te", "tea", "ten", "i", "in", and "inn". : A trie for keys "t", "to", "te", "tea", "ten", "i", "in", and "inn". HASH FUNCTION : HASH FUNCTION A hash function is any well-defined procedure or mathematical function for turning some kind of data into a relatively small integer, that may serve as an index into an array. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes. Hash functions are mostly used to speed up table lookup or data comparison tasks — such as finding items in a database, detecting duplicated or similar records in a large file, finding similar stretches in DNA sequences, and so on. Hash functions are related to (and often confused with) checksums, check digits, fingerprints, , error correcting codes, and cryptographic hash functions. Although these concepts overlap to some extent, each has its own uses and requirements. The HashKeeper database maintained by the National Drug Intelligence Center, for instance, is more aptly described as a catalog of file fingerprints than of hash values. A typical hash function at work : A typical hash function at work Hash table : Hash table In computer science, a hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person's name), find the corresponding value (e.g. that person's telephone number). It works by transforming the key using a hash function into a hash, a number that is used as an index in an array to locate the desired location ("bucket") where the values should be. Hash tables support the efficient insertion of new entries, in expected O(1) time. The time spent in searching depends on the hash function and the load of the hash table; both insertion and search approach O(1) time with well chosen values and hashes. Slide 8: Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees. You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
about the file organization presentation alanruiz Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 839 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: November 17, 2008 This Presentation is Public Favorites: 0 Presentation Description hi to all this is my presentation!!!!!!!!!!!!!!!! Comments Posting comment... By: ganeshindian (26 month(s) ago) thanks sir!great upload Saving..... Post Reply Close Saving..... Edit Comment Close By: amjadusman (42 month(s) ago) Respected Sir Ruiz Sir I Am a student of MS IT at NUST Pakistan. i have registered in a course titled as "Advance Database Systems". i need ur ppt presentation. pliz forward it to mw . i will be very thankful to u Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript EXTENDIBLE HASHING : EXTENDIBLE HASHING A hash table in which the hash function is the last few bits of the key and the table refers to buckets. Table entries with the same final bits may use the same bucket. If a bucket overflows, it splits, and if only one entry referred to it, the table doubles in size. If a bucket is emptied by deletion, entries using it are changed to refer to an adjoining bucket, and the table may be halved. Extendible hashing is a type of hash system which treats a hash as a bit string, and uses a trie for bucket lookup. Because of the hierarchal nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes. Extendible hashing is a kind of fast indexing technology; it provides with a way of storing structural data records so that each of them can be gotten very quickly. Ruiz, Alan R. CS-304 bucket : bucket An area of storage where items with a common property are stored. Typically tree data structures and sort algorithms use many buckets, one for each group of items. Usually buckets are kept on disk. A bucket is a structure containing an array of records, a count of the number of records actually occupied, and a bucket depth, which indicates the number of significant bits used to address into this bucket. TRIE : TRIE In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. The term trie comes from "retrieval." Following the etymology, the inventor, Edward Fredkin, pronounces it [tri] ("tree") . However, it is usually pronounced [traɪ] ("try"). A trie for keys "t", "to", "te", "tea", "ten", "i", "in", and "inn". : A trie for keys "t", "to", "te", "tea", "ten", "i", "in", and "inn". HASH FUNCTION : HASH FUNCTION A hash function is any well-defined procedure or mathematical function for turning some kind of data into a relatively small integer, that may serve as an index into an array. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes. Hash functions are mostly used to speed up table lookup or data comparison tasks — such as finding items in a database, detecting duplicated or similar records in a large file, finding similar stretches in DNA sequences, and so on. Hash functions are related to (and often confused with) checksums, check digits, fingerprints, , error correcting codes, and cryptographic hash functions. Although these concepts overlap to some extent, each has its own uses and requirements. The HashKeeper database maintained by the National Drug Intelligence Center, for instance, is more aptly described as a catalog of file fingerprints than of hash values. A typical hash function at work : A typical hash function at work Hash table : Hash table In computer science, a hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person's name), find the corresponding value (e.g. that person's telephone number). It works by transforming the key using a hash function into a hash, a number that is used as an index in an array to locate the desired location ("bucket") where the values should be. Hash tables support the efficient insertion of new entries, in expected O(1) time. The time spent in searching depends on the hash function and the load of the hash table; both insertion and search approach O(1) time with well chosen values and hashes. Slide 8: Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees.