Efficient Processing of k-Nearest Neighbor Queries in Spatial Databases with the SH-tree

Khanh Tran Dang; Josef Küng; Roland Wagner

Efficient Processing of k-Nearest Neighbor Queries in Spatial Databases with the SH-tree

Khanh Tran Dang
, Josef Küng
, Roland Wagner

Institute for Application-oriented Knowledge Processing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceedings › peer-review

Abstract

Nearest neighbor problem has special considerations among database researchers. In many cases of querying, users want to see returned results that contain database objects similar to a given query object, and especially these returned results are ranked according to their similarity to the query object. In this paper, we introduce two adapted algorithms to the SH-tree [KKW2001] from the state-of-the-art of corresponding research results for efficiently processing the nearest neighbor problem in spatial databases. We do intensive performance tests on synthetic data sets, which dimension number varies from 2 to 64, as well as on real data set. Our experimental results show that the SH-tree with these adapted algorithms totally outperforms the search performance of the SR-tree in both IO-cost and CPU-time when processing the k-nearest neighbor queries. This result also confirms our theory analyses in [KKW2001]: the SH-tree can efficiently scale to high dimensional spatial databases.

Original language	English
Title of host publication	Proceedings of the Third International Conference on Information and Integration and Web-based Applications and Services
Pages	425-435
Number of pages	11
Publication status	Published - Sept 2001

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure
SDG 16 Peace, Justice and Strong Institutions

Fields of science

102001 Artificial intelligence
102006 Computer supported cooperative work (CSCW)
102010 Database systems
102014 Information design
102015 Information systems
102016 IT security
102028 Knowledge engineering
102019 Machine learning
102022 Software development
102025 Distributed systems
502007 E-commerce
505002 Data protection
506002 E-government
509018 Knowledge management
202007 Computer integrated manufacturing (CIM)
102033 Data mining
102035 Data science

Cite this

@inproceedings{5c25160adea14fab935d11bc090d8d19,

title = "Efficient Processing of k-Nearest Neighbor Queries in Spatial Databases with the SH-tree",

abstract = "Nearest neighbor problem has special considerations among database researchers. In many cases of querying, users want to see returned results that contain database objects similar to a given query object, and especially these returned results are ranked according to their similarity to the query object. In this paper, we introduce two adapted algorithms to the SH-tree [KKW2001] from the state-of-the-art of corresponding research results for efficiently processing the nearest neighbor problem in spatial databases. We do intensive performance tests on synthetic data sets, which dimension number varies from 2 to 64, as well as on real data set. Our experimental results show that the SH-tree with these adapted algorithms totally outperforms the search performance of the SR-tree in both IO-cost and CPU-time when processing the k-nearest neighbor queries. This result also confirms our theory analyses in [KKW2001]: the SH-tree can efficiently scale to high dimensional spatial databases.",

author = "Dang, \{Khanh Tran\} and Josef K{\"u}ng and Roland Wagner",

year = "2001",

month = sep,

language = "English",

isbn = "3-85403-150-5",

pages = "425--435",

booktitle = "Proceedings of the Third International Conference on Information and Integration and Web-based Applications and Services",

}

Efficient Processing of k-Nearest Neighbor Queries in Spatial Databases with the SH-tree. / Dang, Khanh Tran; Küng, Josef ; Wagner, Roland.
Proceedings of the Third International Conference on Information and Integration and Web-based Applications and Services. 2001. p. 425-435.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceedings › peer-review

TY - GEN

T1 - Efficient Processing of k-Nearest Neighbor Queries in Spatial Databases with the SH-tree

AU - Dang, Khanh Tran

AU - Küng, Josef

AU - Wagner, Roland

PY - 2001/9

Y1 - 2001/9

N2 - Nearest neighbor problem has special considerations among database researchers. In many cases of querying, users want to see returned results that contain database objects similar to a given query object, and especially these returned results are ranked according to their similarity to the query object. In this paper, we introduce two adapted algorithms to the SH-tree [KKW2001] from the state-of-the-art of corresponding research results for efficiently processing the nearest neighbor problem in spatial databases. We do intensive performance tests on synthetic data sets, which dimension number varies from 2 to 64, as well as on real data set. Our experimental results show that the SH-tree with these adapted algorithms totally outperforms the search performance of the SR-tree in both IO-cost and CPU-time when processing the k-nearest neighbor queries. This result also confirms our theory analyses in [KKW2001]: the SH-tree can efficiently scale to high dimensional spatial databases.

AB - Nearest neighbor problem has special considerations among database researchers. In many cases of querying, users want to see returned results that contain database objects similar to a given query object, and especially these returned results are ranked according to their similarity to the query object. In this paper, we introduce two adapted algorithms to the SH-tree [KKW2001] from the state-of-the-art of corresponding research results for efficiently processing the nearest neighbor problem in spatial databases. We do intensive performance tests on synthetic data sets, which dimension number varies from 2 to 64, as well as on real data set. Our experimental results show that the SH-tree with these adapted algorithms totally outperforms the search performance of the SR-tree in both IO-cost and CPU-time when processing the k-nearest neighbor queries. This result also confirms our theory analyses in [KKW2001]: the SH-tree can efficiently scale to high dimensional spatial databases.

M3 - Conference proceedings

SN - 3-85403-150-5

SP - 425

EP - 435

BT - Proceedings of the Third International Conference on Information and Integration and Web-based Applications and Services

ER -