Cache-Oblivious Iterated Predecessor Queries via Range Coalescing
In this paper we develop an optimal cache-oblivious data structure that solves the iterated predecessor problem. Given k static sorted lists L[subscript 1],L[subscript 2],…,L[subscript k] of average length n and a query value q, the iterated predecessor problem is to find the largest element in eac...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110844 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0001-6915-0216 |
| _version_ | 1811079818218831872 |
|---|---|
| author | Demaine, Erik D Gopal, Vineet Hasenplaugh, William Cleaburn |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D Gopal, Vineet Hasenplaugh, William Cleaburn |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | In this paper we develop an optimal cache-oblivious data structure that solves the iterated predecessor problem. Given k static sorted lists L[subscript 1],L[subscript 2],…,L[subscript k] of average length n and a query value q, the iterated predecessor problem is to find the largest element in each list which is less than q. Our solution to this problem, called “range coalescing”, requires O(log[subscript B+1]n+k/B) memory transfers for a query on a cache of block size B, which is information-theoretically optimal. The range-coalescing data structure consumes O(kn) space, and preprocessing requires only O(kn / B) memory transfers with high probability, given a tall cache of size M=Ω(B[superscript 2]). |
| first_indexed | 2024-09-23T11:20:56Z |
| format | Article |
| id | mit-1721.1/110844 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:20:56Z |
| publishDate | 2017 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1108442022-09-27T18:56:19Z Cache-Oblivious Iterated Predecessor Queries via Range Coalescing Demaine, Erik D Gopal, Vineet Hasenplaugh, William Cleaburn Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D Gopal, Vineet Hasenplaugh, William Cleaburn In this paper we develop an optimal cache-oblivious data structure that solves the iterated predecessor problem. Given k static sorted lists L[subscript 1],L[subscript 2],…,L[subscript k] of average length n and a query value q, the iterated predecessor problem is to find the largest element in each list which is less than q. Our solution to this problem, called “range coalescing”, requires O(log[subscript B+1]n+k/B) memory transfers for a query on a cache of block size B, which is information-theoretically optimal. The range-coalescing data structure consumes O(kn) space, and preprocessing requires only O(kn / B) memory transfers with high probability, given a tall cache of size M=Ω(B[superscript 2]). 2017-07-25T19:21:39Z 2017-07-25T19:21:39Z 2015-07 Article http://purl.org/eprint/type/ConferencePaper 978-3-319-21839-7 978-3-319-21840-3 0302-9743 1611-3349 http://hdl.handle.net/1721.1/110844 Demaine, Erik D., Vineet Gopal, and William Hasenplaugh. “Cache-Oblivious Iterated Predecessor Queries via Range Coalescing.” Algorithms and Data Structures. Ed. Frank Dehne, Jörg-Rüdiger Sack, and Ulrike Stege. Vol. 9214. Cham: Springer International Publishing, 2015. 249–262. https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0001-6915-0216 en_US http://dx.doi.org/10.1007/978-3-319-21840-3_21 Workshop on Algorithms and Data Structures, WADS 2015 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Springer Berlin / Heidelberg MIT Web Domain |
| spellingShingle | Demaine, Erik D Gopal, Vineet Hasenplaugh, William Cleaburn Cache-Oblivious Iterated Predecessor Queries via Range Coalescing |
| title | Cache-Oblivious Iterated Predecessor Queries via Range Coalescing |
| title_full | Cache-Oblivious Iterated Predecessor Queries via Range Coalescing |
| title_fullStr | Cache-Oblivious Iterated Predecessor Queries via Range Coalescing |
| title_full_unstemmed | Cache-Oblivious Iterated Predecessor Queries via Range Coalescing |
| title_short | Cache-Oblivious Iterated Predecessor Queries via Range Coalescing |
| title_sort | cache oblivious iterated predecessor queries via range coalescing |
| url | http://hdl.handle.net/1721.1/110844 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0001-6915-0216 |
| work_keys_str_mv | AT demaineerikd cacheobliviousiteratedpredecessorqueriesviarangecoalescing AT gopalvineet cacheobliviousiteratedpredecessorqueriesviarangecoalescing AT hasenplaughwilliamcleaburn cacheobliviousiteratedpredecessorqueriesviarangecoalescing |