Richard M. Karp and Rajeev Motwani and Prabhakar Raghavan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-87-320

, 1987

http://www2.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. <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.

---

BibTeX citation:

@techreport{Karp:CSD-87-320,
    Author= {Karp, Richard M. and Motwani, Rajeev and Raghavan, Prabhakar},
    Title= {Deferred Data Structuring},
    Year= {1987},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/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 1987
%@ UCB/CSD-87-320
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5988.html
%F Karp:CSD-87-320