Reordering columns for smaller indexes
作者： Daniel Lemire , Owen Kaser
DOI: 10.1016/J.INS.2011.02.002
关键词:
摘要: Column-oriented indexes-such as projection or bitmap indexes-are compressed by run-length encoding to reduce storage and increase speed. Sorting the tables improves compression. On realistic data sets, permuting columns in right order before sorting can number of runs a factor two more. Unfortunately, determining best column is NP-hard. For many cases, we prove that table minimized if sort increasing cardinality. Experimentally, based on Hilbert space-filling curves poor at minimizing runs.
arxiv.org
core.ac.uk
128.84.21.199
acm.org
elsevier.com参考文章(74)
Donald E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming) The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming). ,(2005)
Ibrahim Kamel, Faloutsos: "hilbert r-tree: an improved r-tree using fractals very large data bases. ,(1994)
Alexander Zeier, Christian Lemke, Kai-Uwe Sattler, Franz Faerber, Speeding up queries in column stores: a case for compression data warehousing and knowledge discovery. pp. 117- 129 ,(2010)
S. W. Golomb, Run-length encodings. ,(1966)
Abraham D Flaxman, Shlomo Hoory, None, Maximum Matchings in Regular Graphs of High Girth Electronic Journal of Combinatorics. ,vol. 14, pp. 1- 4 ,(2007) , 10.37236/1002
Patrick E. O'Neil, Model 204 Architecture and Performance high performance transaction systems workshop. pp. 40- 59 ,(1987) , 10.1007/3-540-51085-0_42
Todd Eavis, David Cueva, A hilbert space compression architecture for data warehouse environments data warehousing and knowledge discovery. pp. 1- 12 ,(2007) , 10.1007/978-3-540-74553-2_1
Henri Leon Lebesgue, Leçons sur l'intégration et la recherche des fonctions primitives professées au Collège de France Cambridge University Press. ,(2009) , 10.1017/CBO9780511701825
Alistair Moffat, Lang Stuiver, Binary Interpolative Coding for Effective Index Compression Information Retrieval. ,vol. 3, pp. 25- 47 ,(2000) , 10.1023/A:1013002601898
Yannis E. Ioannidis, Viswanath Poosala, Selectivity Estimation Without the Attribute Value Independence Assumption very large data bases. pp. 486- 495 ,(1997)