text:
# DPG: A Cache-Efficient Accelerator for Sorting and for Join Operators

## 1 Introduction

Two important database operations are sorting and joins. These operations have three primary hardware-related costs: disk access, CPU operation and main memory access. The growth of main memory in current computers implies that main memory databases become more popular. For main memory databases, the bottleneck moves from disk to main memory and the cost for disk access is not an issue anymore.

Further, the growing CPU-memory gap implies that CPU costs represent an increasingly small portion of the total time. This has been borne out by several studies of DBMs . The impact of the CPU-memory gap was popularized by the paper of Wulf and McKee  on the memory wall.

The diminishing role of the CPU in the total running time is partially accounted for by increasing CPU speeds and greater on-chip functional parallelism. In part, it is also accounted for because most CPUs today implement non-blocking caches and hardware prefetch in order to overlap CPU execution with memory access . Hence, memory access becomes the bottleneck. Therefore, we follow the example of previous researchers  in concentrating on main memory as the bottleneck.

At the heart of this memory bottleneck lies the record retrieval problem: the problem of copying records from a source array into a destination array according to a new ordering. In a typical application, one will be given a source data file, a sequence of record ids (rids) for that data file, and a destination file. The task is to copy the source records into the destination file in the order specified by the sequence of rids. Fast record retrieval is the key to faster sorting and faster joins.

A standard approach for data retrieval accesses the records of the source data file directly according to the sequence of the rids. This implies random access to the main memory. This, for example, is what was done in AlphaSort  and SuperScalarSort , the current record holders for the Datamation sorting challenge . However, the cost of such random access has now become the dominant cost in main memory sorting, since the CPU-memory gap has widened still further since the original work on sorting. (In fact, AlphaSort and SuperScalarSort sort data on disk, but the size of the data file, 100 MB, is small enough that the disk access consists solely of reading the source data file from disk, and writing to a destination data file.)

Random access is harmful not just in disk resident databases, but also in main memory resident databases. Current DRAM technologies, such as DDR RAM and Rambus RAM (RDRAM), extract a large latency penalty for any non-sequential access to RAM. This is because the memory chips are divided into memory pages of several kilobytes, and there is a latency penalty for switching to a new memory page .

Random access to RAM also harms performance in a second manner. Random access incurs a heavy penalty when large cache blocks are used. On a cache miss, the entire cache block is loaded into memory. If the record size is small compared to the cache block size, then there is a large overhead to load the entire cache block. For example, for a cache miss on a Pentium 4 with DDR-266 RAM, approximately 60 ns are spent loading the cache block, and approximately 60 ns are spent waiting on the latency of DDR RAM. The trend is toward larger cache blocks. The 128 byte L2 cache blocks of the Pentium 4 are four times larger than those of the Pentium III. The IBM Power4 processor goes still further using 512 byte L3 cache blocks.

The solution to avoid these latency penalties in main memory is to access main memory sequentially. This is similar in spirit to the way in which traditional databases strongly prefer to access disk sequentially. In analogy with operation on disk, two-pass algorithms are a key for faster main memory performance.

The DPG-based sorting algorithms immediately yield faster sorting algorithms. Both AlphaSort and SuperScalarSort sort their data essentially in three phases: extraction of key-pointer pairs; sorting of the key-pointer pairs; and copying of the original records into the destination array according to the sorted key-pointer pairs. The last phase is essentially record retrieval.

A re-implementation of AlphaSort and SuperScalarSort on a IBM p690 Turbo shows that the record retrieval phase now dominates the running time. With the DPG record retrieval algorithm replacing the standard record retrieval algorithm, we immediately produce a faster sorting algorithm. In the re-implementation of SuperScalarSort, the versions with DPG as an accelerator are 27% faster.

A direct consequence of faster record retrieval is faster main memory sort-merge joins. For example, in implementing sort-merge join using SuperScalarSort, we find that the use of DPG sort instead of SuperScalarSort results in a 27% faster join algorithm.. The DPG record retrieval phase in isolation is 48% faster than traditional record retrieval algorithm.

Finally, we apply DPG algorithm in the context of foreign key joins. In a foreign key join the join key is the same as the foreign key. we assume that one relation has an secondary index on the join key. Foreign key joins have the advantage that one need only rearrange the records of one of the files. This is in distinction to sort-merge join and hash join, which both require to rearrange each of the two files into a new file with join key values in sorted order.

Foreign key joins require less record retrieval because it is possible to first extract join triples, ($`k`$, ridR, ridF), where $`R`$ and $`F`$ are the two relations and $`k`$ is the join key value. Assume that $`R`$ references a foreign key of $`F`$. To construct a join triple, do file scan of $`R`$, for each record of $`R`$, its key $`k`$ is extracted. The secondary B-tree index of the join key on $`F`$ is then used to derive the corresponding record id, ridF, with the key value $`k`$. The standard index lookup is very expensive, we propose a cache efficient B-tree batch lookup to generate the join triples.

Join triples reduce foreign key join to record pair retrieval. The join triples specify the record pairs, (ridR, ridF), to be retrieved. One can re-order the records of $`F`$ to match the ordering of ridR in the sequence of record pairs. Recall that, we do file scan for $`R`$, so ridRs in the join triples are in sorted order. Alternatively, one can sort the join triples according to ridF, and re-order the records of $`R`$ to match the ordering of ridF in the sorted rid pairs. In either situation, there are fewer record retrievals, and so foreign key join is faster than a general join.

The ideas of faster record retrieval can also be applied to the general case of record pair retrieval. Many algorithms for spatial join  and temporal join  produce record pairs. Unlike equijoin, there is no single search key, and so record retrieval is more difficult. The ideas of this paper are described in terms of foreign key join. However, it is even simpler to translate the ideas into record pair retrieval, since an initial join triple extraction is not required.

## 2 Distribute-Probe-Gather

The distribute-probe-gather algorithm (DPG) is a record retrieval algorithm. Given a data file of records and a sequence of record ids (rids) for the file, the goal is to copy the records into a destination file with the property that the ordering of records in the destination file corresponds to the ordering of the rids in the given sequence.

For example, let the source file, R, be the array of records with a secondary B+ tree index on the attribute A. We want to place the records of R in sorted order according to the values of A. The sequence of record ids, S\_rid, at leaf nodes of the B+ tree is a list of record ids in sorted order according to the value of A. Then, the destination file, D, below, will contain the corresponding records in sorted order according to the value of A.

> for each i, D\[i\] = R\[S\_rid\[i\]\]

In the case that the sequence of rids is a permutation of the rids for the data file, the sequence of rids acts as a permutation vector. The destination file is then a permutation of the records in the input file.

Note, however, that the DPG algorithm is not limited to permutations of data. In the case of join, one record from one relation may match more than one records from another relation. In such cases portion of the original records must be duplicated. The DPG algorithm also works for this case.

### 2.1 Algorithm

The input for the algorithm is: a list of rids, RID\_LIST, and a data file of records, INPUT. The DPG algorithm partitions the rids, RID\_LIST, into separate runs. It also partitions the data records, INPUT, into separate runs. The algorithm makes two passes over the record ids, RID\_LIST, and two passes over the records of the data file, INPUT.

The ideas are presented in the context of main memory databases. We assume that neither the sequence of rids, RID\_LIST, nor the data file, INPUT, fit in cache. The DPG algorithm applies equally well as an external data retrieval algorithm between disk and main memory.

The spirit of the DPG algorithm is: try to transform arbitrary memory access patterns into sequential memory access patterns; where arbitrary memory access patterns are unavoidable, we try to divide the data into small partitions that fit into the cache.

For a sequential access pattern, it is easy to maintain a buffer in cache. In the DPG algorithm we need to read many streams simultaneously, and maintain a buffer for each stream. Hence, we want to keep the buffer as small as possible while maintaining reasonable efficiency. We define a buffer in cache to consist of two cache blocks. When a cache block is full, it is written back to main memory and a new cache block is loaded from main memory into cache. On Pentium 4, this is done automatically by the hardware prefetch function unit if the access to main memory is sequential. On other architectures without the hardware prefetch function unit, the software instructions, $`cflush`$ and $`prefetchnta`$, are needed to maintain the buffers.

##### Constraints:

The data records and rids are split into runs of length $`L`$. The run length $`L`$ is chosen based on two constraints. First, the cache must be able to simultaneously hold both one run of data records of length $`L`$ and one single buffer for the corresponding run of rids. (This constraint applies in the second phase of DPG.) Second, the cache must simultaneously be able to hold a buffer for each run. (This constraint applies in the first phase and in the third phase of DPG.) These constraints are typical of the constraints for two-pass algorithms, such as external sorting.

If the data file has $`N`$ records, then the data file is partitioned into $`N/L`$ sets of consecutive records. Assuming an rid consists of a page id and offset on that page, the high order bits of the page number can be used to efficiently identify the particular partition to which the rid belongs. This assumes that the number of pages in a partition is a power of two, which can be satisfied by appropriate choice of $`L`$. For the sake of clarity, we assume the rids values are in the rage of $`0`$ and $`N`$.

##### Three Phases:

There are three phases in the DPG algorithm. The three phases are also illustrated by pseudo-code in Figure 1 and by the diagram of Figure 2.

1. Phase I. The first phase is the Distribute phase. One distributes the rids of RID\_LIST into appropriate RID runs according to the values of the rids. The first RID run contains the rid values in the range from $`0`$ to $`L`$, the second RID run contains the rid values in the range from $`L`$ to $`2L`$, and so on. Both the access to every RID run and the access to RID\_LIST are sequential. Therefore, one only needs to maintains a buffer in cache for each RID run and a single buffer in cache for RID\_LIST, At the end, we form $`N/L`$ RID runs and each RID run is a permutation vector. For example, the $`i`$-th RID run is a permutation vector in the range from $`(i1)L`$ and $`iL`$.
2. Phase II. The second phase is the Probe phase. In this phase, we allocate a second, temporary data file, INTERNAL, in main memory. The temporary data file has the same size as the original data file, INPUT, and is organized into the same number of runs as the original data file. One then proceeds through each of the runs of rids and each of the runs of INPUT. The rids from the $`i`$-th RID run are used to probe the $`i`$-th INPUT run and the corresponding records are copied into the $`i`$-th INTERNAL run.

At the end, the $`i`$-th INTERNAL run contains the same records as the $`i`$-th INPUT run, but the order of records in the INTERNAL run is organized according to the $`i`$-th RID run. Both the $`i`$-th RID run and the $`i`$-th INTERNAL run are accessed sequentially. The $`i`$th INPUT run is accessed randomly, but it can fit in cache. Hence, every time, one loads the $`i`$-th INPUT run entirely into cache and maintains two buffers in cache: one for the $`i`$th RID run and the other for the $`i`$-th INTERNAL run.
3. Phase III. The third phase is the Gather phase. This is an inverse of the Distribute phase and is similar to the merge phase of external sorting. In the Distribute phase, the rids are distributed into runs. As a result of the Probe phase, the records in a given INTERNAL run are now in the same order as the rids in the corresponding RID run created in Phase I. Hence, it suffices to gather (merge) the records from the INTERNAL runs in exactly the same order as the order of the rids in RID\_LIST. More precisely, if the $`i`$-th rid was distributed to the $`j`$-th RID run during the Distribute phase, then at the $`i`$-th step of the Gather phase, the next record from the $`j`$-th INTERNAL run is copied to the destination array. One maintains several buffers in cache: one single buffer for RID\_LIST, one single buffer for the destination array, and a buffer for each INTERNAL run.

### 2.2 Example

The DPG algorithm is presented more formally in pseudo-code in Figure 1. The input of the algorithm is an array, RID, of rids (record ids) and a data file, INPUT\_REC, of records. It is desired to retrieve the records from INPUT\_REC in the order corresponding to RID. The retrieved records are then written to OUTPUT\_REC.

The three phases of the DPG algorithm are illustrated by an example in Figure 2. The input in this example is the leaf nodes of a secondary B+-tree index. The input contains a sequence of key-rid pairs sorted according to the key values. The output is a sequence of records sorted according to the key values of the secondary index. The output will either be stored again on disk or else pipelined to the next stage. The ability of the DPG algorithm to take advantage of pipelining is an important feature for sorting and joins.

The letters a, b, c, … are used to indicate the sorted keys on the leaf nodes of the index. So (a, 5) indicates that the record with the rid value of 5 has a key value of a. The first two rows are for Phase I, the next three rows for Phase II, and the following three rows for Phase III. The horizontal rectangle of the first row represents a sequence of key-rid pairs sorted according to the key values. The second row represents the runs of rids into which the first row is partitioned. Similarly, the third row again represents the runs of rids, but now as part of Phase II. The fourth row is the partitioned runs of input records, and so on. There are 12 elements and 3 runs in the example and each run contains 4 elements.

During Phase I, one has a sequence of key-rid pairs sorted according to the key values and will distribute them into appropriate RID runs. The first RID run will contain rid values from 0 to 3, the second RID run will contain rid values from 4 to 7, and the third RID run will contain rid values from 8 to 11. Upon reading the sequence of pairs from the first row, one places the rids in their proper runs. For example, the rid 5 goes to the second RID run, the rid 7 goes to the second RID run, the rid 3 goes to the first RID run, the rid 8 goes to the third RID run, and so on. The third row in the figure presents the end of Phase I. In this phase, we do sequential read on a single stream and sequential writes on multiple streams.

During Phase II, one copies the original data file, INPUT, to a temporary data file, INTERNAL. The input to this phase is the third row. In the third row, each RID run has rid values that correspond to one contiguous range of the INPUT file, an INPUT run. For example, for the first RID run, we will load the first INPUT run into the cache. The first INPUT run consists of the first 4 contiguous records. The first rid in the first RID run is 3 and $`INPUT[3]`$ is in the cache, so one finds this record, INPUT, in cache and copies it to the buffer maintained in cache for the first INTERNAL run, and so on. At the end of Phase II, the records in the first INPUT run with key values in the sequence of i, l, f, c are reordered as records in the first INTERNAL run with key values in the sequence of c, f, i, l. The reordering is done according to a permutation specified by the first RID run, 3, 2, 0, 1.

During Phase III, we will use the original rid sequence in the list of key-rid pairs to gather (merge) records from all INTERNAL run. For example, upon reading 5, we go to the second INTERNAL run to gather the record; upon reading 7, we go to the second INTERNAL run to gather the record; upon reading 3, we go to the first INTERNAL run to gather the record; upon reading 8 we go to the third INTERNAL run to gather the record, and so on. For this phase, we maintain a buffer for the key-rid list, a buffer for OUTPUT in cache and a buffer for each INTERNAL run. All buffers are in cache.

### 2.3 Data Skew

Implicit in the description of the DPG algorithm is that the input sequence of rids is distributed uniformly among the set of all rids of the input data file. This is always the case when DPG is applied to retrieve records after sorting key-pointer pairs. In that situation, the key-pointer pairs act as a permutation vector to permute the records in the input data file.

If the input sequence of rids is not uniformly distributed, then some RID runs will be larger than other runs. As a consequence, in Phase II, when the partition of the temporary data file (the partition of RECORD\_RUN in Figure 1) may be larger than the size of the cache. If only a few of the partitions of the temporary data file are larger than cache then the overall running time is not greatly affected.

If there is a great deal of data skew and many of the temporary partitions RECORD\_RUN are larger than cache, then the $`N/L`$ partitions of the input sequence of rids must be chosen on some other basis than the high order bits of the page number. In such cases, one can invoke the data skew handling techniques of DeWitt et al. . Their solution, reformulated in our context, is to sample the rids from the rid sequence. The sampled set of rids is then sorted, and partitions of the rids are chosen so as to evenly partition the sampled set.

## 3 Sorting

As discussed in the introduction, DPG acts as an accelerator for many main memory sorting algorithms. Recall that main memory sorts typically proceed in three phases:

1. extraction of key-pointer;
2. sorting of the key-pointer pairs; and
3. copying of the original records into the destination array according to the sorted key-pointer pairs.

AlphaSort  and SuperScalarSort  are examples of this three-phase sorting paradigm. Both sorting algorithms can be considered as main memory sorting algorithms.

In principle, the sorting algorithms are single-pass disk-based sorting algorithms. Both sorting algorithms were introduced as an answer to the Datamation Sorting Challenge . The Datamation challenge dictates that one is given one million records of 100 bytes. Each record has a 10 byte key. The keys are uniformly distributed. At the time of the Datamation Challenge, external sorting algorithms were required. On today’s computers, the data file of 100 MB easily fits in main memory.

Hence, the only disk-related portion of the Datamation Challenge is to overlap disk I/O with CPU operation. Disk striping has the potential to provide very fast disk I/O. This occurs because the disks are accessed in parallel. In this situation, main memory data retrieval becomes the bottleneck.

The DPG algorithm pushes back this main memory bottleneck. By using DPG for data movement, the largest cost of main memory sorting is reduced. We have reimplemented the main memory portion of SuperScalarSort, both with and without DPG.

## 4 Join Methods with DPG

We use the ideas of DPG to present three new join algorithms: 1.c, 2 and 3. Algorithms 1.a, 1.b and 4, will be included in the experimental section 5.3 for completeness.

1. Sort-Merge Join

1. Sort-Merge Join with AlphaSort (sort based on )
    2. Sort-Merge Join with SuperScalarSort (sort based on )
    3. Sort-Merge Join with DPG Sort (sort based on DPG; see 4.1)
2. DPG-Sort Join (see Section 4.2.1)
3. DPG-Move Join (see Section 4.2.1)
4. Radix Join (from )

### 4.1 Sort-Merge Join with DPG Sort

The well-known Sort-Merge join was introduced by Blasgen and Eswaran . There are two steps in Sort-Merge joins: sort two relations on the join key and scan the sorted relations to do a merge on the join key.

Applying DPG sort at the first step provides a new faster sort-merge join method, Sort-Merge join with DPG Sort. In Sections 5.2 and 5.3, we experimentally compare different versions of sort-merge join, according to the sorting methods used. Specifically, we consider using DPG sort, AlphaSort and SuperScalarSort for the sorting step.

### 4.2 Foreign Key Join with DPG

We next consider joins in which the join key is a foreign key, and it has an index. We denote by $`R`$ a non-indexed relation. We denote by $`F`$ an indexed relation. The notation is motivated by the example of a foreign key join. In a foreign key join, the join key is the same as the foreign key. So, the join key is a set of attributes in the relation $`R`$ that refers to a foreign key from relation $`F`$.

A join triple is a triple ($`k`$, ridR, ridF), such that $`k`$ is a key value, ridR is the rid of a record from $`R`$ with key $`k`$, and ridF the rid of a record from $`F`$ with key $`k`$.

There are three steps in a foreign key join algorithm with DPG. The first step is to construct join triples. The second step is to use the join triples to copy one of the two relations into a temporary file according to an order derived from the join triples. The third step is to join the temporary file with the remaining relation.

We describe the second and third steps initially in Section 4.2.1. We then return to the more technical problem of efficiently constructing join triples in Sections 4.2.2 and 4.2.3.

#### 4.2.1 Two Foreign Key Join Methods with DPG

This section describes two DPG join algorithms. It assumes that one has already constructed the join triples. Some algorithms for constructing the join triples are described later in Sections 4.2.2 and 4.2.3.

Assume that one has generated the join triples ($`k`$, ridR, ridF). It is now possible to ignore the key $`k`$, and deal directly with the rid pairs (ridR, ridF). We wish to satisfy one of two goals:

1. DPG-Move join: Move the records of $`F`$ into a temporary file according to the ordering of the records of $`R`$.
2. DPG-Sort join: Move the records of $`R`$ into a temporary file according to the ordering of the records of $`F`$. So, the rid pairs (ridR, ridF) will be sorted according to ridF.

First consider DPG-Move join. We will see how to generate the join triples in the order of ridR. This is done by scanning the records of the relation $`R`$ in file order (in order of increasing ridR). Therefore the rid pairs can be used directly as part of a DPG algorithm. The second component of the pair, ridF, is the sequence of rids according to which we want to move the records of $`F`$. This algorithm does not require any sorting or hashing. Hence, we call it DPG-Move join.

Next consider DPG-Sort join. In this version, we first sort the rid pairs (ridR, ridF) according to the order of ridF. This is done, for example, with SuperScalarSort and DPG. The algorithm then reduces to record movement in which we wish to move the records of $`R`$ according to the ordering of ridF in the sorted sequence (ridR, ridF).

Note that DPG-Move join is preferred when the relation $`F`$ is smaller. DPG-Sort join is preferred when the relation $`R`$ is smaller.

#### 4.2.2 Construction of Join Triples

The simplest solution for a foreign key join is to do a file scan of $`R`$, and for each record of $`R`$ to extract the join key and do an index lookup in the index of $`F`$. One can then join the record of $`R`$ with the corresponding record of $`F`$. This involves random access, and is economical only if the join produces very few records. In particular, this will be the case only if the number of records of $`R`$ is small.

A better solution is to do a file scan of $`R`$, and to use the index on $`F`$ to create join triples. To construct the join triples, one scans the relation $`R`$. For each record of $`R`$, one extracts the corresponding rid and associated join key $`k`$. One then looks up the key $`k`$ in the index of $`F`$. The index lookup yields the final element of the triple, ridF.

#### 4.2.3 Batch Lookup in Indexes

Note that the join triple is constructed at the cost of a file scan of $`R`$ and an index lookup in the index of $`F`$ for each record of $`R`$. Usually an index on a data file is much smaller than the full data file. If the index fits entirely in cache, then the index lookup will be significantly cheaper than the file scan.

Unfortunately, the indexes in many main memory databases generally do not fit in cache. In such cases, the index lookup in the index of $`F`$ will dominate the costs. For example, in a B+ tree indexing $`N`$ records, if an internal node has $`m`$ children, then $`\mathrm{log}_mN`$ nodes of the B+ tree must be accessed. Each such access will be a random access in main memory. Most of the random accesses imply a cache miss. The cost of so many random accesses makes a naive index lookup uneconomical. Even if the index is a hash index, at least one random access in memory will be required.

Luckily, it is possible to execute the index lookup faster than the above analysis would indicate. This is because the construction of the join triples requires many index lookups, with no intervening record accesses. For purposes of join triple construction, batch lookup of keys in an index suffices. By batch lookup, we assume that an array of join keys is first extracted by scanning the data file of $`R`$. The batch lookup then produces an array of rids for $`F`$ through the use of the index on $`F`$. We show that the index lookups can be reorganized into a two-pass algorithm. Two such two-pass algorithms are demonstrated: one for B+ tree indexes, and one for hash indexes.

Note that batch lookup of rids in an index can be substantially faster than individual lookup. Rao and Ross had previously discussed cache conscious indexes for main memory . There they present CSS-trees, which have better cache behavior than either B+ trees or hash indexes. However, they only consider individual lookup of keys in an index, one at a time. In their scenario, a second key is not looked up until the index lookup of the first key has been resolved.

##### Batch Lookup in B+ Tree Indexes

For simplicity, we describe the two-pass lookup for an enhanced B+ tree. The notion of enhanced B+ tree was introduced by Rao and Ross . The idea is that all slots of a B+ tree node are used. This is similar to compact B-Trees  or to the ISAM method introduced by IBM . In the context of a general B+ tree this can be accomplished by maintaining updates to the B+ tree in a separate index, and then doing a batch update by reorganizing the B+ tree. For brevity, we will sometimes refer to B+ tree, although in all cases, an enhanced B+ tree is intended.

Assume that we are executing a file scan of $`R`$ with the purpose of constructing the join triples. We collect a sequence of keys from the relation $`R`$, and we wish to carry out a batch lookup of rids in the enhanced B+-tree. The rids will be used to retrieve records from the foreign relation $`F`$. We assume that the B+ tree does not fit in cache. Our goal is a two-pass algorithm which will efficiently accomplish batch lookup.

Assume that the B+ tree has $`m`$ entries per node. Assume that the B+ tree indexes $`N`$ records. Then there are $`\mathrm{log}_mN`$ levels. Assume further that the first $`(\mathrm{log}_mN)/2`$ levels (the top half of the B+ tree) fit in cache. For $`m2`$, the top half of the tree has approximately $`m^{(\mathrm{log}_mN)/2}=\sqrt{N}`$ slots. For example, if there are $`N=10^9`$ records, then there are 32,000 slots, which clearly fit inside cache.

The strategy is a two-pass strategy. In the first pass, one performs a lookup of each key, but only using the top half of the B+ tree. As shown in Figure 3, each leaf of the subtree comprising this upper half can be considered as the root of a second subtree comprising nodes in the lower half of the B+ tree. Thus, at the end of this first pass, a key can be associated with a leaf of the upper subtree, which is also a root of one of the lower subtrees.

After the first pass, one can associate each key with a subtree within the lower half of the B+ tree. So, in the second pass, one loads a subtree from the lower half. One then continues the lookup for all keys associated with the root of the subtree in the lower half. At the end, one then has a sequence of keys and rids.

If one wishes to have the keys in the same order as the order of the original rids, then this can also be arranged. In this case, one extends the previous scenario to use the DPG algorithm.

The first phase of the DPG algorithm is to distribute the keys into runs. In the initial lookup of a key in the first half, it was associated with a root of a subtree in the first half. The particular root of a subtree identifies the run into which the key is copied.

The second phase of the DPG algorithm is to use the key to probe the index, in order to find the rid. One completes the lookup of all keys in a run associated with a particular subtree of the B+ tree, before proceeding to the next subtree in the lower half. The resulting rids are stored in a temporary partition or run. This is exactly what was described earlier.

Finally, the third phase of the DPG algorithm gathers the rids into a destination array in the same order as that of the original keys. Hence, we have completed a batch lookup of the keys, and returned an array of rids in the same order as that of the original keys.

##### Batch Lookup in Hash Indexes

Batch lookup of hash indexes also proceeds in two passes. We assume that the hash array of the hash index stores at each hash entry one key-rid pair. A second hash array associated with the index stores pointers to overflow key-rid pairs that would have collided with an occupied slot in the first hash array.

The two-pass lookup for hash indexes proceeds in a very simple manner. We extract the sequence of keys from $`R`$. As the keys are extracted, the hash values are computed. Those key-hash value pairs are saved in an array in an order corresponding to the rid order of $`R`$.

It now suffices to apply the DPG algorithm. The hash array is partitioned into sets of $`L`$ hash slots. In the distribute phase, the hash value acts as an index into the hash array. Hence, this becomes the permutation vector of the DPG algorithm. The key and hash value are then written into separate runs according to the partition of the hash array. There is one run of key-hash values for each partition of the hash array.

In the probe phase, a run of hash values is loaded into cache along with the corresponding partition of the hash array. As part of the probe phase, the key and hash values from the run are used to look up the the corresponding rid in the partition of the hash array. The rids are then saved in a temporary partition, in the same order as the order in which the key-hash values of the original partition are stored.

Finally, in the gather phase, the ordering of the key-hash value pairs are used to gather the rids from the temporary partition. As in Section 2, the rids are gathered into a destination array in an order corresponding the ordering of the original key-hash value pairs.

## 5 Experimental Evaluation

### 5.1 Sorting Comparisons

Figure 4 demonstrates the acceleration achieved by SuperScalarSort when DPG is used. The results are demonstrated on the IBM pSeries 690 Turbo. The IBM p690 has an L3 cache of size 128 MB. Hence, in order to realistically demonstrate DPG, we were forced to increase the size of the database. We chose to implement SuperScalarSort for a data file of size 512 MB. The record size was treated as a variable, to illustrate the influence of record size. As in the original Datamation Challenge, the key is 10 bytes.

Note that the additional speed of SuperScalarSort with DPG is most pronounced for smaller record sizes. For record sizes of 256 bytes and higher, DPG provides only a small advantage. This is because the IBM p690 has an L3 cache block of size 512 bytes. So, for record sizes below 256 bytes, a cache miss incurs significant overhead in loading a 512 byte cache block.

There was some variability in the results because the data was taken on a time-shared, shared memory machine. On the IBM p690, the L2 cache is shared among two CPUs, and the L3 cache is shared among eight CPUs. Our experiments were run on a single CPU. Hence another process on a neighboring CPU could consume some of our cache, thereby affecting the timings. The reported experimental results are the averages of three runs each.

### 5.2 Comparion of Sort-Merge Join using Different Sorting Algorithms

We implement two sort-merge join methods: sort-merge join with DPG sort and sort-merge join with SuperScalarSort. As defined in section 4.1, sort-merge join with DPG sort applies the DPG sort for the sorting phase and sort-merge join with SuperScalarSort applies SuperScalarSort for the sorting phase.

As expected, the acceleration in the speed of sort-merge join in Figure 5 follows the same pattern as that of Figure 4 for sorting. In this case, we illustrate our results on a database of size 128 MB on the IBM p690. The IBM p690 has an L2 cache of size 1.4 MB. So, in this case, the L3 cache is acting as the main memory, while L2 cache is acting as the “cache”.

### 5.3 Comparion of Six Different Join Methods

In Figures 6 through 12, we now experimentally compare the six join methods originally presented at the begining of Section 4. The three join algorithms labelled Sort-Merge Join with DPG Sort, DPG-Sort Join, and DPG-Move Join are all new. The remaining algorithms, Sort-Merge Join with AlphaSort, Sort-Merge Join with SuperScalarSort, and Radix Join, are all based on sorting or join algorithms from the literature.

As explained earlier, we denote by $`F`$ an indexed relation and $`R`$ a relation that has foreign key on the indexed attribute of $`F`$. We consider both uniform and non-uniform distribution of foreign key values.

##### The non-uniform distribution of join key values.

Sort-merge join with AlphaSort and DPG-Sort are the only two of the previously discussed join methods that operate correctly for a non-uniform distribution of join key values.

In the following we use count bucket sort for bucket sort. The count bucket sort is as follows:

1. count the number of elements destined for each bucket.
2. set bucket boundaries according to the statics computed and distribute elements to buckets.

AlphaSort works for non-uniformly distributed data, because it uses quicksort to sort each run and uses replacement-selection to merge the runs. DPG-Sort join works for non-uniformly distributed data too, because we use count bucket sort to sort RIDs.

DPG-Sort join sorts the RIDs according to the lowest $`\mathrm{log}N`$ bits is enough, $`N`$ is the number of records. In the simulation, we assign the RID values in the range $`[1,\mathrm{},n]`$, the lowest $`\mathrm{log}N`$ bits is sufficient for sorting. For example, for $`N=2^{20}`$ sorting RIDs according to the lowest 20 bits is enough. This could be done in two steps with count bucket sort: first do count bucket sort according to the lower 10 bits, then do count bucket sort according to the higher 10 bits.

Using the UNIX $`random()`$ and $`exp()`$ functions we generate an exponential distribution of the data as $`exp(c(random()>>10))`$ ($`c`$ is a constant and in our experiments we assign c with $`0.0000001`$). A comparison of Sort-Merge join with AlphaSort and DPG-Sort join on three different computer architectures is provided in the figures 6, 7, and 8. The three different architectures are the IBM Power4 Pseries 690 Turbo, the 3.06 GHz Pentium 4 with Rambus PC-1200 RAM, and the 2.6 GHz Pentium 4 with DDR-266 RAM, From the comparison, we can see that DPG-sort join is much faster than Sort-Merge join with AlphaSort.

##### The uniform distribution of join key values.

First we will show how all algorithms work for uniformly distributed join key values. SuperScalarSort is a key-prefix-sort explained further in section 1. It assumes that data is uniformly distributed according to the highest 7 bits of the key. This kind of distribution can be applied to all DPG algorithms, because a unform distribution of the join key values is the only constraint of Sort-Merge join with DPG and DPG-move join.

We also implement the radix join of Manegold et al. . They describe a variation of hash join for main memory. Radix join also requires a uniform distribution of the join key values. Otherwise, some of their partitions will be too large to fit into the L2 cache and how to set the boundaries is unknown.

We produce uniformly distributed foreign key values using the UNIX $`random()`$ function. A comparison of the different join methods on three different computer architectures as before is provided in the figures. Figure 9 reflects data with no duplicate join key values in the relation $`R`$. Figures 10, 11, and 12, show the same information in which duplicate join key values are allowed. From the comparison, we can see that DPG-move join and radix join are the fastest. DPG-move is better for large records and radix join is better for small records.

## 6 Conclusions

The use of DPG in the sorting provides an accelerator for existing sorting algorithms. Especially for the smaller record sizes, such as 32 bytes and 64 bytes, the performance improvements are really impressive.

For the more common case of non-uniform distribution of join key values, DPG-Sort join works better than sort-merge join with AlphaSort across all the tested platforms. For smaller records sizes, such as, 32, 64, DPG-Sort join is much better than sort-merge join with AlphaSort. More impressively, on the newer platform, Rambus PC-1200 RAM, DPG-Sort works better than on PC with DDR-266 RAM and even works better for larger record sizes, for example 512 bytes.

For special case of uniform distribution of join key values, DPG-move join and radix join are the best. The remaining DPG algorithms are also competitive with older algorithms although with a smaller improvement.

## 7 Future Work

The DPG algorithm can be easily generalized to multiple passes. This can be useful when there is a very small cache in relation to the size of main memory. However, we do not encounter this scenario in our current experiments.

## 8 Acknowledgements

We would like to thank Betty Salzberg and Donghui Zhang for extensive conversations and insights into additional situations where distribute-probe-gather can be beneficial. We also gratefully acknowledge the use of the support for the computations on the IBM p690 by the Scientific Computing and Visualization (SCV) group at Boston University.


format: text

text:
# Chapter 1 A Study Of Very Inclined Showers In The Pierre Auger Observatory

## Chapter 1 A Study Of Very Inclined Showers In The Pierre Auger Observatory

### Abstract

The Engineering Array of the Auger Observatory has been running successfully since 2001 and inclined showers have been recorded from the start. We have analysed the events with zenith angle $`>`$ 700 recorded between May and November 2002. The different algorithms developed to analyze these showers are also discussed. An preliminary discussion of a reconstructed event having 20 detectors hit is presented. Inclined showers will be detected by the full Auger Observatory and they will allow significant enhancement of the array aperture. High energy events will be seen as spectacular events with 30 or 40 tanks triggered and they will provide alternative information on muon content in air showers.

### 1. Introduction

Uncovering the origin, composition and energy spectrum of the highest energy cosmic rays is one of the biggest challenges in astroparticle physics. The Pierre Auger project is the next step in the search for answers to intriguing questions about the origin of these particles. Before proceeding to the construction of the full-size observatory, a subset of it, the Engineering Array (EA), has been built and operated. A detailed description of the EA can be found in .

Ground arrays of water Čerenkov detectors are very sensitive to extensive air showers at large zenith angles. In these showers the majority of the particles reaching ground level are energetic muons and electromagnetic particles resulting from muon interactions or decay. The rate of these showers is then governed by their muon content and is thus sensitive to primary composition. The understanding of these showers is also important because they constitute the background to search for very inclined showers induced by ultra-high energy neutrinos.

Inclined showers would not be very different from vertical showers except for the fact that they develop in the upper part of the atmosphere. As a result the electromagnetic part of the shower, produced mainly from $`\pi ^0`$ decay, is mostly absorbed well before the shower front reaches ground level. However, the muon front propagates through the atmosphere mixed with an electromagnetic halo coming from bremsstrahlung, pair production and muon decays. This halo is continuously generated and proportional to the number of muons, representing less than 15% of the signal in a Čerenkov tank as long as one is sufficiently far away from the core (a few tens of meters).

The muon energy spectrum at ground has a low energy cutoff, caused by muon decay, which increases as the zenith angle rises and the average muon energy at ground level also increases. The high energy part of the muon spectrum is also slightly different due to the rise of the pion critical energy (the energy at which the pions are more likely to decay than to interact), caused by the smaller density in the upper part of the atmosphere where inclined showers develop.

These energetic muons travel making small angles to the incoming cosmic ray direction and their trajectories are deflected by the magnetic field of the Earth. These effects start to be important at zenith angles above 700 for the geomagnetic latitude of the Auger Observatory. At these zenith angles the muon density patterns at ground are very different from typical densities measured in vertical showers that show symmetry around the shower axis. The geomagnetic field acts as a “natural magnetic spectrometer” selecting high energetic muons and deforming the symmetric pattern.

Signals of inclined showers in Čerenkov tanks being due to muons differ from those in vertical showers. Since the electromagnetic part is heavily suppressed inclined signals have a sharper time structure, with a higher rise time. The signals are proportional to the muon tracks which increase as the zenith angle rises. Direct light, Čerenkov photons to fall directly onto the PMT without reflection from the tank walls, also increase the signal produced by inclined muons. Finally, inclined muons are more energetic enhancing the probability of muon interactions inside the tank, such as bremsstrahlung, pair production and muon nuclear interactions .

In this paper we report the preliminary results of the analysis of the inclined shower events recorded by the EA between May and November 2002.

### 2. Analysis procedure and results

The analysis of inclined showers is a 3 step procedure. The direction of the events are obtained by fitting the particle arrival times recorded at each station to a plane or curved front.

To reconstruct the energy of inclined events a theoretical prediction of the muon density patterns is required. Geomagnetic field effects must be taken into account. There are 3 independent groups working on this issue: a) An analytical approximation of the deflection of muons in the geomagnetic field based on the correlation of the muon energy with the distance to the shower axis, Monte Carlo simulations without magnetic field are required to apply this method . b) Parameterizations of the number of muons in a tank based on detailed Monte Carlo simulations with geomagnetic field effects. This is a two step simulation: first the hadronic shower is simulated in the absence of magnetic field, the position, the energy and the direction of the muons is kept at their production point, and in the second step the muons are propagated in the geomagnetic field. The second step is very fast in computing time, allowing to produce simulations for all possible azimuth angles rapidly . c) An analytical approximation of the lateral and longitudinal distribution of muons in the absence of geomagnetic field, with the geomagnetic field effects implemented a posteriori in a similar way to method a), .

Finally, a likelihood function is built to fit the energy of each event. Two different likelihood functions are being used: a) The signal in VEM is converted to muon numbers dividing it by the average signal produced by a muon at the corresponding zenith angle, Poisson statistics are then used to calculate the probability using the prediction of the number of muons. b) The other approach uses a probability density function of the signal produced by $`k`$ muons, obtained in simulations, and multiplies it by the Poisson probability. Details of the two methods can be found in , . In order to account for the tank response to inclined muons with different energies and angles of incidence, simulations were performed using the GEANT  and SDSIM  packages.

We have analyzed all the events recorded between May and November 2002 with zenith angles larger than 700 and with 5 or more stations triggered. In the present work we have assumed proton primaries and the QGSJET hadronic model . Different assumptions about hadronic models and the mass of the primary particle have a direct impact in the number of muons and give rise to different results.

The left panel of Fig. 1 shows the correlation between the energy as reconstructed in two independent analysis. One combines the parameterization of the muon densities and the likelihood function described as a) in the previous section and the other corresponds to different parameterization and likelihood function (b). The agreement is encouraging. We can define $`\mathrm{\Delta }E_0`$ as the distance of each point to the line defined by $`E_a=E_b`$. Right panel of Fig. 1 shows the distribution of the ratio of $`\mathrm{\Delta }E_0`$ to the mean energy using both algorithms. The spread of this distribution is 20% and no significant offset is present.

The results presented here are preliminary. The agreement between the two algorithms used is encouraging but further checks are in progress. The energy of some events are very sensitive to the shape of the muon density patterns used, specially at high energies, where the EA is small compared to the size of the shower at ground. Fig. 2 shows an example: the density map of a reconstructed event in the plane perpendicular to the shower axis. This result was obtained using method a) and displays the signals in each tank (converted to mean number of recorded muons). The position of the best-fit impact point is indicated by a cross. The $`y`$-axis is aligned with the component of the magnetic field perpendicular to the shower axis. Contour levels for 2, 5, 10 and 20 muons per station are shown for the fit. Events like this will be very common in the full array and they will help to check the muon density patterns obtained through simulations or analytical techniques.

1. J. Abraham et al, Nucl. Inst. Met., to be published.

2. M. Ave, R. A. Vázquez, and E. Zas, Astropart. Phys. 14, 91 (2000).

3. P. Billoir, O. Deligny, A. Letessier-Savon, Internal Note GAP 2003-003.

4. A. Dorofeev and D. Nitz, Private Communication.

5. R. Brun et al. GEANT, Program Library CERN (1993).

6. Sylvie Dagoret Campagne, Internal Note, GAP 2002-072.

7. M. Ave, et al, Phys.Rev. D67 (2003) 043005

8. N. Kalmykov, et al, Nucl. Phys. B 52, 17 (1997).


text:
# Note on spin carried by quarks

We note that recent results on the role of final state interactions in deep inelastic scattering make more complicated an extraction of a nucleon spin fraction carried by quarks from the experimental data obtained in deep inelastic scattering.

Crucial results on the essential role of final state interactions in the interpretation of structure functions $`F_i(x,Q^2)`$ in deep inelastic scattering have been obtained recently . It appeared that final state interactions of the struck quark with proton remnants cannot be eliminated and this fact invalidates interpretation of the structure functions as parton probability densities. These results lead to the important phenomenological implications, in particular, they provide significant single spin asymmetries in SIDIS  and Drell–Yan processes .

It is evident that arguments of  can be applied to the polarized structure functions $`G_i(x,Q^2)`$ as well. Experimentally measured quark spin distributions
$`\stackrel{~}{\mathrm{\Delta }q}(x,Q^2)`$ will include then rescattering effects related to the presence of the path ordered exponent in their definitions as Fourier transform of the matrix elements of the axial vector current operator similar to the case of unpolarized quark distributions . By definition111We apply definition of quark densities, which allow straightforward interpretations of the experimental results; thorough discussion of definitions of parton densities has been given recently in . quark spin densities $`q_{}(x,Q^2)`$ and $`q_{}(x,Q^2)`$ are the probability densities to find a quark of flavor $`q`$ with a given helicity value and momentum fraction in the hadron wavefunction resolved in the transverse plane with the resolution scale determined by $`Q^2`$. This allow us to interpret the first moment of the function

$$\mathrm{\Delta }q(x,Q^2)=q_{}(x,Q^2)q_{}(x,Q^2)+\overline{q}_{}(x,Q^2)\overline{q}_{}(x,Q^2)$$

as the net fractions of the nucleon spin carried by quarks of particular flavor, and total fraction of hadron spin carried by quarks $`\mathrm{\Sigma }`$ is a sum of the first moments over all flavors. Thus, we immediately arrive to conclusion that it is more difficult to extract in a usual way quark the spin densities $`\mathrm{\Delta }q(x,Q^2)`$ from the experimentally measured polarized structure functions $`g_{1,2}(x,Q^2)`$. Indeed, rescattering affects most strongly the region of small $`x`$ and we can then expect here a maximal deviation of the functions $`\stackrel{~}{\mathrm{\Delta }q}(x,Q^2)`$ from the usual quark spin densities $`\mathrm{\Delta }q(x,Q^2)`$. At the same time the region of small $`x`$ is most important for the calculation of the net spin carried by quarks and antiquarks. Since, the structure functions are experimentally measured in the limited region of $`x`$ the cancellation of the rescattering effects, which is valid for $`_0^1\mathrm{\Delta }q(x,Q^2)`$, may not take place for the limited integration region.

It is well known now that the functions $`\stackrel{~}{\mathrm{\Delta }q}(x,Q^2)`$ and $`\mathrm{\Delta }q(x,Q^2)`$ can be different due to perturbative contribution of an axial vector anomaly and this way to treat “spin crisis” was proposed at its early stage . Rescattering effects adherent to both polarized and unpolarized structure functions have a different origin.

To this end, the conclusion on the increasing difficulty of the extraction of fraction of spin carried by quarks from the experimental data in deep inelastic scattering due to rescattering effects seems inevitable and the fundamental reason for this conclusion is that we have to deal with not free but interacting fields. This interaction leads to strong coherence effects in the interaction of virtual photon with hadron. Account for such effects can be done in the model way. For example, modelling of these effects in the nonperturbative approach based on unitarity has been performed in .


text:
# Classification of operator algebraic conformal field theories in dimensions one and two

## 1 Introduction

Our main results, together with R. Longo, are classification results for conformal field theories, in the operator algebraic approach. We first briefly describe our basic framework for quantum field theory and its relation to a more conventional approach based on Wightman axioms using operator-valued distributions.

Our framework is called algebraic quantum field theory or local quantum physics, and its standard textbook is  by R. Haag. We first explain our axiomatic setting on the 4-dimensional Minkowski space, although we will later work on lower dimensional spacetime. Recently, several attempts have been made on studies on curved spacetime or even noncommutative spacetime, but we will not deal with such topics in this review.

In our setting, a physical system is described by a family of operator algebras $`𝒜(O)`$ on a fixed Hilbert space $`H`$, where $`O`$ is a bounded region in the Minkowski space. As such a region $`O`$, we consider only double cones, which are of the form $`(x+V_+)(y+V_{})`$, where $`x,y^4`$ and

$$V_\pm =\{z=(z_0,z_1,z_2,z_3)^4z_0^2z_1^2z_2^2z_3^2>0,\pm z_0>0\}.$$

We assume that we have a von Neumann algebra $`𝒜(O)`$ acting on $`H`$ for each double cone $`O`$ and the following properties hold. (An algebra of bounded linear operators on a Hilbert space is called a von Neumann algebra if it is closed under the $``$-operation and weak-operator topology.)

1. (Isotony) For $`O_1O_2`$, we have $`𝒜(O_1)𝒜(O_2)`$.
2. (Locality) If $`O_1`$ and $`O_2`$ are spacelike separated, then elements in $`𝒜(O_1)`$ and $`𝒜(O_2)`$ commute.
3. (Poincaré Covariance) There exists a unitary representation $`U`$ of the universal covering of the restricted Poincaré group satisfying $`𝒜(gO)=U_g𝒜(O)U_g^{}`$.
4. (Vacuum) We have a unit vector $`\mathrm{\Omega }H`$, unique up to phase, satisfying $`U_g\mathrm{\Omega }=\mathrm{\Omega }`$ for all elements $`g`$ in the restricted Poincaré group and $`_O𝒜(O)\mathrm{\Omega }`$ is dense in $`H`$.
5. (Spectrum Condition) If we restrict the representation $`U`$ to the translation subgroup, its spectrum is contained in the closure of $`V_+`$.

The isotony axioms simply states that we have more observables for a larger region. The locality axiom means that if we have two spacelike separated regions, then we have no interactions between them even at a speed of light, so the two operators taken from the two regions mutually commute. It is also called the Einstein causality. Covariance means that a “spacetime symmetry” acts as a symmetry of the family of operator algebras. We will later use a higher spacetime symmetry than restricted Poincaré group. The vector $`\mathrm{\Omega }`$ is called a vacuum vector and it gives a vacuum state. The spectrum condition means stability.

If we denote the set of the elements that are spacelike separated with all the elements of a region $`D`$ by $`D^{}`$, then we have $`O^{}=O`$ for a double cone $`O`$. This is why we use only double cones. For a general region $`D`$, we could define $`𝒜(D)`$ as the von Neumann algebra generated by $`𝒜(O)`$ for all double cones $`O`$ contained in $`D`$.

Since the set of double cones is directed with respect to inclusions, we often say that the family $`𝒜(O)`$ is a net of von Neumann algebras. We also say a net of factors, if each von Neumann algebra $`𝒜(O)`$ has a trivial center, which is often the case in the lower dimensional spacetime as below, since such a von Neumann algebra is called a factor. In many such cases, the local algebras are all isomorphic, so each local algebra itself does not contain physical information about the system. A basic idea is that all information about a certain physical system is contained in such a net $`𝒜(O)`$.

From a mathematical viewpoint, such a net of von Neumann algebras is simply a family of operator algebras subject to certain set of axioms, so we can study classification theory of such families of operator algebras up to an obvious notion of isomorphism. A useful and important tool for such a study is a representation theory of a net of von Neumann algebras.

A basic tool to study a net of von Neumann algebras is its representation theory formulated by Doplicher-Haag-Roberts (DHR) . Each operator algebra $`𝒜(O)`$ acts on a fixed Hilbert space from the beginning, but we can also consider a representation of a family of operator algebras on a different Hilbert space where we do not have a vacuum vector any more. A basic idea of Doplicher-Haag-Roberts is that if we assume a nice condition called the Haag duality and select a nice class of representations with their criterion, then each such representation is realized, up to unitary equivalence, as a certain endomorphism of (the norm closure of) $`_O𝒜(O)`$. Such an endomorphism is often called a DHR endomorphism. An important feature of endomorphisms is that they can be composed. This composition gives an operation in the set of DHR endomorphisms which plays a role of a tensor product. Through this operation (and others), mathematical structure of DHR endomorphisms becomes quite similar to that of unitary representations of a compact group, and it gives a $`C^{}`$-tensor category.

We briefly mention a relation of the above approach to a more conventional one based on the Wightman axioms. In the setting of the Wightman axioms, one considers a family of operator-valued distributions $`\{\varphi _j(x)\}`$ on the Minkowski space. If we have such a family at the beginning, then, roughly speaking, we apply smooth functions supported in $`O`$ to these distributions, apply bounded functional calculus to the resulting (unbounded) operators, and let $`𝒜(O)`$ be the von Neumann algebra generated by these bounded operators. In this way, we should obtain a local net of von Neumann algebras. If we start with a local net $`𝒜(O)`$ of von Neumann algebras, we should obtain operator valued distributions $`\{\varphi _j(x)\}`$ through a certain limiting procedure in which bounded regions $`O`$ shrink to one point $`x`$. It is believed that the approach based on the Wightman axioms and the one based on local nets of von Neumann algebras are essentially equivalent, and there have been many works which study under what conditions we obtain one from the other, but the exact relations between the two approaches have not been fully understood yet.

## 2 Full and chiral algebraic conformal quantum field theories

The above general framework in the previous section obviously works on a Minkowski space of any dimension. We now specialize on the 2-dimensional Minkowski space $``$ and require higher symmetry than the general Poincaré covariance. This is our approach to conformal field theory. Then through a chiral decomposition of a full algebraic conformal quantum field theory, we obtain a chiral algebraic conformal quantum field theory which is now described as a one-dimensional net of factors. After such a general description, we will briefly mention a relation to vertex (operator) algebras, which give another mathematical approach to chiral conformal field theories.

We now work on a two-dimensional Minkowski space $``$ where we use $`t`$ and $`x`$ for the time and space coordinates, respectively. We have a von Neumann algebra $`𝒜(O)`$ on a fixed Hilbert space $`H`$ for each double cone $`O`$ in this Minkowski space $`M`$ as above. We set $`L_\pm =\{t\pm x=0\}`$ and each double cone is a direct product $`I_+\times I_{}`$, where $`I_\pm `$ are bounded intervals in $`L_\pm `$, respectively. We consider the Möbius group $`PSL(2,)`$ which acts on $`\{\mathrm{}\}`$ as linear fractional transformations. In this way, we obtain a local action of the universal covering group $`\overline{PSL}(2,)`$ on $``$. We impose the following axioms for our net of von Neumann algebras $`𝒜(O)`$ on $`H`$ and call such a net a Möbius covariant net of von Neumann algebras. (See  for more details.)

1. (Isotony) For $`O_1O_2`$, we have $`𝒜(O_1)𝒜(O_2)`$.
2. (Locality) If $`O_1`$ and $`O_2`$ are spacelike separated, then elements in $`𝒜(O_1)`$ and $`𝒜(O_2)`$ commute.
3. (Möbius Covariance) There exists a unitary representation $`U`$ of $`\overline{PSL}(2,)\times \overline{PSL}(2,)`$ on $`H`$ such that for every double cone $`O`$, we have $`𝒜(gO)=U_g𝒜(O)U_g^{}`$ when $`gW`$ where $`W`$ is a connected neighbourhood of the identity in $`\overline{PSL}(2,)\times \overline{PSL}(2,)`$ satisfying $`gOM`$ for all $`gW`$.
4. (Vacuum) We have a unit vector $`\mathrm{\Omega }H`$, unique up to phase, satisfying $`U_g\mathrm{\Omega }=\mathrm{\Omega }`$ for all elements $`g`$ and $`_O𝒜(O)\mathrm{\Omega }`$ is dense in $`H`$.
5. (Positive energy) The one-parameter unitary subgroup of $`U`$ corresponding to the time translation has a positive generator.

We now further strengthen the axiom of Möbius covariance as follows. Let $`𝖦`$ be the quotient of $`\overline{PSL}(2,)\times \overline{PSL}(2,)`$ modulo the relation $`(r_{2\pi },r_{2\pi })=(\mathrm{id},\mathrm{id})`$. Then it turns out that our representation $`U`$ as above gives a representation of this group $`𝖦`$, due to the spacelike locality. We then find that our net $`𝒜(O)`$ extends to a local $`𝖦`$-covariant net on the Einstein cylinder $`=\times S^1`$, which is the cover of the 2-torus obtained by lifting the time coordinate from $`S^1`$ to $``$. We also have several consequences from the above set of axioms. See \[18, Proposition 2.2\], for example.

Let $`\mathrm{Diff}()`$ be the group of the orientation preserving diffeomorphisms which are smooth at infinity. Then this group naturally acts on $``$ as a diffeomorphic action. Let $`\mathrm{Conf}()`$ be the group of global, orientation preserving conformal diffeomorphisms of $``$. This group is generated by $`\mathrm{Diff}()\times \mathrm{Diff}()`$ and $`𝖦`$. If a Möbius covariant net $`𝒜`$ further satisifies the following axiom, we say that the net $`𝒜`$ is a local conformal net. This is the class we study.

(Diffeomorphism covariance) The unitary representation $`U`$ of $`𝖦`$ extends to a projective unitary representation of $`\mathrm{Conf}()`$ such that the extended net on $``$ is covariant. Furthermore, we have $`U_gXU_g^{}=X`$ for $`g\mathrm{Diff}()\times \mathrm{Diff}()`$, if $`X𝒜(O)`$ and $`g`$ acts on $`O`$ as identity.

This gives our framework for conformal quantum field theory. We study a net $`𝒜(O)`$ as a family of von Neumann algebras satisfying the above set of axioms. Such a family here is also called a full algebraic conformal quantum field theory. The DHR theory works in this setting perfectly.

Suppose we have a local conformal net $`𝒜`$ as above. Then for each bounded interval $`IL_+`$, we set $`𝒜_+(I)=_J𝒜(I\times J)`$. In this way, we have a family of von Neumann algebras $`𝒜_+`$ parameterized by bounded intervals $`I`$. We regard these von Neumann algebras as subalgebras of $`B(H_+)`$, where $`H_+`$ is the closure of $`_I𝒜_+(I)\mathrm{\Omega }`$. This family extends to a family $`𝒜_+(I)`$, where $`I`$ is any open, nondense, nonempty, and connected set of $`S^1=\{\mathrm{}\}`$. (Such $`I`$ is simply called an interval in $`S^1`$.) This family $`𝒜_+(I)`$ satisfies the following conditions. We may take these as axioms for such a family. (See  for more details.)

1. (Isotony) For $`I_1I_2`$, we have $`𝒜_+(I_1)𝒜_+(I_2)`$.
2. (Locality) If $`I_1`$ and $`I_2`$ are disjoint, then elements in $`𝒜_+(I_1)`$ and $`𝒜_+(I_2)`$ commute.
3. (Diffeomorphism Covariance) There exists a projective unitary representation $`U`$ of $`\mathrm{Diff}(S^1)`$ on $`H_+`$ such that for every interval $`I`$, we have $`𝒜_+(gI)=U_g𝒜_+(I)U_g^{}`$. Furthermore, we have $`U_gXU_g^{}=X`$ for $`g\mathrm{Diff}(S^1)`$, if $`X𝒜(I)`$ and $`g`$ acts on $`I`$ as identity.
4. (Vacuum) We have a unit vector $`\mathrm{\Omega }H_+`$, unique up to phase, satisfying $`U_g\mathrm{\Omega }=\mathrm{\Omega }`$ for all elements $`g`$ in the Möbius group $`PSL(2,)`$ and $`_I𝒜_+(I)\mathrm{\Omega }`$ is dense in $`H_+`$.
5. (Positive energy) The one-parameter unitary subgroup of $`U`$ corresponding to the rotation on $`S^1`$ has a positive generator.

A family $`𝒜_+`$ satisfying the above set of axioms is called a chiral algebraic conformal quantum field theory. We can similarly define $`𝒜_{}`$. We then have an embedding $`𝒜_+(I)𝒜_{}(J)𝒜(I\times J)`$. The DHR theory works fine for a chiral algebraic conformal quantum field theory. Now, for two DHR endomorphisms $`\rho ,\sigma `$, we have a unitary equivalence for $`\rho \sigma `$ and $`\sigma \rho `$, but we have a canonical unitary $`\epsilon (\rho ,\sigma )`$ implementing this unitary equivalence and this family $`\epsilon `$ of unitaries contains non-trivial information. This family $`\epsilon `$ is called a braiding. See , for example, for details.

Our classification method for full algebraic conformal quantum field theories $`𝒜(O)`$ consists of two steps. In the first step, we classify the chiral algebraic conformal quantum field theories $`𝒜_\pm `$. In the second step, we classify the embedding $`𝒜_+(I)𝒜_{}(J)𝒜(I\times J)`$, which is a non-trivial subfactor, usually.

## 3 Complete rationality and classification

Our basic idea for classification is that if we have a certain nice condition, generally called “amenability”, a simple set of invariants related to representation theory should give a complete classification. We have given a general idea along this line in , so here we only briefly explain the condition called complete rationality, which was introduced in  and plays a role of amenability in classification theory.

Here we state complete rationality for a chiral algebraic conformal quantum field theory $`𝒜(I)`$, $`IS^1`$. We also have a version for a full algebraic conformal quantum field theory and we refer the reader to  for the definition in such a setting. Consider a chiral algebraic conformal quantum field theory $`𝒜`$. Split $`S^1`$ into $`2n`$ intervals, and label them $`I_1,I_2,\mathrm{},I_{2n}`$ in the counterclockwise order. Let $`\mu _n`$ be the Jones index of the subfactor $`𝒜(I_1)𝒜(I_3)\mathrm{}𝒜(I_{2n1})(𝒜(I_2)𝒜(I_4)\mathrm{}𝒜(I_{2n}))^{}`$. (Note that we have this inclusion because of locality.) This number is independent of the way to split the circle. We remark that we automatically have $`\mu _1=1`$, which is called the Haag duality. Complete rationality consists of the following three conditions.

1. (Strong additivity) Remove one point from an interval $`I`$ and label the resulting two intervals as $`I_1,I_2`$. Then we have $`𝒜(I)=𝒜(I_1)𝒜(I_2)`$.
2. (Split property) Consider two intervals $`I_1,I_2`$ with $`\overline{I}_1\overline{I}_2=\mathrm{}`$. Then the von Neumann algebra $`𝒜(I_1)𝒜(I_2)`$ is naturally isomorphic to $`𝒜(I_1)𝒜(I_2)`$.
3. (Finiteness of the $`\mu `$-index) We have $`\mu _2<\mathrm{}`$.

The main results in  give the following two conditions under complete rationality.

1. We have only finitely many equivalence classes of irreducible DHR endomorphisms of the net $`𝒜`$.
2. The braiding naturally gives a unitary representations of $`SL(2,)`$ whose dimension is the number of the equivalence classes in (1).

This shows that the category of the DHR endomorphisms of the net $`𝒜`$ gives a modular tensor category, which plays an important role in theory of quantum invariants of 3-manifolds as in .

We next explain the first numerical invariant of a local conformal net, a central charge, of $`𝒜`$. Let $`𝒜`$ be a local conformal net. (Here we do not need complete rationality.) Then we have a projective unitary representation of $`\mathrm{Diff}(S^1)`$. Recall that the Virasoro algebra is the infinite dimensional Lie algebra generated by elements $`\{L_nn\}`$ and $`c`$ with relations

$$[L_m,L_n]=(mn)L_{m+n}+\frac{c}{12}(m^3m)\delta _{m,n},$$

and $`[L_n,c]=0`$. This is unique, non-trivial one-dimensional central extension of the Lie algebra of $`\mathrm{Diff}(S^1)`$. We now obtain a representation of the Virasoro algebra and then the central element $`c`$ is mapped to a scalar. This value is the central charge of the net $`𝒜`$ and is also denoted by $`c`$. It has been shown by Friedan-Qiu-Shenker  that this central charge value is in

$$\{16/m(m+1)m=2,3,4,\mathrm{}\}[1,\mathrm{})$$

and the values $`\{16/m(m+1)m=2,3,4,\mathrm{}\}`$ have been realized by Goddard-Kent-Olive . (The values in $`[1,\mathrm{})`$ are easier to realize.) Jones has proved in his theory of index for subfactors  that the index value is in the set $`\{4\mathrm{cos}^2\pi /mm=3,4,5\mathrm{}\}[4,\mathrm{}]`$ and all the values in this set can be realized. It is obvious that we have a formal similarity between the two cases. A relation between the Jones theory of subfactors and algebraic quantum field theory was found in . Our classification results give further deeper relations between the two. (See  for a general theory of subfactors and related topics.)

In classification theory of subfactors, Ocneanu  has found a paragroup, which gives a combinatorial invariant for a subfactor through its representation theory. If the Jones index value is less than 4, the subfactor is of finite depth automatically, and this finite depth case is a special case of the amenable case which Popa’s classification theorem  covers. We have shown in  that if the central charge value is less than 1, then the net of factors is automatically completely rational.

Wassermann’s construction of the $`SU(n)_k`$ nets based on loop group representations gives the first examples of chiral algebraic conformal quantum field theories and they are completely rational. The finiteness of the $`\mu `$-index for these nets was proved by Xu . Xu also studied the coset and orbifold constructions in the setting of chiral algebraic conformal quantum field theory in . They give completely rational nets by .

We briefly note that we have some formal similarity between our complete rationality and a condition in theory of vertex operator algebras, which is another mathematical approach to a chiral conformal field theory. They have a condition called $`C_2`$-finiteness introduced by Zhu , which is formally analogous to the above finiteness of the $`\mu `$-index. See  for more details on vertex operator algebras. On a vertex operator algebra $`V`$, we have binary operations $`a_{(n)}b`$, $`a,bV`$, parameterized by integers $`n`$. The finiteness of the codimension $`dimV/V_{(2)}V`$ is called the $`C_2`$-finiteness condition. A vertex operator algebra $`V`$ is said to be rational if every $`V`$-module is completely reducible, and this condition implies that $`V`$ has only finitely many inequivalent simple modules. Zhu has proved that if we have the $`C_2`$-finiteness condition, then the modular group $`SL(2,)`$ acts on the space of characters of all the mutually inequivalent simple $`V`$-modules. This finiteness of the codimension and the above finiteness of the $`\mu `$-index have some formal common similarity as follows.

1. The $`\mu `$-index is also a certain multiplicative codimension.
2. Both the codimension $`dimV/V_{(k)}V`$ and the index $`\mu _k`$ can be defined for any positive integer $`k`$.
3. The above codimension and the index are trivial for $`k=1`$.
4. If the above codimension and the index are finite for $`k=2`$, then they are also finite for all positive integers $`k`$, and we obtain a unitary actions of the modular group $`SL(2,)`$ on certain natural finite dimensional spaces.

However, the action of $`SL(2,)`$ in the setting of vertex operator algebras is on the space of characters while its action in the setting of representation categories of a net of factors is on the intertwiner spaces, and we do not have any direct relation between the two situations. It would be very interesting to clarify this formal analogy.

## 4 $`\alpha `$-induction, modular invariants, and classification

Here we explain our classification method for completely rational nets on $`S^1`$ with central charge less than 1.

Suppose we have a chiral algebraic conformal quantum field theory $`𝒜(I)`$, $`IS^1`$, with central charge $`c<1`$. Then the projective representation $`U`$ of the diffeomorphism group gives a subnet as follows. For an interval $`IS^1`$, we define $`(I)`$ be the von Neumann algebra generated by $`U_g`$, where $`g`$ is a diffeomorphism which acts trivially outside of $`I`$. It is easy to see that this $`(I)`$ is a subalgebra of $`𝒜(I)`$ by the Haag duality and $``$ gives a subnet in the sense of . (Note that the vacuum vector is not cyclic for $``$.) We use a notation $`\mathrm{Vir}_c(I)`$ for this subnet and call it a Virasoro subnet with central charge $`c`$. This net is among the coset constructions due to Xu , which relies on A. Wassermann’s construction of $`SU(2)_k`$-nets . (See  for more on the Virasoro nets.) We have shown in  that the subfactor $`\mathrm{Vir}_c(I)𝒜(I)`$ has a trivial relative commutant and finite index, which is a quite nontrivial fact.

For a net of subfactors $`\mathrm{Vir}_c𝒜`$, we have a machinery of $`\alpha `$-induction, which is analogous to a machinery of induction and restriction for representations of groups. For a DHR endomorphism $`\lambda `$ of the smaller net $`\mathrm{Vir}_c`$, we obtain an endomorphism $`\alpha _\lambda ^\pm `$ of the larger net $`𝒜`$. This is “almost” a DHR endomorphism, but not completely. This operation is regarded as an extension of an endomorphism and depends on a choice $`\pm `$ of the braiding on the system of DHR endomorphisms of the smaller net. This method was defined by Longo-Rehren  and many interesting properties and examples were studied by Xu  and Böckenhauer-Evans . Ocneanu  had a graphical method based on a quite different motivation, and it was unified with the theory of $`\alpha `$-induction by us in . One of the main results in  is that if we define a matrix $`Z`$ by $`Z_{\lambda \mu }=dim\mathrm{Hom}(\alpha _\lambda ^+,\alpha _\mu ^{})`$ for irreducible DHR endomorphisms $`\lambda ,\mu `$ of the smaller net, then this matrix is in the commutant of the unitary representation of $`SL(2,)`$ arising from the braiding on the system of DHR endomorphisms of the smaller net. Obviously, each entry of $`Z`$ is a nonnegative integer and we have $`Z_{00}=1`$ for the vacuum representation denoted by $`0`$. Such a matrix $`Z`$ is called a modular invariant (of the unitary representation of $`SL(2,)`$).

It is easy to see that for a given unitary representation of $`SL(2,)`$, we have only finitely many modular invariants, and this finite number is often quite small in concrete examples. For the Virasoro net $`\mathrm{Vir}_c`$, the corresponding modular invariants have been completely classified by Cappelli-Itzykson-Zuber  and they are labeled with pairs of $`A`$-$`D`$-$`E`$ Dynkin diagrams with difference of the Coxeter numbers being 1. Also it is fairly easy to see in our current context that we have only so-called type I modular invariants in the classification of  where we have only $`A_n`$, $`D_{2n}`$, $`E_6`$, $`E_8`$ diagrams. In this way, starting with a chiral algebraic conformal quantum field theory $`𝒜`$ with central charge less than 1, we obtain a type I modular invariant matrix $`Z`$ in the classification list of  labeled with pairs of the $`A_n`$-$`D_{2n}`$-$`E_{6,8}`$ Dynkin diagrams with difference of the Coxeter numbers being 1. Our main result in  with R. Longo is that this correspondence gives a complete classification of chiral algebraic conformal quantum field theories. Note that we have no reason, a priori, to believe or expect that this correspondence from a conformal field theory to a matrix in a certain list is injective or surjective, but we have proved both injectivity and surjectivity of this correspondence.

Our classification list is as follows.

1. Virasoro nets with central charge $`c=16/m(m+1)`$.
2. Their simple current extensions of index $`2`$.
3. The exceptional net labeled with $`(E_6,A_{12})`$.
4. The exceptional net labeled with $`(E_8,A_{30})`$.
5. The exceptional net labeled with $`(A_{10},E_6)`$.
6. The exceptional net labeled with $`(A_{28},E_8)`$.

The first two of the above exceptional ones are realized as the coset constructions for $`SU(2)_{11}SO(5)_1SU(2)_1`$ and $`SU(2)_{29}(G_2)_1SU(2)_1`$. They were first considered by Böckenhauer-Evans \[1, II, Subsection 5.2\] as possible candidates realizing the corresponding modular invariants in the Cappelli-Itzykson-Zuber list, but they were unable to show that these coset constructions indeed produce the desired modular invariants. With our complete classification, it is easy to identify these cosets with the above two in our list.

Recently, Köster  identified the third exceptional net in the above list , $`(A_{10},E_6)`$, with the two cosets $`SU(9)_2(E_8)_2`$ and $`(E_8)_3(E_8)_2(E_8)_1`$, assuming that the local conformal nets $`(E_8)_k`$ have the expected WZW-fusion rules. The last one, $`(A_{28},E_8)`$, does not seem to be a coset nor an orbifold, and it appears to be a genuine new example.

Carpi  and Xu  recently obtained certain classification results of chiral algebraic conformal quantum field theories with central charge equal to 1, independently.

## 5 Classification of 2-dimensional theories and 2-cohomology

We now explain how to obtain a classification of full algebraic conformal quantum field theories with central charge less than 1, using the results in the previous section. This is our joint work with R. Longo . As we mentioned before, our strategy is to study a subfactor $`𝒜_+(I)𝒜_{}(J)𝒜(I\times J)`$, where $`𝒜(I\times J)`$ is a given full algebraic conformal quantum field theory with central charge 1. By the classification list in the previous section, we have a complete information on the chiral ones $`𝒜_\pm `$.

We now assume the so-called parity symmetry condition for a full algebraic conformal quantum field theory $`𝒜`$, which in particular implies that $`𝒜_+`$ and $`𝒜_{}`$ are isomorphic and they contain the same $`\mathrm{Vir}_c`$. Then the dual canonical endomorphism for the subfactor $`\mathrm{Vir}_c(I)\mathrm{Vir}_c(J)𝒜(I\times J)`$ gives a decomposition $`_{\lambda ,\mu }Z_{\lambda \mu }\lambda \mu `$, where $`\lambda ,\mu `$ are irreducible DHR endomorphisms of $`\mathrm{Vir}_c`$. In a more general setting, the following was conjectured by Rehren and proved by Müger .

###### Theorem 5.1.

Under the above conditions, the following are equivalent.

1. The net $`𝒜`$ has only the trivial representation theory.
2. The $`\mu `$-index of the net $`𝒜`$ is 1.
3. The matrix $`Z`$ above is a modular invariant.

In this way, we obtain a modular invariant $`Z`$ for $`\mathrm{Vir}_c`$ in the classification list of Cappelli-Itzykson-Zuber  from a full algebraic conformal quantum field theory $`𝒜`$ with parity symmetry and trivial representation theory. Then we can prove as in  that a full algebraic conformal quantum field theory $`𝒜`$ with parity symmetry has only the trivial representation theory if and only if it is maximal with respect to extensions. Thus we obtain a modular invariant in  from full algebraic conformal quantum field theory $`𝒜`$ with parity symmetry and maximality. Our main result in  with R. Longo shows that this gives a bijective correspondence. Note that the modular invariants in  are labeled with pairs of $`A`$-$`D`$-$`E`$ Dynkin diagrams with difference of the Coxeter numbers being 1 as before, but we now do not have a restriction to so-called type I modular invariants, so the Dynkin diagrams $`D_{2n+1}`$ and $`E_7`$ do appear.

Surjectivity of this correspondence is not difficult by Rehren’s result , together with our previous analysis in .

To prove injectivity of this correspondence, we need to study the subfactor $`𝒜_+(I)𝒜_{}(J)𝒜(I\times J)`$, where we have a natural identification of $`𝒜_+(I)`$ and $`𝒜_{}(J)`$ and the dual canonical endomorphism decomposes in the form of $`\lambda \lambda `$, where $`\lambda `$ is in a system of irreducible endomorphisms. In subfactor theory, such a subfactor was first studied by Ocneanu  under the name of the asymptotic inclusion and it plays a role of the quantum double construction. (See  and also  for more details.) Popa  gave a quite general construction and named it a symmetric enveloping algebra. Here we use a formulation of Longo-Rehren  where they gave a specific system of $`Q`$-system in the sense of Longo .

Based on , we studied this type of subfactors in  and found that the $`Q`$-system of a general subfactor of this type has a “twist” arising from a 2-cocycle of the tensor category of the endomorphisms. This notion of a 2-cocycle for a tensor category is a generalization of a 2-cocycle for a finite group, so it does not vanish in general, but we have proved in  it always vanishes for the tensor categories of the representation categories of chiral algebraic conformal quantum field theories with central charge less than 1. This 2-cohomology vanishing gives the desired injectivity of the above correspondence from a full algebraic conformal quantum field theory to the modular invariants in .

With extra combinatorial work along the same line, we can drop the triviality condition of the representation theory and classify full algebraic conformal quantum field theories with parity symmetry and central charge less than 1 completely as in .

## Acknowledgments

We gratefully acknowledge the support of GNAMPA-INDAM and MIUR (Italy) and Grants-in-Aid for Scientific Research, JSPS (Japan). We thank R. Longo, A. Matsuo, and C. Schweigert for useful correspondences on the related materials.