Sökning: onr:"swepub:oai:DiVA.org:umu-110695" >
Efficient increment...
Efficient incremental evaluation of succinct regular expressions
-
- Björklund, Henrik, 1973- (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
- Martens, Wim (författare)
- Universität Bayreuth
-
- Timm, Thomas (författare)
- Universität Bayreuth
-
(creator_code:org_t)
- 2015-10-17
- 2015
- Engelska.
-
Ingår i: 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
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- XML
- Schema
- Regular Expressions
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas