Storing a Sparse Table with <i>0</i> (1) Worst Case Access Time
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A data structure for representing a set of n items from a universe of m items, which uses space n+o(n) and accommodates membership queries in constant time and is easy to implement.
Abstract
article Free Access Share on Storing a Sparse Table with 0(1) Worst Case Access Time Authors: Michael L. Fredman Univ. of California, San Diego, La Jolla Univ. of California, San Diego, La JollaView Profile , János Komlós View Profile , Endre Szemerédi View Profile Authors Info & Claims Journal of the ACMVolume 31Issue 3pp 538–544https://doi.org/10.1145/828.1884Published:26 June 1984Publication History 576citation3,796DownloadsMetricsTotal Citations576Total Downloads3,796Last 12 Months379Last 6 weeks36 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF