JP5709903B2 - データレコードを圧縮し圧縮されたデータレコードを処理するための方法、システム、コンピュータプログラム、その記録媒体、データコレクションを記憶したデータ記憶媒体、並びに通話データ記録システム - Google Patents

Description

この発明は、特にデータベースシステム内にあるデータレコードからなるデータコレクション（ｄａｔａ ｃｏｌｌｅｃｔｉｏｎ）を処理するための方法に関する。特に、この発明は、データレコードを圧縮し、圧縮されたデータを処理することに関する。この発明はさらに、圧縮されたデータレコードを含むデータ構造製品、データベースコンピュータシステム及びコンピュータプログラムに関する。

データベースの支援により、データコレクションを処理できる。例えば、これらを検索したり、これらを互いに組合せることで評価したりできる。

多くの場合、データコレクションは、データコレクションから生成される二値構造を有するデータレコードの中に、使用されたデータによっては、部分的に二値データ構造がゼロの値のみを含む広い部分領域からなるような形で提供される。データコレクションが生成されるときに、例えば、ごくわずかしか相違しないデータを組合せることができず、２つの異なるデータレコードとして生成することもあり得る。したがってデータベース内のデータレコードの量はしばしば非常に多くなる。

それにも関わらず、データレコードをうまく管理するために、情報を失うことなくデータレコードのサイズを削減するのが趨勢となっている。これは、例えば、データ圧縮によって達成される。

これは、例えば電子形式で記憶されるデータの量が大幅に削減されるので有利である。しかし、データの組合せ等の電子処理動作において、対応の処理動作を行なうためには、圧縮されたデータの各々を完全に伸張して元の状態に戻さなければならない。この伸張処理を行なう結果、処理時間が増大する。

さらに、処理前にデータを元の形に戻さなければならない、又は伸張しなければならないが、データのシーケンシャルな処理しかできない。その理由は、圧縮の種類によって、多くの場合、伸張はシーケンシャルにしかできないからである。データの電子処理の中間結果を記憶するためには、伸張したデータを保持できる非常に大きなランダムアクセスメモリが必要とされる。

ＥＰ０６３３５３７Ｂ１は、圧縮された文書中に記録されている複数個の文字列が圧縮コードで記憶されているような、圧縮された文書の検索方法及びシステムを開示している。クエリリクエストを受信すると、クエリリクエストは圧縮コードに変換され、変換後のクエリリクエストが圧縮された文書中に記憶された圧縮コードと比較される。

ＥＰ０６３３５３７Ｂ１

この発明によれば、請求項１の特徴を含む方法、請求項１５及び１６の特徴を備えたデータ記憶媒体又はデータ構造製品、請求項２２の特徴を備えた圧縮データレコードの処理方法、ならびに請求項２５及び２６の特徴を備えたデータベースコンピュータシステムが、それぞれ提案される。

この発明は、二値構造を備えたデータレコードをいくつかのビットベクトルに分割することを提案する。各ビットベクトルのサイズは、まず、ビットベクトルを、各部分領域がｎビットからなる、等しいサイズの連続した部分領域に分割することで削減される。その後これらの部分領域は、そのコンテンツ構造によってトリビアル部分領域、準トリビアル部分領域、又は非トリビアル部分領域、に分類される。

ビットベクトルの１つ又はいくつかの連続した非トリビアル部分領域を組合せて、Ｒブロックと称される１つのブロックにする。トリビアル部分領域は削除される。１つ又はいくつかの連続した準トリビアル部分領域を組合せて、Ｏブロックと称される１つのブロックにする。

このようにして、データレコードのサイズを大幅に削減できる。

１つのビットベクトルの非トリビアル部分領域を組合せて、Ｒブロックと称される１つのブロックにする場合、それぞれのＲブロックに含まれる最初の非トリビアル部分領域の最初のビットのビットベクトルの絶対位置Ｐ_Ｒと、このＲブロックと称されるもののなかにある連続した非トリビアル部分領域の数ｍ_Ｒとを、Ｒブロック内に記しておくことができる。これによって、Ｒブロックのコンテンツを迅速に判断し、それに従って迅速にデータを検索できる。数ｍ_ＲはＲブロック内の連続した非トリビアル部分領域の計数又は数量を与える。

１つのビットベクトルの準トリビアル部分領域を組合せて、Ｏブロックと称される１つのブロックにする場合、このＯブロックと称されるものに含まれる最初の準トリビアル部分領域の最初のビットのビットベクトルの絶対位置Ｐ_Ｏと、このＯブロックにある連続した準トリビアル部分領域の数ｍ_Ｏとを、Ｏブロック内に記しておくことができる。これによって、Ｒブロックのコンテンツを迅速に判断し、それに従って迅速にデータを検索できる。数ｍ_ＯはＯブロック内の連続した準トリビアル部分領域の計数又は数量を与える。

さらに、準トリビアル部分領域を削除（消去）することもできるので、ビットベクトルのサイズをさらに削減することにつながる。

発明が提案する削減の際に、情報が失われることはない。この削減は、例えば、電子データ処理においてデータの圧縮によって行なわれる。ビットベクトルのサイズが削減されるので、処理すべきデータ量は大幅に削減される。これに関して、本発明は、この圧縮によって各ビットベクトルのサイズが減じられるようにする。この目的のために、ビットベクトルは各々等しいサイズの連続した部分領域に分割され、各部分領域はｎビットからなる。ここで、部分領域は異なる値のビットを含んでもよいし、同じ値のビットのみを含んでもよい。

これを基本に、部分領域を異なる部分領域に分類できる。トリビアル部分領域と準トリビアル部分領域とは、例えば、規則的なビット構造を有する部分領域とすることができる。トリビアル部分領域は、ゼロのみを含む部分領域と定義し、準トリビアル部分領域は１のみを含む部分領域と定義できる。非トリビアル部分領域は１とゼロとの両方を含む部分領域と定義できる。部分領域のそれぞれの名称の上記定義は、例示の目的のみであって限定的なものではない。当然、ビットが値１のみを有する部分領域をトリビアル部分領域と定義し、ビットが値０のみを有する部分領域を準トリビアル部分領域と定義することもできる。

連続した非トリビアル部分領域と、連続した準トリビアル部分領域とを組合せてブロックとすることができる。非トリビアル部分領域は、組合せてＲブロックとすることができる。各Ｒブロックには、各Ｒブロックに含まれる最初の部分領域の最初のビットの、当初の状態のビットベクトル内で存在する位置Ｐ_Ｒを記しておく。さらに、１つのＲブロックに含まれる連続した非トリビアル部分領域の数ｍ_Ｒを記しておくこともできる。もし準トリビアル部分領域又はトリビアル部分領域が非トリビアル部分領域のすぐ後に続く場合、個々の非トリビアル部分領域がＲブロックにされ、ビットベクトル位置Ｐ_Ｒと数ｍ_Ｒ＝１とが記されてもよい。

準トリビアル部分領域は、連続した準トリビアル部分領域を見つけ、各Ｏブロック内に名目上含まれる最初の準トリビアル部分領域の最初のビットの、当初の状態のビットベクトルでのそのビットが存在する絶対位置Ｐ_Ｏを、１つのＯブロック内の連続した準トリビアル部分領域の数ｍ_Ｏと合わせて記しておくことで、実質的に「名目上」組合せることもできる。準トリビアル部分領域を削除して、ビットベクトルの絶対位置Ｐ_Ｏと数ｍ_Ｏとに関する情報のみがＯブロックに残される。もしトリビアル部分領域又は準トリビアル部分領域が準トリビアル部分領域のすぐ後に続く場合には、この準トリビアル部分領域の最初のビットのビットベクトルの絶対位置Ｐ_Ｏと数ｍ_Ｏ＝１のみが記される。

トリビアル部分領域は完全に削除される。

各Ｒブロックに含まれる最初の部分領域の最初のビットの絶対位置とＲブロック内の連続した非トリビアル部分領域の数ｍ_Ｒとを記しておくことにより、各Ｒブロックに含まれるデータを、ビットベクトルを元の状態に戻したり又は伸張したりする必要なしに利用できる。

各Ｏブロックに当初含まれていた準トリビアル部分領域のビットベクトルの絶対位置Ｐ_Ｏと、１つのＯブロック内の当初の連続した準トリビアル部分領域の数ｍ_Ｏとを用いることによって、Ｏブロックはデータレコードの処理においてビットベクトルを元の状態に戻したり又は伸張したりする必要なしにこれらのデータを利用するのに充分な情報を含んでいることになる。

ＯブロックとＲブロックとのビットベクトルの絶対位置Ｐ_ＯとＰ_Ｒとがそれぞれ分かっているため、これらのブロックに含まれるデータをパラレルなデータ処理に用いることが可能になる。したがって、少なくとも２つのビットベクトルを組合せて解又は結果ベクトルとする場合、ビットベクトルの個々のＯブロック及び／又はＲブロックの組合せをパラレルに行なうことができる。これによって、データレコードの極めて迅速な処理が可能になる。さらに、結果として得られるビットベクトルの１ブロック内の、各々ｎ個のビットを有する連続した情報領域をパラレルに処理することもできる。

Ｒブロック内のビットベクトルの絶対位置Ｐ_Ｒと連続した非トリビアル部分領域の数ｍ_Ｒとは、各Ｒブロックの始めに記しておくことができる。これはバイナリ形式で行なうことができる。各Ｒブロックにおいて、ｎビットを有する情報領域を生成し、ここに例えばバイナリ形式で、ビットベクトルの絶対位置Ｐ_ＲとＲブロックにおける連続した非トリビアル部分領域の数ｍ_Ｒとを記しておくことができる。数ｍ_Ｒは情報領域の最終ｘビットで記すことができ、ここでｘ＝ｌｏｇ_２ｎである。この種のラベル付け又は指定に必要なのはわずかなデータ量である。各Ｒブロックの先頭にこの情報領域を設けることにより、Ｒブロックに含まれるデータの処理が簡潔化される。なぜなら、所与のＲブロックの処理を始める時点ですでにそのＲブロック中にいくつのデータがあり、それらのデータがビットベクトルにおいて当初どの位置にあったかが分かっているからである。

各部分領域がｎビットからなり、各Ｒブロックが常に整数個ｍ_Ｒの非トリビアル部分領域を含むので、ビットベクトルの絶対位置Ｐ_Ｒは常にｎの整数倍である。

この結果、ビットベクトルの絶対位置Ｐ_Ｒを、例えばバイナリ形式で記す場合、ｘ＝ｌｏｇ_２ｎとすれば、情報領域の最後のｘビットは常に０のままである。したがって、ビットベクトルの絶対位置Ｐ_Ｒを記すために、情報領域の最後のｘビットは必要とされず、連続した非トリビアル部分領域の数ｍ_Ｒをここに記すことができる。これによって、情報領域に必要とされるデータ量が削減できる。

さらに、排他的に、ビットベクトルの絶対位置Ｐ_Ｏ、１つのＯブロック内に当初含まれていた準トリビアル部分領域の数ｍ_Ｏ、及びＯブロックの識別子を、例えばバイナリ形式でＯブロック内に記すことができる。この場合、各Ｏブロックに、各々がｎビットの第１及び第２の情報領域を生成し、ここに、ビットベクトルの絶対位置Ｐ_ＯとＯブロック内に当初含まれていた準トリビアル部分領域の数ｍ_Ｏとを例えばバイナリ形式で記すようにすることができる。ビットベクトルの絶対位置Ｐ_Ｏを第１の情報領域に記し、数ｍ_Ｏを第２の情報領域に記してもよい（当然、これらを逆にしてもよい）。識別子をさらに第１の情報領域の最後のｘビットに記してもよく、ここでｘ＝ｌｏｇ_２ｎである。例えば、識別又はラベル付けは、値０を有する最後のｘビットに基づいて行なうことができる。

