There\'s a class of data structures where you preprocess some other data structu

Question

There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently.

That includes trivial things like sorting/hashing, less trivial things like quad trees, and includes far less trivial things such as dominator trees, interval decompositions of DAGs or distributed data structures using labelings.

I was wondering what is a common term for such data structures, and if there isn't, how to describe them best. "index-like" comes to mind, but there aren't yet any tags with the word "index" here so it does not seem to be common.

Explanation / Answer

These are sometimes called (static) online data structures or online query data structures. It's actually rather hard to find a definition written down and the notion is "soft", in the sense that you can reasonably argue that almost anything would qualify especially if you allow updating. Here's one definition and mini-taxonomy:

Online data structures support query operations in a continous manner. When the data items do not change and the data strucuture can be preprocessed before any queries are made, the data structure is known as static. When the data structure supports insertions and deletions of items, intermixed with the queries, the data structure is called dynamic.

The term online algorithm is used with a related meaning. It seems to be more widespread (as a term) than its counterpart for data structures. Since the query is the stuff/input that's online in your case, "data structure for online query" is more explicit; searching this as an entire phrase doesn't find much, but as nearby terms you'll get relevant hits e.g. from books [1] [2] [3] [4] etc. Likewise one can speak of "data structure" for "online updating".

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.