M. Schlag, Y.Z. Liao, et al.
Integration, the VLSI Journal
In this paper we present a fide structure designed for a database system in which four types of retrieval requests (queries) are allowed: exact match, partial match, range, and partial range queries. For a file of N records, each of k keys, the worst-case running times of our search algorithms are bounded above, respectively, by O(k + log N), O(t + 3k-(s + log N)), O(t + (log N)k), and O(t + 3k-s(log N)) where s is the number of keys specified in a partial match (or range) query and t is the number of records retrieved by the query. The fde structure can be built in O(N(log N)k/(k - l)!) time and requires similar storage; by a slight modification, both of these requirements can be reduced to O(N(log N)k-/(k - l)!). We also sketch outlines for inserting and deleting records that require O(k + (log N)k) time, on the average. This structure achieves faster response time than previously known structures (for many of the queries) at the cost of extra storage. © 1980, ACM. All rights reserved.
M. Schlag, Y.Z. Liao, et al.
Integration, the VLSI Journal
Inder S. Gopal, Don Coppersmith, et al.
IEEE TC
C.C. Lee, D.T. Lee, et al.
Acta Informatica
Charles Chiang, Majid Sarrafzadeh, et al.
IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications