Abstract
In Geographic Information Systems (GIS) the attributes of the space (altitude, temperature, etc.) are usually represented using a raster model. There are no compact representations of raster data that provide efficient query capabilities. In this paper we propose compact representations to efficiently store and query raster datasets in main memory. We experimentally compare our proposals with traditional storage mechanisms for raster data, showing that our structures obtain competitive space performance while efficiently answering range queries involving the values stored in the raster.
GdB, NB, SAG and OP were funded by MICINN (PGE and FEDER) grants TIN2009-14560-C03-02, TIN2010-21246-C02-01 and CDTI CEN-20091048, and by Xunta de Galicia (co-funded with FEDER) ref. 2010/17. GN was founded by Millennium Nucleus Information and Coordination in Networks ICM/FIC P10-024F.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-319-02432-5_33
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barbay, J., Gagie, T., Navarro, G., Nekrich, Y.: Alphabet partitioning for compressed rank/select and applications. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol. 6507, pp. 315–326. Springer, Heidelberg (2010)
Boldi, P., Vigna, S.: The Webgraph framework I: compression techniques. In: Proc. 13th WWW, pp. 595–602 (2004)
Brisaboa, N.R., de Bernardo, G., Navarro, G.: Compressed dynamic binary relations. In: Proc. 22nd DCC, pp. 52–61 (2012)
Brisaboa, N.R., Ladra, S., Navarro, G.: k2-Trees for compact web graph representation. In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 18–30. Springer, Heidelberg (2009)
Chan, T.M., Larsen, K.G., Pătraşcu, M.: Orthogonal range searching on the RAM, revisited. In: Proc. 27th SoCG, pp. 1–10 (2011)
Chang, H.K., Chang, J.W.: Fixed binary linear quadtree coding scheme for spatial data. In: Proc. 9th VCIP, vol. 2308, pp. 1214–1220 (1994)
Finkel, R.A., Bentley, J.L.: Quad trees: A data structure for retrieval on composite keys. Acta Informatica 4, 1–9 (1974)
Gargantini, I.: An effective way to represent quadtrees. Communications of the ACM 25(12), 905–910 (1982)
Golynski, A., Munro, J.I., Rao, S.S.: Rank/select operations on large alphabets: a tool for text indexing. In: Proc. 17th SODA, pp. 368–373 (2006)
Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. 14th SODA, pp. 841–850 (2003)
Lin, T.W.: Set operations on constant bit-length linear quadtrees. Pattern Recognition 30(7), 1239–1249 (1997)
Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol. 1180, pp. 37–42. Springer, Heidelberg (1996)
Navarro, G.: Wavelet trees for all. In: Kärkkäinen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol. 7354, pp. 2–26. Springer, Heidelberg (2012)
Rigaux, P., Scholl, M., Voisard, A.: Spatial databases - with applications to GIS. Elsevier (2002)
Welch, T.A.: A technique for high-performance data compression. Computer 17(6), 8–19 (1984)
Worboys, M., Duckham, M.: GIS: A Computing Perspective, 2nd edn. CRC Press, Inc. (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
de Bernardo, G., Álvarez-García, S., Brisaboa, N.R., Navarro, G., Pedreira, O. (2013). Compact Querieable Representations of Raster Data. In: Kurland, O., Lewenstein, M., Porat, E. (eds) String Processing and Information Retrieval. SPIRE 2013. Lecture Notes in Computer Science, vol 8214. Springer, Cham. https://doi.org/10.1007/978-3-319-02432-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-02432-5_14
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02431-8
Online ISBN: 978-3-319-02432-5
eBook Packages: Computer ScienceComputer Science (R0)