MulRF: A Multi-dimensional Range Filter for Sublinear Time Range Query Processing

Range query is an important operation on big multi-dimensional data. This paper studies the problem of multi-dimensional range query filtering for speeding up the range query processing by avoiding reading the useless data. To solve the problem, a novel multi-dimensional range filter is proposed to filter the multi-dimensional range queries, while the existing one-dimensional range filters can not provide efficient filtering. Based on the multi-dimensional range filter, an efficient range query processing algorithm is presented. It can directly return the locations of the I/O units that contain the data in the query result without any access to the input dataset. The time complexity of the algorithm is <tex-math notation="LaTeX">O(3ᵐh)</tex-math> , where <tex-math notation="LaTeX">h</tex-math> is the number of I/O units partially overlapping with a range query, and <tex-math notation="LaTeX">m</tex-math> is the dimension number. Since <tex-math notation="LaTeX">m</tex-math> is usually <tex-math notation="LaTeX">o(√log n)</tex-math> , it is a sublinear time algorithm if <tex-math notation="LaTeX">$V=O(n)$</tex-math> , where <tex-math notation="LaTeX">n</tex-math> is the size of the input dataset, <tex-math notation="LaTeX">V=∏ ᵢ₌₁ᵐdᵢ</tex-math> , and <tex-math notation="LaTeX">dᵢ</tex-math> is the number of distinct values on the <tex-math notation="LaTeX">i</tex-math> -th dimension of the dataset for <tex-math notation="LaTeX">1≤ i≤ m</tex-math> . Experimental results show that the multi-dimensional range filter has low false positive rate and good filtering efficiency. The proposed range query processing algorithm achieves at least 3 <tex-math notation="LaTeX">~</tex-math> 7 times improvement compared to the one-dimensional filter based algorithms on different datasets.