Multidimensional quantile hashing is very efficient for nonuniform distributions
作者： Hans-Peter Kriegel , Bernhard Seeger
DOI: 10.1016/0020-0255(89)90014-5
关键词:
摘要: Abstract Previous multidimensional hashing schemes without directory which generalize the concept of Litwin's linear partition data space into equidistant cells using a dynamic orthogonal grid. Thus performance these degenerates in case nonuniform record distributions. We propose new scheme directory, called quantile hashing, avoids this important drawback. Quantile exhibits for independent distributions practically same as uniform The gain comparison with other is demonstrated by experiments.
elsevier.com
sci-hub.se 参考文章(21)
Ekow J. Otoo, A Mapping Function for the Directory of a Multidimensional Extendible Hashing very large data bases. pp. 493- 506 ,(1984)
Per-Åke Larson, Linear hashing with partial expansions very large data bases. pp. 224- 232 ,(1980)
Hans-Peter Kriegel, Bernhard Seeger, Multidimensional Order Preserving Linear Hashing with Partial Expansions international conference on database theory. pp. 203- 220 ,(1986) , 10.1007/3-540-17187-8_38
Kotagiri Ramamohanarao, Ron Sacks-Davis, Recursive linear hashing ACM Transactions on Database Systems. ,vol. 9, pp. 369- 391 ,(1984) , 10.1145/1270.1285
Mireille Regnier, Analysis of grid file algorithms Bit Numerical Mathematics. ,vol. 25, pp. 335- 357 ,(1985) , 10.1007/BF01934379
Herbert Robbins, Sutton Monro, A Stochastic Approximation Method Annals of Mathematical Statistics. ,vol. 22, pp. 400- 407 ,(1951) , 10.1214/AOMS/1177729586
Hans-Peter Kriegel, Performance comparison of index structures for multi-key retrieval Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. ,vol. 14, pp. 186- 196 ,(1984) , 10.1145/602259.602284
Markku Tamminen, The extendible cell method for closest point problems Bit Numerical Mathematics. ,vol. 22, pp. 27- 41 ,(1982) , 10.1007/BF01934393
M. Aris Ouksel, The interpolation-based grid file symposium on principles of database systems. pp. 20- 27 ,(1985) , 10.1145/325405.325408
John T. Robinson, The K-D-B-tree Proceedings of the 1981 ACM SIGMOD international conference on Management of data - SIGMOD '81. pp. 10- 18 ,(1981) , 10.1145/582318.582321