New Range and k-NN Query Processing Algorithms Using Materialization Technique on Spatial Network

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 requi...

Full description

Saved in:
Bibliographic Details
Main Authors: Jung-Ho Um, Chowdhury, N.K., Jae-Woo Chang
Format: Conference Proceeding
Language:English
Subjects:
Computer networks
Data models
Information technology
Joining processes
Nearest neighbor searches
Partitioning algorithms
Query processing
Roads
Space stations
Spatial databases
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 80
container_issue
container_start_page 76
container_title
container_volume
creator Jung-Ho Um
Chowdhury, N.K.
Jae-Woo Chang
description 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.
doi_str_mv 10.1109/ISITC.2007.22
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_4410609</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>4410609</ieee_id><sourcerecordid>4410609</sourcerecordid><originalsourceid>FETCH-LOGICAL-i105t-e237293ac128256e97f229f10409bbfe6492728b9cdbc45a6fe327057bb8eafd3</originalsourceid><addsrcrecordid>eNpNjM1OwkAURscYExVZunIzL1C8c6fT6SxJo9IE6w9lTablFkZKi9MSgk8vURd-m5NzFh9jtwJGQoC5T2dpnowQQI8Qz9g16MgoCaES5__lkg277gNOk0Yh4BWzGR34u21WxG2z5Jsgy_jbnvyRv_q2pK5zzYqP61XrXb_ednz-E55tT97Z2n3Z3rUNz6lcN-5zT_wks90p2ppn1B9av7lhF5WtOxr-ccDmjw95MgmmL09pMp4GToDqA0Kp0UhbCoxRRWR0hWgqASGYoqgoCg1qjAtTLosyVDaqSKIGpYsiJlst5YDd_f46IlrsvNtaf1yEoYAIjPwGnjJUuA</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>New Range and k-NN Query Processing Algorithms Using Materialization Technique on Spatial Network</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Jung-Ho Um ; Chowdhury, N.K. ; Jae-Woo Chang</creator><creatorcontrib>Jung-Ho Um ; Chowdhury, N.K. ; Jae-Woo Chang</creatorcontrib><description>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.</description><identifier>ISBN: 0769530451</identifier><identifier>ISBN: 9780769530451</identifier><identifier>EISBN: 0769530451</identifier><identifier>EISBN: 9780769530451</identifier><identifier>DOI: 10.1109/ISITC.2007.22</identifier><language>eng</language><publisher>IEEE</publisher><subject>Computer networks ; Data models ; Information technology ; Joining processes ; Nearest neighbor searches ; Partitioning algorithms ; Query processing ; Roads ; Space stations ; Spatial databases</subject><ispartof>2007 International Symposium on Information Technology Convergence (ISITC 2007), 2007, p.76-80</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/4410609$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,27925,54920</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/4410609$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Jung-Ho Um</creatorcontrib><creatorcontrib>Chowdhury, N.K.</creatorcontrib><creatorcontrib>Jae-Woo Chang</creatorcontrib><title>New Range and k-NN Query Processing Algorithms Using Materialization Technique on Spatial Network</title><title>2007 International Symposium on Information Technology Convergence (ISITC 2007)</title><addtitle>ISITC</addtitle><description>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.</description><subject>Computer networks</subject><subject>Data models</subject><subject>Information technology</subject><subject>Joining processes</subject><subject>Nearest neighbor searches</subject><subject>Partitioning algorithms</subject><subject>Query processing</subject><subject>Roads</subject><subject>Space stations</subject><subject>Spatial databases</subject><isbn>0769530451</isbn><isbn>9780769530451</isbn><isbn>0769530451</isbn><isbn>9780769530451</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2007</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNpNjM1OwkAURscYExVZunIzL1C8c6fT6SxJo9IE6w9lTablFkZKi9MSgk8vURd-m5NzFh9jtwJGQoC5T2dpnowQQI8Qz9g16MgoCaES5__lkg277gNOk0Yh4BWzGR34u21WxG2z5Jsgy_jbnvyRv_q2pK5zzYqP61XrXb_ednz-E55tT97Z2n3Z3rUNz6lcN-5zT_wks90p2ppn1B9av7lhF5WtOxr-ccDmjw95MgmmL09pMp4GToDqA0Kp0UhbCoxRRWR0hWgqASGYoqgoCg1qjAtTLosyVDaqSKIGpYsiJlst5YDd_f46IlrsvNtaf1yEoYAIjPwGnjJUuA</recordid><startdate>200711</startdate><enddate>200711</enddate><creator>Jung-Ho Um</creator><creator>Chowdhury, N.K.</creator><creator>Jae-Woo Chang</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>200711</creationdate><title>New Range and k-NN Query Processing Algorithms Using Materialization Technique on Spatial Network</title><author>Jung-Ho Um ; Chowdhury, N.K. ; Jae-Woo Chang</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i105t-e237293ac128256e97f229f10409bbfe6492728b9cdbc45a6fe327057bb8eafd3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2007</creationdate><topic>Computer networks</topic><topic>Data models</topic><topic>Information technology</topic><topic>Joining processes</topic><topic>Nearest neighbor searches</topic><topic>Partitioning algorithms</topic><topic>Query processing</topic><topic>Roads</topic><topic>Space stations</topic><topic>Spatial databases</topic><toplevel>online_resources</toplevel><creatorcontrib>Jung-Ho Um</creatorcontrib><creatorcontrib>Chowdhury, N.K.</creatorcontrib><creatorcontrib>Jae-Woo Chang</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Electronic Library Online</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Jung-Ho Um</au><au>Chowdhury, N.K.</au><au>Jae-Woo Chang</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>New Range and k-NN Query Processing Algorithms Using Materialization Technique on Spatial Network</atitle><btitle>2007 International Symposium on Information Technology Convergence (ISITC 2007)</btitle><stitle>ISITC</stitle><date>2007-11</date><risdate>2007</risdate><spage>76</spage><epage>80</epage><pages>76-80</pages><isbn>0769530451</isbn><isbn>9780769530451</isbn><eisbn>0769530451</eisbn><eisbn>9780769530451</eisbn><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.</abstract><pub>IEEE</pub><doi>10.1109/ISITC.2007.22</doi><tpages>5</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISBN: 0769530451
ispartof 2007 International Symposium on Information Technology Convergence (ISITC 2007), 2007, p.76-80
issn
language eng
recordid cdi_ieee_primary_4410609
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Computer networks
Data models
Information technology
Joining processes
Nearest neighbor searches
Partitioning algorithms
Query processing
Roads
Space stations
Spatial databases
title New Range and k-NN Query Processing Algorithms Using Materialization Technique on Spatial Network
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-21T03%3A46%3A02IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=New%20Range%20and%20k-NN%20Query%20Processing%20Algorithms%20Using%20Materialization%20Technique%20on%20Spatial%20Network&rft.btitle=2007%20International%20Symposium%20on%20Information%20Technology%20Convergence%20(ISITC%202007)&rft.au=Jung-Ho%20Um&rft.date=2007-11&rft.spage=76&rft.epage=80&rft.pages=76-80&rft.isbn=0769530451&rft.isbn_list=9780769530451&rft_id=info:doi/10.1109/ISITC.2007.22&rft.eisbn=0769530451&rft.eisbn_list=9780769530451&rft_dat=%3Cieee_6IE%3E4410609%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i105t-e237293ac128256e97f229f10409bbfe6492728b9cdbc45a6fe327057bb8eafd3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=4410609&rfr_iscdi=true