New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases
Identifieur interne : 005C19 ( Istex/Corpus ); précédent : 005C18; suivant : 005C20New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases
Auteurs : Jae-Woo Chang ; Yong-Ki Kim ; Sang-Mi Kim ; Young-Chang KimSource :
- 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 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><affiliation><mods:affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jwchang@chonbuk.ac.kr</mods:affiliation></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><mods:affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: ykkim@dblab.chonbuk.ac.kr</mods:affiliation></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><mods:affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: smkim@dblab.chonbuk.ac.kr</mods:affiliation></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><mods:affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: yckim@dblab.chonbuk.ac.kr</mods:affiliation></affiliation></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></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><mods:affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jwchang@chonbuk.ac.kr</mods:affiliation></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><mods:affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: ykkim@dblab.chonbuk.ac.kr</mods:affiliation></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><mods:affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: smkim@dblab.chonbuk.ac.kr</mods:affiliation></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><mods:affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: yckim@dblab.chonbuk.ac.kr</mods:affiliation></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><istex><corpusName>springer</corpusName><author><json:item><name>Jae-Woo Chang</name><affiliations><json:string>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</json:string><json:string>E-mail: jwchang@chonbuk.ac.kr</json:string></affiliations></json:item><json:item><name>Yong-Ki Kim</name><affiliations><json:string>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</json:string><json:string>E-mail: ykkim@dblab.chonbuk.ac.kr</json:string></affiliations></json:item><json:item><name>Sang-Mi Kim</name><affiliations><json:string>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</json:string><json:string>E-mail: smkim@dblab.chonbuk.ac.kr</json:string></affiliations></json:item><json:item><name>Young-Chang Kim</name><affiliations><json:string>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</json:string><json:string>E-mail: yckim@dblab.chonbuk.ac.kr</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><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].</abstract><qualityIndicators><score>6.282</score><pdfVersion>1.3</pdfVersion><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>1228</abstractCharCount><pdfWordCount>4014</pdfWordCount><pdfCharCount>22708</pdfCharCount><pdfPageCount>10</pdfPageCount><abstractWordCount>189</abstractWordCount></qualityIndicators><title>New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases</title><genre.original><json:string>OriginalPaper</json:string></genre.original><chapterId><json:string>16</json:string><json:string>Chap16</json:string></chapterId><genre><json:string>conference [eBooks]</json:string></genre><serie><editor><json:item><name>David Hutchison</name><affiliations><json:string>Lancaster University, UK</json:string></affiliations></json:item><json:item><name>Takeo Kanade</name><affiliations><json:string>Carnegie Mellon University, Pittsburgh, PA, USA</json:string></affiliations></json:item><json:item><name>Josef Kittler</name><affiliations><json:string>University of Surrey, Guildford, UK</json:string></affiliations></json:item><json:item><name>Jon M. Kleinberg</name><affiliations><json:string>Cornell University, Ithaca, NY, USA</json:string></affiliations></json:item><json:item><name>Friedemann Mattern</name><affiliations><json:string>ETH Zurich, Switzerland</json:string></affiliations></json:item><json:item><name>John C. Mitchell</name><affiliations><json:string>Stanford University, CA, USA</json:string></affiliations></json:item><json:item><name>Moni Naor</name><affiliations><json:string>Weizmann Institute of Science, Rehovot, Israel</json:string></affiliations></json:item><json:item><name>Oscar Nierstrasz</name><affiliations><json:string>University of Bern, Switzerland</json:string></affiliations></json:item><json:item><name>C. Pandu Rangan</name><affiliations><json:string>Indian Institute of Technology, Madras, India</json:string></affiliations></json:item><json:item><name>Bernhard Steffen</name><affiliations><json:string>University of Dortmund, Germany</json:string></affiliations></json:item><json:item><name>Madhu Sudan</name><affiliations><json:string>Massachusetts Institute of Technology, MA, USA</json:string></affiliations></json:item><json:item><name>Demetri Terzopoulos</name><affiliations><json:string>University of California, Los Angeles, CA, USA</json:string></affiliations></json:item><json:item><name>Dough Tygar</name><affiliations><json:string>University of California, Berkeley, CA, USA</json:string></affiliations></json:item><json:item><name>Moshe Y. Vardi</name><affiliations><json:string>Rice University, Houston, TX, USA</json:string></affiliations></json:item><json:item><name>Gerhard Weikum</name><affiliations><json:string>Max-Planck Institute of Computer Science, Saarbruecken, Germany</json:string></affiliations></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>2006</copyrightDate></serie><host><editor><json:item><name>John F. Roddick</name><affiliations><json:string>Flinders University, Adelaide, Australia</json:string><json:string>E-mail: roddick@cs.flinders.edu.au</json:string></affiliations></json:item><json:item><name>V. Richard Benjamins</name><affiliations><json:string>iSOCO, Spain</json:string><json:string>E-mail: rbenjamins@isoco.com</json:string></affiliations></json:item><json:item><name>Samira Si-said Cherfi</name><affiliations><json:string>CEDRIC-CNAM, France</json:string><json:string>E-mail: sisaid@cnam.fr</json:string></affiliations></json:item><json:item><name>Roger Chiang</name><affiliations><json:string>University of Cincinnati, USA</json:string><json:string>E-mail: roger.chiang@uc.edu</json:string></affiliations></json:item><json:item><name>Christophe Claramunt</name><affiliations><json:string>Naval Academy Research Institute, Brest Naval, France</json:string><json:string>E-mail: claramunt@ecole-navale.fr</json:string></affiliations></json:item><json:item><name>Ramez A. Elmasri</name><affiliations><json:string>Department of Computer Science and Engineering, The University of Texas at Arlington, USA</json:string><json:string>E-mail: elmasri@uta.edu</json:string></affiliations></json:item><json:item><name>Fabio Grandi</name><affiliations><json:string>Dipartimento di Elettronica, Informatica e Sistemistica, Alma Mater Studiorum – Università di Bologna, Italy</json:string><json:string>E-mail: fabio.grandi@unibo.it</json:string></affiliations></json:item><json:item><name>Hyoil Han</name><affiliations><json:string>Drexel University, USA</json:string><json:string>E-mail: hhan@ischool.drexel.edu</json:string></affiliations></json:item><json:item><name>Martin Hepp</name><affiliations><json:string>E-Business and Web Science Research Group, Bundeswehr University Munich, Germany</json:string><json:string>E-mail: mhepp@computer.org</json:string></affiliations></json:item><json:item><name>Miltiadis D. Lytras</name><affiliations><json:string>University of Patras, Argolidos 40-42, 153-44, Gerakas Attikis, Greece</json:string><json:string>E-mail: miltiadis.lytras@gmail.com</json:string></affiliations></json:item><json:item><name>Vojislav B. Mišić</name><affiliations><json:string>University of Manitoba, Canada</json:string><json:string>E-mail: vmisic@cs.umanitoba.ca</json:string></affiliations></json:item><json:item><name>Geert Poels</name><affiliations><json:string>Ghent University, Belgium</json:string><json:string>E-mail: geert.poels@ugent.be</json:string></affiliations></json:item><json:item><name>Il-Yeol Song</name><affiliations><json:string>College of Information Science and Technology, Drexel University, USA</json:string><json:string>E-mail: song@drexel.edu</json:string></affiliations></json:item><json:item><name>Juan Trujillo</name><affiliations><json:string>Department of Software and Computing Systems, University of Alicante, Spain</json:string><json:string>E-mail: jtrujillo@dlsi.ua.es</json:string></affiliations></json:item><json:item><name>Christelle Vangenot</name><affiliations><json:string>EPFL, Switzerland</json:string><json:string>E-mail: christelle.vangenot@epfl.ch</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Information Systems Applications (incl.Internet)</value></json:item><json:item><value>Database Management</value></json:item><json:item><value>Information Storage and Retrieval</value></json:item><json:item><value>Artificial Intelligence (incl. Robotics)</value></json:item><json:item><value>Computer Applications in Earth Sciences</value></json:item><json:item><value>Business Information Systems</value></json:item></subject><isbn><json:string>978-3-540-47703-7</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Advances in Conceptual Modeling - Theory and Practice</title><genre.original><json:string>Proceedings</json:string></genre.original><bookId><json:string>978-3-540-47704-4</json:string></bookId><volume>4231</volume><pages><last>139</last><first>130</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>Book Series</json:string></genre><eisbn><json:string>978-3-540-47704-4</json:string></eisbn><copyrightDate>2006</copyrightDate><doi><json:string>10.1007/11908883</json:string></doi></host><publicationDate>2006</publicationDate><copyrightDate>2006</copyrightDate><doi><json:string>10.1007/11908883_16</json:string></doi><id>F93C9F64BFE20E5EF780E2F559156EE01B3D75FC</id><score>1</score><fulltext><json:item><original>true</original><mimetype>application/pdf</mimetype><extension>pdf</extension><uri>https://api.istex.fr/document/F93C9F64BFE20E5EF780E2F559156EE01B3D75FC/fulltext/pdf</uri></json:item><json:item><original>false</original><mimetype>application/zip</mimetype><extension>zip</extension><uri>https://api.istex.fr/document/F93C9F64BFE20E5EF780E2F559156EE01B3D75FC/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/F93C9F64BFE20E5EF780E2F559156EE01B3D75FC/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases</title><respStmt xml:id="ISTEX-API" resp="Références bibliographiques récupérées via GROBID" name="ISTEX-API (INIST-CNRS)"></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>SPRINGER</p></availability><date>2006</date></publicationStmt><sourceDesc><biblStruct type="inbook"><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><persName><forename type="first">Jae-Woo</forename><surname>Chang</surname></persName><email>jwchang@chonbuk.ac.kr</email><affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</affiliation></author><author><persName><forename type="first">Yong-Ki</forename><surname>Kim</surname></persName><email>ykkim@dblab.chonbuk.ac.kr</email><affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</affiliation></author><author><persName><forename type="first">Sang-Mi</forename><surname>Kim</surname></persName><email>smkim@dblab.chonbuk.ac.kr</email><affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</affiliation></author><author><persName><forename type="first">Young-Chang</forename><surname>Kim</surname></persName><email>yckim@dblab.chonbuk.ac.kr</email><affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</affiliation></author></analytic><monogr><title level="m">Advances in Conceptual Modeling - Theory and Practice</title><title level="m" type="sub">ER 2006 Workshops BP-UML, CoMoGIS, COSS, ECDM, OIS, QoIS, SemWAT, Tucson, AZ, USA, November 6-9, 2006. Proceedings</title><idno type="pISBN">978-3-540-47703-7</idno><idno type="eISBN">978-3-540-47704-4</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/11908883</idno><idno type="BookID">978-3-540-47704-4</idno><idno type="BookTitleID">142214</idno><idno type="BookSequenceNumber">4231</idno><idno type="BookVolumeNumber">4231</idno><idno type="BookChapterCount">52</idno><editor><persName><forename type="first">John</forename><forename type="first">F.</forename><surname>Roddick</surname></persName><email>roddick@cs.flinders.edu.au</email><affiliation>Flinders University, Adelaide, Australia</affiliation></editor><editor><persName><forename type="first">V.</forename><forename type="first">Richard</forename><surname>Benjamins</surname></persName><email>rbenjamins@isoco.com</email><affiliation>iSOCO, Spain</affiliation></editor><editor><persName><forename type="first">Samira</forename><surname>Si-said Cherfi</surname></persName><email>sisaid@cnam.fr</email><affiliation>CEDRIC-CNAM, France</affiliation></editor><editor><persName><forename type="first">Roger</forename><surname>Chiang</surname></persName><email>roger.chiang@uc.edu</email><affiliation>University of Cincinnati, USA</affiliation></editor><editor><persName><forename type="first">Christophe</forename><surname>Claramunt</surname></persName><email>claramunt@ecole-navale.fr</email><affiliation>Naval Academy Research Institute, Brest Naval, France</affiliation></editor><editor><persName><forename type="first">Ramez</forename><forename type="first">A.</forename><surname>Elmasri</surname></persName><email>elmasri@uta.edu</email><affiliation>Department of Computer Science and Engineering, The University of Texas at Arlington, USA</affiliation></editor><editor><persName><forename type="first">Fabio</forename><surname>Grandi</surname></persName><email>fabio.grandi@unibo.it</email><affiliation>Dipartimento di Elettronica, Informatica e Sistemistica, Alma Mater Studiorum – Università di Bologna, Italy</affiliation></editor><editor><persName><forename type="first">Hyoil</forename><surname>Han</surname></persName><email>hhan@ischool.drexel.edu</email><affiliation>Drexel University, USA</affiliation></editor><editor><persName><forename type="first">Martin</forename><surname>Hepp</surname></persName><email>mhepp@computer.org</email><affiliation>E-Business and Web Science Research Group, Bundeswehr University Munich, Germany</affiliation></editor><editor><persName><forename type="first">Miltiadis</forename><forename type="first">D.</forename><surname>Lytras</surname></persName><email>miltiadis.lytras@gmail.com</email><affiliation>University of Patras, Argolidos 40-42, 153-44, Gerakas Attikis, Greece</affiliation></editor><editor><persName><forename type="first">Vojislav</forename><forename type="first">B.</forename><surname>Mišić</surname></persName><email>vmisic@cs.umanitoba.ca</email><affiliation>University of Manitoba, Canada</affiliation></editor><editor><persName><forename type="first">Geert</forename><surname>Poels</surname></persName><email>geert.poels@ugent.be</email><affiliation>Ghent University, Belgium</affiliation></editor><editor><persName><forename type="first">Il-Yeol</forename><surname>Song</surname></persName><email>song@drexel.edu</email><affiliation>College of Information Science and Technology, Drexel University, USA</affiliation></editor><editor><persName><forename type="first">Juan</forename><surname>Trujillo</surname></persName><email>jtrujillo@dlsi.ua.es</email><affiliation>Department of Software and Computing Systems, University of Alicante, Spain</affiliation></editor><editor><persName><forename type="first">Christelle</forename><surname>Vangenot</surname></persName><email>christelle.vangenot@epfl.ch</email><affiliation>EPFL, Switzerland</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2006"></date><biblScope unit="volume">4231</biblScope><biblScope unit="page" from="130">130</biblScope><biblScope unit="page" to="139">139</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName><affiliation>Lancaster University, UK</affiliation></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName><affiliation>University of Surrey, Guildford, UK</affiliation></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName><affiliation>Cornell University, Ithaca, NY, USA</affiliation></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName><affiliation>ETH Zurich, Switzerland</affiliation></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName><affiliation>Stanford University, CA, USA</affiliation></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName><affiliation>University of Bern, Switzerland</affiliation></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName><affiliation>Indian Institute of Technology, Madras, India</affiliation></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName><affiliation>University of Dortmund, Germany</affiliation></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName><affiliation>University of California, Los Angeles, CA, USA</affiliation></editor><editor><persName><forename type="first">Dough</forename><surname>Tygar</surname></persName><affiliation>University of California, Berkeley, CA, USA</affiliation></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName><affiliation>Rice University, Houston, TX, USA</affiliation></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName><affiliation>Max-Planck Institute of Computer Science, Saarbruecken, Germany</affiliation></editor><biblScope><date>2006</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="seriesId">558</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></fileDesc><profileDesc><creation><date>2006</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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].</p></abstract><textClass><keywords scheme="Book Subject Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book Subject Group"><list><label>I</label><label>I18040</label><label>I18024</label><label>I18032</label><label>I21017</label><label>G13007</label><label>W26007</label><item><term>Computer Science</term></item><item><term>Information Systems Applications (incl.Internet)</term></item><item><term>Database Management</term></item><item><term>Information Storage and Retrieval</term></item><item><term>Artificial Intelligence (incl. Robotics)</term></item><item><term>Computer Applications in Earth Sciences</term></item><item><term>Business Information Systems</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2006">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-3-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><original>false</original><mimetype>text/plain</mimetype><extension>txt</extension><uri>https://api.istex.fr/document/F93C9F64BFE20E5EF780E2F559156EE01B3D75FC/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff6"><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff7"><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff8"><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff9"><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff10"><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff11"><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff12"><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff13"><EditorName DisplayOrder="Western"><GivenName>Dough</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff14"><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff15"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Lancaster University</OrgName><OrgAddress><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Carnegie Mellon University</OrgName><OrgAddress><City>Pittsburgh</City><State>PA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>University of Surrey</OrgName><OrgAddress><City>Guildford</City><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff4"><OrgName>Cornell University</OrgName><OrgAddress><City>Ithaca</City><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgName>ETH Zurich</OrgName><OrgAddress><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgName>Stanford University</OrgName><OrgAddress><City>CA</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff7"><OrgName>Weizmann Institute of Science</OrgName><OrgAddress><City>Rehovot</City><Country>Israel</Country></OrgAddress></Affiliation><Affiliation ID="Aff8"><OrgName>University of Bern</OrgName><OrgAddress><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff9"><OrgName>Indian Institute of Technology</OrgName><OrgAddress><City>Madras</City><Country>India</Country></OrgAddress></Affiliation><Affiliation ID="Aff10"><OrgName>University of Dortmund</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff11"><OrgName>Massachusetts Institute of Technology</OrgName><OrgAddress><City>MA</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff12"><OrgName>University of California</OrgName><OrgAddress><City>Los Angeles</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff13"><OrgName>University of California</OrgName><OrgAddress><City>Berkeley</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff14"><OrgName>Rice University</OrgName><OrgAddress><City>Houston</City><State>TX</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff15"><OrgName>Max-Planck Institute of Computer Science</OrgName><OrgAddress><City>Saarbruecken</City><Country>Germany</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingDepth="2" NumberingStyle="ContentOnly" OutputMedium="All" TocLevels="0"><BookID>978-3-540-47704-4</BookID><BookTitle>Advances in Conceptual Modeling - Theory and Practice</BookTitle><BookSubTitle>ER 2006 Workshops BP-UML, CoMoGIS, COSS, ECDM, OIS, QoIS, SemWAT, Tucson, AZ, USA, November 6-9, 2006. Proceedings</BookSubTitle><BookVolumeNumber>4231</BookVolumeNumber><BookSequenceNumber>4231</BookSequenceNumber><BookDOI>10.1007/11908883</BookDOI><BookTitleID>142214</BookTitleID><BookPrintISBN>978-3-540-47703-7</BookPrintISBN><BookElectronicISBN>978-3-540-47704-4</BookElectronicISBN><BookChapterCount>52</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2006</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I18040" Priority="1" Type="Secondary">Information Systems Applications (incl.Internet)</BookSubject><BookSubject Code="I18024" Priority="2" Type="Secondary">Database Management</BookSubject><BookSubject Code="I18032" Priority="3" Type="Secondary">Information Storage and Retrieval</BookSubject><BookSubject Code="I21017" Priority="4" Type="Secondary">Artificial Intelligence (incl. Robotics)</BookSubject><BookSubject Code="G13007" Priority="5" Type="Secondary">Computer Applications in Earth Sciences</BookSubject><BookSubject Code="W26007" Priority="6" Type="Secondary">Business Information Systems</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff16"><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>F.</GivenName><FamilyName>Roddick</FamilyName></EditorName><Contact><Email>roddick@cs.flinders.edu.au</Email></Contact></Editor><Editor AffiliationIDS="Aff17"><EditorName DisplayOrder="Western"><GivenName>V.</GivenName><GivenName>Richard</GivenName><FamilyName>Benjamins</FamilyName></EditorName><Contact><Email>rbenjamins@isoco.com</Email></Contact></Editor><Editor AffiliationIDS="Aff18"><EditorName DisplayOrder="Western"><GivenName>Samira</GivenName><FamilyName>Si-said Cherfi</FamilyName></EditorName><Contact><Email>sisaid@cnam.fr</Email></Contact></Editor><Editor AffiliationIDS="Aff19"><EditorName DisplayOrder="Western"><GivenName>Roger</GivenName><FamilyName>Chiang</FamilyName></EditorName><Contact><Email>roger.chiang@uc.edu</Email></Contact></Editor><Editor AffiliationIDS="Aff20"><EditorName DisplayOrder="Western"><GivenName>Christophe</GivenName><FamilyName>Claramunt</FamilyName></EditorName><Contact><Email>claramunt@ecole-navale.fr</Email></Contact></Editor><Editor AffiliationIDS="Aff21"><EditorName DisplayOrder="Western"><GivenName>Ramez</GivenName><GivenName>A.</GivenName><FamilyName>Elmasri</FamilyName></EditorName><Contact><Email>elmasri@uta.edu</Email></Contact></Editor><Editor AffiliationIDS="Aff22"><EditorName DisplayOrder="Western"><GivenName>Fabio</GivenName><FamilyName>Grandi</FamilyName></EditorName><Contact><Email>fabio.grandi@unibo.it</Email></Contact></Editor><Editor AffiliationIDS="Aff23"><EditorName DisplayOrder="Western"><GivenName>Hyoil</GivenName><FamilyName>Han</FamilyName></EditorName><Contact><Email>hhan@ischool.drexel.edu</Email></Contact></Editor><Editor AffiliationIDS="Aff24"><EditorName DisplayOrder="Western"><GivenName>Martin</GivenName><FamilyName>Hepp</FamilyName></EditorName><Contact><Email>mhepp@computer.org</Email></Contact></Editor><Editor AffiliationIDS="Aff25"><EditorName DisplayOrder="Western"><GivenName>Miltiadis</GivenName><GivenName>D.</GivenName><FamilyName>Lytras</FamilyName></EditorName><Contact><Email>miltiadis.lytras@gmail.com</Email></Contact></Editor><Editor AffiliationIDS="Aff26"><EditorName DisplayOrder="Western"><GivenName>Vojislav</GivenName><GivenName>B.</GivenName><FamilyName>Mišić</FamilyName></EditorName><Contact><Email>vmisic@cs.umanitoba.ca</Email></Contact></Editor><Editor AffiliationIDS="Aff27"><EditorName DisplayOrder="Western"><GivenName>Geert</GivenName><FamilyName>Poels</FamilyName></EditorName><Contact><Email>geert.poels@ugent.be</Email></Contact></Editor><Editor AffiliationIDS="Aff28"><EditorName DisplayOrder="Western"><GivenName>Il-Yeol</GivenName><FamilyName>Song</FamilyName></EditorName><Contact><Email>song@drexel.edu</Email></Contact></Editor><Editor AffiliationIDS="Aff29"><EditorName DisplayOrder="Western"><GivenName>Juan</GivenName><FamilyName>Trujillo</FamilyName></EditorName><Contact><Email>jtrujillo@dlsi.ua.es</Email></Contact></Editor><Editor AffiliationIDS="Aff30"><EditorName DisplayOrder="Western"><GivenName>Christelle</GivenName><FamilyName>Vangenot</FamilyName></EditorName><Contact><Email>christelle.vangenot@epfl.ch</Email></Contact></Editor><Affiliation ID="Aff16"><OrgName>Flinders University</OrgName><OrgAddress><City>Adelaide</City><Country>Australia</Country></OrgAddress></Affiliation><Affiliation ID="Aff17"><OrgName>iSOCO</OrgName><OrgAddress><Country>Spain</Country></OrgAddress></Affiliation><Affiliation ID="Aff18"><OrgName>CEDRIC-CNAM</OrgName><OrgAddress><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff19"><OrgName>University of Cincinnati</OrgName><OrgAddress><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff20"><OrgName>Naval Academy Research Institute</OrgName><OrgAddress><City>Brest Naval</City><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff21"><OrgDivision>Department of Computer Science and Engineering</OrgDivision><OrgName>The University of Texas at Arlington</OrgName><OrgAddress><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff22"><OrgDivision>Dipartimento di Elettronica, Informatica e Sistemistica</OrgDivision><OrgName>Alma Mater Studiorum – Università di Bologna</OrgName><OrgAddress><Country>Italy</Country></OrgAddress></Affiliation><Affiliation ID="Aff23"><OrgName>Drexel University</OrgName><OrgAddress><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff24"><OrgDivision>E-Business and Web Science Research Group</OrgDivision><OrgName>Bundeswehr University Munich</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff25"><OrgName>University of Patras</OrgName><OrgAddress><Street>Argolidos 40-42</Street><Postcode>153-44</Postcode><City>Gerakas Attikis</City><Country>Greece</Country></OrgAddress></Affiliation><Affiliation ID="Aff26"><OrgName>University of Manitoba</OrgName><OrgAddress><Country>Canada</Country></OrgAddress></Affiliation><Affiliation ID="Aff27"><OrgName>Ghent University</OrgName><OrgAddress><Country>Belgium</Country></OrgAddress></Affiliation><Affiliation ID="Aff28"><OrgDivision>College of Information Science and Technology</OrgDivision><OrgName>Drexel University</OrgName><OrgAddress><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff29"><OrgDivision>Department of Software and Computing Systems</OrgDivision><OrgName>University of Alicante</OrgName><OrgAddress><Country>Spain</Country></OrgAddress></Affiliation><Affiliation ID="Aff30"><OrgName>EPFL</OrgName><OrgAddress><Country>Switzerland</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part6"><PartInfo TocLevels="0"><PartID>6</PartID><PartSequenceNumber>6</PartSequenceNumber><PartTitle>Optimizing Representation and Access to Spatial Data</PartTitle><PartChapterCount>3</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Advances in Conceptual Modeling - Theory and Practice</BookTitle></PartContext></PartInfo><Chapter ID="Chap16" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingDepth="2" NumberingStyle="ContentOnly" TocLevels="0"><ChapterID>16</ChapterID><ChapterDOI>10.1007/11908883_16</ChapterDOI><ChapterSequenceNumber>16</ChapterSequenceNumber><ChapterTitle Language="En">New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases</ChapterTitle><ChapterFirstPage>130</ChapterFirstPage><ChapterLastPage>139</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2006</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>6</PartID><BookID>978-3-540-47704-4</BookID><BookTitle>Advances in Conceptual Modeling - Theory and Practice</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff31"><AuthorName DisplayOrder="Western"><GivenName>Jae-Woo</GivenName><FamilyName>Chang</FamilyName></AuthorName><Contact><Email>jwchang@chonbuk.ac.kr</Email></Contact></Author><Author AffiliationIDS="Aff31"><AuthorName DisplayOrder="Western"><GivenName>Yong-Ki</GivenName><FamilyName>Kim</FamilyName></AuthorName><Contact><Email>ykkim@dblab.chonbuk.ac.kr</Email></Contact></Author><Author AffiliationIDS="Aff31"><AuthorName DisplayOrder="Western"><GivenName>Sang-Mi</GivenName><FamilyName>Kim</FamilyName></AuthorName><Contact><Email>smkim@dblab.chonbuk.ac.kr</Email></Contact></Author><Author AffiliationIDS="Aff31"><AuthorName DisplayOrder="Western"><GivenName>Young-Chang</GivenName><FamilyName>Kim</FamilyName></AuthorName><Contact><Email>yckim@dblab.chonbuk.ac.kr</Email></Contact></Author><Affiliation ID="Aff31"><OrgDivision>Dept. of Computer Engineering</OrgDivision><OrgName>Chonbuk National Univ.</OrgName><OrgAddress><City>Chonju, Chonbuk</City><Postcode>561-756</Postcode><Country>South Korea</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>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].</Para></Abstract><ArticleNote Type="Misc"><SimplePara>This work is financially supported by the Ministry of Education and Human Resources Development(MOE), the Ministry of Commerce, Industry and Energy(MOCIE) and the Ministry of Labor(MOLAB) though the fostering project of the Lab of Excellency.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases</title></titleInfo><name type="personal"><namePart type="given">Jae-Woo</namePart><namePart type="family">Chang</namePart><affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</affiliation><affiliation>E-mail: jwchang@chonbuk.ac.kr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Yong-Ki</namePart><namePart type="family">Kim</namePart><affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</affiliation><affiliation>E-mail: ykkim@dblab.chonbuk.ac.kr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Sang-Mi</namePart><namePart type="family">Kim</namePart><affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</affiliation><affiliation>E-mail: smkim@dblab.chonbuk.ac.kr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Young-Chang</namePart><namePart type="family">Kim</namePart><affiliation>Dept. of Computer Engineering, Chonbuk National Univ., 561-756, Chonju, Chonbuk, South Korea</affiliation><affiliation>E-mail: yckim@dblab.chonbuk.ac.kr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference [eBooks]" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2006</dateIssued><copyrightDate encoding="w3cdtf">2006</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract 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].</abstract><relatedItem type="host"><titleInfo><title>Advances in Conceptual Modeling - Theory and Practice</title><subTitle>ER 2006 Workshops BP-UML, CoMoGIS, COSS, ECDM, OIS, QoIS, SemWAT, Tucson, AZ, USA, November 6-9, 2006. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">John</namePart><namePart type="given">F.</namePart><namePart type="family">Roddick</namePart><affiliation>Flinders University, Adelaide, Australia</affiliation><affiliation>E-mail: roddick@cs.flinders.edu.au</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">V.</namePart><namePart type="given">Richard</namePart><namePart type="family">Benjamins</namePart><affiliation>iSOCO, Spain</affiliation><affiliation>E-mail: rbenjamins@isoco.com</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Samira</namePart><namePart type="family">Si-said Cherfi</namePart><affiliation>CEDRIC-CNAM, France</affiliation><affiliation>E-mail: sisaid@cnam.fr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Roger</namePart><namePart type="family">Chiang</namePart><affiliation>University of Cincinnati, USA</affiliation><affiliation>E-mail: roger.chiang@uc.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Christophe</namePart><namePart type="family">Claramunt</namePart><affiliation>Naval Academy Research Institute, Brest Naval, France</affiliation><affiliation>E-mail: claramunt@ecole-navale.fr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Ramez</namePart><namePart type="given">A.</namePart><namePart type="family">Elmasri</namePart><affiliation>Department of Computer Science and Engineering, The University of Texas at Arlington, USA</affiliation><affiliation>E-mail: elmasri@uta.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Fabio</namePart><namePart type="family">Grandi</namePart><affiliation>Dipartimento di Elettronica, Informatica e Sistemistica, Alma Mater Studiorum – Università di Bologna, Italy</affiliation><affiliation>E-mail: fabio.grandi@unibo.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Hyoil</namePart><namePart type="family">Han</namePart><affiliation>Drexel University, USA</affiliation><affiliation>E-mail: hhan@ischool.drexel.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Martin</namePart><namePart type="family">Hepp</namePart><affiliation>E-Business and Web Science Research Group, Bundeswehr University Munich, Germany</affiliation><affiliation>E-mail: mhepp@computer.org</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Miltiadis</namePart><namePart type="given">D.</namePart><namePart type="family">Lytras</namePart><affiliation>University of Patras, Argolidos 40-42, 153-44, Gerakas Attikis, Greece</affiliation><affiliation>E-mail: miltiadis.lytras@gmail.com</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Vojislav</namePart><namePart type="given">B.</namePart><namePart type="family">Mišić</namePart><affiliation>University of Manitoba, Canada</affiliation><affiliation>E-mail: vmisic@cs.umanitoba.ca</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Geert</namePart><namePart type="family">Poels</namePart><affiliation>Ghent University, Belgium</affiliation><affiliation>E-mail: geert.poels@ugent.be</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Il-Yeol</namePart><namePart type="family">Song</namePart><affiliation>College of Information Science and Technology, Drexel University, USA</affiliation><affiliation>E-mail: song@drexel.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juan</namePart><namePart type="family">Trujillo</namePart><affiliation>Department of Software and Computing Systems, University of Alicante, Spain</affiliation><affiliation>E-mail: jtrujillo@dlsi.ua.es</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Christelle</namePart><namePart type="family">Vangenot</namePart><affiliation>EPFL, Switzerland</affiliation><affiliation>E-mail: christelle.vangenot@epfl.ch</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="Book Series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2006</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book Subject Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book Subject Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I18040">Information Systems Applications (incl.Internet)</topic><topic authority="SpringerSubjectCodes" authorityURI="I18024">Database Management</topic><topic authority="SpringerSubjectCodes" authorityURI="I18032">Information Storage and Retrieval</topic><topic authority="SpringerSubjectCodes" authorityURI="I21017">Artificial Intelligence (incl. Robotics)</topic><topic authority="SpringerSubjectCodes" authorityURI="G13007">Computer Applications in Earth Sciences</topic><topic authority="SpringerSubjectCodes" authorityURI="W26007">Business Information Systems</topic></subject><identifier type="DOI">10.1007/11908883</identifier><identifier type="ISBN">978-3-540-47703-7</identifier><identifier type="eISBN">978-3-540-47704-4</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">142214</identifier><identifier type="BookID">978-3-540-47704-4</identifier><identifier type="BookChapterCount">52</identifier><identifier type="BookVolumeNumber">4231</identifier><identifier type="BookSequenceNumber">4231</identifier><identifier type="PartChapterCount">3</identifier><part><date>2006</date><detail type="part"><title>Optimizing Representation and Access to Spatial Data</title></detail><detail type="volume"><number>4231</number><caption>vol.</caption></detail><extent unit="pages"><start>130</start><end>139</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2006</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><affiliation>Lancaster University, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><affiliation>University of Surrey, Guildford, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><affiliation>Cornell University, Ithaca, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><affiliation>ETH Zurich, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><affiliation>Stanford University, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><affiliation>University of Bern, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><affiliation>Indian Institute of Technology, Madras, India</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><affiliation>University of Dortmund, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><affiliation>University of California, Los Angeles, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Dough</namePart><namePart type="family">Tygar</namePart><affiliation>University of California, Berkeley, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><affiliation>Rice University, Houston, TX, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><affiliation>Max-Planck Institute of Computer Science, Saarbruecken, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2006</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2006</recordOrigin></recordInfo></relatedItem><identifier type="istex">F93C9F64BFE20E5EF780E2F559156EE01B3D75FC</identifier><identifier type="DOI">10.1007/11908883_16</identifier><identifier type="ChapterID">16</identifier><identifier type="ChapterID">Chap16</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2006</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2006</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/TelematiV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005C19 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 005C19 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= TelematiV1
|flux= Istex
|étape= Corpus
|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. |  |