このようにして、ビットベクトルの絶対位置Ｐ_Ｏと数ｍ_Ｏとに関するＯブロック内に含まれる情報に基づいて、必要とする記憶容量の少ないＯブロックが生成され得る。

この発明のある実施例では、数ｍ_Ｒについてｍ_Ｒ＜ｎ−１の関係が成り立つ。さらに、数ｍ_Ｏについて、ｍ_Ｏ≦２^ｎの関係が成り立つ。各ビットベクトルの長さは最大で２^ｎ＋ｎ−１である。

上述のとおり圧縮又は削減されたデータレコードは、少なくとも２つのビットベクトルを選択しその少なくとも２つのビットベクトルを組合せて１つの解ベクトルとすることにより、元の伸張された状態に戻す必要なしに処理することができ、ここでビットベクトルの組合せはビットベクトルのＯブロック及び／又はＲブロックの組合せによって行なわれる。

圧縮されたデータレコードの構造のために、この発明はビットベクトルのＯブロック及び／又はＲブロックのいくつかの組合せをパラレルで行なうことを可能にする。

データレコードの処理は、いくつかのＳＩＭＤプロセッサを含むコンピュータユニットで行なわれても良く（ＳＩＭＤ−ｓｉｎｇｌｅ ｉｎｓｔｒｕｃｔｉｏｎ ｍｕｌｔｉｐｌｅ ｄａｔａ：単一命令複数データ）、ここでパラレルの組合せがいくつかのＳＩＭＤプロセッサに分配される。

この発明はまた、コンピュータプログラムをコンピュータで実行する際に、上述の発明に従った方法を実行するのに好適なプログラムコーディング手段を備えたコンピュータプログラムをカバーする。コンピュータプログラム自体と、コンピュータ可読媒体に記録されたものとが請求項に記載されている。

この発明のさらなる特徴と実施例とは、発明の説明と添付の図面から明らかとなるであろう。

上述の特徴と以下に記載される特徴とは、特定された組合せで使用されるだけでなく、この発明の範囲を逸脱することなく、他の組合せ、又はそれ自体で使用できる。

この発明を概略的に図示し例として実施例を挙げて、以下に図面を参照して詳細に説明する。以下の説明は本件発明の範囲を限定するものではなく、単に発明の好ましい実施例を例示するものであることが理解されるべきである。

発明を例示する概略ブロック図である。 発明を具体化可能なコンピュータデータベースシステムの概略図である。 図２のコンピュータシステムのより詳細なブロック図である。 この発明に従ったＳＩＭＤプロセッサによる処理を例示する図である。

この発明に従った、特にデータベースシステムにおけるデータレコード処理方法は、例えば、通信分野における課金システムの通話データ記録（ｃａｌｌ ｄａｔａ ｒｅｃｏｒｄｓ：ＣＤＲ）のデータベースシステムに利用可能である。

通信サービスのデータコレクションは例えば、データベースシステムに記憶される。データのセットは、例えば、電話番号、通話の持続時間、通話時刻等を含む。データベースシステムによってこれらのデータの評価を行なうことができる。

しかし、データセット又はレコードはしばしば、情報の１つだけ、例えば時刻又は持続時間のみ、が有効であるようなやり方で生成される。例えばある接続で同じ電話番号にすぐ続けて発呼があった場合、これらは２つの独立した通話と見なされ、２つの異なるデータセットが生成される。この結果データの数が非常に多くなる。例えば、ドイツにおいて、このようなデータの数は数十億に及ぶ。

これらデータのコレクションは二値構造を有するデータレコードに変換される。これは例えば、行がそれぞれの通話を表し、列が時刻、持続時間等の対応の条件を示す、マトリックス（ビットマップ）の形であり得る。

このような行列において、二進値１は対応の情報が真であることを意味し、二進値０はこの情報が真でないことを意味する。上述のデータレコードの性質のため、図１に示すようなマトリックスの形の二値構造は値０を有するビットを含む大きな領域を含み、また値１を有する連続した複数個のビットを含む領域もある。

ここで、二値構造をいくつかのビットベクトルに分割することができ、図１の例では各列が１つのビットベクトルを表す。

ここで、ビットベクトルは情報を失うことなくサイズを減じることができる。この目的のために、ビットベクトルは同じサイズの連続した部分領域に分割される。部分領域の各々はｎビットからなる。対応の部分領域を図１に概略的に示す。分かりやすくするために、ビットベクトルの第１の部分領域、ビットベクトルの第３の部分領域、及びビットベクトルの第５の部分領域のみを図１に示す。例示した実施例では、部分領域は各々３２ビットからなり、これは今日の多くのコンピュータで基本的な記憶ユニットが３２ビットからなるためである。より最近のシステムでは６４ビットの基本記憶ユニットを有するものもあり、したがって、当然、６４ビットの部分領域を提供することも可能である。

部分領域は分類される。それぞれ値０及び値１を任意のシーケンスで有する部分領域は、この出願の文脈においては、非トリビアル部分領域である。値１を有するビットのみを排他的に含む部分領域は、いわゆる準トリビアル部分領域である。値０を有するビットのみを排他的に含む部分領域は、いわゆるトリビアル部分領域である。

いくつかの非トリビアル部分領域が組合されて、いわゆるＲブロックとなる。

Ｒブロックにおいて、Ｒブロックの始めにｎビット長の情報領域が生成される。図示の例では、Ｒブロックの情報領域は３２ビット長である。この情報領域に、組合わされてこのＲブロックとなった元のビットベクトルの連続した部分領域の最初のビットの絶対位置が記される。図において、ビットベクトルの絶対位置はオフセットとして指定されている。

図１に示す実施例のように、各々が３２ビットの長さを有する部分領域で、情報領域の最終５ビット、すなわちビット２８から３２は、ビットベクトルの絶対位置Ｐ_Ｒが記されるときに常に不変なので、これらはビットベクトルの絶対位置Ｐ_Ｒを記すのに必要とされない。したがって、ビット２８から３２をＲブロック内の連続した非トリビアル部分領域の数ｍ_Ｒを記すために用いることができる。

図１の表記では、情報領域のビット番号２７は値０を有し、これはビットベクトル位置Ｐ_Ｒもまた０であることを意味する。ビット３２は値１を有し、これはこのブロックに非トリビアル部分領域が含まれることを示す。１つのＲブロックに最大３１個の非トリビアル部分領域が含まれる。もし１ビットベクトルに３１個を超える非トリビアル部分領域が含まれる場合には、これらは２個以上の異なるＲブロックにそれぞれ分割される。

６４ビット長のビットベクトルの場合、情報領域の最終６ビットは空いているので、ビット番号５８から始めて絶対的なビットベクトルが記される。したがって、１つのＲブロック中に６３個の非トリビアル部分領域を含めることができる。

１つの所与のＲブロックに含まれる非トリビアル部分領域の数量である数ｍ_Ｒについて、したがって、ｍ_Ｒ≦ｎ−１の関係が成り立つ。

所与のＲブロックは、例えば図に示した例にあるように、１つの非トリビアル部分領域を含むのみである。

値１を有するビットのみを含む準トリビアル部分領域もまた、組合わされて、Ｏブロックと称されるブロックになる。ここで、これらのブロックは「名目上」組合わされるだけである。これは、この出願の文脈においては、Ｏブロックが単に第１の情報領域と第２の情報領域のみを含みうる、という意味である。

第１の情報領域はこのブロックがＯブロックであるという識別子を含む。さらに、Ｏブロックに名目上含まれる最初の部分領域の最初のビットのビットベクトルの絶対位置が記される。図１の例では、ビットベクトルの絶対位置Ｐ_Ｏは６４であり、したがって第１の情報領域のビット番号２６は値１を有する。この識別は、第１の情報領域においてビット番号２８から３２までが値０を有することで行なわれる。こうして、ＯブロックをＲブロックから区別できる。

第２の情報領域では、Ｏブロックに名目上含まれる準トリビアル部分領域の数量である数ｍ_Ｏが、例えばバイナリ形式で記される。図示の例では、最大２^３２個の準トリビアル部分領域がＯブロックに名目上含まれ得る。

部分領域が６４ビットからなるシステムでは、第１の情報領域のビット番号５９から６４に、これらのビットを０に設定することで識別子を記す。この数はまた、第２の情報領域にも再び記され、したがって、この場合、１つのＯブロックにある名目上連続した準トリビアル部分領域の数は理論的には最大でｍ_Ｏ＝２^６４となる。

その後、この準トリビアル部分領域は削除される。

さらに、ビット値が常に０であるトリビアル部分領域もまた削除される。

こうするにあたって、記憶すべきデータ量を、ビットベクトルの上述の削減又は「圧縮」によって大いに減じることができる。これは特に上で述べたような性質の、値０を有するビット又は値１を有するビットを含む大量のデータが連続して配置されるようなデータレコードに関連して重要である。

圧縮されたデータレコードのさらなる処理において、例えばデータクエリに関連して、少なくとも２つのビットベクトルが選択され組合される。

ビットベクトルの選択は特定の要求に依存する。ビットベクトルの組合せにおいて、ビットベクトルのＯブロック及び／又はＲブロックが組合される。

この目的のために、組合せるべき２つのブロックに交差領域があるか否かを最初に判断する。交差領域はその後単に対応の演算により組合される。これは、例えばＡＮＤ演算又はＯＲ演算であり得る。この結果は解ベクトルに書込まれる。

解は圧縮した形で解ベクトルに書込むことができる。当然、解ベクトルもまた、圧縮しない形で出力することもできる。後者の場合、組合せ後の解ベクトルに残る空のスペースが値０で埋められる。

今や、それぞれの要求（例えば１分又は１時間といった、所与の期間より長く続く通話のクエリ等）を満たす通話を、解ベクトルから検索できる、なぜなら、このような通話に関しては、解ベクトルの対応の位置のビットベクトルが１だからである。

ビットベクトルを組合せる際に、ビットベクトルのＯブロック及び／又はＲブロックの組合せをパラレルに行なうことができる。なぜなら、ブロックにおいてそれらブロックに含まれる部分領域のビットベクトルの絶対位置が知られているからである。特に、組合せるためにビットベクトルをそれらの元の状態に戻す、すなわちそれらを伸張することは
必要とされない。

したがって、組合せの処理において非常に多くの時間を節約できる。さらに、データレコードを処理するためのコンピュータシステムを利用する際に、組合せのための記憶装置の要求が非常に少ない。

図２は本発明の実施例を具体化するコンピュータシステム１０をごく簡潔に示す図である。コンピュータシステム１０は、データ通信のためのバス２２と、処理ユニット１４と、データのセットを記憶するためのデータベース記憶媒体（データベース）２０とを備えたコンピュータ１２を含む。コンピュータシステム１０はさらに、少なくとも１つの入出力装置１８を含み、これは図１の例ではキーボード１８．２、カーソルを制御するためのポインティングデバイス１８．３、及びモニタ１８．１を備えたクライアントである。この少なくとも１つの入出力装置１８は、例えばイントラネットネットワーク内でコンピュータと接続できる。

