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

P-Tree: A B-Tree Index for Lists.

Ke Wang, Beng Chin Ooi, Sam Yuan Sung: P-Tree: A B-Tree Index for Lists. DASFAA 1999: 221-228
@inproceedings{DBLP:conf/dasfaa/WangOS99,
  author    = {Ke Wang and
               Beng Chin Ooi and
               Sam Yuan Sung},
  editor    = {Arbee L. P. Chen and
               Frederick H. Lochovsky},
  title     = {P-Tree: A B-Tree Index for Lists},
  booktitle = {Database Systems for Advanced Applications, Proceedings of the
               Sixth International Conference on Database Systems for Advanced
               Applications (DASFAA), April 19-21, Hsinchu, Taiwan},
  publisher = {IEEE Computer Society},
  year      = {1999},
  isbn      = {0-7695-0084-6},
  pages     = {221-228},
  ee        = {db/conf/dasfaa/WangOS99.html},
  crossref  = {DBLP:conf/dasfaa/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The high frequency of applications involving large, ordered, nested lists suggests that list is the "next most" natural data type after set. A list differs from a set through positioning and nesting elements within the list. Directly supporting such position-related operations will greatly improve the performance of database systems targeting at the above applications. Unlike other attributes, the position will be changed by insertion and deletion within a list and known methods are not appropriate for indexing the position. We present an indexing structure, called the P-tree (where P for position), to index a set of lists. The P-tree generalizes the B-tree by dealing with a set of lists rather than a set of records, while preserving all the properties of the B-tree.

Copyright © 1999 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 2 Number 1" and ...

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Online Edition: IEEE Computer Society Digital Library

Citation Page

References

[1]
François Bancilhon, Sophie Cluet, Claude Delobel: A Query Language for the O2 Object-Oriented Database System. DBPL 1989: 122-138 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Michael J. Carey, David J. DeWitt, Scott L. Vandenberg: A Data Model and Query Language for EXODUS. SIGMOD Conference 1988: 413-423 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Hans-Peter Kriegel: Performance Comparison of Index Structures for Multi-Key Retrieval. SIGMOD Conference 1984: 186-196 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Joel E. Richardson: Supporting Lists in a Data Model (A Timely Approach). VLDB 1992: 127-138 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Michael Stonebraker, Heidi Stettner, Nadene Lynn, Joseph Kalash, Antonin Guttman: Document Processing in a Relational Database System. ACM Trans. Inf. Syst. 1(2): 143-158(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Bharathi Subramanian, Stanley B. Zdonik, Theodore W. Leung, Scott L. Vandenberg: Ordered Types in the AQUA Data Model. DBPL 1993: 115-135 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:09:19 2010 by Michael Ley (ley@uni-trier.de)