New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases
Identifieur interne : 002018 ( Main/Merge ); précédent : 002017; suivant : 002019New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases
Auteurs : Jae-Woo Chang [Corée du Sud] ; Yong-Ki Kim [Corée du Sud] ; Sang-Mi Kim [Corée du Sud] ; Young-Chang Kim [Corée du Sud]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2006.
Abstract
Abstract: In this paper, we design the architecture of disk-based data structures for spatial network databases (SNDB). Based on this architecture, we propose new query processing algorithms for range search and k nearest neighbors (k-NN) search, depending on the density of point of interests (POIs) in the spatial network. For this, we effectively combine Euclidean restriction and the network expansion techniques according to the density of POIs. In addition, 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 maintaining the shortest network distances of all the nodes in the spatial network. It is shown that our range query processing algorithm achieves about up to one order of magnitude better performance than the existing range query processing algorithm, such as RER and RNE [1]. In addition, our k-NN query processing algorithm achieves about up to 170~400% performance improvements over the existing network expansion k-NN algorithm, called INE, while it shows about up to one order of magnitude better performance than the existing Euclidean restriction k-NN algorithm, called IER [1].
Url:
DOI: 10.1007/11908883_16
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 005C19
- to stream Istex, to step Curation: 005C19
- to stream Istex, to step Checkpoint: 001577
Links to Exploration step
ISTEX:F93C9F64BFE20E5EF780E2F559156EE01B3D75FCLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases</title><author><name sortKey="Chang, Jae Woo" sort="Chang, Jae Woo" uniqKey="Chang J" first="Jae-Woo" last="Chang">Jae-Woo Chang</name></author><author><name sortKey="Kim, Yong Ki" sort="Kim, Yong Ki" uniqKey="Kim Y" first="Yong-Ki" last="Kim">Yong-Ki Kim</name></author><author><name sortKey="Kim, Sang Mi" sort="Kim, Sang Mi" uniqKey="Kim S" first="Sang-Mi" last="Kim">Sang-Mi Kim</name></author><author><name sortKey="Kim, Young Chang" sort="Kim, Young Chang" uniqKey="Kim Y" first="Young-Chang" last="Kim">Young-Chang Kim</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:F93C9F64BFE20E5EF780E2F559156EE01B3D75FC</idno><date when="2006" year="2006">2006</date><idno type="doi">10.1007/11908883_16</idno><idno type="url">https://api.istex.fr/document/F93C9F64BFE20E5EF780E2F559156EE01B3D75FC/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">005C19</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">005C19</idno><idno type="wicri:Area/Istex/Curation">005C19</idno><idno type="wicri:Area/Istex/Checkpoint">001577</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001577</idno><idno type="wicri:doubleKey">0302-9743:2006:Chang J:new:query:processing</idno><idno type="wicri:Area/Main/Merge">002018</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases</title><author><name sortKey="Chang, Jae Woo" sort="Chang, Jae Woo" uniqKey="Chang J" first="Jae-Woo" last="Chang">Jae-Woo Chang</name><affiliation wicri:level="1"><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk</wicri:regionArea><wicri:noRegion>Chonbuk</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Corée du Sud</country></affiliation></author><author><name sortKey="Kim, Yong Ki" sort="Kim, Yong Ki" uniqKey="Kim Y" first="Yong-Ki" last="Kim">Yong-Ki Kim</name><affiliation wicri:level="1"><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk</wicri:regionArea><wicri:noRegion>Chonbuk</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Corée du Sud</country></affiliation></author><author><name sortKey="Kim, Sang Mi" sort="Kim, Sang Mi" uniqKey="Kim S" first="Sang-Mi" last="Kim">Sang-Mi Kim</name><affiliation wicri:level="1"><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk</wicri:regionArea><wicri:noRegion>Chonbuk</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Corée du Sud</country></affiliation></author><author><name sortKey="Kim, Young Chang" sort="Kim, Young Chang" uniqKey="Kim Y" first="Young-Chang" last="Kim">Young-Chang Kim</name><affiliation wicri:level="1"><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk</wicri:regionArea><wicri:noRegion>Chonbuk</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Corée du Sud</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2006</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">F93C9F64BFE20E5EF780E2F559156EE01B3D75FC</idno><idno type="DOI">10.1007/11908883_16</idno><idno type="ChapterID">16</idno><idno type="ChapterID">Chap16</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper, we design the architecture of disk-based data structures for spatial network databases (SNDB). Based on this architecture, we propose new query processing algorithms for range search and k nearest neighbors (k-NN) search, depending on the density of point of interests (POIs) in the spatial network. For this, we effectively combine Euclidean restriction and the network expansion techniques according to the density of POIs. In addition, 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 maintaining the shortest network distances of all the nodes in the spatial network. It is shown that our range query processing algorithm achieves about up to one order of magnitude better performance than the existing range query processing algorithm, such as RER and RNE [1]. In addition, our k-NN query processing algorithm achieves about up to 170~400% performance improvements over the existing network expansion k-NN algorithm, called INE, while it shows about up to one order of magnitude better performance than the existing Euclidean restriction k-NN algorithm, called IER [1].</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/TelematiV1/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002018 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 002018 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= TelematiV1
|flux= Main
|étape= Merge
|type= RBID
|clé= ISTEX:F93C9F64BFE20E5EF780E2F559156EE01B3D75FC
|texte= New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases
}}
| This area was generated with Dilib version V0.6.31. |  |