Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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