Digital Symposium Collection 2000

Locality Preserving Dictionaries: Theory and Application to Clustering in Databases Vijayshankar Raman   View Paper (PDF)   Return to Indexing Abstract We discuss strategies for building locality preserving dictionaries (LPDs) in which all data items within a range lie together, within a space that is a small function of the number of items in the range. We describe an approach where the memory space is partitioned and items are placed in sorted order, with judiciously placed gaps between them, resulting in efficient insert, delete, and search operations. We adapt our algorithms to the particular application of storing database relations on disk via LPDs. By providing a natural clustering mechanism for data in a sorted order instead of simply clustering data at a page granularity, LPDs provide much better I/O performance than traditional clustered indexes on range searches, as well as on access of data in sorted order. Analytical studies of LPDs and clustered B-Trees show that using LPDs results in up to 5 to 13 times faster range searches and sorted order accesses over using a clustered B-Tree, at the expense of 0 to 75% overhead in storage needs and up to 28% overhead in insert/delete costs. References Note: References link to DBLP on the Web. [BBK98] Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel : The Pyramid-Tree: Breaking the Curse of Dimensionality. SIGMOD Conference 1998 : 142-153 [CLR90] ... [DNO98] ... [GG97] Jim Gray , Goetz Graefe : The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb. SIGMOD Record 26(4) : 63-68(1997) [GK97] ... [HS66] F. C. Hennie , Richard Edwin Stearns : Two-Tape Simulation of Multitape Turing Machines. JACM 13(4) : 533-546(1966) [IMRV97] Piotr Indyk , Rajeev Motwani , Prabhakar Raghavan , Santosh Vempala : Locality-Preserving Hashing in Multidimensional Spaces. STOC 1997 : 618-625 [Jag97] H. V. Jagadish : Analysis of the Hilbert Curve for Representing Two-Dimensional Space. IPL 62(1) : 17-22(1997) [JS94] Theodore Johnson , Dennis Shasha : Utilization of B-trees with Inserts, Deletes and Modifies. PODS 1989 : 235-246 [LS96] Nathan Linial , Ori Sasson : Non-Expansive Hashing. STOC 1996 : 509-518 [PK98] ... [RvIG98] ... [Yao78] Andrew Chi-Chih Yao : On Random 2-3 Trees. Acta Informatica 9 : 159-170(1978) [ZS96] Chendong Zou , Betty Salzberg : On-line Reorganization of Sparsely-populated B+trees. SIGMOD Conf. 1996 : 115-124 BIBTEX @inproceedings{DBLP:conf/pods/Raman99,   author    = {Vijayshankar Raman},    title     = {Locality Preserving Dictionaries: Theory and Application to Clustering                 in Databases},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {337-345},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM