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}
}
BibTeX

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 ... BibTeX

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 BibTeX , 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 BibTeX
[2]
T. Bially: Space-Filling Curves: Their Generation and Their Application to Bandwidth Reduction. IEEE Transactions on Information Theory 15(6): 658-664(1969) BibTeX
[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) BibTeX
[5]
Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238 BibTeX
[6]
Christos Faloutsos: Gray Codes for Partial Match and Range Queries. IEEE Trans. Software Eng. 14(10): 1381-1393(1988) BibTeX
[7]
Christos Faloutsos, Shari Roseman: Fractals for Secondary Key Retrieval. PODS 1989: 247-252 BibTeX
[8]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[9]
...
[10]
H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319 BibTeX
[11]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
[12]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[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) BibTeX
[14]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 BibTeX
[15]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX
[16]
Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305 BibTeX
[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) BibTeX
[20]
Hanan Samet: Hierarchical Representations of Collections of Small Rectangles. ACM Comput. Surv. 20(4): 271-309(1988) BibTeX
[21]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
[22]
Yuzuru Tanaka: Adaptive Segmentation Schemes for Large Relational Database Machines. IWDM 1983: 293-318 BibTeX

Referenced by

  1. Joseph K. P. Kuan, Paul H. Lewis: A Study on Data Point Search for HG-Trees. SIGMOD Record 28(1): 90-96(1999)
  2. Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, Yun Wang: High Level Indexing of User-Defined Types. VLDB 1999: 554-564
  3. H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava: Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse. SIGMOD Conference 1999: 37-48
  4. Volker Markl, Martin Zirkel, Rudolf Bayer: Processing Operations with Restrictions in RDBMS without External Sorting: The Tetris Algorithm. ICDE 1999: 562-571
  5. Shashi Shekhar, Sivakumar Ravada, Vipin Kumar, Douglas Chubb, Greg Turner: Declustering and Load-Balancing Methods for Parallelizing Geographic Information Systems. IEEE Trans. Knowl. Data Eng. 10(4): 632-655(1998)
  6. Bongki Moon, Joel H. Saltz: Scalability Analysis of Declustering Methods for Multidimensional Range Queries. IEEE Trans. Knowl. Data Eng. 10(2): 310-327(1998)
  7. Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast and Effective Retrieval of Medical Tumor Shapes. IEEE Trans. Knowl. Data Eng. 10(6): 889-904(1998)
  8. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  9. Rasa Bliujute, Christian S. Jensen, Simonas Saltenis, Giedrius Slivinskas: R-Tree Based Indexing of Now-Relative Bitemporal Data. VLDB 1998: 345-356
  10. Kaushik Chakrabarti, Sharad Mehrotra: Dynamic Granular Locking Approach to Phantom Protection in R-Trees. ICDE 1998: 446-454
  11. Apostolos Papadopoulos, Yannis Manolopoulos: Multiple Range Query Optimization in Spatial Databases. ADBIS 1998: 71-82
  12. Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: Using Extended Feature Objects for Partial Similarity Retrieval. VLDB J. 6(4): 333-348(1997)
  13. Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations. IEEE Trans. Knowl. Data Eng. 9(1): 102-119(1997)
  14. Euripides G. M. Petrakis, Christos Faloutsos: Similarity Searching in Medical Image Databases. IEEE Trans. Knowl. Data Eng. 9(3): 435-447(1997)
  15. Christos Faloutsos, H. V. Jagadish, Yannis Manolopoulos: Analysis of the n-Dimensional Quadtree Decomposition for Arbitrary Hyperectangles. IEEE Trans. Knowl. Data Eng. 9(3): 373-383(1997)
  16. Sunita Sarawagi: Indexing OLAP Data. IEEE Data Eng. Bull. 20(1): 36-43(1997)
  17. Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik: The New Jersey Data Reduction Report. IEEE Data Eng. Bull. 20(4): 3-45(1997)
  18. John C. Shafer, Rakesh Agrawal: Parallel Algorithms for High-dimensional Similarity Joins for Data Mining Applications. VLDB 1997: 176-185
  19. Viswanath Poosala, Yannis E. Ioannidis: Selectivity Estimation Without the Attribute Value Independence Assumption. VLDB 1997: 486-495
  20. Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997: 249-256
  21. Chialin Chang, Bongki Moon, Anurag Acharya, Carter Shock, Alan Sussman, Joel H. Saltz: Titan: A High-Performance Remote Sensing Database. ICDE 1997: 375-384
  22. Kenneth C. Sevcik, Nick Koudas: Filter Trees for Managing Spatial Data over a Range of Size Granularities. VLDB 1996: 16-27
  23. Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996: 215-226
  24. Ajit A. Diwan, Sanjeeva Rane, S. Seshadri, S. Sudarshan: Clustering Techniques for Minimizing External Path Length. VLDB 1996: 342-353
  25. Shaul Dar, Michael J. Franklin, Björn Þór Jónsson, Divesh Srivastava, Michael Tan: Semantic Data Caching and Replacement. VLDB 1996: 330-341
  26. Gennady Antoshenkov: Dynamic Optimization of Index Scans Restricted by Booleans. ICDE 1996: 430-440
  27. Nick Koudas, Christos Faloutsos, Ibrahim Kamel: Declustering Spatial Databases on a Multi-Computer Architecture. EDBT 1996: 592-614
  28. Paolo Ciaccia: Optimal Multi-Block Read Schedule for Partitioned Signature Files. EDBT 1996: 241-255
  29. Christos Faloutsos: Fast Searching by Content in Multimedia Databases. IEEE Data Eng. Bull. 18(4): 31-40(1995)
  30. Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573
  31. Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79
  32. Christos Faloutsos, King-Ip Lin: FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995: 163-174
  33. Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509
  34. David J. DeWitt, Navin Kabra, Jun Luo, Jignesh M. Patel, Jie-Bing Yu: Client-Server Paradise. VLDB 1994: 558-569
  35. Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Kumar V. Vadaparty: A Scientific Database System for Polymers and Materials Engineering Needs. SSDBM 1994: 138-148
  36. Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208
  37. Yvonne Zhou, Shashi Shekhar, Mark Coyle: Disk Allocation Methods for Parallelizing Grid Files. ICDE 1994: 243-252
  38. Sunita Sarawagi, Michael Stonebraker: Efficient Organization of Large Multidimensional Arrays. ICDE 1994: 328-336
  39. Bhaskar Himatsingka, Jaideep Srivastava: Performance Evaluation of Grid Based Multi-Attibute Record Declustering Methods. ICDE 1994: 356-365
  40. Manish Arya, William F. Cody, Christos Faloutsos, Joel E. Richardson, Arthur Toya: QBISM: Extending a DBMS to Support 3D Medical Images. ICDE 1994: 314-325
  41. Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204
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:40:03 2009