Deferred Data Structuring
Richard M. Karp, Rajeev Motwani and Prabhakar Raghavan
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-320
1986
http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-320.pdf
We consider the problem of answering a series of on-line queries on a static data set. The conventional approach to such problems involves a preprocessing phase which constructs a data structure with good search behavior. The data structure representing the data set then remains fixed throughout the processing of the queries. Our approach involves dynamic or query-driven structuring of the data set; our algorithm processes the data set only when doing so is required for answering a query. A data structure constructed progressively in this fashion is called a deferred data structure.
We develop the notion of deferred data structures by solving the problem of answering membership queries on an ordered set. We obtain a randomized algorithm which achieves asymptotically optimal performance with high probability. We then present optimal deferred data structures for the following problems in the plane: testing convex hull membership, half-plane intersection queries and fixed-constraint multi-objective linear programming. We also apply the deferred data structuring technique to multidimensional dominance query problems.
BibTeX citation:
@techreport{Karp:CSD-87-320,
Author = {Karp, Richard M. and Motwani, Rajeev and Raghavan, Prabhakar},
Title = {Deferred Data Structuring},
Institution = {EECS Department, University of California, Berkeley},
Year = {1986},
Month = {Dec},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1986/5988.html},
Number = {UCB/CSD-87-320}
}
EndNote citation:
%0 Report %A Karp, Richard M. %A Motwani, Rajeev %A Raghavan, Prabhakar %T Deferred Data Structuring %I EECS Department, University of California, Berkeley %D 1986 %@ UCB/CSD-87-320 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1986/5988.html %F Karp:CSD-87-320