Uncertain probabilistic range queries on multidimensional data
| Autor: | Jorge Bernad, Carlos Bobed, Eduardo Mena |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Information Systems and Management
Theoretical computer science Range query (data structures) Computer science 05 social sciences Probabilistic logic Multidimensional data 050301 education 02 engineering and technology Type (model theory) Computer Science Applications Theoretical Computer Science Range (mathematics) Index (publishing) Artificial Intelligence Control and Systems Engineering 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing State (computer science) 0503 education Software |
| Zdroj: | Information Sciences. 537:334-367 |
| ISSN: | 0020-0255 |
| DOI: | 10.1016/j.ins.2020.05.068 |
| Popis: | Probabilistic Range Queries (PRQ) retrieve objects which, according to imprecise object properties, are (with a given probability) inside a precise range. When the query range is based on some imprecise object properties, which makes the query range imprecise as well, then Uncertain Probabilistic Range Queries (UPRQ) arise. Unfortunately, in the literature UPRQs ranges are constrained to be balls, i.e., the range is defined by providing a certain radius around an imprecise object property. Moreover, another important issue is the efficiency of answering UPRQs due to the necessary numerical operations to calculate probabilities. In this work we give a novel definition for UPRQs with query ranges of any shape; in addition we prove that any UPRQ can be reduced to a PRQ. Concerning the efficiency of UPRQs, we adopt and improve the usual way to address this family of queries (i.e., constructing indexes to prune/validate which objects belong to the answer, avoiding unnecessary numerical calculations) presenting: (1) a method to improve the filtering capabilities of the indexes when dealing with uniform distributions over rectangles or balls; and (2) a new index (eUD-Index), which enhances the state of the art, for any type of probability distribution. Our experiments show the feasibility of the proposals. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect