A declustering algorithm for minimising spatial join cost

Yanchun Zhang; Jitian Xiao; Xiaofang Zhou

doi:10.1007/bfb0045103

A declustering algorithm for minimising spatial join cost

Yanchun Zhang, Jitian Xiao, Xiaofang Zhou

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

5 Citations (Scopus)

Abstract

Spatial joins are important, yet time-consuming operations in spatial databases. In this paper we consider to minimise the I/O cost for the spatial join processing. A graph model is proposed to formalise the cost, and an algorithm originally proposed for distributed database design is adapted for spatial object declustering. We improve the algorithm by giving special consideration to the clusters with overlapped objects. Our algorithm can not only reduce the number of objects fetched from disk for refinement processing, but also be computationally more efficient than the previous algorithms.

Original language	English
Title of host publication	Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings
Editors	Tao Jiang, D.T. Lee
Publisher	Springer Verlag
Pages	363-372
Number of pages	10
ISBN (Print)	354063357X, 9783540633570
DOIs	https://doi.org/10.1007/bfb0045103
Publication status	Published - 1997
Externally published	Yes
Event	3rd Annual International Computing and Combinatorics Conference, COCOON 1997 - Shanghai, China Duration: 20 Aug 1997 → 22 Aug 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1276
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd Annual International Computing and Combinatorics Conference, COCOON 1997
Country/Territory	China
City	Shanghai
Period	20/08/97 → 22/08/97

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.

Access to Document

10.1007/bfb0045103

Cite this

Zhang, Y., Xiao, J., & Zhou, X. (1997). A declustering algorithm for minimising spatial join cost. In T. Jiang, & D. T. Lee (Eds.), Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings (pp. 363-372). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1276). Springer Verlag. https://doi.org/10.1007/bfb0045103

Zhang, Yanchun ; Xiao, Jitian ; Zhou, Xiaofang. / A declustering algorithm for minimising spatial join cost. Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings. editor / Tao Jiang ; D.T. Lee. Springer Verlag, 1997. pp. 363-372 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9ed0645e8e6a4b19b4676732afb13583,

title = "A declustering algorithm for minimising spatial join cost",

abstract = "Spatial joins are important, yet time-consuming operations in spatial databases. In this paper we consider to minimise the I/O cost for the spatial join processing. A graph model is proposed to formalise the cost, and an algorithm originally proposed for distributed database design is adapted for spatial object declustering. We improve the algorithm by giving special consideration to the clusters with overlapped objects. Our algorithm can not only reduce the number of objects fetched from disk for refinement processing, but also be computationally more efficient than the previous algorithms.",

author = "Yanchun Zhang and Jitian Xiao and Xiaofang Zhou",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 3rd Annual International Computing and Combinatorics Conference, COCOON 1997 ; Conference date: 20-08-1997 Through 22-08-1997",

year = "1997",

doi = "10.1007/bfb0045103",

language = "English",

isbn = "354063357X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "363--372",

editor = "Tao Jiang and D.T. Lee",

booktitle = "Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings",

}

Zhang, Y, Xiao, J & Zhou, X 1997, A declustering algorithm for minimising spatial join cost. in T Jiang & DT Lee (eds), Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1276, Springer Verlag, pp. 363-372, 3rd Annual International Computing and Combinatorics Conference, COCOON 1997, Shanghai, China, 20/08/97. https://doi.org/10.1007/bfb0045103

A declustering algorithm for minimising spatial join cost. / Zhang, Yanchun; Xiao, Jitian; Zhou, Xiaofang.
Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings. ed. / Tao Jiang; D.T. Lee. Springer Verlag, 1997. p. 363-372 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1276).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - A declustering algorithm for minimising spatial join cost

AU - Zhang, Yanchun

AU - Xiao, Jitian

AU - Zhou, Xiaofang

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

N2 - Spatial joins are important, yet time-consuming operations in spatial databases. In this paper we consider to minimise the I/O cost for the spatial join processing. A graph model is proposed to formalise the cost, and an algorithm originally proposed for distributed database design is adapted for spatial object declustering. We improve the algorithm by giving special consideration to the clusters with overlapped objects. Our algorithm can not only reduce the number of objects fetched from disk for refinement processing, but also be computationally more efficient than the previous algorithms.

AB - Spatial joins are important, yet time-consuming operations in spatial databases. In this paper we consider to minimise the I/O cost for the spatial join processing. A graph model is proposed to formalise the cost, and an algorithm originally proposed for distributed database design is adapted for spatial object declustering. We improve the algorithm by giving special consideration to the clusters with overlapped objects. Our algorithm can not only reduce the number of objects fetched from disk for refinement processing, but also be computationally more efficient than the previous algorithms.

UR - https://openalex.org/W1604117325

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

U2 - 10.1007/bfb0045103

DO - 10.1007/bfb0045103

M3 - Conference Paper published in a book

SN - 354063357X

SN - 9783540633570

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 363

EP - 372

BT - Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings

A2 - Jiang, Tao

A2 - Lee, D.T.

PB - Springer Verlag

T2 - 3rd Annual International Computing and Combinatorics Conference, COCOON 1997

Y2 - 20 August 1997 through 22 August 1997

ER -

Zhang Y, Xiao J, Zhou X. A declustering algorithm for minimising spatial join cost. In Jiang T, Lee DT, editors, Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings. Springer Verlag. 1997. p. 363-372. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0045103

A declustering algorithm for minimising spatial join cost

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this