Uncertain probabilistic range queries on multidimensional data

Bernad, Jorge (Universidad de Zaragoza) ; Bobed, Carlos (Universidad de Zaragoza) ; Mena, Eduardo (Universidad de Zaragoza)

Resumen: 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.

Idioma: Inglés

DOI: 10.1016/j.ins.2020.05.068

Año: 2020

Publicado en: Information Sciences 537 (2020), 334-367
ISSN: 0020-0255

Factor impacto JCR: 6.795 (2020)

Categ. JCR: COMPUTER SCIENCE, INFORMATION SYSTEMS rank: 18 / 161 = 0.112 (2020) - Q1 - T1

Factor impacto SCIMAGO: 1.524 - Artificial Intelligence (Q1) - Computer Science Applications (Q1) - Software (Q1) - Information Systems and Management (Q1) - Control and Systems Engineering (Q1)

Financiación: info:eu-repo/grantAgreement/ES/AEI-FEDER/TIN2016-78011-C4-3-R

Tipo y forma: Article (PostPrint)

Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)