A data structure for lattice representation. (English) Zbl 0896.06006
Summary: In this paper, we present an implicit data structure for the representation of a partial lattice \({\mathcal L}=(\prec,{\mathcal N})\), which allows to test the partial order relation among two given elements in constant time. The data structure proposed has an overall \(O(n\sqrt{n})\)-space complexity, where \(n\) is the size of ground set \({\mathcal N}\), which we will prove to be optimal in the worst case. Hence, we derive an overall \(O(n\sqrt{n})\)-space* time bound for the relation testing problem thus beating the \(O(n^{2})\) bottle-neck representing the present complexity. The overall pre-processing time is \(O(n^{2})\).
References:
| [1] | Agrawal, R., Alpha: An extension of relational algebra to express a class of recursive queries, (IEEE 3rd Internat. Conf. Data Eng. (1987)) |
| [2] | Agrawal, R.; Borgida, A.; Jagadish, H. V., Efficient management of transitive relationship in large data and knowledge bases, (ACM SIGMOD (1989)) |
| [3] | Ait-Kaci, H.; Boyer, R.; Lincoln, P.; Nasr, R., Efficient implementation of lattice operations, ACM Trans. Prog. Lang. Systems, 11, 115-146 (1989) |
| [4] | Alt, H.; Mehlhorn, K.; Munro, J. J., Partial match retrieval in implicit data structures, Inform. Process. Lett., 19, 61-66 (1984) · Zbl 0549.68033 |
| [5] | Birkhoff, G.; Frink, O., Representation of lattices by sets, Trans. AMS, 64, 299-316 (1948) · Zbl 0032.00504 |
| [6] | Biskup, J.; Stiefeling, H., Evaluation of upper bounds and least nodes as database operations, Technical Report, ESPRIT-project 311 — Advanced Data and Knowledge Management System (1992) |
| [7] | Borodin, A.; Fich, F. E.; auf der Heide, F. Meyer; Upfal, E.; Wigderson, A., A trade-off between search and update time for the implicit dictionary problem, Theoret. Comput. Sci., 58, 57-68 (1988) · Zbl 0654.68078 |
| [8] | Dushnik, B.; Miller, E., Partially ordered sets, Amer. J. Math., 63, 600-610 (1941) · JFM 67.0157.01 |
| [9] | Franciosa, P. G.; Talamo, M., Orders, implicit \(k\)-sets representation and fast halfplane searching, (Bouchitté, V.; Morvan, M., Orders, Algorithms, and Applications, Internat. Workshop ORDAL ’94. Orders, Algorithms, and Applications, Internat. Workshop ORDAL ’94, Lecture Notes in Computer Science, Vol. 831 (1994), Springer: Springer Berlin), 117-127 · Zbl 0953.68608 |
| [10] | Gambosi, G.; Protasi, M.; Talamo, M., An efficient implicit data structure for relation testing and searching in partially ordered sets, BIT, Vol. 32, 2-16 (1992) |
| [11] | Jagadish, H. V., Incorporating hierarchy in a realation model of data, (ACM-SIGMOD 1989 Internat. Conf. Management of Data. ACM-SIGMOD 1989 Internat. Conf. Management of Data, Portland, Oregon (1989)) · Zbl 1336.68058 |
| [12] | Kameda, T., On the vector representation of the reachability in planar directed acyclic graphs, Inform. Process. Lett., 3, 75-77 (1975) · Zbl 0302.05106 |
| [13] | Kleitman, D. J.; Winston, K. J., The asymptotic number of lattices, Ann. Discrete Math., 6, 243-249 (1980) · Zbl 0446.06005 |
| [14] | Markowsky, G., The representation of posets and lattices by sets, Algebra Universalis, 11, 173-192 (1980) · Zbl 0449.06007 |
| [15] | Preparata, F. P.; Shamos, M. I., Computational Geometry (1985), Springer: Springer Berlin · Zbl 0759.68037 |
| [16] | Preparata, F. P.; Tamassia, R., Fully dynamic point location in a monotone subdivision, SIAM J. Comput., 18, 811-830 (1989) · Zbl 0682.68056 |
| [17] | Rival, I., Graphical data structures for ordered sets, (Rival, I., Algorithms and Orders (1989), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht) · Zbl 1261.68047 |
| [18] | M. Talamo and P. Vocca, A time optimal \(Onn\)SIAM J. Comput.; M. Talamo and P. Vocca, A time optimal \(Onn\)SIAM J. Comput. · Zbl 0896.06006 |
| [19] | Tamassia, R.; Tollis, J. G., Reachability in planar digraphs with one source and one sink, Theoret. Comput. Sci., 119 (1993) · Zbl 0830.68105 |
| [20] | Trotter, W. T.; Moore, J. I., The dimension of planar posets, J. Combin. Theory, 22, 54-57 (1977) · Zbl 0307.06003 |
| [21] | Yannakakis, M., Graph theoretic methods in database theory, (ACM STOC (1990)) |
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.
