H-MRST: A Novel Framework For Supporting Probability Degree Range Query Using Extreme Learning Machine

Background/Introduction: Data classification is an important application in the domain of cognitive computation, which has various applications. In this paper, we use classification techniques to solve some key issues in answering range query over probabilistic data. The key of answering this query is to store the feature of each uncertain object in a lightweight structure and use these structures for pruning/validating. However, in these works, the costly integral calculation has to be carried out when dealing with objects that cannot be pruned/validated, and some of the structure construction algorithms are not general. Methods: In this paper, we employ ELM, a popular classification technique, to tackle the above issues. Our proposed methods are as follows: We firstly propose a new query called PDR (short for probabilistic degree range) query to substitute the traditional prob-range query, which helps us avoid the costly integral calculation. We propose an ELM-based “adapter” to construct the lightweight structure for uncertain data in a more general manner. We design the GO-ELM algorithm for answering PDR query. It first avoids most of the integral calculation via using a group of bit vector-based filter. In addition, we propose an ELM-based classifier, which is designed to further avoid integral operations. Results: From the experiment results, we find that: (1) our ELM-based adapter is superior compared with both SVM-based and DNN-based adapter due to its better training efficiency and classification efficiency as well; (2) the performance of H-MRST is better than that of U-tree and UD-tree; and (3) ELM-filter could effectively avoid integral calculation. Conclusions: This paper studies the problem of PDR query over uncertain data. We firstly define PDR query and propose a general scheme to handle uncertain object if its PDF is discrete. We then design GO-ELM algorithm for answering PDR query. Our experiments faithfully demonstrated the efficiency of our indexing techniques.