Cost model for x-BR-tree in spatial databases

Marcin Gorawski, Marcin Bugdoł


The paper proposes the cost model for spatial databases based on x BR-tree index. The model evaluates the cost for spatial queries in database, meant as a number of node accesses or disc reads. In addition, experimental results are presented, which shows the accuracy of analytical estimation compared with actual results.


spatial database; x-BR-tree; cost estimation

Full Text:

PDF (Polski)


Gorawski M., Malczok R.: On Efficient Storing and Processing of Long Aggregate Lists. Proceedings of the 7th International Conference Data Warehousing and Knowledge Discovery (DaWak2005, LNCS 3589), Copenhagen. Denmark 2005

Vassilakopoulos M.. Manolopoulos Y.: Extemal Balanced Regular (x-BR) Trees: New Structure for Veiy Large Spatial Databases. Technical Report TR99-13.

Faloutsos C. Kamei I.:Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension, In Proceedings of the 13th ACM Symposium on Principles of Database Systems (PODS), 1994.

Theodoridis Y., Sellis T.: A model for the Prediction of R-tree Performance. Proc. Symp. Principles of Database Systems, 1996.

Yu S., Atluri V.,. Adam N. R.: Selective View Materialization in a Spatial Data Warehouse. DaWaK 2005: s. 157-167.

Dellis E., Seeger B., Vlachou A.: Nearest Neighbor Search on Vertically Partitioued High-Dimensional Data. DaWaK 2005: s. 243-253.