ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Discipline for Robustness or Storage Reduction in Binary Search Trees.

J. Ian Munro, Patricio V. Poblete: A Discipline for Robustness or Storage Reduction in Binary Search Trees. PODS 1983: 70-75
@inproceedings{DBLP:conf/pods/MunroP83,
  author    = {J. Ian Munro and
               Patricio V. Poblete},
  title     = {A Discipline for Robustness or Storage Reduction in Binary Search
               Trees},
  booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 21-23, 1983, Colony Square Hotel,
               Atlanta, Georgia},
  publisher = {ACM},
  year      = {1983},
  isbn      = {0-89791-097-4},
  pages     = {70-75},
  ee        = {http://doi.acm.org/10.1145/588058.588069, db/conf/pods/MunroP83.html},
  crossref  = {DBLP:conf/pods/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We develop a method of representing binary search trees in an environment in which pointers and other structural information may be "lost" or "maliciously altered". Our fault tolerant representation permits any 2 field changes to be detected and any 1 to be corrected without significantly increasing to storage requirements of the binary tree. The detection and correction procedures applied to the entire tree require O(n) time.

Our discipline is also used to represent binary search trees with a single pointer per datum without altering the cost of searching or updating. While our scheme can be applied in conjunction with any underlying tree balancing scheme ([AVL], bounded balance [Nievergelt et al.] etc.), if no balancing scheme is employed, the trees we form will have significantly shorter search paths than those formed using the straightforward algorithm.

Copyright © 1983 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia. ACM 1983, ISBN 0-89791-097-4
Contents BibTeX

Online Edition: ACM Digital Library


References

[AVL]
...
[Knuth]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[Nievergelt et al.]
Jürg Nievergelt, Edward M. Reingold: Binary Search Trees of Bounded Balance. SIAM J. Comput. 2(1): 33-43(1973) BibTeX
[Poblete]
...
[Taylor et al. 1]
David J. Taylor, David E. Morgan, James P. Black: Redundancy in Data Structures: Improving Software Fault Tolerance. IEEE Trans. Software Eng. 6(6): 585-594(1980) BibTeX
[Taylor et al. 2]
David J. Taylor, David E. Morgan, James P. Black: Redundancy in Data Structures: Some Theoretical Result. IEEE Trans. Software Eng. 6(6): 595-604(1980) BibTeX
[Taylor et al. 3]
...
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:42 2009