GiST seems to drop left-branch leaf tuples

One minor correction:

postgres=# explain select count(*) from fps2 f1 join fps2 f2 on
f1.fingerprint = f2.fingerprint;
QUERY PLAN
------------------------------------------------------------------------------------------------
Aggregate (cost=1173.67..1173.68 rows=1 width=0)
-> Nested Loop (cost=0.00..1170.54 rows=1250 width=0)
-> Seq Scan on fps2 f1 (cost=0.00..105.00 rows=500 width=32)
-> Index Scan using fps2_fingerprint_ix on fps2 f2
(cost=0.00..2.11 rows=2 width=32)
Index Cond: (f1.fingerprint = f2.fingerprint)

(The previous query example used the ~= operator which was defined to
match at > .5 but in this case there no matches in the table so ~= is
the same as =.)

On Nov 22, 2010, at 4:18 PM, Peter Tanski wrote:

On 22.11.2010 23:18, Peter Tanski wrote:

Whatever test I use for Same(), Penalty() and Consistent() does not seem
to affect the problem significantly. For now I am only using
Consistent() as a check for retrieval.

I believe it's not possible to lose leaf tuples with incorrectly defined
gist support functions. You might get completely bogus results, but the
tuples should be there when you look at gist_tree() output. So this
sounds like a gist bug to me.

Note that there are only 133 leaf tuples -- for 500 rows. If the index
process were operating correctly, there should have been 500 leaf tuples
there. If I REINDEX the table the number of leaf tuples may change
slightly but not by much.

One idea for debugging is to insert the rows to the table one by one,
and run the query after each insertion. When do the leaf tuples disappear?

If you can put together a small self-contained test case and post it to
the list, I can take a look.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Thanks for the advice. I ran a row-by-row test, including debug output. I'll put a test case together as well but I believe I have narrowed down the problem somewhat. The first split occurrs when the 6th row is inserted and there are 6 calls to Compress(), however picksplit only receives 4 of those 6 tuples and the other two are dropped.

postgres=# \i xaa
psql:xaa:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# select gist_stat('fps2_fingerprint_ix');
gist_stat
---------------------------------------
Number of levels: 1 +
Number of pages: 1 +
Number of leaf pages: 1 +
Number of tuples: 1 +
Number of invalid tuples: 0 +
Number of leaf tuples: 1 +
Total size of tuples: 1416 bytes+
Total size of leaf tuples: 1416 bytes+
Total size of index: 8192 bytes+

postgres=# \i xab
psql:xab:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# select gist_stat('fps2_fingerprint_ix');
gist_stat
---------------------------------------
Number of levels: 1 +
Number of pages: 1 +
Number of leaf pages: 1 +
Number of tuples: 2 +
Number of invalid tuples: 0 +
Number of leaf tuples: 2 +
Total size of tuples: 2820 bytes+
Total size of leaf tuples: 2820 bytes+
Total size of index: 8192 bytes+

postgres=# \i xac
psql:xac:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# select gist_stat('fps2_fingerprint_ix');
gist_stat
---------------------------------------
Number of levels: 1 +
Number of pages: 1 +
Number of leaf pages: 1 +
Number of tuples: 3 +
Number of invalid tuples: 0 +
Number of leaf tuples: 3 +
Total size of tuples: 4224 bytes+
Total size of leaf tuples: 4224 bytes+
Total size of index: 8192 bytes+

postgres=# \i xad
psql:xad:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# select gist_stat('fps2_fingerprint_ix');
gist_stat
---------------------------------------
Number of levels: 1 +
Number of pages: 1 +
Number of leaf pages: 1 +
Number of tuples: 4 +
Number of invalid tuples: 0 +
Number of leaf tuples: 4 +
Total size of tuples: 5628 bytes+
Total size of leaf tuples: 5628 bytes+
Total size of index: 8192 bytes+

postgres=# \i xae
psql:xae:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# select gist_stat('fps2_fingerprint_ix');
gist_stat
---------------------------------------
Number of levels: 1 +
Number of pages: 1 +
Number of leaf pages: 1 +
Number of tuples: 5 +
Number of invalid tuples: 0 +
Number of leaf tuples: 5 +
Total size of tuples: 7032 bytes+
Total size of leaf tuples: 7032 bytes+
Total size of index: 8192 bytes+

postgres=# \i xaf
psql:xaf:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:421] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:421] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:421] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:421] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:421] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:421] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_picksplit:660] entered picksplit
psql:xaf:1: NOTICE: [pgfprint.c:fprint_picksplit:812] split: 2 left, 2 right
psql:xaf:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# select gist_stat('fps2_fingerprint_ix');
gist_stat
----------------------------------------
Number of levels: 2 +
Number of pages: 3 +
Number of leaf pages: 2 +
Number of tuples: 6 +
Number of invalid tuples: 0 +
Number of leaf tuples: 4 +
Total size of tuples: 8460 bytes +
Total size of leaf tuples: 5640 bytes +
Total size of index: 24576 bytes+

postgres=#

There are checks inside the Picksplit() function for the number of entries:

OffsetNumber maxoff = entryvec->n - 1;
int n_entries, j;
n_entries = Max(maxoff, 1) - 1;

j = 0;
for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) {
FPrint* v = deserialize_fprint(entv[i].key);
if (!GIST_LEAF(&entv[i])) {
leaf_split = false;
}
if (v == NULL) {
elog(ERROR, "entry %d is invalid", i);
}
raw_vec[j] = v;
vec_ixs[j++] = i;
}
if (n_entries > j) {
elog(WARNING, "[%s:%s:%d]: " SIZE_T_FMT " bad entries",
__FILE__, __func__, __LINE__, n_entries - j);
n_entries = j;
} else if (n_entries < j) {
elog(ERROR, "skipping %d entries", j-n_entries);
}

So I know the number of entries sent to Picksplit() is 4, for 6 calls to decompress.

Note that Decompress() returns the input unchanged and entries are untoasted in the deserialize_fprint() function, which malloc's each value:

Datum fprint_decompress(PG_FUNCTION_ARGS) {
GISTENTRY* entry = (GISTENTRY*)PG_GETARG_POINTER(0);

FPDEBUG("entered decompress");

if (!entry) {
elog(ERROR, "fprint_decompress: entry is NULL");
}

// cut out here -- we handle the memory
PG_RETURN_POINTER(entry);
}

I'll put together a test case and send that on.

On Nov 23, 2010, at 2:29 AM, Heikki Linnakangas wrote:

Excerpts from Peter Tanski's message of mar nov 23 12:00:52 -0300 2010:

There are checks inside the Picksplit() function for the number of entries:

OffsetNumber maxoff = entryvec->n - 1;
int n_entries, j;
n_entries = Max(maxoff, 1) - 1;

j = 0;
for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) {
FPrint* v = deserialize_fprint(entv[i].key);

Isn't this off by one? Offset numbers are 1-based, so the maxoff
computation is wrong.

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Picksplit() seems to be an exceptional case here: the first and last
numbers in entryvec are invalid so

entryvec->vector[entryvec->n - 1]

is invalid. All the other GiST code Picksplit() functions use the
same convention. For example, see the btree_gist picksplit function, at
http://doxygen.postgresql.org/btree__utils__num_8c-source.html#l00241

OffsetNumber i,
maxoff = entryvec->n - 1;

On Nov 23, 2010, at 10:22 AM, Alvaro Herrera wrote:

I should correct what I just wrote: the first and last entries in
entryvec->vector are invalid.

On Nov 23, 2010, at 11:39 AM, Peter Tanski wrote:

On Nov 23, 2010, at 1:37 PM, Yeb Havinga wrote:

j = 0;
for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) {
FPrint* v = deserialize_fprint(entv[i].key);

Isn't this off by one? Offset numbers are 1-based, so the maxoff
computation is wrong.

The first for loop of all others compare with i <= maxoff instead of i < maxoff.

You are right: I am missing the last one, there. (During a memory-debugging phase entv[entryvec-n - 1] was always invalid, probably as a memory overwrite error but I fixed that later and never changed it back.)

On the other hand, there are two problems:

1. the maximum size on a GiST page is 4240 bytes, so I cannot add a full-size Datum using this kind of hash-key setup (the base Datum size is 4230 bytes on a 64-bit machine). The example test cases I used were smaller in order to get around that issue: they are 2326 bytes base size.

2. Even after fixing the Picksplit() loop, the dropped-leaf problem still manifests itself:

postgres=# set enable_seqscan=false;
SET
postgres=# set enable_indexscan=true;
SET
postgres=# create table fps2 (id serial, soid character(24) not null, fingerprint fprint not null);
NOTICE: CREATE TABLE will create implicit sequence "fps2_id_seq" for serial column "fps2.id"
CREATE TABLE
postgres=# create index fps2_fingerprint_ix on fps2 using gist (fingerprint fprint_gist_ops);
CREATE INDEX
postgres=# \i xaa
psql:xaa:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# \i xab
psql:xab:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# \i xac
psql:xac:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# \i xad
psql:xad:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# select gist_stat('fps2_fingerprint_ix');
gist_stat
---------------------------------------
Number of levels: 1 +
Number of pages: 1 +
Number of leaf pages: 1 +
Number of tuples: 4 +
Number of invalid tuples: 0 +
Number of leaf tuples: 4 +
Total size of tuples: 5628 bytes+
Total size of leaf tuples: 5628 bytes+
Total size of index: 8192 bytes+

postgres=# \i xae
psql:xae:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# select gist_stat('fps2_fingerprint_ix');
gist_stat
---------------------------------------
Number of levels: 1 +
Number of pages: 1 +
Number of leaf pages: 1 +
Number of tuples: 5 +
Number of invalid tuples: 0 +
Number of leaf tuples: 5 +
Total size of tuples: 7032 bytes+
Total size of leaf tuples: 7032 bytes+
Total size of index: 8192 bytes+

postgres=# \i xaf
psql:xaf:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_picksplit:659] entered picksplit
psql:xaf:1: NOTICE: [pgfprint.c:fprint_picksplit:838] split: 3 left, 2 right
psql:xaf:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xaf:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
INSERT 0 1
postgres=# select gist_stat('fps2_fingerprint_ix');
gist_stat
----------------------------------------
Number of levels: 2 +
Number of pages: 3 +
Number of leaf pages: 2 +
Number of tuples: 7 +
Number of invalid tuples: 0 +
Number of leaf tuples: 5 +
Total size of tuples: 9864 bytes +
Total size of leaf tuples: 7044 bytes +
Total size of index: 24576 bytes+

