Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

RE-tree: an efficient index structure for regular expressions

Chan Chee-Yong, Garofalakis Minos, Rastogi Rajeev

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/66495CCA-1AE1-48DA-AD5D-20DB8D5944C8-
Αναγνωριστικόhttp://link.springer.com/article/10.1007%2Fs00778-003-0094-0-
Αναγνωριστικόhttps://doi.org/10.1007/s00778-003-0094-0-
Γλώσσαen-
Μέγεθος18 pagesen
ΤίτλοςRE-tree: an efficient index structure for regular expressionsen
ΔημιουργόςChan Chee-Yongen
ΔημιουργόςGarofalakis Minosen
ΔημιουργόςΓαροφαλακης Μινωςel
ΔημιουργόςRastogi Rajeeven
ΕκδότηςSpringer Verlagen
ΠερίληψηDue to their expressive power, regular expressions (REs) are quickly becoming an integral part of language specifications for several important application scenarios. Many of these applications have to manage huge databases of RE specifications and need to provide an effective matching mechanism that, given an input string, quickly identifies the REs in the database that match it. In this paper, we propose the RE-tree, a novel index structure for large databases of RE specifications. Given an input query string, the RE-tree speeds up the retrieval of matching REs by focusing the search and comparing the input string with only a small fraction of REs in the database. Even though the RE-tree is similar in spirit to other tree-based structures that have been proposed for indexing multidimensional data, RE indexing is significantly more challenging since REs typically represent infinite sets of strings with no well-defined notion of spatial locality. To address these new challenges, our RE-tree index structure relies on novel measures for comparing the relative sizes of infinite regular languages. We also propose innovative solutions for the various RE-tree operations including the effective splitting of RE-tree nodes and computing a "tight" bounding RE for a collection of REs. Finally, we demonstrate how sampling-based approximation algorithms can be used to significantly speed up the performance of RE-tree operations. Preliminary experimental results with moderately large synthetic data sets indicate that the RE-tree is effective in pruning the search space and easily outperforms naive sequential search approaches.en
ΤύποςPeer-Reviewed Journal Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-10-29-
Ημερομηνία Δημοσίευσης2003-
Θεματική ΚατηγορίαRegular expressionsen
Θεματική ΚατηγορίαIndex structureen
Θεματική ΚατηγορίαSize measuresen
Θεματική ΚατηγορίαSampling-based approximationsen
Βιβλιογραφική ΑναφοράC.-Y. Chan, M. Garofalakis and R. Rastogi, "RE-tree: an efficient index structure for regular expressions", VLDB J., vol. 12, no. 2, pp. 102-119, Ayg. 2003. doi:10.1007/s00778-003-0094-0en

Υπηρεσίες

Στατιστικά