? Indexing Techniques of Distributed Ordered Tables: A Survey and Analysis
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2018, Vol. 33 Issue (1) :169-189    DOI: 10.1007/s11390-018-1813-8
Survey Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
Indexing Techniques of Distributed Ordered Tables: A Survey and Analysis
Chen Feng1,2, Student Member, CCF, Chun-Dian Li1,2, Student Member, CCF, Rui Li3
1 State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China;
2 University of Chinese Academy of Sciences, Beijing 100049, China;
3 Tencent Inc., Beijing 100080, China

Abstract
Reference
Related Articles
Download: [PDF 2555KB]     Export: BibTeX or EndNote (RIS)  
Abstract Many NoSQL (Not Only SQL) databases were proposed to store and query on a huge amount of data. Some of them like BigTable, PNUTS, and HBase, can be modeled as distributed ordered tables (DOTs). Many additional indexing techniques have been presented to support queries on non-key columns for DOTs. However, there was no comprehensive analysis or comparison of these techniques, which brings troubles to users in selecting or proposing a proper indexing technique for a certain workload. This paper proposes a taxonomy based on six indexing issues to classify indexing techniques on DOTs and provides a comprehensive review of the state-of-the-art techniques. Based on the taxonomy, we propose a performance model named QSModel to estimate the query time and storage cost of these techniques and run experiments on a practical workload from Tencent to evaluate this model. The results show that the maximum error rates of the query time and storage cost are 24.2% and 9.8%, respectively. Furthermore, we propose IndexComparator, an open source project that implements representative indexing techniques. Therefore, users can select the best-fit indexing technique based on both theoretical analysis and practical experiments.
Articles by authors
Keywordsdatabase   Not Only SQL (NoSQL)   range query   indexing     
Received 2017-03-27;
Fund:

This work is partially supported by the Strategic Priority Program of Chinese Academy of Sciences under Grant No. XDB02040009, the Key Program of the National Natural Science Foundation of China under Grant No. 61532016, the Key Program of Cloud Computing and Big Data of the Ministry of the Science and Technology of China under Grant No. 2016YFB1000200, and Tencent Inc.

About author: Chen Feng is a Ph.D. candidate of Institute of Computing Technology, Chinese Academy of Sciences, Beijing. He received his B.S. degree in software engineering from Nankai University, Tianjin, in 2011. His current research interests include big data computing and distributed system. He is a student member of CCF.
Cite this article:   
Chen Feng, Chun-Dian Li, Rui Li.Indexing Techniques of Distributed Ordered Tables: A Survey and Analysis[J]  Journal of Computer Science and Technology, 2018,V33(1): 169-189
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/10.1007/s11390-018-1813-8
Copyright 2010 by Journal of Computer Science and Technology