Rank and select: Another lesson learned. (March 2018)
- Record Type:
- Journal Article
- Title:
- Rank and select: Another lesson learned. (March 2018)
- Main Title:
- Rank and select: Another lesson learned
- Authors:
- Grabowski, Szymon
Raniszewski, Marcin - Abstract:
- Highlights: We present new solutions for the primitives on binary vectors, ranks and select. Special care for blocks with all 0 or all 1 bits poses a good space-time tradeoff. Compressed select is not much slower than compressed rank in a similar space. Abstract: Rank and select queries on bitmaps are essential building bricks of many compressed data structures, including text indexes, membership and range supporting spatial data structures, compressed graphs, and more. Theoretically considered yet in 1980s, these primitives have also been a subject of vivid research concerning their practical incarnations in the last decade. We present a few novel rank/select variants, focusing mostly on speed, obtaining competitive space-time results in the compressed setting. Our findings can be summarized as follows: ( i ) no single rank/select solution works best on any kind of data (ours are optimized for bit arrays obtained from wavelet trees for real text datasets, but also work well for LOUDS-encoded XML tree layouts), ( ii ) it pays to efficiently handle blocks consisting of all 0 or all 1 bits, ( iii ) compressed select does not have to be significantly slower than compressed rank at a comparable memory use.
- Is Part Of:
- Information systems. Volume 73(2018)
- Journal:
- Information systems
- Issue:
- Volume 73(2018)
- Issue Display:
- Volume 73, Issue 2018 (2018)
- Year:
- 2018
- Volume:
- 73
- Issue:
- 2018
- Issue Sort Value:
- 2018-0073-2018-0000
- Page Start:
- 25
- Page End:
- 34
- Publication Date:
- 2018-03
- Subjects:
- Binary sequences -- Rank -- Select -- Compressed data structures
68W32
Database management -- Periodicals
Electronic data processing -- Periodicals
Bases de données -- Gestion -- Périodiques
Informatique -- Périodiques
Database management
Electronic data processing
Periodicals
005.7 - Journal URLs:
- http://www.sciencedirect.com/science/journal/03064379 ↗
http://www.elsevier.com/journals ↗ - DOI:
- 10.1016/j.is.2017.12.001 ↗
- Languages:
- English
- ISSNs:
- 0306-4379
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 4496.367300
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 5777.xml