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

Linear Clustering of Objects with Multiple Atributes.

H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342
@inproceedings{DBLP:conf/sigmod/Jagadish90,
  author    = {H. V. Jagadish},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {Linear Clustering of Objects with Multiple Atributes},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {332-342},
  ee        = {http://doi.acm.org/10.1145/93597.98742, db/conf/sigmod/Jagadish90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

There is often a need to map a multi-dimensional space on to a one-dimensional space. For example, this kind of mapping has been proposed to permit the use of one-dimensional indexing techniques to a multi-dimensional index space such as in a spatial database. This kind of mapping is also of value in assigning physical storage, such as assigning buckets to records that have been indexed on multiple attributes, to minimize the disk access effort.

In this paper, we discuss what the desired properties of such a mapping are, and evaluate, through analysis and simulation, several mappings that have been proposed in the past. We present a mapping based on Hilbert's space-filling curve, which out-performs previously proposed mappings on average over a variety of different operating conditions.

Copyright © 1990 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

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

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

Printed Edition

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library


References

[1]
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
T. Bially: Space-Filling Curves: Their Generation and Their Application to Bandwidth Reduction. IEEE Transactions on Information Theory 15(6): 658-664(1969) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Christos Faloutsos: Gray Codes for Partial Match and Range Queries. IEEE Trans. Software Eng. 14(10): 1381-1393(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Christos Faloutsos, Shari Roseman: Fractals for Secondary Key Retrieval. PODS 1989: 247-252 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
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
[9]
...
[10]
H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
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
[14]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
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
[16]
Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
...
[18]
...
[19]
James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Hanan Samet: Hierarchical Representations of Collections of Small Rectangles. ACM Comput. Surv. 20(4): 271-309(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Yuzuru Tanaka: Adaptive Segmentation Schemes for Large Relational Database Machines. IWDM 1983: 293-318 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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