More Web Proxy on the site http://driver.im/

Article

Exponential Structures for Efficient Cache-Oblivious Algorithms

Authors:

Michael A. Bender,

Rajeev RamanAuthors Info & Claims

ICALP '02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming

Pages 195 - 207

Published: 08 July 2002 Publication History

Abstract

We present cache-oblivious data structures based upon exponential structures. These data structures perform well on a hierarchical memory but do not depend on any parameters of the hierarchy, including the block sizes and number of blocks at each level. The problems we consider are searching, partial persistence and planar point location. On a hierarchical memory where data is transferred in blocks of size B , some of the results we achieve are: - We give a linear-space data structure for dynamic searching that supports searches and updates in optimal O (log _B N ) worst-case I/Os, eliminating amortization from the result of Bender, Demaine, and Farach-Colton (FOCS '00).We also consider finger searches and updates and batched searches. - We support partially-persistent operations on an ordered set, namely, we allow searches in any previous version of the set and updates to the latest version of the set (an update creates a new version of the set). All operations take an optimal O (log _B( m + N )) amortized I/Os, where N is the size of the version being searched/updated, and m is the number of versions. - We solve the planar point location problem in linear space, taking optimal O (log _B N ) I/Os for point location queries, where N is the number of line segments specifying the partition of the plane. The pre-processing requires O((N / B ) log _M/B N ) I/Os, where M is the size of the 'inner' memory.

References

[1]

A. Aggarwal and J. S. Vitter. The I/O complexity of sorting and related problems. Communications of the ACM 31 , 1116-1127, 1988.

[2]

A. Ailamaki, D. J. DeWitt, M. D. Hill, and D. A. Wood. DBMSs on a Modern Processor: Where Does Time Go? In Proc. 25th VLDB Conference (1999), pp 266-277.

[3]

A. Andersson. Faster Deterministic Sorting and Searching in Linear Space. In Proc. 37th IEEE FOCS (1996), pp. 135-141.

[4]

A. Andersson and M. Thorup. Tight(er) worst-case bounds on dynamic searching and priority queues. In Proc. 31st ACM STOC (2000), pp. 335-342.

[5]

L. Arge. External memory data structures. In J. Abello, P. M. Pardalos, and M. G. C. Resende, eds, Handbook of Massive Data Sets . Kluwer Academic, 2002.

[6]

L. Arge, D. E. Vengroff and J. S. Vitter. External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (Extended Abstract). In Proc. 6th European Symposium on Algorithms (1995), LNCS 979, 295-310.

[7]

R. Bayer and E. M. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica , 1(3):173-189, February 1972.

[8]

M.A. Bender, E. Demaine and M. Farach-Colton Cache-oblivous B-trees. In Proc. 41st IEEE FOCS (2000), pp. 399-409.

[9]

M. A. Bender, R. Cole and R. Raman. Exponential structures for efficient cache-oblivious algorithms. University of Leicester TR 2002/19, 2002.

[10]

M. A. Bender, Z. Duan, J. Iacono and J.Wu. A locality-preserving cache-oblivious dynamic dictionary. In Proc. 13th ACM-SIAM SODA (2002), pp. 29-38.

[11]

R. D. Blumofe, M. Frigo, C. F. Joerg, C. E. Leiserson, and K. H. Randall. An analysis of dag-consistent distributed shared-memory algorithms. In Proc. 8th ACM SPAA , pp. 297-308, 1996.

[12]

G. S. Brodal, R. Fagerberg and R. Jacob. Cache-oblivious search trees via binary trees of small height. In Proc. 13th ACM-SIAM SODA (2002), pp. 39-48.

[13]

M. R. Brown, R. E. Tarjan. A data structure for representing sorted lists. SIAM J. Comput. 9 (1980), pp. 594-614.

[14]

M. T. Goodrich, J-J. Tsay, D. E. Vengroff and J. S. Vitter. External-Memory Computational Geometry (Preliminary Version). In Proc. 34th IEEE FOCS (1993), pp. 714-723.

[15]

M. L. Fredman and D. E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. System Sci. , 47(3):424-436, 1993.

[16]

M. Frigo, C. E. Leiserson, H. Prokop and S. Ramachandran Cache-oblivious algorithms. In Proc. 40th IEEE FOCS (1999), pp. 285-298.

[17]

K. Mehlhorn. Data structures and algorithms, 1. Sorting and searching . Springer, 1984.

[18]

H. Prokop. Cache-oblivious algorithms. MS Thesis, MIT, 1999.

[19]

N. Rahman and R. Raman. Adapting radix sort to the memory hierarchy. TR 00-02, King's College London, 2000. Prel. vers. in Proc. ALENEX 2000 .

[20]

N. Rahman, R. Cole and R. Raman. Optimised predecessor data structures for internal memory. In Proc. 5th Workshop on Algorithm Engg. , LNCS 2141, pp. 67-78, 2001.

[21]

N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Communications of the ACM 29 , 1986, 669-679.

[22]

M. Thorup. Faster Deterministic Sorting and Priority Queues in Linear Space. Proc. 9th ACM-SIAM SODA (1998), pp. 550-555.

[23]

S. Toledo. Locality of reference in LU decomposition with partial pivoting. SIAM Journal on Matrix Analysis and Applications , 18(4):1065-1081, Oct. 1997.

[24]

J. S. Vitter. External memory algorithms and data structures: Dealing with MASSIVE data. ACM Computing Surveys 33 (2001) pp. 209-271.

[25]

D. E.Willard. A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Information and Computation , 97(2):150-204, 1992.

Cited By

Hu XSheng CTao Y(2019)Building an Optimal Point-Location Structure in $$O( sort (n))$$O(sort(n)) I/OsAlgorithmica10.1007/s00453-018-0518-281:5(1921-1937)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s00453-018-0518-2
Bender MBerry JJohnson RKroeger TMcCauley SPhillips CSimon BSingh SZage DMilo TTan W(2016)Anti-Persistence on Persistent StorageProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902276(289-302)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902276
Chan T(2013)Persistent Predecessor Search and Orthogonal Point Location on the Word RAMACM Transactions on Algorithms10.1145/2483699.24837029:3(1-22)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2483699.2483702
Show More Cited By

Exponential Structures for Efficient Cache-Oblivious Algorithms

Recommendations

Cache-oblivious dynamic dictionaries with update/query tradeoffs
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms

Several existing cache-oblivious dynamic dictionaries achieve O(log_B N) (or slightly better O(log_B N/M)) memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the block size, which matches the classic B-...
Cache-oblivious data structures for massive data sets
Cache-oblivious range reporting with optimal queries requires superlinear space
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(log_BN + K/B) block ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICALP '02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming

July 2002

1065 pages

ISBN:3540438645

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 July 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hu XSheng CTao Y(2019)Building an Optimal Point-Location Structure in $$O( sort (n))$$O(sort(n)) I/OsAlgorithmica10.1007/s00453-018-0518-281:5(1921-1937)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s00453-018-0518-2
Bender MBerry JJohnson RKroeger TMcCauley SPhillips CSimon BSingh SZage DMilo TTan W(2016)Anti-Persistence on Persistent StorageProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902276(289-302)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902276
Chan T(2013)Persistent Predecessor Search and Orthogonal Point Location on the Word RAMACM Transactions on Algorithms10.1145/2483699.24837029:3(1-22)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2483699.2483702
Farzan AMunro JRaman R(2012)Succinct indices for range queries with applications to orthogonal range maximaProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part I10.1007/978-3-642-31594-7_28(327-338)Online publication date: 9-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31594-7_28
Afshani PZeh NRandall D(2011)Improved space bounds for cache-oblivious range reportingProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133170(1745-1758)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133170
Chan TRandall D(2011)Persistent predecessor search and orthogonal point location on the word RAMProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133121(1131-1145)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133121
Afshani PHamilton CZeh NHershberger JFogel E(2009)A general approach for cache-oblivious range reporting and approximate range countingProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542413(287-295)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542413
Arge LBerg MHaverkort H(2009)Cache-Oblivious R-TreesAlgorithmica10.1007/s00453-007-9007-853:1(50-68)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1007/s00453-007-9007-8
Nekrich Y(2008)I/O-efficient point location in a set of rectanglesProceedings of the 8th Latin American conference on Theoretical informatics10.5555/1792918.1792977(687-698)Online publication date: 7-Apr-2008
https://dl.acm.org/doi/10.5555/1792918.1792977
Barbay JKenyon C(2008)Alternation and redundancy analysis of the intersection problemACM Transactions on Algorithms10.1145/1328911.13289154:1(1-18)Online publication date: 28-Mar-2008
https://dl.acm.org/doi/10.1145/1328911.1328915
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents