{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:19:44Z","timestamp":1737436784934,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425007"},{"type":"electronic","value":"9783540446880"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44688-5_6","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T13:43:33Z","timestamp":1188308613000},"page":"67-78","source":"Crossref","is-referenced-by-count":13,"title":["Optimised Predecessor Data Structures for Internal Memory"],"prefix":"10.1007","author":[{"given":"Naila","family":"Rahman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Cole","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"L. Arge, J. S. Vitter. Optimal Dynamic Interval Management in External Memory (extended abstract). FOCS 1996, pp. 560\u2013569.","key":"6_CR1","DOI":"10.1145\/258533.258647"},{"doi-asserted-by":"crossref","unstructured":"A. Andersson. Faster Deterministic Sorting and Searching in Linear Space. In Proc. 37th IEEE FOCS, pp. 135\u2013141, 1996.","key":"6_CR2","DOI":"10.1109\/SFCS.1996.548472"},{"doi-asserted-by":"crossref","unstructured":"Bender, M., Cole, R. and Raman. R. Exponential trees for cache-oblivious algorithms. In preparation, 2001.","key":"6_CR3","DOI":"10.1007\/3-540-45465-9_18"},{"doi-asserted-by":"crossref","unstructured":"Bender, M., Demaine, E. and Farach-Colton, M. Cache-oblivous B-trees. In Proc. 41st IEEE FOCS, pp. 399\u2013409, 2000.","key":"6_CR4","DOI":"10.1109\/SFCS.2000.892128"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"Comer, D. The Ubiquitous B-Tree. ACM Comput. Surv. 11 (1979), p. 121.","journal-title":"ACM Comput. Surv."},{"doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. Cache-oblivious algorithms. In Proc. 40th IEEE FOCS, pp. 285\u2013298, 1999.","key":"6_CR6","DOI":"10.1109\/SFFCS.1999.814600"},{"unstructured":"Furber, S. B. Arm System-On-Chip Architecture Addison-Wesley Professional, 2nd ed., 2000.","key":"6_CR7"},{"unstructured":"Hennessy, J. L. and Patterson, D. A. Computer Architecture: A Quantitative Approach (Second ed.). Morgan Kaufmann, 1996.","key":"6_CR8"},{"unstructured":"D. E. Knuth. The Art of Computer Programming. Volume 3: Sorting and Searching, 3rd ed. Addison-Wesley, 1997.","key":"6_CR9"},{"unstructured":"Ladner, R. E., Fix, J. D., and LaMarca, A. Cache performance analysis of traversals and random accesses. In Proc. 10th ACM-SIAM SODA (1999), pp. 613\u2013622.","key":"6_CR10"},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.1998.0985","volume":"31","author":"A. Marca La","year":"1999","unstructured":"LaMarca, A. and Ladner, R. E. The influence of caches on the performance of sorting. J. Algorithms 31, 66\u2013104, 1999.","journal-title":"J. Algorithms"},{"key":"6_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/3-540-48318-7_18","volume-title":"Proc. 3rd WAE","author":"M. Korda","year":"1999","unstructured":"Korda, M. and Raman, R. An experimental evaluation of hybrid data structures for searching. In Proc. 3rd WAE, LNCS 1668, pp. 213\u2013227, 1999."},{"key":"6_CR13","series-title":"Lect Notes Comput Sci","volume-title":"Proc. 26th ICALP","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K. and Sanders, P. Accessing multiple sequences through set-associative cache, 2000. Prel. vers. Proc. 26th ICALP, LNCS 1555, 1999."},{"unstructured":"H. Prokop. Cache-oblivious algorithms. MS Thesis, MIT, 1999.","key":"6_CR14"},{"key":"6_CR15","series-title":"Lect Notes Comput Sci","first-page":"184","volume-title":"ACM J. Exper. Algorithmics","author":"N. Rahman","year":"1999","unstructured":"Rahman, N. and Raman, R. Analysing cache effects in distribution sorting. ACM J. Exper. Algorithmics, WAE\u2019 99 special issue, to appear. Prel. vers. in Proc. 3rd WAE, LNCS 1668, pp. 184\u2013198, 1999."},{"key":"6_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1007\/3-540-45253-2_35","volume-title":"Proc. 8th ESA","author":"N. Rahman","year":"2000","unstructured":"Rahman, N. and Raman, R. Analysing the cache behaviour of non-uniform distribution sorting algorithms. In Proc. 8th ESA, LNCS 1879, pp. 380\u2013391, 2000."},{"key":"6_CR17","volume-title":"TR 00-02","author":"N. Rahman","year":"2000","unstructured":"Rahman, N. and Raman, R. Adapting radix sort to the memory hierarchy. TR 00-02, King\u2019s College London, 2000, http:\/\/www.dcs.kcl.ac.uk\/technical-reports\/2000.html Prel. vers. in Proc. ALENEX 2000."},{"unstructured":"Sen, S. and Chatterjee, S. Towards a theory of cache-efficient algorithms (extended abstract). In Proc. 11th ACM-SIAM SODA (2000), pp. 829\u2013838.","key":"6_CR18"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1995","unstructured":"Sleator, D. D. and Tarjan, R. E. Amortized efficiency of list update and paging rules. Communications of the ACM 28, 202\u2013208, 1995.","journal-title":"Communications of the ACM"},{"unstructured":"Sun Microsystem. UltraSPARC User\u2019s Manual. Sun Microsystems, 1997.","key":"6_CR20"},{"doi-asserted-by":"crossref","unstructured":"Vitter, J. S. External memory algorithms and data structures: Dealing with MASSIVE data. To appear in ACM Computing Surveys, 2000.","key":"6_CR21","DOI":"10.1145\/384192.384193"},{"doi-asserted-by":"crossref","unstructured":"D. E. Willard. Reduced memory space for multi-dimensional search trees. In Proc. STACS\u2019 85, pages 363\u2013374, 1985.","key":"6_CR22","DOI":"10.1007\/BFb0024024"}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44688-5_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T18:06:34Z","timestamp":1737396394000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44688-5_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425007","9783540446880"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44688-5_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}