Predecessor on the Ultra-Wide Word RAM

Philip Bille; Inge Li Gørtz; Tord Stordalen

doi:10.4230/LIPIcs.SWAT.2022.18

Predecessor on the Ultra-Wide Word RAM

Philip Bille, Inge Li Gørtz, Tord Stordalen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

75 Downloads (Pure)

Abstract

We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with ultrawords consisting of w2 bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addition to scattered memory operations that access or modify w (potentially non-contiguous) memory addresses simultaneously. The ultrawide word RAM model captures (and idealizes) modern vector processor architectures. Our main result is a simple, linear space data structure that supports predecessor in constant time and updates in amortized, expected constant time. This improves the space of the previous constant time solution that uses space in the order of the size of the universe. Our result is based on a new implementation of the classic x-fast trie data structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new dictionary data structure that supports fast parallel lookups.

Original language	English
Title of host publication	Proceedings of the 18^th Scandinavian Workshop and Symposium on Algorithms
Number of pages	15
Volume	227
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date	2022
Article number	18
DOIs	https://doi.org/10.4230/LIPIcs.SWAT.2022.18
Publication status	Published - 2022
Event	18^th Scandinavian Symposium and Workshops on Algorithm Theory - Vestarabryggja 15, Torshavn, Faroe Islands Duration: 27 Jun 2022 → 29 Jun 2022 https://www.setur.fo/en/education/swat-2022/

Conference

Conference	18^th Scandinavian Symposium and Workshops on Algorithm Theory
Location	Vestarabryggja 15
Country/Territory	Faroe Islands
City	Torshavn
Period	27/06/2022 → 29/06/2022
Internet address	https://www.setur.fo/en/education/swat-2022/

Series	Leibniz International Proceedings in Informatics, LIPIcs
ISSN	1868-8969

Access to Document

10.4230/LIPIcs.SWAT.2022.18

FulltextFinal published version, 771 KB

OpenUrl availability

Full text

Cite this

@inproceedings{cda008dcd8ba4f1288cad182756c0055,

title = "Predecessor on the Ultra-Wide Word RAM",

abstract = "We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with ultrawords consisting of w2 bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addition to scattered memory operations that access or modify w (potentially non-contiguous) memory addresses simultaneously. The ultrawide word RAM model captures (and idealizes) modern vector processor architectures. Our main result is a simple, linear space data structure that supports predecessor in constant time and updates in amortized, expected constant time. This improves the space of the previous constant time solution that uses space in the order of the size of the universe. Our result is based on a new implementation of the classic x-fast trie data structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new dictionary data structure that supports fast parallel lookups.",

author = "Philip Bille and G{\o}rtz, {Inge Li} and Tord Stordalen",

year = "2022",

doi = "10.4230/LIPIcs.SWAT.2022.18",

language = "English",

volume = "227",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

booktitle = "Proceedings of the 18th Scandinavian Workshop and Symposium on Algorithms",

note = "18<sup>th</sup> Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022 ; Conference date: 27-06-2022 Through 29-06-2022",

url = "https://www.setur.fo/en/education/swat-2022/",

}

Bille, P , Gørtz, IL & Stordalen, T 2022, Predecessor on the Ultra-Wide Word RAM. in Proceedings of the 18^th Scandinavian Workshop and Symposium on Algorithms. vol. 227, 18, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, 18^th Scandinavian Symposium and Workshops on Algorithm Theory, Torshavn, Faroe Islands, 27/06/2022. https://doi.org/10.4230/LIPIcs.SWAT.2022.18

Predecessor on the Ultra-Wide Word RAM. / Bille, Philip ; Gørtz, Inge Li; Stordalen, Tord.
Proceedings of the 18^th Scandinavian Workshop and Symposium on Algorithms. Vol. 227 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. 18 (Leibniz International Proceedings in Informatics, LIPIcs).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Predecessor on the Ultra-Wide Word RAM

AU - Bille, Philip

AU - Gørtz, Inge Li

AU - Stordalen, Tord

PY - 2022

Y1 - 2022

N2 - We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with ultrawords consisting of w2 bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addition to scattered memory operations that access or modify w (potentially non-contiguous) memory addresses simultaneously. The ultrawide word RAM model captures (and idealizes) modern vector processor architectures. Our main result is a simple, linear space data structure that supports predecessor in constant time and updates in amortized, expected constant time. This improves the space of the previous constant time solution that uses space in the order of the size of the universe. Our result is based on a new implementation of the classic x-fast trie data structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new dictionary data structure that supports fast parallel lookups.

AB - We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with ultrawords consisting of w2 bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addition to scattered memory operations that access or modify w (potentially non-contiguous) memory addresses simultaneously. The ultrawide word RAM model captures (and idealizes) modern vector processor architectures. Our main result is a simple, linear space data structure that supports predecessor in constant time and updates in amortized, expected constant time. This improves the space of the previous constant time solution that uses space in the order of the size of the universe. Our result is based on a new implementation of the classic x-fast trie data structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new dictionary data structure that supports fast parallel lookups.

U2 - 10.4230/LIPIcs.SWAT.2022.18

DO - 10.4230/LIPIcs.SWAT.2022.18

M3 - Article in proceedings

VL - 227

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Proceedings of the 18th Scandinavian Workshop and Symposium on Algorithms

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 18<sup>th</sup> Scandinavian Symposium and Workshops on Algorithm Theory

Y2 - 27 June 2022 through 29 June 2022

ER -

Predecessor on the Ultra-Wide Word RAM

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this