View in EDS

Efficient successor retrieval operations for aggregate query processing on clustered road networks

Saved in:
Bibliographic Details
Title: Efficient successor retrieval operations for aggregate query processing on clustered road networks
Authors: Demir, Engin1 demir@cse.ohio-state.edu, Aykanat, Cevdet2 aykanat@cs.bilkent.edu.tr
Source: Information Sciences. Jul2010, Vol. 180 Issue 14, p2743-2762. 20p.
Subjects: Semiconductor junctions, GKS (Computer system), Roads, Grid computing, Personnel management information storage & retrieval systems, Fuzzy hypergraphs, Document clustering, Disk access (Computer science), QUERY (Information retrieval system), Computer engineering
Abstract: Abstract: Get-Successors (GS) which retrieves all successors of a junction is a kernel operation used to facilitate aggregate computations in road network queries. Efficient implementation of the GS operation is crucial since the disk access cost of this operation constitutes a considerable portion of the total query processing cost. Firstly, we propose a new successor retrieval operation Get-Unevaluated-Successors (GUS), which retrieves only the unevaluated successors of a given junction. The GUS operation is an efficient implementation of the GS operation, where the candidate successors to be retrieved are pruned according to the properties and state of the algorithm. Secondly, we propose a hypergraph-based model for clustering successively retrieved junctions by the GUS operations to the same pages. The proposed model utilizes query logs to correctly capture the disk access cost of GUS operations. The proposed GUS operation and associated clustering model are evaluated for two different instances of GUS operations which typically arise in Dijkstra’s single source shortest path algorithm and incremental network expansion framework. Our simulation results show that the proposed successor retrieval operation together with the proposed clustering hypergraph model is quite effective in reducing the number of disk accesses in query processing. [Copyright &y& Elsevier]
Copyright of Information Sciences is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 50393207
AccessLevel: 6
PubType: Periodical
PubTypeId: serialPeriodical
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Efficient successor retrieval operations for aggregate query processing on clustered road networks
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Demir%2C+Engin%22">Demir, Engin</searchLink><relatesTo>1</relatesTo><i> demir@cse.ohio-state.edu</i><br /><searchLink fieldCode="AR" term="%22Aykanat%2C+Cevdet%22">Aykanat, Cevdet</searchLink><relatesTo>2</relatesTo><i> aykanat@cs.bilkent.edu.tr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Information+Sciences%22">Information Sciences</searchLink>. Jul2010, Vol. 180 Issue 14, p2743-2762. 20p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Semiconductor+junctions%22">Semiconductor junctions</searchLink><br /><searchLink fieldCode="DE" term="%22GKS+%28Computer+system%29%22">GKS (Computer system)</searchLink><br /><searchLink fieldCode="DE" term="%22Roads%22">Roads</searchLink><br /><searchLink fieldCode="DE" term="%22Grid+computing%22">Grid computing</searchLink><br /><searchLink fieldCode="DE" term="%22Personnel+management+information+storage+%26+retrieval+systems%22">Personnel management information storage & retrieval systems</searchLink><br /><searchLink fieldCode="DE" term="%22Fuzzy+hypergraphs%22">Fuzzy hypergraphs</searchLink><br /><searchLink fieldCode="DE" term="%22Document+clustering%22">Document clustering</searchLink><br /><searchLink fieldCode="DE" term="%22Disk+access+%28Computer+science%29%22">Disk access (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22QUERY+%28Information+retrieval+system%29%22">QUERY (Information retrieval system)</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+engineering%22">Computer engineering</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Abstract: Get-Successors (GS) which retrieves all successors of a junction is a kernel operation used to facilitate aggregate computations in road network queries. Efficient implementation of the GS operation is crucial since the disk access cost of this operation constitutes a considerable portion of the total query processing cost. Firstly, we propose a new successor retrieval operation Get-Unevaluated-Successors (GUS), which retrieves only the unevaluated successors of a given junction. The GUS operation is an efficient implementation of the GS operation, where the candidate successors to be retrieved are pruned according to the properties and state of the algorithm. Secondly, we propose a hypergraph-based model for clustering successively retrieved junctions by the GUS operations to the same pages. The proposed model utilizes query logs to correctly capture the disk access cost of GUS operations. The proposed GUS operation and associated clustering model are evaluated for two different instances of GUS operations which typically arise in Dijkstra’s single source shortest path algorithm and incremental network expansion framework. Our simulation results show that the proposed successor retrieval operation together with the proposed clustering hypergraph model is quite effective in reducing the number of disk accesses in query processing. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Information Sciences is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=50393207
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.ins.2010.03.015
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 20
        StartPage: 2743
    Subjects:
      – SubjectFull: Semiconductor junctions
        Type: general
      – SubjectFull: GKS (Computer system)
        Type: general
      – SubjectFull: Roads
        Type: general
      – SubjectFull: Grid computing
        Type: general
      – SubjectFull: Personnel management information storage & retrieval systems
        Type: general
      – SubjectFull: Fuzzy hypergraphs
        Type: general
      – SubjectFull: Document clustering
        Type: general
      – SubjectFull: Disk access (Computer science)
        Type: general
      – SubjectFull: QUERY (Information retrieval system)
        Type: general
      – SubjectFull: Computer engineering
        Type: general
    Titles:
      – TitleFull: Efficient successor retrieval operations for aggregate query processing on clustered road networks
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Demir, Engin
      – PersonEntity:
          Name:
            NameFull: Aykanat, Cevdet
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 15
              M: 07
              Text: Jul2010
              Type: published
              Y: 2010
          Identifiers:
            – Type: issn-print
              Value: 00200255
          Numbering:
            – Type: volume
              Value: 180
            – Type: issue
              Value: 14
          Titles:
            – TitleFull: Information Sciences
              Type: main
ResultId 1