Search: onr:"swepub:oai:DiVA.org:umu-110695" >
Efficient increment...
Efficient incremental evaluation of succinct regular expressions
-
- Björklund, Henrik, 1973- (author)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
- Martens, Wim (author)
- Universität Bayreuth
-
- Timm, Thomas (author)
- Universität Bayreuth
-
(creator_code:org_t)
- 2015-10-17
- 2015
- English.
-
In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. - New York, NY, USA : Association for Computing Machinery (ACM). - 9781450337946 ; , s. 1541-1550
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- Regular expressions are omnipresent in database applications. They form the structural core of schema languages for XML, they are a fundamental ingredient for navigational queries in graph databases, and are being considered in languages for upcoming technologies such as schema- and transformation languages for tabular data on the Web. In this paper we study the usage and effectiveness of the counting operator (or: limited repetition) in regular expressions. The counting operator is a popular extension which is part of the POSIX standard and therefore also present in regular expressions in grep, Java, Python, Perl, and Ruby. In a database context, expressions with counting appear in XML Schema and languages for querying graphs such as SPARQL 1.1 and Cypher.We first present a practical study that suggests that counters are extensively used in practice. We then investigate evaluation methods for such expressions and develop a new algorithm for efficient incremental evaluation. Finally, we conduct an extensive benchmark study that shows that exploiting counting operators can lead to speed-ups of several orders of magnitude in a wide range of settings: normal and incremental evaluation on synthetic and real expressions.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- XML
- Schema
- Regular Expressions
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
To the university's database