login/register

Snip!t channels - Alan Dix

Channels > AVL trees

Order by: date | title | url | snip    Show: just this cat | subcats too

2007-03-22 11:10:44     An Optimal in-Situ Disk Sorting Algorithm Based on Heapsort (ResearchIndex)

http://citeseer.ist.psu.edu/wiedermann97optimal.html

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

view snip

/Channels/AVL trees

2006-07-02 09:42:00     Implementing Sets Efficiently in a Functional Language (ResearchIndex)

http://citeseer.ist.psu.edu/162336.html

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

view snip

/Channels/AVL trees

2007-03-22 15:12:41     Practical In-Place Mergesort - Katajainen, Pasanen, Teuhola (ResearchIndex)

http://citeseer.ist.psu.edu/katajainen96practical.html

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

view snip

/Channels/AVL trees

2006-07-02 09:29:29     AVL tree

http://www.nist.gov/dads/HTML/avltree.html

AVL tree
(data structure)
Definition: A balanced binary search tree where the heig ...

view snip

/Channels/AVL trees

2006-07-02 09:28:04     AVL tree - Wikipedia, the free encyclopedia

http://en.wikipedia.org/wiki/AVL_tree

AVL tree
From Wikipedia, the free encyclopedia

view snip

/Channels/AVL trees

2006-07-02 09:26:43     OOPWeb.com - Data Structures and Algorithms by John Morris

http://www.oopweb.com/Algorithms/Do.../VolumeFrames.html?...

[ From frame: http://www.oopweb.com/Algorithms/Documents/PLDS2.../AVL.html ]

AVL Trees
An AVL tree is another balanced binary search tree. Name ...

view snip

/Channels/AVL trees

2007-03-22 15:08:46     External memory algorithms and data structures

http://portal.acm.org/citation.cfm?...

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

view snip

/Channels/AVL trees

2007-03-22 12:28:35     Speeding Up External Mergesort

http://csdl2.computer.org/persagen/DLAbsToc.jsp?...

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

view snip

/Channels/AVL trees

2007-03-22 14:56:58     FastSort: a distributed single-input single-output external sort

http://portal.acm.org/citation.cfm?doid=93597.98719

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

view snip

/Channels/AVL trees

2007-03-22 14:47:31     Brown CS: Tech Report CS-91-20

http://www.cs.brown.edu/publications/techre.../CS-91-20.html

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 ...

view snip

/Channels/AVL trees

2007-03-22 11:59:07     The External Heapsort

http://csdl2.computer.org/persagen/DLAbsToc.jsp?...

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

view snip

/Channels/AVL trees

2007-03-22 11:24:16     DBIS: Databases and Information Systems Group

http://www.tu-ilmenau.de/...ases-and-Inform.dbis2.0.html?...

M. L�ng, K. Sattler, K. Schmidt, E. Schallehn:
Autonomous Tuning with Soft Indexes
ICDE Workshop on Self-Managing Database Systerms (SMDB07 ...

view snip

/Channels/AVL trees

2007-03-22 14:48:51     Optimal disk I/O with parallel block transfer

http://portal.acm.org/citation.cfm?doid=100216.100234

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

view snip

/Channels/AVL trees

2007-03-22 14:53:42     Performance comparison of distributive and mergesort as external sorting algorithms

http://portal.acm.org/citation.cfm?doid=68684.68687

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

view snip

/Channels/AVL trees

2006-07-22 14:20:47     Selection algorithm - Wikipedia, the free encyclopedia

http://en.wikipedia.org/wiki/Selection_algorithm

Selecting k smallest or largest elements
Another fundamental selection problem is that of selecti ...

view snip

/Channels/AVL trees

2007-03-22 12:26:27     The *M-ary tree and *Ternary hillsort

http://portal.acm.org/citation.cfm?...

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

view snip

/Channels/AVL trees

2007-03-22 12:02:00     The External Heapsort

http://www.diku.dk/forskning/performance-engi.../node23.html

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

view snip

/Channels/AVL trees

2007-03-22 12:28:00     The input/output complexity of sorting and related problems

http://portal.acm.org/citation.cfm?doid=48529.48535

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

view snip

/Channels/AVL trees

2006-07-02 09:47:59     General Balanced Trees - Andersson (ResearchIndex)

http://citeseer.ist.psu.edu/andersson99general.html

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

view snip

/Channels/AVL trees

Order by: date | title | url | snip    Show: just this cat | subcats too