Technical details:
about Linear Filtering Method (LFM)

1. Overview of Linear Filtering Method

The Linear Filtering Method (LFM) is a groundbreaking database technology developed by Turbo Data Laboratories. It is covered by numerous patents in Japan and internationally.

Traditionally, the following performance and functional improvements have been demanded from database systems:

  • Safely updating data
  • Handling volumes of data an order of magnitude larger
  • Processing speeds an order of magnitude faster
  • Applicability to analytics
  • Applicability to batch processing to handle complex computer processing
  • Compatibility with a distributed computing environment

Linear Filtering Method can be described as the best solution for most of the above requirements.

2. Strong points of Linear filtering Method

Linear Filtering Method has the following strengths.

1. Computational complexity: O(n)

Makes it possible to reduce the computational complexity of nearly all algorithms to O(n) (n: number of records). Since the computational complexity of a traditional database system is O(n*log(n)), this makes it possible to realize speeds an order of magnitude higher. This is an extremely useful property in handling of Big Data.

2.High-performance, high-speed indexing

Solves a wide range of issues related to indexing, key to increasing the speed and efficiency of a database. Realizes an effective index through repeated processing in multiple stages. Demonstrates overwhelming speed in multistage processing including BOM deployment.

3.Parallel processing

Nearly all database processing can be conducted in parallel. By putting to maximum use the parallel processing functions of the multicore CPUs that have become commonplace in recent years, it can increase processing speeds by several times.

3. Example of Linear Filtering Method of spreadsheet data

In the illustration below, the display of database content (logical rendition) is shown on the left side and the corresponding content of memory (physical rendition) is shown on the right side. Linear Filtering Method converts a logical rendition to a physical rendition.図1

At the top level is the initial state of the database. All items are controlled by ValueNumber, and the actual values of items are placed in ValueLists. All ValueLists are sorted.

In the middle level are the results of processing a search of the upper level. This is processed through the following steps.

  1. Search for items with values of 8 or above in the Age ValueList. Results are 2 and 3 (light processing).
  2. Search for 2 and 3 in the Age ValueNumber. Results are 0, 2, 5, 6, and 7.
  3. Reference 0, 2, 5, 6, and 7 from the Name ValueNumber. Results are 2, 1, 0, 2, and 1.
  4. Reference 2, 1, 0, 2, and 1 from the Name ValueList. Results are Cathy, Beth, Ann, Cathy, and Beth.
  5. Reference 0, 2, 5, 6, and 7 from the Age ValueNumber. Results are 2, 3, 3, 3, and 2.
  6. Reference 2, 3, 3, 3, and 2 from the Age ValueList. Results are 8, 9, 8, 9, and 8.
  7.  The results of processing are the combination of 4 and 6 above.

It is clear from the above that this processing is very lightweight.

The bottom level is the middle level sorted by Name. This is processed through the following steps.

Reference the content of OrderedSet 0, 2, 5, 6, and 7 from the Name ValueNumber. Results are 2, 1, 0, 2, and 1.
2. Sort 2, 1, 0, 2, and 1. Results are 0, 1, 1, 2, and 2.
3. Reference 0, 1, 1, 2, and 2 from the Name ValueList. Results are Ann, Beth, Beth, Cathy, and Cathy.
4. Subsequent steps omitted.

Through the above processing, the physical renditions remain unchanged except for OrderedSet. In other words, there are no changes to the index added by Linear Filtering Method (nonvolatile), which shows how processing is carried out extremely efficiently.

4. Model names of Linear Filtering Method

There is a number of types (models) of Linear Filtering Method. The main types are the 1/3 model, the 3/4 model, and the 3/5 model.

The formats of data broken down through Linear Filtering Method can be categorized as follows. (one-dimensional array)

1.Ascending and unique data (e.g., integers, floating points, text strings)
2.Random integers with defined upper and lower limits
3.(Partial) ascending integers (tree technology)

The model names take the following format: Each linear filtering model has a name n/m where m indicates the number of all types of components used by the model and n indicates the number of types of components in ascending or partial ascending order included in m.

1/3 model: Zap-In (simple, most successful model)
3/4 model: tree
3/5 model: for ultra-parallel special-purpose hardware

5. Reference literature

Shinji Furusho: “General-purpose ultra-high-speed database processing technology: RealTimeVIDP, a universal approach to diverse data structures and ultra-parallel processing” <amazon>