Efficient search for the top-k probable nearest neighbors in uncertain databases

• DOI: 10.14778/1453856.1453895
• Publication Date: 2014-06-24T12:17:57Z
• Authors: George Beskales; Mohamed A. Soliman; Ihab F. Ilyas
• Keywords: Online aggregation; Feature (linguistics)

Uncertainty pervades many domains in our lives. Current real-life applications, e.g., location tracking using GPS devices or cell phones, multimedia feature extraction, and sensor data management, deal with different kinds of uncertainty. Finding the nearest neighbor objects to a given query point is an important type these applications. In this paper, we study problem finding highest marginal probability being neighbors object. We adopt general uncertainty model allowing for Under model, define new semantics, provide several efficient evaluation algorithms. analyze cost factors involved evaluation, present novel techniques address trade-offs among factors. give multiple extensions including handling dependencies objects, answering threshold queries. conduct extensive experimental evaluate on both real synthetic data.