Shortest average-distance query on heterogeneous neighboring objects

Yuan Ko Huang, Wu Hsiu Kuo, Chiang Lee, Tzu Hsien Wang

研究成果: Paper

2 引文 (Scopus)

摘要

Currently, most of the processing techniques for the conventional location-based queries focus only on a single type of objects. However, in real-life applications the user may be interested in obtaining information about different types of objects, in terms of their neighboring relationship. We term the different types of objects closer to each other the heterogeneous neighboring objects (HNOs for short). Efficient processing of the location-based queries on the HNOs is more complicated than that on a single data source, because the neighboring relationship between the HNOs inevitably affects the query result. In this paper, we present a novel and important query on the HNOs, namely the shortest average-distance query (SAvgDQ for short), which can provide useful object information by considering both the spatial closeness of objects to the query object and the neighboring relationship between objects. Given a query object q and a distance d, the SAvgDQ retrieves a set of HNOs, such that the distances between any two objects in this set are less than or equal to d and its average distance to q is the smallest among all HNOs sets. To efficiently process the SAvgDQ, we develop an algorithm, the SAvgDQ processing algorithm, which operates based on three devised heuristics, the HNOs-qualifying heuristic, the HNOs-pruning heuristic, and the SAvgD-pruning heuristic, to reduce the number of distance computations required for query processing. Comprehensive experiments are conducted to demonstrate the effectiveness of the heuristics and the efficiency of the proposed algorithm.

原文English
頁面116-125
頁數10
DOIs
出版狀態Published - 2015 七月 13
事件19th International Database Engineering and Applications Symposium, IDEAS 2015 - Yokohama, Japan
持續時間: 2015 七月 132015 七月 15

Other

Other19th International Database Engineering and Applications Symposium, IDEAS 2015
國家Japan
城市Yokohama
期間15-07-1315-07-15

指紋

Processing
Query processing
Experiments

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

引用此文

Huang, Y. K., Kuo, W. H., Lee, C., & Wang, T. H. (2015). Shortest average-distance query on heterogeneous neighboring objects. 116-125. 論文發表於 19th International Database Engineering and Applications Symposium, IDEAS 2015, Yokohama, Japan. https://doi.org/10.1145/2790755.2790767
Huang, Yuan Ko ; Kuo, Wu Hsiu ; Lee, Chiang ; Wang, Tzu Hsien. / Shortest average-distance query on heterogeneous neighboring objects. 論文發表於 19th International Database Engineering and Applications Symposium, IDEAS 2015, Yokohama, Japan.10 p.
@conference{3ba9ab439add407f9d3ef262a731ecfa,
title = "Shortest average-distance query on heterogeneous neighboring objects",
abstract = "Currently, most of the processing techniques for the conventional location-based queries focus only on a single type of objects. However, in real-life applications the user may be interested in obtaining information about different types of objects, in terms of their neighboring relationship. We term the different types of objects closer to each other the heterogeneous neighboring objects (HNOs for short). Efficient processing of the location-based queries on the HNOs is more complicated than that on a single data source, because the neighboring relationship between the HNOs inevitably affects the query result. In this paper, we present a novel and important query on the HNOs, namely the shortest average-distance query (SAvgDQ for short), which can provide useful object information by considering both the spatial closeness of objects to the query object and the neighboring relationship between objects. Given a query object q and a distance d, the SAvgDQ retrieves a set of HNOs, such that the distances between any two objects in this set are less than or equal to d and its average distance to q is the smallest among all HNOs sets. To efficiently process the SAvgDQ, we develop an algorithm, the SAvgDQ processing algorithm, which operates based on three devised heuristics, the HNOs-qualifying heuristic, the HNOs-pruning heuristic, and the SAvgD-pruning heuristic, to reduce the number of distance computations required for query processing. Comprehensive experiments are conducted to demonstrate the effectiveness of the heuristics and the efficiency of the proposed algorithm.",
author = "Huang, {Yuan Ko} and Kuo, {Wu Hsiu} and Chiang Lee and Wang, {Tzu Hsien}",
year = "2015",
month = "7",
day = "13",
doi = "10.1145/2790755.2790767",
language = "English",
pages = "116--125",
note = "19th International Database Engineering and Applications Symposium, IDEAS 2015 ; Conference date: 13-07-2015 Through 15-07-2015",

}