postgres=# select id, soid from fps2;
id | soid
----+--------------------------
1 | 4c65a39d4d9bca2c33000082
2 | 4c65a39d4d9bca2c3300008a
3 | 4c65a39d4d9bca2c33000090
4 | 4c65a39d4d9bca2c33000099
5 | 4c65a39d4d9bca2c330000a5
6 | 4c65a39d4d9bca2c330000a8

postgres=# select f1.id, f2.id, fprint_cmp(f1.fingerprint, f2.fingerprint) from fps2 f1 join fps2 f2 on f1.fingerprint=f2.fingerprint;
id | id | fprint_cmp
----+----+------------------
1 | 1 | 1.00031467691569
2 | 2 | 1.00031467691569
4 | 4 | 1.00031467691569
5 | 5 | 1.00031467691569
6 | 6 | 1.00031467691569

So GiST does not include a tuple for row 3; one of the old tuples.

After inserting a few more rows to trigger another Picksplit():

postgres=# \i xag
psql:xag:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xag:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xag:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xag:1: NOTICE: [pgfprint.c:fprint_penalty:913] entered penalty
psql:xag:1: NOTICE: [pgfprint.c:fprint_penalty:935] penalty: 703.4312133789062500
psql:xag:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xag:1: NOTICE: [pgfprint.c:fprint_penalty:913] entered penalty
psql:xag:1: NOTICE: [pgfprint.c:fprint_penalty:935] penalty: 832.1127319335937500
psql:xag:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xag:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xag:1: NOTICE: [pgfprint.c:fprint_union:453] entered union
psql:xag:1: NOTICE: [pgfprint.c:fprint_same:951] entered same
psql:xag:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xag:1: NOTICE: [pgfprint.c:fprint_compress:384] returning non-leafkey entry raw
INSERT 0 1
postgres=# \i xah
psql:xah:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xah:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xah:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xah:1: NOTICE: [pgfprint.c:fprint_penalty:913] entered penalty
psql:xah:1: NOTICE: [pgfprint.c:fprint_penalty:935] penalty: 880.7246093750000000
psql:xah:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xah:1: NOTICE: [pgfprint.c:fprint_penalty:913] entered penalty
psql:xah:1: NOTICE: [pgfprint.c:fprint_penalty:935] penalty: 903.4860839843750000
psql:xah:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xah:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xah:1: NOTICE: [pgfprint.c:fprint_union:453] entered union
psql:xah:1: NOTICE: [pgfprint.c:fprint_same:951] entered same
psql:xah:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xah:1: NOTICE: [pgfprint.c:fprint_compress:384] returning non-leafkey entry raw
INSERT 0 1
postgres=# \i xai
psql:xai:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xai:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xai:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xai:1: NOTICE: [pgfprint.c:fprint_penalty:913] entered penalty
psql:xai:1: NOTICE: [pgfprint.c:fprint_penalty:935] penalty: 904.7127075195312500
psql:xai:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xai:1: NOTICE: [pgfprint.c:fprint_penalty:913] entered penalty
psql:xai:1: NOTICE: [pgfprint.c:fprint_penalty:935] penalty: 907.4243164062500000
psql:xai:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xai:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xai:1: NOTICE: [pgfprint.c:fprint_union:453] entered union
psql:xai:1: NOTICE: [pgfprint.c:fprint_same:951] entered same
psql:xai:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xai:1: NOTICE: [pgfprint.c:fprint_compress:384] returning non-leafkey entry raw
INSERT 0 1
postgres=# \i xaj
psql:xaj:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_penalty:913] entered penalty
psql:xaj:1: NOTICE: [pgfprint.c:fprint_penalty:935] penalty: 910.3089599609375000
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_penalty:913] entered penalty
psql:xaj:1: NOTICE: [pgfprint.c:fprint_penalty:935] penalty: 906.1793212890625000
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_picksplit:659] entered picksplit
psql:xaj:1: NOTICE: [pgfprint.c:fprint_picksplit:838] split: 2 left, 3 right
psql:xaj:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_compress:384] returning non-leafkey entry raw
psql:xaj:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_compress:384] returning non-leafkey entry raw
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_decompress:419] entered decompress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_union:453] entered union
psql:xaj:1: NOTICE: [pgfprint.c:fprint_compress:379] entered compress
psql:xaj:1: NOTICE: [pgfprint.c:fprint_compress:384] returning non-leafkey entry raw
INSERT 0 1
postgres=# select id, soid from fps2;
id | soid
----+--------------------------
1 | 4c65a39d4d9bca2c33000082
2 | 4c65a39d4d9bca2c3300008a
3 | 4c65a39d4d9bca2c33000090
4 | 4c65a39d4d9bca2c33000099
5 | 4c65a39d4d9bca2c330000a5
6 | 4c65a39d4d9bca2c330000a8
7 | 4c65a39d4d9bca2c330000b0
8 | 4c65a39d4d9bca2c330000be
9 | 4c65a39d4d9bca2c330000c8
10 | 4c65a39d4d9bca2c330000d3
(10 rows)

