New range and k-NN query processing algorithms using materialization technique on spatial network

Jung Ho Um; Nihad Karim Chowdhury; Jae Woo Chang

doi:10.1109/ISITC.2007.69

New range and k-NN query processing algorithms using materialization technique on spatial network

Jung Ho Um^*
, Nihad Karim Chowdhury
, Jae Woo Chang

^*Corresponding author for this work

Jeonbuk National University

Research output: Contribution to conference › Conference paper › peer-review

2 Scopus citations

Abstract

In this paper, we propose new query processing algorithms for typical spatial queries in SNDB, such as range search and k nearest neighbors (k-NN) search. Our two query processing algorithms can reduce the computation time of network distance between a pair of nodes and the number of disk I/Os required for accessing nodes by using a materialization-based technique with the shortest network distances of all the nodes in the spatial network. Thus, our query processing algorithms improve the existing efficient k-NN (INE) and range search (RNE) algorithms proposed by [1]. It is shown that our range query processing algorithm achieves about up to one of magnitude better performance than the RNE and our k-NN query processing algorithm achieves about up to 150% performance improvements over INE.

Original language	English
Title of host publication	Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007
Pages	76-80
Number of pages	5
DOIs	https://doi.org/10.1109/ISITC.2007.69
State	Published - 2007
Event	2007 International Symposium on Information Technology Convergence, ISITC 2007 - Jeonju, Korea, Republic of Duration: 2007.11.23 → 2007.11.24

Publication series

Name	Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007

Conference

Conference	2007 International Symposium on Information Technology Convergence, ISITC 2007
Country/Territory	Korea, Republic of
City	Jeonju
Period	07.11.23 → 07.11.24

Quacquarelli Symonds(QS) Subject Topics

Computer Science & Information Systems
Communication & Media Studies

Access to Document

10.1109/ISITC.2007.69

Cite this

Um, J. H., Chowdhury, N. K., & Chang, J. W. (2007). New range and k-NN query processing algorithms using materialization technique on spatial network. In Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007 (pp. 76-80). Article 4410609 (Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007). https://doi.org/10.1109/ISITC.2007.69

@inproceedings{1f7e1adbf41241caad4051d45d964f9e,

title = "New range and k-NN query processing algorithms using materialization technique on spatial network",

abstract = "In this paper, we propose new query processing algorithms for typical spatial queries in SNDB, such as range search and k nearest neighbors (k-NN) search. Our two query processing algorithms can reduce the computation time of network distance between a pair of nodes and the number of disk I/Os required for accessing nodes by using a materialization-based technique with the shortest network distances of all the nodes in the spatial network. Thus, our query processing algorithms improve the existing efficient k-NN (INE) and range search (RNE) algorithms proposed by [1]. It is shown that our range query processing algorithm achieves about up to one of magnitude better performance than the RNE and our k-NN query processing algorithm achieves about up to 150\% performance improvements over INE.",

author = "Um, \{Jung Ho\} and Chowdhury, \{Nihad Karim\} and Chang, \{Jae Woo\}",

year = "2007",

doi = "10.1109/ISITC.2007.69",

language = "English",

isbn = "0769530451",

series = "Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007",

pages = "76--80",

booktitle = "Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007",

note = "2007 International Symposium on Information Technology Convergence, ISITC 2007 ; Conference date: 23-11-2007 Through 24-11-2007",

}

Um, JH, Chowdhury, NK & Chang, JW 2007, New range and k-NN query processing algorithms using materialization technique on spatial network. in Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007., 4410609, Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007, pp. 76-80, 2007 International Symposium on Information Technology Convergence, ISITC 2007, Jeonju, Korea, Republic of, 07.11.23. https://doi.org/10.1109/ISITC.2007.69

New range and k-NN query processing algorithms using materialization technique on spatial network. / Um, Jung Ho; Chowdhury, Nihad Karim; Chang, Jae Woo.
Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007. 2007. p. 76-80 4410609 (Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007).

Research output: Contribution to conference › Conference paper › peer-review

TY - GEN

T1 - New range and k-NN query processing algorithms using materialization technique on spatial network

AU - Um, Jung Ho

AU - Chowdhury, Nihad Karim

AU - Chang, Jae Woo

PY - 2007

Y1 - 2007

N2 - In this paper, we propose new query processing algorithms for typical spatial queries in SNDB, such as range search and k nearest neighbors (k-NN) search. Our two query processing algorithms can reduce the computation time of network distance between a pair of nodes and the number of disk I/Os required for accessing nodes by using a materialization-based technique with the shortest network distances of all the nodes in the spatial network. Thus, our query processing algorithms improve the existing efficient k-NN (INE) and range search (RNE) algorithms proposed by [1]. It is shown that our range query processing algorithm achieves about up to one of magnitude better performance than the RNE and our k-NN query processing algorithm achieves about up to 150% performance improvements over INE.

AB - In this paper, we propose new query processing algorithms for typical spatial queries in SNDB, such as range search and k nearest neighbors (k-NN) search. Our two query processing algorithms can reduce the computation time of network distance between a pair of nodes and the number of disk I/Os required for accessing nodes by using a materialization-based technique with the shortest network distances of all the nodes in the spatial network. Thus, our query processing algorithms improve the existing efficient k-NN (INE) and range search (RNE) algorithms proposed by [1]. It is shown that our range query processing algorithm achieves about up to one of magnitude better performance than the RNE and our k-NN query processing algorithm achieves about up to 150% performance improvements over INE.

UR - https://www.scopus.com/pages/publications/48149108216

U2 - 10.1109/ISITC.2007.69

DO - 10.1109/ISITC.2007.69

M3 - Conference paper

AN - SCOPUS:48149108216

SN - 0769530451

SN - 9780769530451

T3 - Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007

SP - 76

EP - 80

BT - Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007

T2 - 2007 International Symposium on Information Technology Convergence, ISITC 2007

Y2 - 23 November 2007 through 24 November 2007

ER -

Um JH, Chowdhury NK, Chang JW. New range and k-NN query processing algorithms using materialization technique on spatial network. In Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007. 2007. p. 76-80. 4410609. (Proceedings - 2007 International Symposium on Information Technology Convergence, ISITC 2007). doi: 10.1109/ISITC.2007.69

New range and k-NN query processing algorithms using materialization technique on spatial network

Abstract

Publication series

Conference

Quacquarelli Symonds(QS) Subject Topics

Access to Document

Other files and links

Fingerprint

Cite this