Thumbnail
Access Restriction
Subscribed

Author Willard, Dan E. ♦ Lueker, George S.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1985
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A database is said to allow range restrictions if one may request that only records with some specified field in a specified range be considered when answering a given query. A transformation is presented that enables range restrictions to be added to an arbitrary dynamic data structure on $\textit{n}$ elements, provided that the problem satisfies a certain decomposability condition and that one is willing to allow increases by a factor of $\textit{O}(log$ $\textit{n})$ in the worst-case time for an operation and in the space used. This is a generalization of a known transformation that works for static structures. This transformation is then used to produce a data structure for range queries in $\textit{k}$ dimensions with worst-case times of $\textit{O}(log\textit{k$ n) for each insertion, deletion, or query operation.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1985-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 32
Issue Number 3
Page Count 21
Starting Page 597
Ending Page 617


Open content in new tab

   Open content in new tab
Source: ACM Digital Library