Huang, YK, Kuo, WH, Lee, C & Wang, TH 2015, 'Shortest average-distance query on heterogeneous neighboring objects' 論文發表於 19th International Database Engineering and Applications Symposium, IDEAS 2015, Yokohama, Japan, 15-07-13 - 15-07-15, 頁 116-125. https://doi.org/10.1145/2790755.2790767

Shortest average-distance query on heterogeneous neighboring objects. / Huang, Yuan Ko; Kuo, Wu Hsiu; Lee, Chiang; Wang, Tzu Hsien.

2015. 116-125 論文發表於 19th International Database Engineering and Applications Symposium, IDEAS 2015, Yokohama, Japan.

研究成果: Paper

TY - CONF

T1 - Shortest average-distance query on heterogeneous neighboring objects

AU - Huang, Yuan Ko

AU - Kuo, Wu Hsiu

AU - Lee, Chiang

AU - Wang, Tzu Hsien

PY - 2015/7/13

Y1 - 2015/7/13

N2 - Currently, most of the processing techniques for the conventional location-based queries focus only on a single type of objects. However, in real-life applications the user may be interested in obtaining information about different types of objects, in terms of their neighboring relationship. We term the different types of objects closer to each other the heterogeneous neighboring objects (HNOs for short). Efficient processing of the location-based queries on the HNOs is more complicated than that on a single data source, because the neighboring relationship between the HNOs inevitably affects the query result. In this paper, we present a novel and important query on the HNOs, namely the shortest average-distance query (SAvgDQ for short), which can provide useful object information by considering both the spatial closeness of objects to the query object and the neighboring relationship between objects. Given a query object q and a distance d, the SAvgDQ retrieves a set of HNOs, such that the distances between any two objects in this set are less than or equal to d and its average distance to q is the smallest among all HNOs sets. To efficiently process the SAvgDQ, we develop an algorithm, the SAvgDQ processing algorithm, which operates based on three devised heuristics, the HNOs-qualifying heuristic, the HNOs-pruning heuristic, and the SAvgD-pruning heuristic, to reduce the number of distance computations required for query processing. Comprehensive experiments are conducted to demonstrate the effectiveness of the heuristics and the efficiency of the proposed algorithm.

AB - Currently, most of the processing techniques for the conventional location-based queries focus only on a single type of objects. However, in real-life applications the user may be interested in obtaining information about different types of objects, in terms of their neighboring relationship. We term the different types of objects closer to each other the heterogeneous neighboring objects (HNOs for short). Efficient processing of the location-based queries on the HNOs is more complicated than that on a single data source, because the neighboring relationship between the HNOs inevitably affects the query result. In this paper, we present a novel and important query on the HNOs, namely the shortest average-distance query (SAvgDQ for short), which can provide useful object information by considering both the spatial closeness of objects to the query object and the neighboring relationship between objects. Given a query object q and a distance d, the SAvgDQ retrieves a set of HNOs, such that the distances between any two objects in this set are less than or equal to d and its average distance to q is the smallest among all HNOs sets. To efficiently process the SAvgDQ, we develop an algorithm, the SAvgDQ processing algorithm, which operates based on three devised heuristics, the HNOs-qualifying heuristic, the HNOs-pruning heuristic, and the SAvgD-pruning heuristic, to reduce the number of distance computations required for query processing. Comprehensive experiments are conducted to demonstrate the effectiveness of the heuristics and the efficiency of the proposed algorithm.

UR - http://www.scopus.com/inward/record.url?scp=85007481665&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85007481665&partnerID=8YFLogxK

U2 - 10.1145/2790755.2790767

DO - 10.1145/2790755.2790767

M3 - Paper

AN - SCOPUS:85007481665

SP - 116

EP - 125

ER -

Huang YK, Kuo WH, Lee C, Wang TH. Shortest average-distance query on heterogeneous neighboring objects. 2015. 論文發表於 19th International Database Engineering and Applications Symposium, IDEAS 2015, Yokohama, Japan. https://doi.org/10.1145/2790755.2790767