In our information based society we are faced with the task of searching through an enormous amount of data to retrieve meaningful information. In some cases we also require high-speed access subject to numerous search criteria. One example is an Internet web search engine. Such an engine performs its queries using a hierarchical set of keywords, rather than searching the entire database. Given the extent of the database, this proves to be a task for powerful computers with vast amounts of random access memory. Soon the amount of information required will exceed even the capacity of these computers. Similar remarks apply to the human genome project and many other information-oriented fields.
Most conventional massive database and knowledge base systems store data on magnetic or optical disks and employ indexing techniques to minimize disk accesses. Various clustering and accessing techniques are used to reduce response time. Even so, when the joint requirements of very large database (VLDB) and very short response times are imposed, existing technologies degrade considerably. Holographic memories can: (1) store hundreds of billions of bytes of data, (2) transfer them at a rate of a billion or more bits per second and (3) select a randomly chosen data element in 100 microseconds or less because of the 3-D recording and the parallel readout of an entire page of data at one time. There is no other memory technology that offers all three advantages [1
N. N. Vyukhina, I. S. Gibin, V. A. Dombrovsky, S. A. Dombrovsky, B. N. Pankov, E. F. Pen, A. N. Potapov, A. M. Sinyukov, P. E. Tverdokhleb, and V. V. Shelkovnikov, “A review of aspects relating to the improvement of holographic memory technology,” Opt. & Laser Tech.
28, 269–276 (1996). [CrossRef]
Disks and tapes store bits of information, which can be accessed sequentially. A page oriented holographic memory (POHM) stores and retrieves 2D data arrays (pages) in parallel from storage (a thick hologram) containing many such pages. In the recording of each page, a unique reference beam characterized by a parameter P is used. We then change P and record a different page. In replay, we choose the page by selecting P as suggested in Fig. 1
. The first POHMs featured P as spatial position. Most current work uses P as angle. Using P as the index of a coded reference beam also has great potential. With tunable lasers, the use of P as wavelength for P is also attractive. For the most part, those details are not very relevant to the question of how to design a POHM database management system (DBMS) [2
C. Denz, T. Dellwig, J. Lembcke, and T. Tschudi, “Parallel optical image addition and subtraction in a dynamic photorefractive memory by phase-code multiplexing,” Opt. Lett.
21(4), 278–280 (1996). [CrossRef]
Fig. 1. The POHM concept is to vary a parameter P and record a hologram of a page with each P. Then when we restore the P value, we recall the corresponding page.
Each page can contain B bits (usually in the 105–106 range). Typically we store and recall P pages (usually in the 100 to 10,000 range). The random access time in P is T (usually in the 10-3 to 10-7 range). The total storage capacity is C=BP pages and the data random access rate is CÝ=C/T.
Let us illustrate with some achievable values such as B=105 bits, P=1000, and T=10-6 seconds. Then CÝ=1014 bits/s.
These are achievable, fairly conservative numbers. The critical number is CÝ. Ultra-fast electronics can achieve bit rates of 109 bits/sec, a factor of 105 away from keeping up. And that is just the readout capability. Query requires far more complicated operations with attendant massive slow down if done sequential.
If we hope to understand information almost as fast as we can recall it, we must abandon serial electronics in favor of parallel optics.
Driven primarily by the military need to find targets in noisy backgrounds, Fourier optical pattern recognition has improved immensely over the last 35 years. We now have compact systems with fast components implementing “optimum” masks on line [4
“Optimization Methods for Pattern Recognition,” in Optical PatternRecognition , Joseph L. Horner and Bahram Javidi, Eds., SPIE Optical Engr. Press , Bellingham, Washington, (1991),J. Shamir, Joseph Rosen, Uri Mahlaband, and H. J. Caulfield.
]. But, can we apply this parallel recognition method to PHM data pages?
The POHM DBMS problem will require all of those advances and more. This time, the targets are cooperative — as opposed to the military problem. We can design their signatures. Instead of roughly TV frame rates (~30/second), we seek page decisions much faster (~105/sec to 106/sec). SLMs (Spatial Light Modulators) with frame rates in this range are just now coming to market.
The purpose of this paper is to describe optical DBMSs for POHMs. With POHMs we can randomly access data many orders of magnitude faster than we can serialize and digest them electronically. Parallel optical DBMSs may offer the only hope of catching up with the data rate. In this paper we discuss the application of Fourier optical correlators in POHMs and focus on how construct a relational or object oriented DBMS for POHMs with fast access time, and high transfer rate.
3. System overview
The optical DBMS for POHMs is shown in Fig. 6
. Users require access the POHM for querying, updating, and generating reports. The DBM primarily exists for their use. The query is provided in electronic format. Of course, the POHM can not execute such a search. A dedicated computer works as a query controller. It has three tasks:
5. Recognize the query as a special case of something it knows how to do. That is, it must generate a virtual algorithm.
6. Convert the virtual algorithm into a physical algorithm, a series of physical acts to be performed.
7. Carry out the physical algorithm.
Fig. 6. Optical DBMS for POHMs
The query controller controls page accessing. The output light pattern must be operated upon by the DBMS hardware. As light does not operate on light, some electronics must be involved here. We can not do complex queries on multiple pages in parallel. Thus some sort of intermediate scratchpad memory is required. Finally, the answer to the query must be provided in a convenient electronic format. We imagine that this information will be read out from the scratchpad memory where it has been accumulated and processed. In our system, there are two forms of scratchpad memory: the Opto-Electronic RAM (random access memory, VIII in Figure 6
), and the electronic cache (III) that also provides pointers to the opto-electronically stored data.
When we need a particular piece of information, we first check whether it is in the cache. If it is, we use the information directly from the cache; if it is not, the output of searching the POHM will be put in the cache. Then we can obtain what we want from the cache. A copy of the output will be put in the cache under the assumption that there is a high probability that it will be needed again. If the particular information is not in the cache, the computer will send three signals to POHM, flash addressed OERAM and optical pattern recognizer (OPR), respectively.
The POHM has been described in Sec. 1. A POHM will be able to store gigabits of information in the form of “pages”-2D arrangements of data (usually bits). The representation may be direct or encrypted. For example, a 0 might be represented by the pair 0,1; and a 1 by the pair 1,0. The POHM can call forth any of its stored parts in random access mode very quickly, 10-5
sec to 10-9
sec, depending on the system. The whole page appears optically in parallel, with the 1 positions represented by light and the 0 positions by the absence of light. There are many forms of data organization in current use. The POHM will inspire new ones [10
Louri and J. A. Hatch Jr. “An optical associative parallel processor for high-speed database processing,” Computer 27, 65–72, Nov. (1994).
]. We could certainly group similar items on a page if we could guess which variable will be searched most frequently. The query controller could consult its page index electronically and access only the useful pages. Two morphological discriminants among search procedures can be defined here. First, we have the degree of parallelism. Disk based systems produce a bit at a time (for each head). A POHM produces an entire page. Some of our methods will search a bit at a time, a page at a time, and perhaps even a POHM at a time. In general, the greater the parallelism, the faster will be the rate of search. Second, there is a strategy choice for complex queries. We can do the full complex search on each page before moving to the next. Alternatively, we can do a less-than-full search on all of the pages sequentially. There is no generally better choice. It depends largely on the time needed to prepare to search one page. If the time is long compared with the time to switch between pages and if the whole POHM must be searched, scanning through the pages is probably faster. The output light pattern will be used in OPR.
In a RAM, any addressable location in the memory can be accessed at random. That is, the process of reading from and writing into a location in a RAM is the same and consumes an equal amount of time no matter where the location is physically in the memory. With an optically flash addressed OERAM, we can enter the whole page in parallel and read only the pre-selected data into the cache memory.
After receiving the signal from the computer, the OPR will prepare to realize the pattern selection. A physical recognition mask will be used. If the mask can be an electronically addressed SLM, it can be evolved or at least optimized locally on line. Masks can be stored electronically and called into the SLM from memory quite rapidly. In other cases we will prefer an optically addressed SLM. We must avoid serializing the data on a page. An SLM is used to write the page onto a light beam. SLMs can be optically addressed, so serialization can be avoided. The output of OPR is then projected onto a 2-D charge-coupled device (CCD) or perhaps CMOS array that senses light-and-dark patterns and produces currents in response to the patterns, thereby reading all retrieved data. Now the data is in electronic form and send to cache through application specific integrated circuit (ASIC). With the CMOS system, perhaps these functions can be built into the detector array.
In optical processing there are also virtual algorithms and physical algorithms. We sometimes call the latter “archirithms” or “algotecturers” as they are virtual algorithms embodied in an architecture. For parallel search of an optically represented data page, the virtual algorithm of choice is Fourier optics. The virtual algorithm is to takes two successive optical Fourier transforms of an input coherently illuminated pattern. This is an imaging system, which turns the input amplitude pattern f(x,y) into an output image f(-x,-y). In the middle of this imaging system is a spatial display of
the Fourier transform of f(x,y). We now use the shift theorem
That is, the shape and phase of the Fourier transform is independent of (x0,y0o,yo)-the displacement of the input. The displacement information is retained in the Fourier transform domain as a simple phase factor. Suppose now we multiply F(u,v) by a pattern M(u,v) that favors the Fourier transform of the pattern we seek and attenuates other patterns. Then the image plane will contain bright points everywhere the desired pattern occurs.
Fig. 7. Two physical algorithms for Fourier transforms
There are two physical algorithms. Both use a lens to perform the Fourier transforms as two ways of implementing the Fourier transform based optical search are shown in Fig. 7
(a) and in Fig. 7
M(u,v) is a physical mask. This system is widely used. The mask can be an electronically addressed SLM, which can be evolved on line. Masks can be stored electronically and called into the SLM from memory quite quickly. We will call this the serial mask system transform method. The other approach places the search-for pattern next to the input pattern and Fourier transforms them both onto a detector plane that nonlinearly detects the sum of those patterns. This creates product terms-the ones needed in the virtual algorithm. This detected pattern then Fourier transformed to get the desired output pattern. This is called the joint transform method.
We can now compare the effectiveness of the two methods. The physical mask serial transform method and the joint transform method can both be optimized on line. The two methods both require two transform lenses. Both involve a detector array and Fourier transform lenses and SLMs. Both need two SLMs and detector arrays and system to locate the maximum. There are major problems with the joint transform method when there are numerous inputs, in that the dynamic range must be shared among all correlations. There are major problems with the physical mask also problems with the serial transform system if the mask is to be evolved quickly. There are, as of today, no good algorithms for this. On balance and at this moment, the dynamic range problem with the joint transform method appears more troublesome than the mask evolution problem with the serial physical mask transform method.
There are primitive physical algorithms for pages:
Algorithm 1 is called “page search.” We evolve a physical mask to recognize the desired pattern wherever it occurs.
Algorithm 2 is a variation called “limited page search.” We limit the search part of page by blocking the other parts with an SLM or restricting our attention to the key regions of the detector array.
Algorithm 3 incorporates limited page search into a very powerful and very general algorithm, which we call “logical merge.” Suppose we detect two sets of data A and B. We can draw, symbolically, the relationship between A and B as a Venn diagram. See Fig. 8
(see Fig. 8
Fig. 8. Intersection of data A and B
We can then form all sorts of logical merges such as A OR B, A AND B, A AND NOT B, etc. As A and B are found as 2D maps sequentially and B are found sequentially as 2D maps. We can do the merging in various ways. Although there are various ways to do this optically, it is probably easier to scan both maps synchronously and do the logical operations point-by -point electronically. It is easy to use one pass through both masks (stored on scratchpads) to mark patterns that satisfy the required logical pattern. That pattern can be written back into the scratchpad to allow the formation of more complex patterns such as (A OR B) AND NOT C or to store for subsequent output. To store outputs efficiently, we must recall all of the indicated information selected as an answer to the query. Of course, we want to compact this data - leaving no blank spaces corresponding to data not selected. Again, this is a task probably best done electronically.
The operations just described are for single pages. Now we consider the operations on multiple pages. Suppose we want to find A AND B page by page. Alternatively, we could find all of the A-matching items on all pages and remember their locations electronically. We can then search only those regions for B. This reduces the search time significantly only if there are pages on which A items are absent. If we have a relational database, for example, this can be assured ahead of time. A phone book is a relational database. If we want to find all the Smiths with phone numbers beginning with the prefix 369. It senses the locations of the Smiths first, then searches the prefixes only for the Smiths. It would make no sense at all to search for the 369 first. We have reason to believe that the 369s may be fairly randomly distributed. In general, especially when dealing with ANDs, it is desirable to search in this order:
• items likely to be concentrated on a small fraction of the pages,
• items expected to occur at an average rate of less than one per page,
• all other “fairly-unlikely” events, and
• all other events.
Another approach is to accumulate all the As into a compact set on one “page” of cache opto-electronic memory. We can then search this page for B in parallel optically. Depending on the physical speeds of the operations, this is likely to be the fastest multiple page approach.
4. Critical Component analysis
To make the most efficient use of electro-optical input transducers and the storage capacity of volume holographic memory, we need to apply an efficient encoding scheme. Pattern recognition has long strived to “read” human writing, be it in hand-written or machine generated form. This approach to encoding works well, most of the time, for humans, but electronic and optical processors still struggle to read it. Text has a number of problems:
1. A number of similar symbols, F is contained within E, O within Q, etc.,
2. Symbols that are similar to upside down or other symmetry reversed letters, A and V, and u and n are very difficult for optical correlators to distinguish, and
3. It takes a lot of information to form a letter (7x9=63 pixels minimum).
Any encoding scheme we choose has to be able to cleanly distinguish among all symbols in the character set, while reducing the data bandwidth required of the system.
We want to reduce the number of false identifications, even in the presence of noise. There are numerous schemes to encode symbols into orthogonal one- and two-dimensional spaces. We can use these as a staring point. We then stipulate that an auto-correlation should yield a higher peak than any cross-correlation. In effect, we require a Hamming distance proportional to the true-to-false ratio desired. There is a trade-off, however. The greater the Hamming distance, the more data have to be stored and transferred for a given amount of information.
Table 2. Examples of 1-D Hamming codes
|.|| || || || || || || || || || || || || || || || |
|.|| || || || || || || || || || || || || || || || |
|.|| || || || || || || || || || || || || || || || |
Most text-based data is in 7- or 8-bit character sets (ASCII and extended ASCII), let us assume a 7-bit format. The Hamming distance should be chosen relative to the size of this set. In this case a Hamming distance of 3 is the minimum functional value, while 6 is quite adequate. We used a direct computer search to select a 7-bit character set for a Hamming distance of 6. This requires a 16-bit code sequence. In Table 1
we show some examples:
An excellent way of arranging these 1D codes in 2D is to use linear code strings separated by blank space, combined with 1D Fourier transform lenses.
4.2 Computer and data-bus considerations
The speed of the ODBM system is a function of several factors:
1. The electro-optic transducers,
2. The optical components,
3. The opto-electronic transducers, and
4. The front end host computer.
The electro-optic transducers, usually SLMs, are becoming increasingly fast with rates in the kHz regime. The speed of the optical passive components is never an issue. The opto-electronic transducers, CCD arrays, etc., can also be operated at high frame rates.
These high frame rates show the real limitation of a useful optical processor: the drive electronics. The data bandwidth of the optical system components is much greater than that of the electronic system components. If we assume a 512×512 array with a bit-depth of 1, each frame is 32 kB. At the normal video frame rate of 30, this is still a manageable 0.96 MB/sec, but at a frame rate of 10 kHz the required bandwidth becomes 320 MB/sec. One can use data compression to reduce the required bandwidth somewhat, but even for a 10 kHz frame rate the resulting bandwidth is well above what is available on present-day PCs. Some buses such as EISA, ISA, NuBus and VME cannot handle the bandwidth of video rate data, not to mention 10 kHz frame rates. The PCI bus (64 bit/66 MHz) is the best we can do with non-proprietary technology. It can handle a maximal theoretical throughput of 524 MB/sec [11
]. The PCI but, however does not have symmetrical read and write speed With PCI bus systems one can hope to achieve frame rates between 6000 and 12000 per second for a bit depth of 1 compressed data. Proprietary standards such as found Silicon Graphics multiprocessor servers, can exceed 1 GB/sec. These proprietary standards, however, cannot be used as a basis for universal interface cards.
4.3 Optical hardware choices
The heart of the ODBM system is an optical pattern recognizer. There are two such generic systems: (a) the sequential transform correlator (STC) often also called the 4f correlator, even though a shorter 2f version is known and (b) the JTC discussed earlier.
The STC optically performs two Fourier transforms in sequence. The first lens Fourier transforms the input amplitude imposed by the mask (the data to be searched). In the Fourier domain a second mask (containing the complex conjugate of the Fourier transform of the pattern to be identified) multiplies the transformed data. The product is then Fourier transformed yet again to produce the correlation.
The JTC differs in that there is only one Fourier transform lens. The data and the search pattern are introduced side-by-side in the input plane. The first Fourier transform is performed. The intensity pattern in the Fourier plane is captured into a computer that may perform nonlinear operations on it. The resulting pattern is then reintroduced into the optical system. It is again transformed to produce the final output.
The advantages of a STC over a JTC are: (1) no intermediate processing, higher potential speed and (2) a higher signal-to-noise ratio. In a JTC, we must record the virtual masks for each object in the same medium. For multiple objects this places great strains on the available recording media.
The advantages of a JTC over a STC are: (1) More compact, and (2) no pre-stored filters. We prefer a system that combines the advantages of the JTC and STC. A single step system, similar to the JTC can be used to generate filters near real time. These filters can then be inserted into the STC system for pattern recognition.
The POHM serves as the source of the database data, while the search pattern is usually composed on the computer. The addressing speed of the POHM is more important than that of the filter SLM, since the search pattern does not change as frequently as the data to be searched. The method of addressing individual pages in the POHM depends on the way the data is initially stored. For example, if angle is to be multiplexed, an acousto-optic modulator would be a good choice. The speed of filter insertion is limited by the (serial) electronics to (parallel) optics bottleneck. The only way this could be avoided is to pre-store filters. This option is unattractive, since it comes at a loss of generality.
Fig. 9. A diagram of the optical system. Note that the lens system uses cylindrical lenses for 1-D Fourier transforms. The component required for recording the holograms into the POHM are omitted for clarity.
At this point, this system is in the conceptual stage. However, from our analysis of the encryption and Fourier processing options, we have developed a preliminary design for the optical portion of the ODBM. A diagram of this system is shown in Fig. 9
. Due to the choice of 1-D Hamming codes, we have chosen cylindrical lenses to perform the Fourier optical pattern recognition operations.
The POHM is recorded using the acousto-optical (AO) cell and light imaged from a SLM, not shown in Fig. 9
, located above the POHM.
The POHM is read out by light passed through the AO cell. The light passes through a beamsplitter, and is either directly Fourier transformed onto the transform plane SLM, or passed through a register shifting SLM and detected by the OERAM. The OERAM is made up of an array of detectors and modulators with a small number of memory registers associated to each pixel. The OERAM can also be read out a page at a time and Fourier transformed onto the FT SLM. The FT SLM itself can be a 1D or 2D electronic SLM, or an AO cell.
If we choose to use an AO cell in the FT plane, we can change the filters at the same rate as the pages recalled from the POHM.
Once the product of the input and filter has been obtained, the results are again Fourier transformed and imaged onto a CCD array. In order to reduce the required bandwidth to the host computer, there we require thresholding circuitry packaged with the CCD. This optical system has not been built to date. However, we have performed numerical simulations of the response of various input fields and common FT filter types.