e-journal

Data Acquisition for Probabilistic Nearest-Neighbor Query

---

Management of uncertain data in spatial queries has drawn extensive research interests to consider the granularity of devices and noises in the collection and the delivery of data. Most previous works usually model and handle uncertain data to find the required results directly. However, it is more difficult for users to obtain useful insights when data uncertainty dramatically increases. In this case, users are usually willing to invest more resources to improve the result by reducing the data uncertainty in order to obtain more interesting observations with the existing schemes. In light of this important need, this paper formulates a new problem of selecting a given number of uncertain data objects for acquiring their attribute values to improve the result of the Probabilistic k-Nearest-Neighbor (k-PNN) query. We prove that better query results are guaranteed to be returned with data acquisition, and we devise several algorithms to maximize the expected improvement. We first explore the optimal single-object acquisition for 1-PNN to examine the fundamental problem structure and then propose an efficient algorithm that discovers crucial properties to simplify the probability derivation in varied situations. We extend the proposed algorithm to achieve the optimal multi-object acquisition for 1-PNN by deriving an upper bound to facilitate efficient pruning of unnecessary sets of objects. Moreover, for data acquisition of k-PNN, we extract the k-PNN answers with sufficiently large probabilities to trim the search space and properly exploit the result of single-object acquisition for estimating the gain from multi-object acquisition. The experimental results demonstrate that the probability of k-PNN can be significantly improved even with only a small number of objects for data acquisition.
Index Terms—Uncertainty, algorithm design and analysis, query processing, nearest neighbor searches

---

Ketersediaan

Tidak ada salinan data

Informasi Detail

Judul Seri

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING

No. Panggil

-

Penerbit

New York : IEEE., 2014

Deskripsi Fisik

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 27, NO. 2, FEBRUARY 2015

Bahasa

English

ISBN/ISSN

1041-4347

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

VOL. 27, NO. 2, FEBRUARY 2015

Subjek

TEKNIK

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Yuli/Agus

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar