# Partial Range Query on Inverted File with Combined Index

I am currently reading Multidimensional and Metric Data Structures by Hanan Samet for fun. The combined index is discussed on page 5-6. I do understand it in the sense that the inverted file itself is an index, and then we extrapolate another index by lexicographically ordering the attribute.

So, given a record with four attributes (Name, X, Y, Z), that is, the name and three dimensional point in space. If I created the inverted file such that it maps Name to the X,Y,Z attributes, then we can create another index by lexicographically ordering the attributes X,Y,Z. The possible orders would be XYZ, YXZ ZYX.

Do we order by the values of XYZ in the inverted file at all? Does the index of lexicographically ordered XYZ attributes point to the inverted index, which thus makes it combined?

Any help is greatly appreciated!

• What don't you understand? The top of page 6 of that book seems to explain it quite clearly. As the book explains, there is not a single way of forming a combined index; there are multiple ways of doing it. So which way are you asking about, and what is the question, exactly? Right now the only useful answer I can give you is "it depends on which method you are using". – D.W. Jun 14 '14 at 1:37
• @D.W. Specifically when the data structure we are using is an inverted list. – Gary D. Jun 14 '14 at 1:54
• You're going to need to be more specific. For instance, if you want to know about an inverted list, why do you mention combined indices in the question? (By the way, you're asking about an inverted list, then the ordering on the attributes is irrelevant.) if you're asking about an inverted list, which inverted list? There are multiple. And what exactly don't you understand? Did you work through the example in Figures 1.1 and Figures 1.2 in the book? What didn't you understand? I recommend you edit your question to make it clearer where you are lost. – D.W. Jun 14 '14 at 1:56

I don't think you've got the idea for an inverted file quite right. If there are three attributes (X, Y, and Z), the natural approach is to have three inverted lists:

• The first list maps from the value of X to the record (or from the value of X to the Name, if the Name is unique for each record and is how the record is identified).

• The second list maps from the value of Y to the record (or from the value of Y to the Name, if the Name is unique for each record).

• The third list maps from the value of Z to the record (or from the value of Z to the Name, if the Name is unique for each record).

So, if there are three attributes, we might end up with three inverted files.

See Figure 1.2 in the book for an example of an inverted file.

Now for the idea of a combined index. A combined index for the attribute ordering XYZ would be a sorted list of records, where the sort order works as follows:

• If two records differ in their X attribute, then order them by the value of their X attribute (and ignore their Y,Z attributes).

• If two records have the same X attribute but differ in their Y attribute, then order them by the value of their Y attribute (ignoring their Z attribute).

• If two records have the same X and Y attributes but differ in their Z attribute, then order them by the value of their Z attribute.

This is known as lexicographic order, where the attributes are taken in the order X,Y,Z. You can think of this as XYZ-lexicographic order. Once we sort using this particular order, we get a combined index for the attribute ordering XYZ.

Of course we could also form a combined index for other attribute orderings as well. We might form multiple combined indices, each with a different attribute ordering. The order in each combined index is different. If there are $n$ attributes, we could have up to $n!$ different combined indices, corresponding to the $n!$ different permutations (orderings) on the $n$ attributes. Nothing says we have to store all of those possible combined indices; we could store just one of them, or some of them, or all of them, or none of them.

A combined index is different from an inverted file.

However, you might notice that if you have a combined index for attribute order XYZ, then this obviates the need for an inverted file for attribute X, since you can use the combined index for XYZ in any place where you would have wanted an inverted file for X.

This is all explained pretty clearly in the book you cited. I recommend you work through the example in Figures 1.1 and 1.2 in the book, to better understand inverted lists.

• First off, I'd like to thank you for taking the time to researching and answering my question. You have explained it, and cleared up the confusion that I had with the combined index. I wasn't sure if it was a lexicographical ordering on the record values via the attribute or the name attribute that is in the inverted file itself. For example, in figure 1.2 for the inverted file on the x attribute there is {Denver, Omaha, Chicago, ...} the combined index with lexicographic sort {Chicago, Denver, Omaha, ...}. – Gary D. Jun 14 '14 at 2:40