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

Effective Clustering of Objects Stored by Linear Hashing.

Jukka Teuhola: Effective Clustering of Objects Stored by Linear Hashing. CIKM 1995: 274-280
@inproceedings{DBLP:conf/cikm/Teuhola95,
  author    = {Jukka Teuhola},
  title     = {Effective Clustering of Objects Stored by Linear Hashing},
  booktitle = {CIKM '95, Proceedings of the 1995 International Conference on
               Information and Knowledge Management, November 28 - December
               2, 1995, Baltimore, Maryland, USA},
  publisher = {ACM},
  year      = {1995},
  pages     = {274-280},
  ee        = {db/conf/cikm/Teuhola95.html, http://doi.acm.org/10.1145/221270.221590},
  crossref  = {DBLP:conf/cikm/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A new object identification and storage scheme for object databases is here suggested, supporting fast access of both singular objects and clusters. An object identifier consists of a cluster code prefixed by a unique number within cluster. The page allocation technique of linear hashing is used, but identifiers themselves are used as pseudokeys. Clustering can be based on any rule that determines an existing object, close to which a new object should be positioned. The new identifier is derived from that of the existing ob ject by hashing, maybe repeatedly. Two approaches of repeated hashing are suggested: the l-way scheme performs a linear chain of rehashes, while the 2-way scheme probes a path in art implicit, randomized, tree-structured hierarchy of rehashes. The latter has at most logarithmic insert time, but clustering is somewhat less effective than for the l-way scheme. The suggested approach shares the advantages of plain surrogates and structured addresses: In addition to clustering, objects can be retrieved with one access, as a rule, in spite of page splitting. This is accomplished without any additional stored data to support the technique.

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


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

CIKM '95, Proceedings of the 1995 International Conference on Information and Knowledge Management, November 28 - December 2, 1995, Baltimore, Maryland, USA. ACM 1995
Contents BibTeX

Online Edition

Citation Page BibTeX

References

[1]
Jay Banerjee, Won Kim, Sung-Jo Kim, Jorge F. Garza: Clustering a DAG for CAD Databases. IEEE Trans. Software Eng. 14(11): 1684-1699(1988) BibTeX
[2]
R. G. G. Cattell: Object Data Management: Object-Oriented and Extended Relational Database Systems (Revised Edition). Addison-Wesley 1994, ISBN 0-201-54748-1
BibTeX
[3]
Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988) BibTeX
[4]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) BibTeX
[5]
Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416 BibTeX
[6]
Won Kim: Introduction to Object-Oriented Databases. MIT Press 1990, ISBN 0-262-11124-1
BibTeX
[7]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[8]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[9]
Per-Åke Larson, Ajay Kajla: File Organization: Implementation of a Method Guaranteeing Retrieval in One Access. Commun. ACM 27(7): 670-677(1984) BibTeX
[10]
Per-Åke Larson: Linear Hashing with Overflow-Handling by Linear Probing. ACM Trans. Database Syst. 10(1): 75-89(1985) BibTeX
[11]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[12]
David Maier, Jacob Stein, Allen Otis, Alan Purdy: Development of an Object-Oriented DBMS. OOPSLA 1986: 472-482 BibTeX
[13]
Michael Stonebraker, Lawrence A. Rowe, Michael Hirohama: The Implementation of Postgres. IEEE Trans. Knowl. Data Eng. 2(1): 125-142(1990) BibTeX
[14]
Jukka Teuhola: Selection of Object Surrogates to Support Clustering. Data Knowl. Eng. 15(2): 169-183(1995) BibTeX
[15]
Manolis M. Tsangaris, Jeffrey F. Naughton: A Stochastic Approach for Clustering in Object Bases. SIGMOD Conference 1991: 12-21 BibTeX
[16]
Manolis M. Tsangaris, Jeffrey F. Naughton: On the Performance of Object Clustering Techniques. SIGMOD Conference 1992: 144-153 BibTeX
[17]
...
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
CIKM 1995 Proceedings, 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:01:50 2009