Encoding Nearest Larger Values
- Submitting institution
-
The University of Leicester
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1413
- Type
- D - Journal article
- DOI
-
10.1016/j.tcs.2017.02.017
- Title of journal
- Theoretical Computer Science
- Article number
- -
- First page
- 97
- Volume
- 710
- Issue
- -
- ISSN
- 0304-3975
- Open access status
- Compliant
- Month of publication
- March
- Year of publication
- 2017
- URL
-
-
- Supplementary information
-
https://doi.org/10.1016/j.tcs.2017.02.017
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
-
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Encoding data structures extract and store the absolute minimum data from a dataset needed to answer queries rapidly. Part of a body of work (Fischer, TCS’11, Jo&Satti, TCS’16, Gawrychowski&Nicholson, ICALP’15, Tsur, IPL’18) on encoding nearest larger/smaller values in an array, motivated by uses in highly space-efficient text indexing data structures. This paper shows that encoding one-sided queries (surprisingly) uses significantly less space than needed by the famous Cartesian tree and shows links between encodings and counting paths in automata (a toolkit of interest to future encoding research). Results feature in invited talks by Raman at SPIRE’17 and Dagstuhl workshops.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -