# A Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues
## 5 Existing Indexing Techniques
### Multidimensional Indexing Techniques
#### 5.1.3 Bitmap-Based Technique
\begin{table}
\begin{tabular}{l l l l l l} \hline \hline
**Proposition** & **Refs** & **Dataset Type** & **Data Dimension** & **Indexing Nature** & \multicolumn{2}{c}{**Complexity (Estimation)**} \\ \cline{3-4}  & & & & **Insertion and Deletion** & **Search** \\ \hline Kd-tree & [158] & Geo-graphical & & \(O(allog(n))\) & \(O(n\log(n))\) \\ \hline Adaptive Kd-tree & [167] & Files & & \(O(allog(n))\) & \(O(n\log(n))\) \\ \hline Kd-tree & [168] & Floating point numbers & & \(O(\pi\log(n))\) & \(O(\pi(\log(n)))\) \\ \hline Skd-tree & [169] & Spatial & & \(\bullet\) Not estimated \\ \hline Quad-tree & [159, 160] & Spatial & & \(O((d+1)n\log(n))\) & \(O(n\log(n))\) \\ \hline PH-tree & [176] & Synthetic & & \(O(\pi\log(n))\) & \(O(\pi\log(n))\) \\ \hline ND-tree & [183] & Synthetic & & \(\bullet\) Not estimated \\ \hline QMBR-tree & [184, 185] & Synthetic, spatial & & \(\bullet\) Not estimated \\ \hline VA-file & [162] & Synthetic data and images & & \(\bullet\) Not estimated \\ \hline Octree & [186] & Spatial & & \(O((d+1)n\log(n))\) & \(O(n\log_{6}(n))\) \\ \hline Pyramid & [161] & Synthetic data & & Not estimated \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Analysis of multidimensional indexing techniques based on space partitioning. Traditional bitmaps are suffering from a problem of space over-consumption, especially for highly cardinal data. To address this challenge and for faster retrieval, compressed bitmap indexes are recommended. As a consequence, many efficient bitmap compression algorithms have been developed, including: BBC (Byte-aligned Bitmap Compression) [192], WAH (_Word-Aligned Hybrid_) [198; 199], PLWAH (_Position ListWAH_) [200], EWAH (_Enhanced Word-Aligned Hybrid_) [201], CONCISE (_Compressed N Composable Integer Set_) [202], VALWAH (_Variable-Aligned Length WAH_) [203], SECOMPAX (_Scope-Extended COMPpressed Adaptive indexX_) [204], SBH (_Super Byte-aligned Hybrid_) [205], Roaring [206], SPLWAH (_PLWAH algorithm for sorted data_) [207], BAH (_Byte Aligned Hybrid compression coding_) [208], cSHB (_Compressed Spatial Hierarchical Bitmap_) [209] and CODIS (_COmpressing DIrty Snippet_) [210]. Through these compression algorithms with logical operations, the execution time is reduced compared to the basic bitmap index without compression, which is an essential property of bitmap indexing [211]. Recently, [PERSON] et al. [208] proposed a new compression algorithm more similar to WAH algorithm named BAH (Byte Aligned Hybrid compression coding) whose objective is to improve the performance in terms of space and the efficiency of the requests. BAH uses simple rules for raw bitmap encoding compared to other WAH variants that use a more complicated code book. BAH uses SIMD operations to accelerate the efficiency of the AND operation on multiple compressed bitmaps. Another compression algorithm has been proposed based on the WAH algorithm called CODIS which is proposed by [PERSON] et al. [210]. The basic idea of CODIS is the reduction of space through the representation of the bit string in the bitmap index with fewer bits, without influencing the efficiency of the index. The results obtained during the experimentation demonstrate that this technique is more efficient than the other algorithms in the literature, including WAH [199], COMPAX (COMPressed Adaptive indeX) [212] and PLWAH [207]. Bitmap index method is a very efficient technique for answering complex queries for read-only systems and for data that is not frequently updated as a data warehouse, but it is less efficient in other cases (i.e., for data that is frequently updated). This problem is caused by the compression process where the latter is used to reduce the storage space (as we said before), but at each update operation, it is necessary to decode and encode the bitmap, and this operation is very expensive [213]. [PERSON] et al. [213] proposed a new bitmap index named UpBit (Updatable Bitmap) to overcome this problem. This index offers efficient updates without affecting read performance.