Improving on S-Index : A Hybrid Indexing Scheme for Textbases

Abstract

Στην εργασία αυτή παρουσιάζουμε δυο παραλλαγές της S-Index και μελετούμε την απόδοσή τους ως προς την χρήση του αποθηκευτικού χώρου όταν αυτές ευρετηριοποιούν μια βάση ελεύθερου κειμένου μεγέθους 130ΜΒ. Η S-Index είναι ένα υβριδικό σχήμα ευρετηρίου που συνδυάζει τα προτερήματα δυο δημοφιλών μεθόδων ευρετηριοποίησης: του ανεστραμμένου αρχείου και του αρχείου υπογραφών. Προτείνουμε μια νέα παραλλαγή της μεθόδου και περιγράφουμε τη δομή της καθώς και λεπτομέρειες σχετικές με την υλοποίησή της αρχικής και της νέας παραλλαγής της S-Index. Συγκρίνουμε τις δυο παραλλαγές με βάση τα πειραματικά αποτελέσματα που λαμβάνουμε. Κάτω από συγκεκριμένες προϋποθέσεις, η βελτιωμένη παραλλαγή της S-Index χρησιμοποιεί λιγότερο από το 5% του χώρου που καταλαμβάνει η αντίστοιχη βάση του ελεύθερου κειμένου. Η αρχική S-Index έχει ελαφρώς χειρότερη απόδοση ως προς τις απαιτήσεις σε αποθηκευτικό χώρο, αλλά η απόδοση και των δυο παραλλαγών της S-Index είναι συγκρίσιμη με αυτή του συμπιεσμένου ανεστραμμένου αρχείου.

In this paper are presented two variations of S-Index and their return correlated to the use of storage room is studied, while their indexing a free text database of 130MB size. S-Index is a hybrid form of indexing that combines the merits of two popular indexing methods, the inverted files and the signature files. There is also suggested a new variation of the method and its structure is described, combined with details for materialising the first and the new form of S-Index. The two variations are compared to each other, based on the experimental results that are received. Under specific circumstances, the improved variation of S-Index uses less that 5% of the storage room that occupies the free text indexing database. The first variation has slightly worse attribution related to the storage room, but the attribution of both variations of S-Index is comparable to the one using inverted files.