A strip-splitting-based optimal algorithm for decomposing a query window into maximal quadtree blocks

Author

Tsai, Yao-Hong ; Chung, Kuo-Liang ; Chen, Wan-Yu

Author_Institution

Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ. of Sci. & Technol., Taipei, Taiwan

Volume

16

Issue

4

fYear

2004

fDate

4/1/2004 12:00:00 AM

Firstpage

519

Lastpage

523

Abstract

Decomposing a query window into maximal quadtree blocks is a fundamental problem in quadtree-based spatial database. Recently, Proietti presented the first optimal algorithm for solving this problem. Given a query window of size n₁×n₂, Proietti´s algorithm takes O(n₁) time, where n₁=max(n₁, n₂). Based on a strip-splitting approach, we present a new optimal algorithm for solving the same problem. Experimental results reveal that our proposed algorithm is quite competitive with Proietti´s algorithm.

Keywords

computational complexity; optimisation; quadtrees; query processing; visual databases; Proietti algorithm; maximal quadtree blocks; quadtree-based spatial database; query window decomposition; strip-splitting-based optimal algorithm; Algorithm design and analysis; Computer graphics; Geographic Information Systems; Image databases; Image processing; Performance evaluation; Robots; Senior members; Spatial databases; Testing;

fLanguage

English

Journal_Title

Knowledge and Data Engineering, IEEE Transactions on

Publisher

ieee

ISSN

1041-4347

Type

jour

DOI

10.1109/TKDE.2004.1269662

Filename

1269662