# 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