Partial match retrieval in implicit data structures. (English) Zbl 0549.68033
We consider partial match retrieval in implicit data structures. Consider a set of n records of k attributes each. This set is to be stored in an n by k array such that partial match retrieval can be done efficiently. A partial match query specifies a subset of the attributes, say s attributes, and asks for all tuples in the set agreeing with the query in the set of specified attributes. The complexity of this problem is studied in the paper and matching upper and lower bounds are shown. The model of computation is the comparison model.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68P20 | Information storage and retrieval of data |
| 68P05 | Data structures |
Keywords:
data management; analysis of algorithms; combinatorial problems; optimal algorithms; partial match retrieval; implicit data structures; partial match query; complexity; lower bounds; comparison modelReferences:
| [1] | Alt, H.; Mehlhorn, K., Searching semisorted tables, (Rept. CS-82-82 (1982), Computer Science Dept., Pennsylvania State Univ) · Zbl 0578.68049 |
| [2] | Alt, H.; Mehlhorn, K.; Munro, J. I., Partial match retrieval in implicit data structures, (Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 118 (1981), Springer: Springer Berlin), 156-161 · Zbl 0465.68033 |
| [3] | Bentley, J. L., Multidimensional binary search trees used for associative searching, Comm. ACM, 18, 9, 509-516 (1975) · Zbl 0306.68061 |
| [4] | Frederickson, G. N., Implicit data structures with fast update, IEEE FOCS, 255-259 (1980) |
| [5] | Frederickson, G. N., Implicit data structures for the dictionary problem, J. ACM, 30, 1, 80-94 (1983) · Zbl 0497.68032 |
| [6] | Ghosh, S. P.; Abraham, C. T., Application of finite geometry in file organization for records with multiple-valued attributes, IBM J. Res. Develop., 12, 180-187 (1968) · Zbl 0177.44401 |
| [7] | Munro, J. I., A multikey search problem, Proc. 17th Ann. Allerton Conf. (1979) |
| [8] | Munto, J. I.; Suwanda, H., Implicit data structures, J. Comput. System Sci., 21, 236-250 (1980) · Zbl 0446.68045 |
| [9] | Rivest, R. L., Partial match retrieval algorithms, SIAM J. Comput., 5, 1, 19-50 (1976) · Zbl 0331.68064 |
| [10] | Yao, A. C., Should tables be sorted?, J. ACM, 28, 3, 615-628 (1981) · Zbl 0462.68079 |
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.
