Functional approach to data structures and its use in multidimensional searching

Research output: Contribution to journalArticlepeer-review

261 Scopus citations

Abstract

We establish new upper bounds on the complexity of multidimensional searching. Our results include, in particular, linear-size data structures for range and rectangle counting in two dimensions with logarithmic query time. More generally, we give improved data structures for rectangle problems in any dimension, in a static as well as dynamic setting. Several of the algorithms we give are simple to implement and might be the solutions of choice in practice. Central to this paper is the nonstandard approach followed to achieve these results. At its root we find a redefinition of data structures in terms of functional specifications.

Original languageEnglish (US)
Pages (from-to)427-462
Number of pages36
JournalSIAM Journal on Computing
Volume17
Issue number3
DOIs
StatePublished - 1988

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Functional approach to data structures and its use in multidimensional searching'. Together they form a unique fingerprint.

Cite this