Kısmi-eşleme erişimi ve buna uygun dosya yapıları
Efficient file structures for partial-match retrieval
- Tez No: 21728
- Danışmanlar: DOÇ. DR. MİTHAT UYSAL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Büro otomasyonu, Erişim yöntemleri, Kısmi eşleme erişimi, Office automation, Access methods, Partial match retrieval
- Yıl: 1992
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET Kısmi-Esleme erişini çeşitli anaçlar için ihtiyaç duyulan bir erisin yöntemidir, özellikle ofis otomasyonunda çok kullanılır. Bu erisin üzerine çeşitli yöntemler vardır. Bunlardan bazılarını su şekilde sıralayabiliriz ; 1.- indekslenmis Tanımlayıcı Dosyalar 2.- Tersine Çevrilmiş Dosyalar 3.- tnza Dosyaları 4.- Genisletilebilir Hash (Ext. Hashing) 5.- Tanımlayıcı ve Hash Biz burada bu yapılardan her birini genel hatlarıyla anlatıp, örneklerle daha iyi anlaşılmalarını sağladıktan sonra bu teknikleri genel ve basit bir yapı üzerinde birbiri ile mukayese ederek aralarında en iyi sonuç vereni saptamaya çalıştık. Sinülasyon deneyleri kısmındaki tablo değerleri ve grafik üzerindeki gösterinden de anlaşılacağı gibi indekslenmiş tanımlayıcı dosya yapısı bizce diğer yapılar içerisinde en iyi performansı sağlamıştır.
Özet (Çeviri)
S U H M A R Y EFFICIENT FILE STRUCTURES FOR PARTIAL-HATCH RETRIEVAL Partial-match retrieval is a problem involving searching on secondary keys. A number of approaches have been suggested. One way to tackle the problem is to search the entire file in response to each query, using a string or a regular expression based pattern matching algorithm. Although regular expressions provide considerable flexibility in posing queries, particularly those concerned with text, the requirement of having to search through the entire file to answer each query limits this technique to files that are not too large, unless queries can be batched or special hardware is available. A number of alternative schemes have been suggested to reduce the amount of information that needs to be searched to answer a query. One such class of schemes associates with each record a short representative code word. Searches can then be performed over the shorter code word file to determine which records are potential answers to a given query (or, equivalently, to exclude records that cannot possible be answers). Another common approach is to construct an inverted index list for each field. A query can be answered by intersecting the index lists for each specified field. Some of the methods for partial-match retrieval are shown in the following case: 1.- Extendible Hashing 2.- Indexed Descriptor Files 3.- Signature Files - vi i -1. -Review of Extendible Hashing and Its Appication to Partial Hatch Retrieval The file is contained in a number of pages ( or buckets). There are two kinds of pages. Leaf pages contain the records themselves and directory pages contain the directory. The directory is organized as a linear array of m=2'1 entries where d is called the global depth of the directory. m is always a power of two and changes (doubled or halved) in response to the changes in the volume of the file. Each entry in the directory contains a pointer to a leaf page. Each leaf page has a header that contains its local depth d*. For a leaf page with local depth d'» there are 2lA~A' ' directory entries pointing to it. Fig. 1 shows a file organization when d=3. Fig. 1-- An extendible hashing file with global depth=3. - viii -Associated with the file is a hashing function h:KEY - >D where KEY is the domain of the primary key of the file, D={0, 1, 2, 3,..., 2<1“,*>c-l >, and 2*,”“c is the maximum allowable size of the directory. To locate or insert a record with primary key value V, we calculate the pseudokey V as the first d bits of h(V). V is then used as an index into the directory. The indexed directory entry contains a pointer to the leaf page where the record will be found or inserted. When inserting a record into a full leaf page with local depth d', d'< d, we split the bucket into two buckets, distribute the records between the two buckets according to their pseudokey values, and then change the pointers in the appropriate directory entries. However, when inserting a record into a full leaf page with local depth d'=d, we double the size of the directory; global depth d is then increased by one. Each directory entry becomes two complement directory entries with identical pointer values. Now the overflow leaf page can be split similarly as before. Lloyd and Ramamohanarao extended this single-key file organization to handle partial-match retrievals in the following way. Let n be the number of fields in the record structure of the file. With each field of the record structure, associate a hashing function ht:Ft - >B4, 1=1, 2,..., n where F* is the key space of the ith field and Bi is the pseudokey space of a certain length nu. The index of a record Cri, ra,..., r”) into the directory is assembled using the pseudokeys hı(rı), h2(r2),..., h“(r”) and the choice vector (..., i3, iz,ii) If i4=p in the choice vector, then the jth (rightmost) bit in the index should come from the pth pseudokey h_,(r»). The choice vector has important consequences on the performance of the file. It dynamically adapts to the current state of the system according to the distribution of occurrences of each field in the record structure in the file operations performed thus far. This is done by deferring the calculation of ij until the directory size grows to 2j. The procedure, called Minimal Marginal Increase (MMI), used to calculate the choice vector, and the theory behind it are discussed in C73. - ix -The operations of insertion, searching, bucket splitting, directory doubling, etc., are then similar to the single-key case. Example 1: Let the global depth = 5, record R = (vx, v2, v3, v*) and the choice vector = (..., 4, 2, 2, 3, 2). Let h(Vi) = a“... aiao, h(vz) = b»... bzbib©, h(v3) = cm... CiCo, and h(v«) = dm... dido uhere am... aia0, bm... bib©, Cm... CiCo, and dm... dido are binary numbers with a sufficiently large number m of digits. Then the address of record E = d©babıc0bo. 2.- Indexed Descriptor Files Pfaltz et al. applied the technique of disjoint coding to a file structure called the indexed descriptor file. The idea behind the technique is to speed up retrieval of records by encoding information about the records in an efficient manner. Basically, the infor mation in a single record is represented by a descriptor word and the descriptor words of all records stored in one bucket (on disk) are bitwise OR'd together to form a bucket descriptor D». The directory of an indexed descriptor file is just the collection of all bucket descriptors. A descriptor D, of a record r = (ri, r2|...» r*) where râ?D4 for l<i<k is a bit string of w (for widht) bits. Each descriptor is divided into k disjoint fields. Each field Ft consists of w4 bits; therefore, i Efci«ı Hi = w >. There are k functions H4:D«. - >?1, 2,...,m4} for ISiik. In a descriptor D«- of a record r = (ri, ra,..., r», ), the H±(r4)th bit in F* is set to 1 (the remaining w4-l bits are set to 0). There are exactly k bits set to 1 in a record descriptor. A descriptor D^ for a query q = (Ai = a», A2 = az,..., A* = a*) is a bit string of w bits with the H4(at)th bit in F4 set to 1 if a* = * for l<i<k and the rest of the bits are 0. Mote that the number of bits set to 1 in a query descriptor is equal to the number of uniquely specified attributes in the query. - x -The search algorithm for a given query in an indexed descriptor file is simply to compare D^ to the descriptor D» of each bucket B and access all buckets B whose descriptors have l*s in all the same positions as D^ ; the values contained in the other bit positions in D» do not need to be considered. Note for a bucket B whose bucket descriptor satisfies the above criterion, this method does not guarantee that B contains at least one record in B(q) (a ”false hit"). 3.- Signature Files A content-addressable scheme for a message file system has been proposed here. This scheme uses an idea similar to that of the indexed descriptor files described in Section 3. ' In this scheme, a descriptor file called a signature file is created for each message in the file system. The descriptor file F* for a message F is cre ated by concatenating the descriptors of all uncommon words in message F. Whereas Pfaltz and Cagley set exactly one bit to 1 in each field descriptor, a word descriptor in the message-file scheme is a string of bits which represents (not uniquely) the word. There are many algorithms for transforming a word into its descriptor. One method is to use a hash function to hash each word into a string of bits. Another method is to divide each word into overlapping triplets of letters and then to hash each triplet into a fixed number of bits. The main idea behind both methods is that a descriptor requires much less storage space than an actual word. This reduces the amount of data requiring access when comparison are made. The use of the signature file is illustrated in the following: a user generates a query that specifies a variable number of words and a pattern among those words. The pattern is a boolean expression involving combinations of words. For example, a user can specify five words where the pattern is the conjunction of those five words, i.e., all messages containing those five words should be retrieved. A sequential search is performed on the descriptor file to determine if the five words are contained in any entry in the file» if the - xi -search is successful, the corresponding document is retrieved. Mote, however, that although the descriptor file contains the five words, it is possible that the actual corresponding mesaee need not contain those five words. This is because there is no one-to-one correspondence between a word and its descriptor. Partial-Hatch Retrieval Using Hashing ^ and Descriptors A partial-match retrieval scheme based solely on descriptors seems to have some disadvantages, especially for dynamic files. However, a smail, simplified descriptor file, built on top of a hashing scheme, is a practical and effective solution to the problem of large key spaces. Let us now be more precise about descriptor files. A descriptor is a fixed-length bit string consisting of w bits. Typically, w would be 100 to 500. Each page in the main file has a descriptor associated with it. The descriptors are numbered in the same way as the pages of the main file, and the collection of all descriptors is called the descriptor file. Each field f* has associated with it a transformation T», which maps from the key space of f4 to the subset of bit strings of length Hi, where each bit string has exactly one bit set to 1, with the remainder 0. Furthermore, w» +... + w* = w. Now the descriptor associated with a page is obtained by the (bitwise) ORing of the record descriptors for each record in the page and any associated overflow pages. A record descriptor is obtained by applying the transformation T4 to each field ft (i = 1, 2,..., k) and forming the bit string of length w, which is the concatenation of each of the resulting strings. Only page descriptors are actually stored. When a record is added to or deleted from a page, the descriptor must be updated. A major difference between the descriptor file here and that in indexed descriptor file is that we have only one level of descriptor file. Furthermore, the descriptors in indexed descriptor file are larger than ours because the scheme in indexed descriptor file relies solely on the descriptors for retrieval. Thus our descriptor file is smaller. The size of the descriptor file is w2* bits. - xii -
Benzer Tezler
- Paralel veri tabanlarında parçalama ve yeniden organize etme yöntemleri
Başlık çevirisi yok
MURAT OSMAN ÜNALIR
Yüksek Lisans
Türkçe
1995
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. ALP KUT
- Analitik ve digital fotogrametrik nirengi yöntemlerinin kıyaslanması
Başlık çevirisi yok
OKTAY AKSU
Yüksek Lisans
Türkçe
1998
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiJeodezi ve Fotogrametri Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÖNÜL TOZ
- Modele dayalı kodlama yöntemlerinin incelenmesi
An Investigation on model based coding
SERDAR YILMAZ
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik MühendisliğiAnkara ÜniversitesiElektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MÜMTAZ YILMAZ
- Iğdır yöresi topraklarında kaymak sertliği (kırılma değeri) ile ilgili araştırmalar
Crust strength (Modulus of rupture of the soils of Iğdır district)
MUSTAFA Y. CANBOLAT
- Akım taşıyıcı kullanan devrelerin gerçekleştirilmesinde yeni yöntemler ve sonuçlar
New procedures for the realisations of current conveyor-based networks and some related results
SERDAR ÖZOĞUZ
Doktora
Türkçe
2000
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. CEVDET ACAR