A Unified Analysis of Batched Searching of Sequential and Tree-Structured Files.

@article{DBLP:journals/tods/LangDJ89,
  author    = {Sheau-Dong Lang and
               James R. Driscoll and
               Jiann H. Jou},
  title     = {A Unified Analysis of Batched Searching of Sequential and Tree-Structured
               Files},
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {4},
  year      = {1989},
  pages     = {604-618},
  ee        = {http://doi.acm.org/10.1145/76902.76908, db/journals/tods/LangDJ89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1989 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982) BibTeX

[2]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[3]

Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) BibTeX

[4]

Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX

[5]

To-Yat Cheung: Estimating Block Accesses and Number of Recorde in File Management. Commun. ACM 25(7): 484-487(1982) BibTeX

[6]

Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX

[7]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[8]

James R. Driscoll, Sheau-Dong Lang, LeRoy A. Franklin: Modeling B-Tree Insertion Activity. Inf. Process. Lett. 26(1): 5-18(1987) BibTeX

[9]

...

[10]

Jane Fedorowicz: Database Performance Evaluation in an Indexed File Environment. ACM Trans. Database Syst. 12(1): 85-110(1987) BibTeX

[11]

...

[12]

Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX

[13]

Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou: Improving the Differential File Technique via Batch Operations for Tree Structured File Organizations. ICDE 1986: 524-532 BibTeX

[14]

Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou: Batch Insertion for Tree Structured File Organizations - Improving Differential Database Reprensentation. Inf. Syst. 11(2): 167-175(1986) BibTeX

[15]

Thomas C. Lowe: The Influence of Data Base Characteristics and Usage on Direct Access File Organization. J. ACM 15(4): 535-548(1968) BibTeX

[16]

Prashant Palvia: Expressions for Batched Searching of Sequential and Hierarchical Files. ACM Trans. Database Syst. 10(1): 97-106(1985) BibTeX

[17]

Marek Piwowarski: Comments on Batched Searching of Sequential and Tree-Structured Files. ACM Trans. Database Syst. 10(2): 285-287(1985) BibTeX

[18]

Ben Shneiderman, Victor Goodman: Batched Searching of Sequential and Tree Structured Files. ACM Trans. Database Syst. 1(3): 268-275(1976) BibTeX

[19]

Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: A general framework for computing block accesses. Inf. Syst. 12(2): 177-190(1987) BibTeX

[20]

Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Estimating Block Accesses in Database Organizations: A Closed Noniterative Formula. Commun. ACM 26(11): 940-944(1983) BibTeX

[21]

...

[22]

S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX

[23]

Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

[24]

John Zahorjan, Barbara J. Bell, Kenneth C. Sevcik: Estimating Block Transfers When Record Access Probabilities are Non-Uniform. Inf. Process. Lett. 16(5): 249-252(1983) BibTeX

[25]

George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949
BibTeX

Referenced by

1. Boris Shidlovsky, Elisa Bertino: A Graph-Theoretic Approach to Indexing in Object-Oriented Databases. ICDE 1996: 230-237
2. Elisa Bertino: Index Configuration in Object-Oriented Databases. VLDB J. 3(3): 355-399(1994)