A new representation for linear lists

A new representation for linear lists,10.1145/800105.803395,Leonidas J. Guibas,Edward M. McCreight,Michael F. Plass,Janet R. Roberts

A new representation for linear lists   (Citations: 91)
BibTex | RIS | RefWorks Download
We present a new data structure for maintaining a set of records in a linear list according to their key values. This data structure has the property that we can keep a number of fingers at points of interest in the key space (e.g., the beginning or the end of the list), so that access and modification in the neighborhood of a finger is very efficient. In the Section 2 we discuss the general structure of our B-tree. Since we propose to search the tree from a leaf upwards, additional links need to be introduced. In Section 3 we show how to obtain our result for the case of one finger. A key idea is the construction of a number representation behaving as described above, which we can use to model the propagation of modifications in the B-tree along the finger path. In Section 4 we generalize the structure so that several fingers in the key space can be maintained, with the advantage that access is cheap in the neighborhood of each finger. Finally in Section 5 we present some implementation notes and applications, mostly to sorting.
Conference: ACM Symposium on Theory of Computing - STOC , pp. 49-60, 1977
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Early examples of data structures relying on number systems include finger search trees [2] and binomial queues [3]...

    Amr Elmasryet al. Strictly-Regular Number System and Data Structures

    • ...Guibas, McCreight, Plass, and Roberts [16] showed that any sorting algorithm needs at least ( n(1+log(1+k=n))) comparisons in the worst case, where n is the size of an input array and k is the number of inversions between the positions (or indices) in the input array and the increasing order of numbers themselves...
    • ...Since the procedures except for the kd-tree construction can be done in O(n) time, the lower bound by Guibas, McCreight, Plass, and Roberts [16] proves the theorem...
    • ...For the sorting problem, several algorithms running in O(n(1 + log(1 +k=n))) time [12, 13, 20{23] have been presented, and there is a tight lower bound [16]...

    Hee-Kap Ahnet al. Adaptive Algorithms for Planar Convex Hull Problems

    • ...Among others, Mehlhorn [Meh79] and Guibas et al. [GMPR77] considered the number of pairs in the wrong order, dened more formally as inv(X) =jf(i;j)j1 i < j n;xi > xjgj;...

    Jérémy Barbayet al. Compressed Representations of Permutations, and Applications

    • ...In [17], the performance of an adaptive sorting algorithm with respect to the measure Inv is presented...

    Roger D. Chamberlainet al. Sorting on architecturally diverse computer systems

    • ...Though the Surazhsky-Gotsman algorithm [12] is already a simplification of a previous algorithm [32], it still requires implementation of many nontrivial data structures and algorithms described in [33], [34], [35], [36] in addition to the OðnÞ triangulation of either [37] or [38]...

    Bill Baxteret al. Compatible Embedding for 2D Shape Animation

Sort by: