An Efficient Indexing Structure for Multidimensional Categorical Range Aggregation Query = An Efficient Indexing Structure for Multidimensional Categorical Range Aggregation Query

다국어 초록 (Multilingual Abstract)

Categorical range aggregation, which is conceptually equivalent to running a range aggregation query separately on multiple datasets, returns the query result on each dataset. The challenge is when the number of dataset is as large as hundreds or thousands, it takes a lot of computation time and I/O. In previous work, only a single dimension of the range restriction has been solved, and in practice, more applications are being used to calculate multiple range restriction statistics. We proposed MCRI-Tree, an index structure designed to solve multi-dimensional categorical range aggregation queries, which can utilize main memory to maximize the efficiency of CRA queries. Specifically, the MCRI-Tree answers any query in O(nkn-1) I/Os (where n is the number of dimensions, and k denotes the maximum number of pages covered in one dimension among all the n dimensions during a query). The practical efficiency of our technique is demonstrated with extensive experiments.

참고문헌 (Reference)

1 R. Sears, "bLSM: a general purpose log structured merge tree" 217-228, 2012

2 D. Comer, "Ubiquitous B-Tree" 11 (11): 121-137, 1979

3 Y. Li, "Tree indexing on solid state drives" 3 (3): 1195-1206, 2010

4 B.C. Kuszmaul, "Tokutek White Paper" 2014

5 P. O Neil, "The log-structured merge-tree(LSM-tree)" 33 (33): 351-385, 1996

6 D. B. Lomet, "The hB-tree : A Multiattribute Indexing Method with Good Guaranteed Performance" 15 (15): 625-658, 1990

7 L. Arge, "The buffer tree : A new technique for optimal I/O-algorithms" 3 (3): 334-345, 1995

8 T. Zäschke, "The PH-Tree - a Space-Efficient Storage Structure and Multi-Dimensional Index" 397-408, 2014

9 J.J. Levandoski, "The Bw-Tree: A B-tree for new hardware platforms" 302-313, 2013

10 L. Arge, "The Buffer Tree : A Technique for Designing Batched External Data Structures" 37 (37): 1-24, 2003

11 S. Nishimura, "QUILTS: Multidimensional Data Partitioning Framework Based on Query-Aware and Skew-Tolerant Space-Filling Curves" 1525-1537, 2017

12 P. Jin, "Optimizing B+-tree for hybrid storage systems" 33 (33): 449-475, 2015

13 V. Gaede, "Multidimensional access methods" 30 (30): 170-231, 1998

14 B. Wang, "Maple: scalable multi-dimensional range search over encrypted cloud data with tree-based index" 111-122, 2014

15 J. Rao, "Making B+-trees cache conscious in main memory" 29 (29): 475-486, 2000

16 D. Agrawal, "Lazy-Adaptive Tree : An Optimized Index Structure for Flash Devices" 2 (2): 361-372, 2009

17 S. Singh, "Indexing Uncertain Categorical Data" 616-625, 2007

18 J. Yang, "Incremental Computation and Maintenance of Temporal Aggregates" 12 (12): 262-283, 2003

19 Tao, Yufei, "I/O-Efficient Bundled Range Aggregation" 26 (26): 1521-1531, 2014

20 Nekrich, Yakov, "Efficient range searching for categorical and plain data" 39 (39): 1-21, 2014

21 A. Vlachou, "Efficient RDF Query Processing using Multidimensional Indexing" 2017

22 D. Papadias, "Efficient OLAP Operations in Spatial Data Warehouses" 443-459, 2001

23 G. Li, "Efficient Implementation of a Multi-Dimensional Index Structure Over Flash Memory Storage Systems" 64 (64): 1055-1074, 2013

24 C. S. Ellis, "Concurrent Search and Insertion in AVL Trees" C-29 (C-29): 811-817, 1980

25 N. Sarkas, "Categorical skylines for streaming data" 239-250, 2008

26 E. D. Demaine, "Cache-Oblivious B-Trees" 35 (35): 341-358, 2005

27 J. Rao, "Cache Conscious Indexing for Decision-Support in Main Memory" 78-89, 1999

28 H. Roh, "B+-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives" 5 (5): 286-297, 2012

29 H. Roh, "As B-Tree : A Study of an Efficient B+-tree for SSDs" 30 (30): 85-106, 2014

30 C.H. WuT, "An efficient B-tree layer implementation for flash-memory storage systems" 6 (6): 2007

31 M.K. Aguilera, "A practical scalable distributed B-tree" 1 (1): 598-609, 2008

32 M. Freeston, "A general solution of the n-dimensional B-tree problem" 24 (24): 80-91, 1995