Partial match retrieval in implicit data structures (Q800083)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Partial match retrieval in implicit data structures |
scientific article; zbMATH DE number 3876587
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Partial match retrieval in implicit data structures |
scientific article; zbMATH DE number 3876587 |
Statements
Partial match retrieval in implicit data structures (English)
0 references
1984
0 references
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.
0 references
data management
0 references
analysis of algorithms
0 references
combinatorial problems
0 references
optimal algorithms
0 references
partial match retrieval
0 references
implicit data structures
0 references
partial match query
0 references
complexity
0 references
lower bounds
0 references
comparison model
0 references
0 references
0.7585964202880859
0 references
0.7528184652328491
0 references
0.7380152344703674
0 references
0.7355924248695374
0 references