図３は図１のコンピュータシステム１０をより詳細に示す図である。コンピュータシステム１０は情報通信のためのバス２２又は他の通信機構を含み、さらに、バス２２に結合された、情報処理のためのプロセッサ１４を含む。コンピュータシステム１０はさらに、バス２２に結合され、プロセッサ１４で実行される命令と情報を記憶するための、ランダムアクセスメモリ（ＲＡＭ）又は他の動的記憶装置（例えばダイナミックＲＡＭ（ＤＲＡＭ）、スタティックＲＡＭ（ＳＲＡＭ）及び同期ＤＲＡＭ（ＳＤＲＡＭ））等のメインメモリ２４を含む。

加えて、メインメモリ２４はプロセッサ１４による命令の実行中に一時的な変数又は他の中間情報を記憶するのに用いられてもよい。コンピュータシステム１０はさらに、バス２２に結合されプロセッサ１４のための命令と静的情報を記憶するための、読出専用メモリ（ＲＯＭ）２５又は他の静的記憶装置（例えば、プログラム可能ＲＯＭ（ＰＲＯＭ）、消去可能ＰＲＯＭ（ＥＰＲＯＭ）、電気的に消去可能なＰＲＯＭ（ＥＥＰＲＯＭ））を含む。

コンピュータシステム１０はさらに、バス２２に結合され、磁気ハードディスク２７等の情報及び命令を記憶する１又は２以上の記憶装置を制御するディスク制御装置２６と、取外し可能メディアドライブ２８（フロッピー（登録商標）ディスクドライブ、読出専用コンパクトディスクドライブ、書込／読出コンパクトディスクドライブ、コンパクトディスクジュークボックス、テープドライブ、及び取外し可能磁気−光ドライブ等）とを含む。これらの記憶装置は、適切な装置インターフェィス（例えば、小型コンピュータシステムインターフェィス（ＳＣＳＩ）、統合デバイスエレクトロニクス（ＩＤＥ）、改良ＩＤＥ（Ｅ−ＩＤＥ）、ダイレクトメモリアクセス（ＤＭＡ）又はウルトラＤＭＡ等）を用いてコンピュータシステム１０に付加できる。

コンピュータシステム１０はまた、バス２２に結合され、陰極線管（ＣＲＴ）又は液晶ディスプレイ（ＬＣＤ）等のディスプレイ又はモニタ１８．１を制御してコンピュータユーザに情報を表示するためのディスプレイ制御装置２９を含んでもよい。コンピュータシステムはコンピュータユーザと相互作用しプロセッサ１４に情報を与えるための、キーボード１８．２及びポインティングデバイス１８．３等の入力装置を含む。ポインティングデバイス１８．３は、例えばマウス、トラックボール又はポインティングスティックであって、指示情報及びコマンド選択をプロセッサ１４に伝達し、ディスプレイ１８．１上のカーソルの動きを制御するためのものである。加えて、プリンタがあればコンピュータシステム１０が記憶する及び／生成するデータのリストを提供できる。

コンピュータシステム１０は、プロセッサ１４がメインメモリ２４等のメモリに含まれる１又は２以上の命令の１又は２以上のシーケンスを実行するのに応答して、本発明の処理ステップの全部又は一部を行なう。このような命令は、ハードディスク２７又は取外し可能メディアドライブ２８等の別のコンピュータ可読媒体からメインメモリ２４に読出されてもよい。メインメモリ２４に含まれる命令のシーケンスを実行するために、マルチ処理構成の１又は２以上のプロセッサを用いてもよい。代替的実施例では、ソフトウェア命令に代えて、又はこれと組合せて、ハードワイヤード回路を用いてもよい。すなわち、実施例はハードウェア回路及びソフトウェアの何らかの特定の組合せに限定されるものではない。

電話４０からの通話データがデータリンク接続（無線であってもよい）を介してコンピュータシステムに収集される。この収集されたデータは、この発明に従ってデータ記憶媒体２０に構築されるデータコレクションの一部となる。

