DSpace Repository

Upper and Lower Bounds on Sorting and Searching in External Memory

Show simple item record

dc.contributor.advisor Bender, Michael A. en_US
dc.contributor.author Medjedovic, Dzejla en_US
dc.contributor.other Department of Computer Science en_US
dc.date.accessioned 2017-09-20T16:52:23Z
dc.date.available 2017-09-20T16:52:23Z
dc.date.issued 2014-12-01
dc.identifier.uri http://hdl.handle.net/11401/77297 en_US
dc.description 83 pgs en_US
dc.description.abstract This dissertation presents variants on sorting and searching in external memory. In the first part of the dissertation, we derive lower and upper bounds on sorting with different-sized records. We show that the record size substantially affects the sorting complexity, and so does the final interleaving of the smaller and larger records in the final sorted sequence: sorting costs more when large and small records are segregated than when they are interleaved in the final sorted order. In the second part of the dissertation, we study the batched predecessor problem in external memory. Given the underlying sorted set S of size n, and a sorted query Q of size x <= n^c, 0 <= c < 1, we study tradeoffs between the searching cost, and the cost to preprocess S. We give lower bounds in three external memory models: the I/O comparison model, I/O pointer-machine model, and the indexability model. Our results show that in the I/O comparison model, the batched predecessor problem needs \Omega(\log_{B}n + 1/B) I/Os per element if the preprocessing is polynomial; with exponential preprocessing, the problem can be solved faster, in \Theta((\log_{2}n + 1)/B). In the third part of the dissertation, we introduce alternatives to the well-known Bloom filter data structure. The quotient filter is designed for RAM, but with better data locality than the Bloom filter. The buffered quotient filter and the cascade filter are SSD-optimized alternatives to the Bloom filter. In experiments, the cascade filter and buffered quotient filter performed insertions 8.6-11 times faster than the fastest Bloom filter variant and performed lookups 0.94-2.56 times faster. en_US
dc.description.sponsorship This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. en_US
dc.format Monograph en_US
dc.format.medium Electronic Resource en_US
dc.language.iso en_US en_US
dc.publisher The Graduate School, Stony Brook University: Stony Brook, NY. en_US
dc.subject.lcsh Computer science en_US
dc.subject.other Algorithms, Batched, External Memory, Lower Bounds, Searching, Sorting en_US
dc.title Upper and Lower Bounds on Sorting and Searching in External Memory en_US
dc.type Dissertation en_US
dc.mimetype Application/PDF en_US
dc.contributor.committeemember Mitchell, Joseph en_US
dc.contributor.committeemember Johnson, Robert en_US
dc.contributor.committeemember Farach-Colton, Martin en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account