Top-<i>k</i> Similarity Search over Gaussian Distributions Based on KL-Divergence

• Dong Tingting

  Nagoya University

• Ishikawa Yoshiharu

  Nagoya University

• Xiao Chuan

  Nagoya University

Abstract

The problem of similarity search is a crucial task in many real-world applications such as multimedia databases, data mining, and bioinformatics. In this work, we investigate the similarity search on uncertain data modeled in Gaussian distributions. By employing Kullback-Leibler divergence (KL-divergence) to measure the dissimilarity between two Gaussian distributions, our goal is to search a database for the top-k Gaussian distributions similar to a given query Gaussian distribution. Especially, we consider non-correlated Gaussian distributions, where there are no correlations between dimensions and their covariance matrices are diagonal. To support query processing, we propose two types of novel approaches utilizing the notions of rank aggregation and skyline queries. The efficiency and effectiveness of our approaches are demonstrated through a comprehensive experimental performance study.

Journal

• Journal of Information Processing

  Journal of Information Processing 24 (1), 152-163, 2016

  Information Processing Society of Japan

Keywords

• Gaussian distributions
• Kullback-Leibler divergence
• top-<i>k</i> similarity search

Details

• CRID: 1390282680271660160
• NII Article ID: 130005119987
• DOI: 10.2197/ipsjjip.24.152
• ISSN: 18826652
• Web Site: https://www.jstage.jst.go.jp/article/ipsjjip/24/1/24_152/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed