Abstract
In this paper, we formulate a class of colored range query problems to model the multi-dimensional range queries in the presence of categorical information. By applying appropriate sketching techniques on our framework, we obtained efficient data structures that provide approximate solutions to these problems. In addition, the framework can be employed to attack other related problems by finding the appropriate summary structures.
The work described in this paper was fully supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 1198/03E].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P.K., Govindarajan, S., Muthukrishnan, S.: Range searching in categorical data: colored range searching on grid. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 17–28. Springer, Heidelberg (2002)
Bayer, R.: Symmetric binary B-trees: data structures and maintenance algorithms. Acta Informatica 1, 290–306 (1972)
Bentley, J.L.: Multidimensional divide-and-conquer. Comm. ACM 23(4), 214–228 (1980)
Berg, M., Haverkort, H.J.: Significant-presence range queries in categorical data. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 462–473. Springer, Heidelberg (2003)
Carter, J.L., Wegman, M.N.: Universal classes of hash functions. J. Computer and System Sciences 18, 143–154 (1979)
Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Computing 17(3), 427–462 (1988)
Cormode, G., Datar, M., Indyk, P., Muthukrishnan, S.: Comparing data streams using Hamming norms (how to zero in). In: Proc. of 28th Int’l. Conf. on Very Large Data Bases, pp. 335–345 (2002)
Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 29–38. Springer, Heidelberg (2004)
Ferragina, P., Koudas, N., Srivastava, D., Muthukrishnan, S.: Two-dimensional substring indexing. In: Proc. 20th ACM Symp. on Principles of Database Systems, pp. 282–288 (2001)
Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: FOCS 1978, pp. 8–21 (1978)
Gupta, P., Janardan, R., Smid, M.: Further results on generalized intersection searching problems: counting, reporting, and dynamization. J. Algorithms 19, 282–317 (1995)
Janardan, R., Lopez, M.: Generalized intersection searching problems. Int’l. J. Computational Geometry and Applications 3(1), 39–69 (1993)
Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: SODA 2002, pp. 657–666 (2002)
Nanopoulos, A., Bozanis, P.: Categorical range queries in large databases. In: Hadzilacos, T., Manolopoulos, Y., Roddick, J., Theodoridis, Y. (eds.) SSTD 2003. LNCS, vol. 2750, pp. 122–139. Springer, Heidelberg (2003)
Willard, D.E.: New data structures for orthogonal queries. SIAM J. Computing 14(1), 232–253 (1985)
Willard, D.E., Lueker, G.S.: Adding range restriction capability to dynamic data structures. J. ACM 32(3), 597–617 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lai, Y.K., Poon, C.K., Shi, B. (2005). Approximate Colored Range Queries. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_37
Download citation
DOI: https://doi.org/10.1007/11602613_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)