https://www.snipit.org/public/alan/viewchannel.php?catid=1610 2007-03-22T15:12:41Z https://www.snipit.org/images/scissors.gif https://www.snipit.org/public/alan/viewchannel.php?catid=1610 Snip!t channel - Alan Dix: Channels > AVL trees Abstract: Two in-place variants of the classical mergeso... analysed in detail. The first, straightforward variant p... log 2 N + O(N ) comparisons and 3N log 2 N + O(N ) moves... elements. The second, more advanced variant requires at ... O(N ) compa https://www.snipit.org/public/alan/viewsnip.php?id=4409 http://citeseer.ist.psu.edu/katajainen96practical.html 2007-03-22T15:12:41Z External memory algorithms and data structures: dealing ... Full text pdf formatPdf (828 KB) Source ACM Computing Surveys (CSUR) archive Volume 33 , Issue 2 (June 2001) table of contents ... ACM Press https://www.snipit.org/public/alan/viewsnip.php?id=4408 http://portal.acm.org/citation.cfm?id=384193&coll=portal&dl=ACM 2007-03-22T15:08:46Z FastSort: a distributed single-input single-output exter... Full text pdf formatPdf (928 KB) Source International Conference on Management of Data a ... Proceedings of the 1990 ACM SIGMOD international confere ... ... ACM Press New York, NY, USA https://www.snipit.org/public/alan/viewsnip.php?id=4407 http://portal.acm.org/citation.cfm?doid=93597.98719 2007-03-22T14:56:58Z Performance comparison of distributive and mergesort as ... Source Journal of Systems and Software archive Volume 10 , Issue 3 (October 1989) table of contents Pages: 187 - 200 ... Elsevier Science Inc. New York, NY, USA https://www.snipit.org/public/alan/viewsnip.php?id=4406 http://portal.acm.org/citation.cfm?doid=68684.68687 2007-03-22T14:53:42Z Optimal disk I/O with parallel block transfer Full text pdf formatPdf (1.04 MB) Source Annual ACM Symposium on Theory of Computing archive Proceedings of the twenty-second annual ACM symposium on ... ... ACM Press New York, NY, USA https://www.snipit.org/public/alan/viewsnip.php?id=4405 http://portal.acm.org/citation.cfm?doid=100216.100234 2007-03-22T14:48:51Z Greed Sort: An Optimal External Sorting Algorithm for Mu... Mark H. Nodine and Jeffrey Scott Vitter March 1991 Abstract: We present an optimal deterministic algorithm for extern ... https://www.snipit.org/public/alan/viewsnip.php?id=4404 http://www.cs.brown.edu/publications/techreports/reports/CS-91-20.html 2007-03-22T14:47:31Z External mergesort is normally implemented so that each ... contiguously on disk and blocks of data are read exactly... are needed during merging. We investigate two ideas for ... performance of external mergesort: interleaved layout an... strategy. I https://www.snipit.org/public/alan/viewsnip.php?id=4403 http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tk/&toc=comp/trans/tk/1996/02/k2toc.xml&DOI=10.1109/69.494169 2007-03-22T12:28:35Z We provide tight upper and lower bounds, up to a constan... number of inputs and outputs (I/OS) between internal mem... storage required for five sorting-related problems: sort... Fourier transform (FFT), permutation networks, permuting... transpositi https://www.snipit.org/public/alan/viewsnip.php?id=4402 http://portal.acm.org/citation.cfm?doid=48529.48535 2007-03-22T12:28:00Z Sorting is a significant activity for which better metho... sought. In many computing scenarios, sorting must be don... majority of data items remaining on an auxiliary storage... paper introduces a new data structure, the *M-ary tree, ... external so https://www.snipit.org/public/alan/viewsnip.php?id=4401 http://portal.acm.org/citation.cfm?id=131220&coll=portal&dl=ACM 2007-03-22T12:26:27Z The memory model assumed for this discussion is a paged ... The heapsort algorithms seen so far are not very well su ... NOTE: Be aware that the words 'page access' does not nec ... One may wonder if the d-heaps described in chapter 5 can ... The drawbac https://www.snipit.org/public/alan/viewsnip.php?id=4400 http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node23.html 2007-03-22T12:02:00Z Heapsort is an internal sorting method which sorts an ar... place in O(n log n) time. Heapsort is generally consider... external random-access sorting. By replacing key compari... operations on pages, it is shown how to obtain an in-pla... which requi https://www.snipit.org/public/alan/viewsnip.php?id=4399 http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/ts/&toc=comp/trans/ts/1989/07/e7toc.xml&DOI=10.1109/32.29490 2007-03-22T11:59:07Z M. Lühring, K. Sattler, K. Schmidt, E. Schallehn: Autonomous Tuning with Soft Indexes ICDE Workshop on Self-Managing Database Systerms (SMDB07 ... https://www.snipit.org/public/alan/viewsnip.php?id=4398 http://www.tu-ilmenau.de/fakia/Databases-and-Inform.dbis2.0.html?&L=1 2007-03-22T11:24:16Z A versatile variant of Heapsort, adapted for external di... presented. On a single processor RAM with internal memor... Θ(m + kbw) words, it sorts a file of n records of ... stored in m physical blocks, each consisting of b record... using O(m l https://www.snipit.org/public/alan/viewsnip.php?id=4397 http://citeseer.ist.psu.edu/wiedermann97optimal.html 2007-03-22T11:10:44Z Selecting k smallest or largest elements Another fundamental selection problem is that of selecti ... https://www.snipit.org/public/alan/viewsnip.php?id=1738 http://en.wikipedia.org/wiki/Selection_algorithm 2006-07-22T14:20:47Z We show that, in order to achieve efficient maintenance ... binary search tree, no shape restriction other than a lo... is required. The obtained class of trees, general balanc... maintained at a logarithmic amortized cost with no balan... stored in t https://www.snipit.org/public/alan/viewsnip.php?id=1614 http://citeseer.ist.psu.edu/andersson99general.html 2006-07-02T09:47:59Z Abstract: Most texts describing data structures give imp... implementations. These are either difficult or tedious t... functional (non sideeffecting) form. This technical repo... implementation of sets in the functional subset of Stand... implementat https://www.snipit.org/public/alan/viewsnip.php?id=1613 http://citeseer.ist.psu.edu/162336.html 2006-07-02T09:42:00Z AVL tree (data structure) Definition: A balanced binary search tree where the heig ... https://www.snipit.org/public/alan/viewsnip.php?id=1612 http://www.nist.gov/dads/HTML/avltree.html 2006-07-02T09:29:29Z AVL tree From Wikipedia, the free encyclopedia https://www.snipit.org/public/alan/viewsnip.php?id=1611 http://en.wikipedia.org/wiki/AVL_tree 2006-07-02T09:28:04Z AVL Trees An AVL tree is another balanced binary search tree. Name ... https://www.snipit.org/public/alan/viewsnip.php?id=1609 http://www.oopweb.com/Algorithms/Documents/PLDS210/VolumeFrames.html?/Algorithms/Documents/PLDS210/Volume/AVL.html 2006-07-02T09:26:43Z