Term for index-like data structures

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.

• Raphael: I am not aware of a special term; just "data-structure"? Arguably, even search trees fit the criterion.
• jkff: Yes, search trees fit the criterion. However, not all data structures do - e.g. I'd say that heaps don't, because they answer only a single query - "what's the minimum". I'm interested in data structures that are designed for the use case "build data structure (which may be expensive), then do tons of queries of a certain type".
• Raphael: I'd say heaps qualify; you build them, do tons of queries and, boom, you have your data sorted! So, what are you really after? Queries that don't change the data structure? If that's the only distinguishing feature I'm not sure it's that interesting.
• Pseudonym: To me, the word "index" describes a data structure which helps you find entries in another data structure (which could be as simple as a string or something). If the original data structure is not necessary given the index (Burrows-Wheeler transform would be one example), the term "self-index" or "self-indexing data structure" is typical. But yes, I don't think there's a special term for data structures whose only purpose is to execute a specific query.

Answer 1

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".

Answer 2

"Query-oriented" might be a reasonable modifier for data structures optimized for queries. (Using "query-optimized" may be unclear whether the data structure is optimized by the query — the most likely impression — or for the query.)

For a data structure that is optimized for queries without especially penalizing other uses, "query-aware" might be used.

(Obviously "-oriented" and "-aware" could be applied to any operation, e.g., "insert-oriented" and "insert-aware".)

Neither term seems to be firmly established (though Google Scholar provides several uses of "query-oriented" and "query-aware") and there does not appear to be any prior nomenclature. However, even if prior obscure nomenclature existed, the use of such easily understood, descriptive naming would generally be acceptable or even desirable. At worst it replaces a less familiar established name with a more wordy but accessible term.