Volume 12 Number 2 (Mar. 2017)
Home > Archive > 2017 > Volume 12 Number 2 (Mar. 2017) >
JCP 2017 Vol.12(2): 105-115 ISSN: 1796-203X
doi: 10.17706/jcp.12.2.105-115

k-Expected Nearest Neighbor Search over Gaussian Objects

Tingting Dong1, Yoshiharu Ishikawa1, Chuan Xiao2, Jing Zhao1
1Department of Systems and Social Informatics, Nagoya University, Nagoya, Aichi, Japan.
2Institute for Advanced Research, Nagoya University, Nagoya, Aichi, Japan.

Abstract—Probabilistic location information has been attracting more and more attention due to the advances in computing devices and technologies, and has become an important research topic in recent years. In particular, Gaussian distribution is frequently used to represent probabilistic location information. On the other hand, as one of the commonest queries over location information, the distance-based nearest neighbor search, which finds closest objects to a given query point, has extensive applications in various areas. There have been considerable efforts made to extend nearest neighbor search over traditional location information to probabilistic location information. An example is the expected distance, which defines the distance over probabilistic location information. Following this trend, in this paper, we assume that the closeness between objects represented by Gaussian distributions are measured by their expected distance and consider the problem of k-expected nearest neighbor search. We analyze properties of expected distance on Gaussian distributions mathematically and derive its lower bound and upper bound. Based on our analysis, we propose three novel approaches to efficiently solve this problem. The efficiency of our approaches is demonstrated through extensive experiments.

Index Terms—Probabilistic location information, Gaussian distributions, nearest neighbor search, expected distance.


Cite: Tingting Dong, Yoshiharu Ishikawa, Chuan Xiao, Jing Zhao, "k-Expected Nearest Neighbor Search over Gaussian Objects," Journal of Computers vol. 12, no. 2, pp. 105-115, 2017.

General Information

ISSN: 1796-203X
Frequency: Monthly (2006-2014); Bimonthly (Since 2015)
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Apr 24, 2018 News!

    Vol 13, No 8 has been published with online version   [Click]

  • Dec 26, 2017 News!

    Vol 12, No 1-N0 5 has been indexed by EI (Inspec)     [Click]

  • Dec 26, 2017 News!

    Vol 11, No 4-N0 6 has been indexed by EI (Inspec)     [Click]

  • Dec 21, 2017 News!

    Vol 13, No 7 has been published with online version 12 papers are published in this issue after peer review   [Click]

  • Sep 26, 2017 News!

    Papers published in JCP Volume 12 have all been indexed by DBLP   [Click]

  • Read more>>