postgres=# select f1.id, f2.id, fprint_cmp(f1.fingerprint, f2.fingerprint) from fps2 f1 join fps2 f2 on f1.fingerprint=f2.fingerprint;
id | id | fprint_cmp
----+----+------------------
1 | 1 | 1.00031467691569
4 | 4 | 1.00031467691569
5 | 5 | 1.00031467691569
6 | 6 | 1.00031467691569
7 | 7 | 1.00031467691569
8 | 8 | 1.00031467691569
9 | 9 | 1.00031467691569
10 | 10 | 1.00031467691569
(8 rows)

Index tuples for rows 3 and 2 have been dropped.

I found another off-by-one error in my Picksplit() algorithm and the GiST index contains one leaf tuple for each row in the table now. The error was to start from 1 instead of 0 when assigning the entries. Thanks to everyone for your help.

For the record, this is the only GiST index I know of where the keys are over 2000 bytes in size. So GiST definitely handles large keys. Perhaps the maximum size for intarray could be increased.

On Nov 23, 2010, at 4:01 PM, Yeb Havinga wrote:

Peter, glad to know you succeeded. FYI, a year ago we developed GiST
extension for rdkit.org.

Oleg
On Tue, 23 Nov 2010, Peter Tanski wrote:

I found another off-by-one error in my Picksplit() algorithm and the GiST index contains one leaf tuple for each row in the table now. The error was to start from 1 instead of 0 when assigning the entries. Thanks to everyone for your help.

For the record, this is the only GiST index I know of where the keys are over 2000 bytes in size. So GiST definitely handles large keys. Perhaps the maximum size for intarray could be increased.

On Nov 23, 2010, at 4:01 PM, Yeb Havinga wrote:

On 2010-11-23 20:54, Peter Tanski wrote:

On Nov 23, 2010, at 1:37 PM, Yeb Havinga wrote:

j = 0;
for (i = FirstOffsetNumber; i< maxoff; i = OffsetNumberNext(i)) {
FPrint* v = deserialize_fprint(entv[i].key);

Isn't this off by one? Offset numbers are 1-based, so the maxoff
computation is wrong.

The first for loop of all others compare with i<= maxoff instead of i< maxoff.

You are right: I am missing the last one, there. (During a memory-debugging phase entv[entryvec-n - 1] was always invalid, probably as a memory overwrite error but I fixed that later and never changed it back.)

On the other hand, there are two problems:

1. the maximum size on a GiST page is 4240 bytes, so I cannot add a full-size Datum using this kind of hash-key setup (the base Datum size is 4230 bytes on a 64-bit machine). The example test cases I used were smaller in order to get around that issue: they are 2326 bytes base size.

2. Even after fixing the Picksplit() loop, the dropped-leaf problem still manifests itself:

I noticed an n_entries intialization in one of your earlier mails that might also be a source of trouble. I was under the impression that gistentryvectors have n-1 entries (not n-2 as you say), because the first element (0 / InvalidOffsetNumber) must be skipped. E.g. entryvec->n = 5. This means that there are 4 entries, which are in array positions 1,2,3,4.

btw: interesting topic, audio fingerprinting!

regards,
Yeb Havinga

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83