Deferred Data Structuring

Richard M. Karp, Rajeev Motwani and Prabhakar Raghavan

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-320
December 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},
    Abstract = {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.  <p>  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.}
}

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