Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Data Structure
Point of Interest
Related Publications
(15)
Sorting Presorted Files
Finger search trees with constant insertion time
Linear Lists and Prorty Queues as Balanced Binary Trees
Organization and Maintenance of Large Ordered Indexes
Alternatives to splay trees with O(log n ) worstcase access times
Subscribe
Academic
Publications
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
Edit
A new representation for linear lists
(
Citations: 91
)
BibTex

RIS

RefWorks
Download
Leonidas J. Guibas
,
Edward M. McCreight
,
Michael F. Plass
,
Janet R. Roberts
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 Btree. 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 Btree 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. 4960, 1977
DOI:
10.1145/800105.803395
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.
(
portal.acm.org
)
(
portal.acm.org
)
(
qwas.stl.ru
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(52)
...Early examples of data structures relying on number systems include finger search trees [
2
] and binomial queues [3]...
Amr Elmasry
,
et al.
StrictlyRegular 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 kdtree 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
]...
HeeKap Ahn
,
et 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 Barbay
,
et 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. Chamberlain
,
et al.
Sorting on architecturally diverse computer systems
...Though the SurazhskyGotsman 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 Baxter
,
et al.
Compatible Embedding for 2D Shape Animation
References
(6)
Organization and Maintenance of Large Ordered Indices
(
Citations: 575
)
Rudolf Bayer
,
Edward M. McCreight
Journal:
Acta Informatica  ACTA
, vol. 1, pp. 173189, 1972
Efficient generation of the binary reflected gray code and its applications
(
Citations: 104
)
James R. Bitner
,
Gideon Ehrlich
,
Edward M. Reingold
Journal:
Communications of The ACM  CACM
, vol. 19, no. 9, pp. 517521, 1976
Two applications of a probabilistic search technique: Sorting X+Y and building balanced search trees
(
Citations: 29
)
Michael L. Fredman
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 240244, 1975
Algorithms + data structures &equil; programs
(
Citations: 30
)
N Wirth
Published in 1976.
Organization and Maintenance of Large Ordered Indexes
(
Citations: 406
)
Rudolf Bayer
,
Edward M. Mccreight
Conference:
International Conference on Management of Data  SIGMOD
, pp. 107141, 1970
Sort by:
Citations
(91)
StrictlyRegular Number System and Data Structures
Amr Elmasry
,
Claus Jensen
,
Jyrki Katajainen
Conference:
Scandinavian Workshop on Algorithm Theory  SWAT
, pp. 2637, 2010
Adaptive Algorithms for Planar Convex Hull Problems
HeeKap Ahn
,
Yoshio Okamoto
Conference:
Frontiers in Algorithmics  FAW
, pp. 316326, 2010
Compressed Representations of Permutations, and Applications
(
Citations: 13
)
Jérémy Barbay
,
Gonzalo Navarro
Journal:
Computing Research Repository  CORR
, vol. abs/0902.1, pp. 111122, 2009
Sorting on architecturally diverse computer systems
(
Citations: 7
)
Roger D. Chamberlain
,
Narayan Ganesan
Conference:
Supercomputing Conference  SC
, pp. 3946, 2009
Compatible Embedding for 2D Shape Animation
(
Citations: 1
)
Bill Baxter
,
Pascal Barla
,
Kenichi Anjyo
Journal:
IEEE Transactions on Visualization and Computer Graphics  TVCG
, vol. 15, no. 5, pp. 867879, 2009