STR

STR: a simple and efficient algorithm for R-tree packing. Presents the results from an extensive comparison study of three R-tree packing algorithms: the Hilbert and nearest-X packing algorithms, and an algorithm which is very simple to implement, called the STR (Sort-Tile-Recursive) algorithm. The algorithms are evaluated using both synthetic and actual data from various application domains including VLSI design, GIS (Tiger files), and computational fluid dynamics. Our studies also consider the impact that various degrees of buffering have on query performance. Experimental results indicate that none of the algorithms as best for all types of data. In general, our new algorithm requires up to 50% fewer disk accesses than the best previously proposed algorithm for point and region queries on uniformly distributed or mildly skewed point and region data, and approximately the same for highly skewed point and region data.


References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Lebrun-GrandiƩ, D.; Prokopenko, A.; Turcksin, B.; Slattery, S. R.: ArborX. A performance portable geometric search library (2021)
  2. Jung, HaRim; Chung, Yon Dohn; Liu, Ling: Processing generalized (k)-nearest neighbor queries on a wireless broadcast stream (2012) ioport
  3. Song, MoonBae; Choo, Hyunseung; Kim, Won: Spatial indexing for massively update intensive applications (2012) ioport
  4. Ghinita, Gabriel; Zhao, Keliang; Papadias, Dimitris; Kalnis, Panos: A reciprocal framework for spatial (K)-anonymity (2010) ioport
  5. Yiu, Man Lung; Mamoulis, Nikos: Multi-dimensional top-(k) dominating queries (2009) ioport
  6. Zheng, Baihua; Lee, Wang-Chien; Lee, Ken C. K.; Lee, Dik Lun; Shao, Min: A distributed spatial index for error-prone wireless data broadcast (2009) ioport
  7. Jermaine, Christopher; Omiecinski, Edward; Yee, Wai Gen: The partitioned exponential file for database storage management (2007) ioport
  8. Hadjieleftheriou, Marios; Kollios, George; Tsotras, Vassilis J.; Gunopulos, Dimitrios: Indexing spatiotemporal archives (2006) ioport
  9. Zheng, Baihua; Xu, Jianliang; Lee, Wang-Chien; Lee, Dik Lun: Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services (2006) ioport
  10. Shim, Jeong Min; Song, Seok Il; Yoo, Jae Soo; Min, Young Soo: An efficient cache conscious multi-dimensional index structure (2004)
  11. Kim, Sang-Wook: On batch-constructing B(^+)-trees: Algorithm and its performance evaluation (2002)