上述のとおり、コンピュータシステム１０はこの発明の教示に従ってプログラムされた命令を保持しここで説明したデータ構造、テーブル、レコード又は他のデータを含むための、少なくとも1つのコンピュータ可読媒体又はメモリを含む。コンピュータ可読媒体の例は、コンパクトディスク、ハードディスク、フロッピー（登録商標）ディスク、テープ、磁気光ディスク、ＰＲＯＭ（ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュＥＰＲＯＭ）、ＤＲＡＭ、ＳＲＡＭ、ＳＤＲＡＭ又は他の磁気媒体、コンパクトディスク（ＣＤ−ＲＯＭ等）、又は他の光媒体、パンチカード、紙テープ又は他の穴パターンを備えた物理的媒体、搬送波(以下で述べる）、又はコンピュータが読むことのできる他の何らかの媒体を含む。

本発明は、コンピュータ可読媒体のいずれか、又はそれらの組合せに記憶された、コンピュータシステム１０を制御するためのソフトウェアを含み、これは発明を具体化するための装置を駆動しオペレータ等の人間のユーザと相互作用できるようにコンピュータシステム１０を可能化するためのものである。このようなソフトウェアはデバイスドライバ、オペレーティングシステム、開発ツール及びアプリケーションソフトウェアを含むが、それらに限定されない。このようなコンピュータ可読媒体はさらに、この発明を具体化するために行なわれる処理の全部又は（もし処理が分配されている場合には）一部を実行するための、この発明のコンピュータプログラム製品を含む。

この発明のコンピュータコードデバイスは、スクリプト、翻訳可能プログラム、ダイナミックリンクライブラリ（ＤＬＬ）、Ｊａｖａ（登録商標）クラス、及び完全に実行可能なプログラム等を含むがこれに限定されない何らかの翻訳可能又は実行可能なコード機構であり得る。さらに、この発明の処理の一部は、よりよい性能、信頼性、及び／又は費用のために、分配することもできる。

ここで用いられる「コンピュータ可読媒体」という用語は、実行のためにプロセッサ１４に命令を提供することに関与するすべての媒体をさす。コンピュータ可読媒体は多くの形をとることができ、不揮発性媒体、揮発性媒体、送信媒体を含むがこれらに限定されない。不揮発性媒体は、例えば、ハードディスク２７又は取外し可能メディアドライブ２８等の、光、磁気ディスク、及び磁気−光ディスクを含む。揮発性媒体はメインメモリ２４等のダイナミックメモリを含む。送信媒体は、バス２２を構成する配線を含む、同軸ケーブル、銅線及び光ファイバを含む。送信媒体はまた、電波又は赤外線通信の間に発生する音波又は光波の形をとり得る。

コンピュータシステム１０はさらに、バス２２に結合された通信インターフェイス１６を含む。通信インターフェイス１６は、例えばローカルエリアネットワーク（ＬＡＮ）３２又はインターネット等の別の通信ネットワーク３３に接続されたネットワークリンク３０に結合する２方向のデータ通信を提供する。例えば、通信インターフェイス１６は何らかのパケット交換ＬＡＮに装着されるネットワークインターフェイスカードであり得る。別の例として、通信インターフェイス１６は非対称ディジタル加入者回線（ＡＤＳＬ）カード、総合ディジタル通信網（ＩＳＤＮ）カード又はモデムであって、対応する種類の通信回線にデータ通信接続を提供するものであってもよい。さらにワイヤレスリンクを実現してもよい。このような具体化例のいずれにおいても、通信インターフェイス１６は様々な種類の情報を表すディジタルデータを保持する電気的、電磁的又は光信号を送受信する。

ネットワークリンク３０は典型的には１又は２以上のネットワークを介して他のデータデバイスとのデータ通信を提供する。例えば、ネットワークリンク３０はローカルネットワーク３２（例えばＬＡＮ）を介して、又は通信ネットワーク３３を介して通信サービスを提供するサービスプロバイダによって運営される設備を介して、別のコンピュータに接続を提供してもよい。ローカルネットワーク３０及び通信ネットワーク３３は、例えば、ディジタルデータストリームを保持する電気的、電磁的又は光信号と、関連の物理層（例えばＣＡＴ５ケーブル、同軸ケーブル、光ファイバ等）を用いる。さらに、ネットワークリンク３０は、ＬＡＮ３２を介してパーソナルディジタル端末（ＰＤＡ）、ラップトップコンピュータ、又はセルラー電話等の携帯装置３４への接続を提供してもよい。

この発明に従えば、いくつかのＳＩＭＤ（単一命令複数データ）プロセッサ上で組合せ動作をパラレルに実行できる。これを図４に示す。

図４は（紙面に向かって）左側に２つのビットベクトルＢＶ１及びＢＶ２を示す。これらビットベクトルＢＶ１及びＢＶ２はいくつかのＲブロックとＯブロックとを含み、これらブロックの各々はここでもまた、それぞれビットベクトルの絶対位置Ｐ_Ｒ又はＰ_Ｏと、それぞれこれに従った数ｍ_Ｒ及びｍ_Ｏとから成る。Ｒブロックはまた、データビットシーケンス（図４のビットベクトルの例では右手の列）を含む。Ｏブロックはビットベクトルの絶対位置と連続した準トリビアル部分領域の量／数を反映した数のみを含む。この発明に従えば、準トリビアル部分領域そのものは削除される。

ビットベクトルの処理はこれらを組合せて解又は結果ベクトルＳＢＶにすることで行なわれる。これらは、図４に例示するように、複数個のプロセッサによりパラレルに行なってもよい。図４は３台のプロセッサで２つの図示したビットベクトルＢＶ１及びＢＶ２のＡＮＤ演算を行なう例を示している；しかし、利用可能ないかなる数のプロセッサを用いてもよい。

図４に例示した実施例では、グラフィックカードで利用可能なＳＩＭＤプロセッサを用いてビットベクトルを処理している。この場合、例えば、１コンピュータユニットにいくつかのグラフィックカードが含まれている場合もありうる。

ＳＩＭＤプロセッサは必要とされる組合せタスクに充分である。加えて、これらは通常のコンピュータシステムで多数利用可能である。例えば、強力なグラフィックカードのグラフィックチップは、２５６個のＳＩＭＤプロセッサを含む。この結果、多数の組合せ動作を同時に実行することができ、データ処理を非常に迅速に行なうことができる。

ビットベクトルの組合せはビットベクトルのＯブロック及び／又はＲブロックを組合せることで行なわれる。

当然、この発明に従った方法はまた通信データとは異なるデータレコードについても適用可能である。この発明に従った方法は特に、多数のビット値０又は多数のビット値１が連続した順序で配列されている二値構造を有する種類のデータレコードに特に強力である。

以下にこの発明の様々な局面を番号付リストの形で記載する。
１．特にデータベースシステムにおけるデータコレクションを処理する方法であって、
データコレクションを生成するステップと、
データコレクションを二値構造で配列するステップと、
データレコードをいくつかのビットベクトルに分割するステップと、
各ビットベクトルのサイズを減じるステップとを含み、このステップは
ビットベクトルを、各部分領域がｎビットからなる、等しいサイズの連続した部分領域に分割するサブステップと、
部分領域をトリビアル部分領域、準トリビアル部分領域、及び非トリビアル部分領域に分類するサブステップと、
１つの非トリビアル部分領域又はいくつかの非トリビアル部分領域を組合せてそれぞれＲブロックとし、各Ｒブロックに含まれる最初の非トリビアル部分領域の最初のビットのビットベクトルの絶対位置Ｐ_Ｒと１つのＲブロックに含まれる連続した非トリビアル部分領域の数ｍ_Ｒとを記すサブステップと、
トリビアル部分領域を削除するサブステップと、
１つの準トリビアル部分領域又はいくつかの連続した準トリビアル部分領域を組合せてそれぞれＯブロックとし、各Ｏブロックに含まれる最初の準トリビアル部分領域の最初のビットのビットベクトルの絶対位置Ｐ_Ｏと、１つのＯブロックに含まれる連続した準トリビアル部分領域の数ｍ_Ｏとを記し、準トリビアル部分領域を削除するサブステップとを含み、
前記方法はさらに、
少なくとも２つのビットベクトルを選択し、この少なくとも２つのビットベクトルを組合せて１つの解ベクトルとするステップを含み、ビットベクトルの組合せはビットベクトルのＯブロック及び／又はＲブロックの組合せによって行なわれる、方法。

２．局面１に従った方法であって、少なくとも２つのビットベクトルの組合せにおいて、ビットベクトルのＯブロック及び／又はＲブロックのいくつかの組合せはパラレルに行なわれる、方法。

３．局面１又は２に従った方法であって、ビットベクトルの絶対位置Ｐ_Ｒと１つのＲブロック内の連続した非トリビアル部分領域の数ｍ_Ｒとは、非トリビアル部分領域を有する各Ｒブロックの各々の先頭に、好ましくはバイナリ形式で記される、方法。

４．局面１又は３に従った方法であって、排他的に、ビットベクトルの絶対位置Ｐ_Ｏと、１つのＯブロックに当初含まれていた準トリビアル部分領域の数ｍ_Ｏと、Ｏブロックの識別子とは、好ましくはバイナリ形式でＯブロック内に記される、方法。

５．局面１から４の１つに従った方法であって、数ｍ_Ｒについて、ｍ_Ｒ≦ｎ−１が成り立つ、方法。

６．局面１から５の１つに従った方法であって、数ｍ_Ｏについて、ｍ_Ｏ≦２^ｎが成り立つ、方法。

７．局面１から６の１つに従った方法であって、各ビットベクトルは最大長が２^ｎ＋ｎ−１である、方法。

８．局面３から７のいずれか１つに従った方法であって、各Ｒブロックにおいてｎビットを有する情報領域が生成され、この情報領域に、ビットベクトルの絶対位置Ｐ_Ｒと１つのＲブロックにおける連続した非トリビアル部分領域の数ｍ_Ｒとがバイナリ形式で記され、数ｍ_Ｒは情報領域の最終ｘビットに記され、ここでｘ＝ｌｏｇ_２ｎである、方法。

９．局面４から７のいずれか１つに従った方法であって、各Ｏブロック内に、各々がｎビットを有する第１及び第２の情報領域が生成され、ここにビットベクトルの絶対位置Ｐ_ＯとＯブロックに当初含まれていた準トリビアル部分領域の数ｍ_Ｏとがバイナリ形式で記され、ビットベクトルの絶対位置Ｐ_Ｏは第１の情報領域に記され、数ｍ_Ｏは第２の情報領域に記され、識別子は第１の情報領域の最終ｘビットに記され、ここでｘ＝ｌｏｇ_２ｎである、方法。

１０．局面２から１０のいずれか１つに従った方法であって、いくつかのＳＩＭＤプロセッサを有するコンピュータユニットでパラレルの組合せが行なわれる、方法。

今回開示された実施の形態は単に例示であって、本発明が上記した実施の形態のみに制限されるわけではない。本発明の範囲は、発明の詳細な説明の記載を参酌した上で、特許請求の範囲の各請求項によって示され、そこに記載された文言と均等の意味及び範囲内での全ての変更を含む。

Claims (28)

1. データベースシステムにおいてデータレコードを圧縮する方法であって：
   データレコードに二値構造を与えるステップと；
   データレコードをいくつかのビットベクトルに分割するステップと；
   各ビットベクトルのサイズを、
   ビットベクトルを、各部分領域がｎビットからなる連続した等しいサイズの部分領域に分割し、
   部分領域をトリビアル部分領域、準トリビアル部分領域、及び非トリビアル部分領域に分類し、
   １つの非トリビアル部分領域又はいくつかの連続した非トリビアル部分領域を組合せてそれぞれ１つのＲブロックとし、
   トリビアル部分領域を削除すること、により減じるステップと；
   １つの準トリビアル部分領域又はいくつかの連続した準トリビアル部分領域を組合せてそれぞれ１つのＯブロックとするステップと、を含み、
   １つの非トリビアル部分領域又はいくつかの連続した非トリビアル部分領域を組合せてそれぞれ１つのＲブロックとするステップはさらに、各Ｒブロックに含まれる最初の非トリビアル部分領域の最初のビットのビットベクトルの絶対位置Ｐ _Ｒ と１つのＲブロックにおける連続した非トリビアル部分領域の数ｍ _Ｒ とを記すステップをさらに含む、方法。
2. １つの準トリビアル部分領域又はいくつかの連続した準トリビアル部分領域を組合せてそれぞれ１つのＯブロックとするステップはさらに、各Ｏブロックに含まれる最初の準トリビアル部分領域の最初のビットのビットベクトルの絶対位置Ｐ_Ｏと１つのＯブロックにおける連続した準トリビアル部分領域の数ｍ_Ｏとを記すステップをさらに含む、請求項１に記載の方法。
3. 準トリビアル部分領域を削除するステップをさらに含む、請求項２に記載の方法。
4. ビットベクトルの絶対位置Ｐ_Ｒ及び１つのＲブロック内の連続した非トリビアル部分領域の数ｍ_Ｒは各Ｒブロックの始めに記される、請求項１から請求項３のいずれかに１つに記載の方法。
5. Ｏブロックにおいて、排他的に、ビットベクトルの絶対位置Ｐ_Ｏ、１つのＯブロックに当初含まれていた準トリビアル部分領域の数ｍ_Ｏ及びこのＯブロックの識別子が記される、請求項２から請求項４のいずれか１つに記載の方法。
6. 数ｍ_Ｒについて、ｍ_Ｒ≦ｎ−１が成り立つ、請求項１から請求項５のいずれか１つに記載の方法。
7. 数ｍ_Ｏについて、ｍ_Ｏ≦２^ｎが成り立つ、請求項２から請求項６のいずれか１つに記載の方法。
8. 各ビットベクトルは最大長が２^ｎ＋ｎ−１である、請求項１から請求項７のいずれか１つに記載の方法。
9. 各Ｒブロックにおいてｎビットを有する情報領域を生成するステップをさらに含み、この情報領域に、ビットベクトルの絶対位置Ｐ_Ｒと１つのＲブロックにおける連続した非トリビアル部分領域の数ｍ_Ｒとが記される、請求項４から請求項８のいずれか１つに記載の方法。
10. 数ｍ_Ｒは情報領域の最終ｘビットに記され、ここでｘ＝ｌｏｇ_２ｎである、請求項９に記載の方法。
11. 各Ｏブロック内に、各々がｎビットを有する第１及び第２の情報領域が生成され、この第１及び第２の情報領域にビットベクトルの絶対位置Ｐ_ＯとＯブロックに当初含まれていた準トリビアル部分領域の数ｍ_Ｏとが記される、請求項５から請求項１０のいずれか１つに記載の方法。
12. ビットベクトルの絶対位置Ｐ_Ｏは第１の情報領域に記され、数ｍ_Ｏは第２の情報領域に記される、請求項１１に記載の方法。
13. 識別子は第１の情報領域の最終ｘビットに記され、ここでｘ＝ｌｏｇ_２ｎである、請求項１１又は請求項１２に記載の方法。
14. データコレクションを記憶するためのデータ記憶媒体であって、データコレクションを記憶しており、このデータコレクションは請求項１から請求項１３のいずれか１つに従った方法で圧縮されたデータレコードのセットからなる、データ記憶媒体。
15. データコレクションを記憶するためのデータ記憶媒体であって、データコレクションを記憶しており、このデータコレクションは少なくとも１つのＲブロック及び／又は少なくとも１つのＯブロックに減じられており、このＲブロックはそれぞれのデータレコードの１つの非トリビアル部分領域又はいくつかの連続した非トリビアル部分領域を含み、このＯブロックはそれぞれのデータブロックの１つの準トリビアル部分領域又はいくつかの連続した準トリビアル部分領域を含み、
    ＲブロックはそれぞれのＲブロックに含まれる最初の非トリビアル部分領域の最初のビットのビットベクトルの絶対位置Ｐ _Ｒ と、そのＲブロックにおける連続した非トリビアル部分領域の数ｍ _Ｒ とをさらに含む、データ記憶媒体。
16. ＯブロックはそれぞれのＯブロックに含まれる最初の準トリビアル部分領域の最初のビットのビットベクトルの絶対位置Ｐ_Ｏと、そのＯブロック内の連続した準トリビアル部分領域の数ｍ_Ｏとをさらに含む、請求項１５に記載のデータ記憶媒体。
17. Ｏブロックは、排他的に、ビットベクトルの絶対位置Ｐ_Ｏと、Ｏブロックに当初含まれていた準トリビアル部分領域の数ｍ_Ｏと、そのＯブロックの識別子とを含む、請求項１６に記載のデータ記憶媒体。
18. コンピュータプログラムであって、前記プログラムがデータベースコンピュータシステムで実行されると請求項１から請求項１３のいずれかの方法を行なうプログラムコードを含む、コンピュータプログラム。
19. 請求項１８に記載のコンピュータプログラムが記憶された、コンピュータ読取り可能な記録媒体。
20. 請求項１から請求項１３のいずれか１つの方法に従って圧縮されたデータレコードのセットから成るデータコレクションの処理方法であって、少なくとも２つのビットベクトルを選択し、この少なくとも２つのビットベクトルを組合せて１つの解ベクトルとするステップを含み、ビットベクトルの組合せはビットベクトルのＯブロック及び／又はＲブロックの組合せによって行なわれる、方法。
21. 少なくとも２つのビットベクトルの組合せにおいて、ビットベクトルのＯブロック及び／又はＲブロックのいくつかの組合せはパラレルに行なわれる、請求項２０に記載の方法。
22. いくつかのＳＩＭＤプロセッサを有するコンピュータユニットでパラレルの組合せが行なわれる、請求項２１に記載の方法。
23. 請求項１４から請求項１７のいずれか１つのデータ記憶媒体（２０）を含む、コンピュータデータベースシステム。
24. コンピュータデータベースシステムであって、データ通信のためのバス（２２）及び処理ユニット（１４）、ならびにデータのセット（データレコード）を記憶するためのデータ記憶媒体（２０）を備えたコンピュータ（１２）を含み、コンピュータ（１２）は請求項１から請求項１３のいずれかに従った方法でデータベースシステム内のデータレコードを圧縮し、圧縮されたデータレコードをデータ記憶媒体（２０）に記憶するように設定される、コンピュータデータベースシステム。
25. コンピュータデータベースシステムであって、データ通信のためのバス（２２）及び処理ユニット（１４）、並びにデータのセット（データレコード）を記憶するためのデータ記憶媒体（２０）を備えたコンピュータ（１２）を含み、コンピュータ（１２）は、請求項２０から２２のいずれか１つの方法に従ってデータベースシステム内の圧縮されたデータレコードを処理するように設定される、コンピュータデータベースシステム。
26. コンピュータプログラムであって、前記プログラムがデータベースコンピュータシステムで実行されると請求項２０から請求項２２のいずれか１つの方法を実行するプログラムコード手段を含む、プログラム。
27. 請求項２６のコンピュータプログラムを記憶したコンピュータ読取り可能な記録媒体。
28. 請求項２４又は請求項２５のいずれか１つに従ったデータベースコンピュータシステムを含む、通話データ記録システム。

Images