Approximate colored range and point enclosure queries. (English) Zbl 1160.68352
Summary: We formulate two classes of problems, the colored range query problems and the colored point enclosure query problems to model multi-dimensional range and point enclosure queries in the presence of categorical information. Many of these problems are difficult to solve using traditional data structural techniques. Based on a new framework of combining sketching techniques and traditional data structures, we obtain two sets of results in solving the problems approximately and efficiently. In addition, the framework can be employed to attack other related problems by finding the appropriate summary structures.
Keywords:
colored range queries; colored point enclosure queries; sketches; approximate data structuresReferences:
| [1] | P.K. Agarwal, S. Govindarajan, S. Muthukrishnan, Range searching in categorical data: colored range searching on grid, in: 10th European Symposium on Algorithms, 2002, pp. 17-28; P.K. Agarwal, S. Govindarajan, S. Muthukrishnan, Range searching in categorical data: colored range searching on grid, in: 10th European Symposium on Algorithms, 2002, pp. 17-28 · Zbl 1019.68529 |
| [2] | Bayer, R., Symmetric binary B-trees: Data structures and maintenance algorithms, Acta Inform., 1, 290-306 (1972) · Zbl 0233.68009 |
| [3] | N. Beckmann, H.P. Kriegel, R. Schnieder, B. Seeger, The R*-tree: An efficient and robust access method for points and rectangles, in: ACM SIGMOD Conference on the Management of Data, 1990, pp. 322-331; N. Beckmann, H.P. Kriegel, R. Schnieder, B. Seeger, The R*-tree: An efficient and robust access method for points and rectangles, in: ACM SIGMOD Conference on the Management of Data, 1990, pp. 322-331 |
| [4] | J.L. Bentley, Algorithms for Klee’s rectangle problems, Department of Computer Science, Carnegie Mellon Univ., unpublished notes, 1977; J.L. Bentley, Algorithms for Klee’s rectangle problems, Department of Computer Science, Carnegie Mellon Univ., unpublished notes, 1977 |
| [5] | Bentley, J. L., Multidimensional divide-and-conquer, Comm. ACM, 23, 4, 214-228 (1980) · Zbl 0434.68049 |
| [6] | Berg, M.; Haverkort, H. J., Significant-presence range queries in categorical data, (Workshop on Algorithms and Data Structures. Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 2748 (2003), Springer), 462-473 · Zbl 1278.68324 |
| [7] | Carter, J. L.; Wegman, M. N., Universal classes of hash functions, J. Comput. Syst. Sci., 18, 143-154 (1979) · Zbl 0412.68090 |
| [8] | Chazelle, B., A functional approach to data structures and its use in multidimensional searching, SIAM J. Comput., 17, 3, 427-462 (1988) · Zbl 0679.68074 |
| [9] | G. Cormode, M. Datar, P. Indyk, S. Muthukrishnan, Comparing data streams using Hamming norms (how to zero in), in: Proceedings of the 28th International Conference on Very Large Data Bases, 2002, pp. 335-345; G. Cormode, M. Datar, P. Indyk, S. Muthukrishnan, Comparing data streams using Hamming norms (how to zero in), in: Proceedings of the 28th International Conference on Very Large Data Bases, 2002, pp. 335-345 |
| [10] | Cormode, G.; Muthukrishnan, S., An improved data stream summary: the count-min sketch and its applications, (The 6th Latin American Theoretical Informatics (LATIN). The 6th Latin American Theoretical Informatics (LATIN), Lecture Notes in Computer Science, vol. 2976 (2004), Springer), 29-38 · Zbl 1196.68057 |
| [11] | Edelsbrunner, H., A new approach to rectangle intersections, part i, Int. J. Comput. Math., 13, 209-219 (1983) · Zbl 0513.68058 |
| [12] | Edelsbrunner, H., A new approach to rectangle intersections, part ii, Int. J. Comput. Math., 13, 209-219 (1983) · Zbl 0513.68058 |
| [13] | P. Ferragina, N. Koudas, D. Srivastava, S. Muthukrishnan, Two-dimensional substring indexing, in: Proceedings of the 20th Annual ACM Symposium on Principles of Database Systems, 2001, pp. 282-288; P. Ferragina, N. Koudas, D. Srivastava, S. Muthukrishnan, Two-dimensional substring indexing, in: Proceedings of the 20th Annual ACM Symposium on Principles of Database Systems, 2001, pp. 282-288 · Zbl 1054.68043 |
| [14] | Guibas, L. J.; Sedgewick, R., A dichromatic framework for balanced trees, (19th Annual Symposium on Foundations of Computer Science (1978), IEEE), 8-21 |
| [15] | Gupta, P.; Janardan, R.; Smid, M., Further results on generalized intersection searching problems: Counting, reporting, and dynamization, J. Algorithms, 19, 282-317 (1995) · Zbl 0839.68106 |
| [16] | A. Guttman, R-trees: A dynamic index structure for spatial searching, in: ACM SIGMOD Conference on the Management of Data, 1984, pp. 47-57; A. Guttman, R-trees: A dynamic index structure for spatial searching, in: ACM SIGMOD Conference on the Management of Data, 1984, pp. 47-57 |
| [17] | Janardan, R.; Lopez, M., Generalized intersection searching problems, Internat. J. Comput. Geom. Appl., 3, 1, 39-69 (1993) · Zbl 0777.68078 |
| [18] | Lai, Y. K.; Poon, C. K.; Shi, B. Y., Approximate colored range queries, (16th Symposium on Algorithms and Computation (ISAAC’05). 16th Symposium on Algorithms and Computation (ISAAC’05), Sanya, China. 16th Symposium on Algorithms and Computation (ISAAC’05). 16th Symposium on Algorithms and Computation (ISAAC’05), Sanya, China, Lecture Notes in Computer Science, vol. 3827 (2005), Springer), 360-369 · Zbl 1173.68467 |
| [19] | S. Muthukrishnan, Efficient algorithms for document retrieval problems, in: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 657-666; S. Muthukrishnan, Efficient algorithms for document retrieval problems, in: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 657-666 · Zbl 1093.68588 |
| [20] | Nanopoulos, A.; Bozanis, P., Categorical range queries in large databases, (Proc. 8th Int. Symp. Spatial and Temporal Databases (SSTD 2003). Proc. 8th Int. Symp. Spatial and Temporal Databases (SSTD 2003), Lecture Notes in Computer Science, vol. 2750 (2003), Springer), 122-139 |
| [21] | Sellis, T.; Roussopoulos, N.; Faloutsos, C., The R+-tree: A dynamic index for multi-dimensional objects, (Proceedings of the 13th International Conference on Very Large Data Bases (1987), Morgan-Kaufmann), 507-518 |
| [22] | Willard, D. E., New data structures for orthogonal queries, SIAM J. Comput., 14, 1, 232-253 (1985) · Zbl 0564.68071 |
| [23] | Willard, D. E.; Lueker, G. S., Adding range restriction capability to dynamic data structures, J. ACM, 32, 3, 597-617 (1985) · Zbl 0629.68097 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
