mas01cr@509: extern "C" { mas01cr@509: #include "audioDB_API.h" mas01cr@509: } mas01cr@498: #include "audioDB-internals.h" mas01cr@498: #include "accumulators.h" mas01cr@239: mas01cr@498: bool audiodb_powers_acceptable(const adb_query_refine_t *r, double p1, double p2) { mas01cr@498: if (r->flags & ADB_REFINE_ABSOLUTE_THRESHOLD) { mas01cr@498: if ((p1 < r->absolute_threshold) || (p2 < r->absolute_threshold)) { mas01cr@239: return false; mas01cr@239: } mas01cr@239: } mas01cr@498: if (r->flags & ADB_REFINE_RELATIVE_THRESHOLD) { mas01cr@498: if (fabs(p1-p2) > fabs(r->relative_threshold)) { mas01cr@239: return false; mas01cr@239: } mas01cr@239: } mas01cr@239: return true; mas01cr@239: } mas01cr@239: mas01cr@498: adb_query_results_t *audiodb_query_spec(adb_t *adb, const adb_query_spec_t *qspec) { mas01cr@498: adb_qstate_internal_t qstate = {0}; mas01cr@498: qstate.allowed_keys = new std::set; mas01cr@498: adb_query_results_t *results; mas01cr@498: if(qspec->refine.flags & ADB_REFINE_INCLUDE_KEYLIST) { mas01cr@498: for(unsigned int k = 0; k < qspec->refine.include.nkeys; k++) { mas01cr@498: qstate.allowed_keys->insert(qspec->refine.include.keys[k]); mas01cr@498: } mas01cr@498: } else { mas01cr@498: for(unsigned int k = 0; k < adb->header->numFiles; k++) { mas01cr@498: qstate.allowed_keys->insert((*adb->keys)[k]); mas01cr@498: } mas01cr@498: } mas01cr@498: if(qspec->refine.flags & ADB_REFINE_EXCLUDE_KEYLIST) { mas01cr@498: for(unsigned int k = 0; k < qspec->refine.exclude.nkeys; k++) { mas01cr@498: qstate.allowed_keys->erase(qspec->refine.exclude.keys[k]); mas01cr@498: } mas01cr@498: } mas01mc@292: mas01cr@498: switch(qspec->params.distance) { mas01cr@498: case ADB_DISTANCE_DOT_PRODUCT: mas01cr@498: switch(qspec->params.accumulation) { mas01cr@498: case ADB_ACCUMULATION_DB: mas01cr@498: qstate.accumulator = new DBAccumulator(qspec->params.npoints); mas01cr@498: break; mas01cr@498: case ADB_ACCUMULATION_PER_TRACK: mas01cr@498: qstate.accumulator = new PerTrackAccumulator(qspec->params.npoints, qspec->params.ntracks); mas01cr@498: break; mas01cr@498: case ADB_ACCUMULATION_ONE_TO_ONE: mas01cr@498: qstate.accumulator = new NearestAccumulator(); mas01cr@498: break; mas01cr@498: default: mas01cr@498: goto error; mas01cr@239: } mas01cr@239: break; mas01cr@498: case ADB_DISTANCE_EUCLIDEAN_NORMED: mas01cr@498: case ADB_DISTANCE_EUCLIDEAN: mas01mc@768: case ADB_DISTANCE_KULLBACK_LEIBLER_DIVERGENCE: mas01cr@498: switch(qspec->params.accumulation) { mas01cr@498: case ADB_ACCUMULATION_DB: mas01cr@498: qstate.accumulator = new DBAccumulator(qspec->params.npoints); mas01cr@498: break; mas01cr@498: case ADB_ACCUMULATION_PER_TRACK: mas01cr@498: qstate.accumulator = new PerTrackAccumulator(qspec->params.npoints, qspec->params.ntracks); mas01cr@498: break; mas01cr@498: case ADB_ACCUMULATION_ONE_TO_ONE: mas01cr@498: qstate.accumulator = new NearestAccumulator(); mas01cr@498: break; mas01cr@498: default: mas01cr@498: goto error; mas01mc@263: } mas01mc@263: break; mas01cr@239: default: mas01cr@498: goto error; mas01mc@329: } mas01cr@498: mas01cr@498: if((qspec->refine.flags & ADB_REFINE_RADIUS) && audiodb_index_exists(adb->path, qspec->refine.radius, qspec->qid.sequence_length)) { mas01cr@498: if(audiodb_index_query_loop(adb, qspec, &qstate) < 0) { mas01cr@498: goto error; mas01cr@498: } mas01cr@498: } else { mas01cr@498: if(audiodb_query_loop(adb, qspec, &qstate)) { mas01cr@498: goto error; mas01cr@498: } mas01mc@329: } mas01mc@292: mas01cr@498: results = qstate.accumulator->get_points(); mas01cr@498: mas01cr@498: delete qstate.accumulator; mas01cr@498: delete qstate.allowed_keys; mas01cr@498: mas01cr@498: return results; mas01cr@498: mas01cr@498: error: mas01cr@498: if(qstate.accumulator) mas01cr@498: delete qstate.accumulator; mas01cr@498: if(qstate.allowed_keys) mas01cr@498: delete qstate.allowed_keys; mas01cr@498: return NULL; mas01cr@239: } mas01cr@239: mas01cr@498: int audiodb_query_free_results(adb_t *adb, const adb_query_spec_t *spec, adb_query_results_t *rs) { mas01cr@498: free(rs->results); mas01cr@498: free(rs); mas01cr@498: return 0; mas01cr@239: } mas01cr@239: mas01cr@589: /* FIXME: we should check the return values from allocation */ mas01cr@498: static void audiodb_initialize_arrays(adb_t *adb, const adb_query_spec_t *spec, int track, unsigned int numVectors, double *query, double *data_buffer, double **D, double **DD) { mas01cr@239: unsigned int j, k, l, w; mas01cr@239: double *dp, *qp, *sp; mas01mc@768: double a,b, tmp1; mas01mc@768: #ifdef SYMMETRIC_KL mas01mc@768: double tmp2; mas01mc@768: #endif mas01cr@239: mas01cr@498: const unsigned wL = spec->qid.sequence_length; mas01cr@239: mas01cr@239: for(j = 0; j < numVectors; j++) { mas01cr@239: // Sum products matrix mas01cr@498: D[j] = new double[(*adb->track_lengths)[track]]; mas01cr@239: // Matched filter matrix mas01cr@498: DD[j]=new double[(*adb->track_lengths)[track]]; mas01cr@239: } mas01cr@239: mas01cr@239: // Dot product mas01cr@239: for(j = 0; j < numVectors; j++) mas01cr@498: for(k = 0; k < (*adb->track_lengths)[track]; k++){ mas01cr@498: qp = query + j * adb->header->dim; mas01cr@498: sp = data_buffer + k * adb->header->dim; mas01cr@239: DD[j][k] = 0.0; // Initialize matched filter array mas01cr@239: dp = &D[j][k]; // point to correlation cell j,k mas01cr@239: *dp = 0.0; // initialize correlation cell mas01cr@498: l = adb->header->dim; // size of vectors mas01mc@768: if (spec->params.distance!=ADB_DISTANCE_KULLBACK_LEIBLER_DIVERGENCE){ mas01mc@768: while(l--) mas01mc@768: *dp += *qp++ * *sp++; mas01mc@768: } mas01mc@768: else{ // KL mas01mc@768: while(l--){ mas01mc@768: a = *qp++; mas01mc@768: b = *sp++; mas01mc@768: tmp1 = a * log( a / b ); mas01mc@768: if(isnan(tmp1)) mas01mc@768: tmp1=0.0; mas01mc@768: #ifdef SYMMETRIC_KL mas01mc@768: tmp2 = b * log( b / a ); mas01mc@768: if(isnan(tmp2)) mas01mc@768: tmp2=0.0; mas01mc@768: *dp += ( tmp1 + tmp2 ) / 2.0; mas01mc@768: #else mas01mc@768: *dp += tmp1; mas01mc@768: #endif mas01mc@768: } mas01mc@768: } mas01cr@239: } mas01cr@239: mas01cr@239: double* spd; mas01cr@663: if(!(spec->refine.flags & ADB_REFINE_HOP_SIZE)) { mas01cr@239: for(w = 0; w < wL; w++) { mas01cr@239: for(j = 0; j < numVectors - w; j++) { mas01cr@239: sp = DD[j]; mas01cr@239: spd = D[j+w] + w; mas01cr@498: k = (*adb->track_lengths)[track] - w; mas01mc@292: while(k--) mas01mc@292: *sp++ += *spd++; mas01cr@239: } mas01cr@239: } mas01cr@663: } else { mas01cr@675: uint32_t qhop = spec->refine.qhopsize; mas01cr@675: qhop = qhop ? qhop : 1; mas01cr@675: uint32_t ihop = spec->refine.ihopsize; mas01cr@675: ihop = ihop ? ihop : 1; mas01cr@239: for(w = 0; w < wL; w++) { mas01cr@675: for(j = 0; j < numVectors - w; j += qhop) { mas01cr@239: sp = DD[j]; mas01cr@239: spd = D[j+w]+w; mas01cr@675: for(k = 0; k < (*adb->track_lengths)[track] - w; k += ihop) { mas01cr@239: *sp += *spd; mas01cr@675: sp += ihop; mas01cr@675: spd += ihop; mas01cr@239: } mas01cr@239: } mas01cr@239: } mas01cr@239: } mas01cr@239: } mas01cr@239: mas01cr@498: static void audiodb_delete_arrays(int track, unsigned int numVectors, double **D, double **DD) { mas01cr@239: if(D != NULL) { mas01cr@239: for(unsigned int j = 0; j < numVectors; j++) { mas01cr@239: delete[] D[j]; mas01cr@239: } mas01cr@239: } mas01cr@239: if(DD != NULL) { mas01cr@239: for(unsigned int j = 0; j < numVectors; j++) { mas01cr@239: delete[] DD[j]; mas01cr@239: } mas01cr@239: } mas01cr@239: } mas01cr@239: mas01cr@498: int audiodb_read_data(adb_t *adb, int trkfid, int track, double **data_buffer_p, size_t *data_buffer_size_p) { mas01cr@498: uint32_t track_length = (*adb->track_lengths)[track]; mas01cr@498: size_t track_size = track_length * sizeof(double) * adb->header->dim; mas01cr@498: if (track_size > *data_buffer_size_p) { mas01cr@239: if(*data_buffer_p) { mas01cr@239: free(*data_buffer_p); mas01cr@239: } mas01cr@239: { mas01cr@498: *data_buffer_size_p = track_size; mas01cr@498: void *tmp = malloc(track_size); mas01cr@239: if (tmp == NULL) { mas01cr@498: goto error; mas01cr@239: } mas01cr@239: *data_buffer_p = (double *) tmp; mas01cr@239: } mas01cr@239: } mas01cr@239: mas01cr@498: read_or_goto_error(trkfid, *data_buffer_p, track_size); mas01cr@498: return 0; mas01cr@498: mas01cr@498: error: mas01cr@498: return 1; mas01cr@239: } mas01cr@239: mas01cr@498: int audiodb_track_id_datum(adb_t *adb, uint32_t track_id, adb_datum_t *d) { mas01cr@498: off_t track_offset = (*adb->track_offsets)[track_id]; mas01cr@509: if(adb->header->flags & ADB_HEADER_FLAG_REFERENCES) { mas01cr@498: /* create a reference/insert, then use adb_insert_create_datum() */ mas01cr@498: adb_reference_t reference = {0}; mas01cr@509: char features[ADB_MAXSTR], power[ADB_MAXSTR], times[ADB_MAXSTR]; mas01cr@596: lseek_set_or_goto_error(adb->fd, adb->header->dataOffset + track_id * ADB_FILETABLE_ENTRY_SIZE); mas01cr@509: read_or_goto_error(adb->fd, features, ADB_MAXSTR); mas01cr@498: reference.features = features; mas01cr@509: if(adb->header->flags & ADB_HEADER_FLAG_POWER) { mas01cr@596: lseek_set_or_goto_error(adb->fd, adb->header->powerTableOffset + track_id * ADB_FILETABLE_ENTRY_SIZE); mas01cr@509: read_or_goto_error(adb->fd, power, ADB_MAXSTR); mas01cr@498: reference.power = power; mas01cr@498: } mas01cr@509: if(adb->header->flags & ADB_HEADER_FLAG_TIMES) { mas01cr@596: lseek_set_or_goto_error(adb->fd, adb->header->timesTableOffset + track_id * ADB_FILETABLE_ENTRY_SIZE); mas01cr@509: read_or_goto_error(adb->fd, times, ADB_MAXSTR); mas01cr@498: reference.times = times; mas01cr@498: } mas01cr@498: return audiodb_insert_create_datum(&reference, d); mas01cr@498: } else { mas01cr@498: /* initialize from sources of data that we already have */ mas01cr@498: d->nvectors = (*adb->track_lengths)[track_id]; mas01cr@498: d->dim = adb->header->dim; mas01cr@498: d->key = (*adb->keys)[track_id].c_str(); mas01cr@498: /* read out stuff from the database tables */ mas01cr@596: malloc_and_fill_or_goto_error(double *, d->data, adb->header->dataOffset + track_offset, d->nvectors * d->dim * sizeof(double)); mas01cr@509: if(adb->header->flags & ADB_HEADER_FLAG_POWER) { mas01cr@596: malloc_and_fill_or_goto_error(double *, d->power, adb->header->powerTableOffset + track_offset / d->dim, d->nvectors * sizeof(double)); mas01cr@598: } else { mas01cr@598: d->power = NULL; mas01cr@498: } mas01cr@509: if(adb->header->flags & ADB_HEADER_FLAG_TIMES) { mas01cr@596: malloc_and_fill_or_goto_error(double *, d->times, adb->header->timesTableOffset + 2 * track_offset / d->dim, 2 * d->nvectors * sizeof(double)); mas01cr@598: } else { mas01cr@598: d->times = NULL; mas01cr@498: } mas01cr@498: return 0; mas01cr@498: } mas01cr@498: error: mas01cr@580: audiodb_really_free_datum(d); mas01cr@498: return 1; mas01cr@498: } mas01mc@292: mas01cr@498: int audiodb_datum_qpointers(adb_datum_t *d, uint32_t sequence_length, double **vector_data, double **vector, adb_qpointers_internal_t *qpointers) { mas01cr@498: uint32_t nvectors = d->nvectors; mas01cr@498: mas01cr@498: qpointers->nvectors = nvectors; mas01cr@498: mas01cr@498: size_t vector_size = nvectors * sizeof(double) * d->dim; mas01mc@762: *vector_data = new double[vector_size / sizeof(double) ]; mas01cr@498: memcpy(*vector_data, d->data, vector_size); mas01cr@498: mas01mc@762: qpointers->l2norm_data = new double[vector_size / (sizeof(double)*d->dim)]; mas01cr@498: audiodb_l2norm_buffer(*vector_data, d->dim, nvectors, qpointers->l2norm_data); mas01cr@498: audiodb_sequence_sum(qpointers->l2norm_data, nvectors, sequence_length); mas01cr@498: audiodb_sequence_sqrt(qpointers->l2norm_data, nvectors, sequence_length); mas01cr@498: mas01cr@498: if(d->power) { mas01mc@762: qpointers->power_data = new double[vector_size / (sizeof(double)*d->dim)]; mas01cr@498: memcpy(qpointers->power_data, d->power, vector_size / d->dim); mas01cr@498: audiodb_sequence_sum(qpointers->power_data, nvectors, sequence_length); mas01cr@498: audiodb_sequence_average(qpointers->power_data, nvectors, sequence_length); mas01cr@239: } mas01cr@239: mas01cr@498: if(d->times) { mas01cr@498: qpointers->mean_duration = new double[1]; mas01cr@498: *qpointers->mean_duration = 0; mas01cr@498: for(unsigned int k = 0; k < nvectors; k++) { mas01cr@498: *qpointers->mean_duration += d->times[2*k+1] - d->times[2*k]; mas01cr@239: } mas01cr@498: *qpointers->mean_duration /= nvectors; mas01cr@239: } mas01cr@239: mas01cr@498: *vector = *vector_data; mas01cr@498: qpointers->l2norm = qpointers->l2norm_data; mas01cr@498: qpointers->power = qpointers->power_data; mas01cr@498: return 0; mas01cr@498: } mas01cr@498: mas01cr@498: int audiodb_query_spec_qpointers(adb_t *adb, const adb_query_spec_t *spec, double **vector_data, double **vector, adb_qpointers_internal_t *qpointers) { mas01cr@498: adb_datum_t *datum; mas01cr@498: adb_datum_t d = {0}; mas01cr@498: uint32_t sequence_length; mas01cr@498: uint32_t sequence_start; mas01cr@498: mas01cr@498: datum = spec->qid.datum; mas01cr@498: sequence_length = spec->qid.sequence_length; mas01cr@498: sequence_start = spec->qid.sequence_start; mas01cr@498: mas01cr@498: if(datum->data) { mas01cr@498: if(datum->dim != adb->header->dim) { mas01cr@498: return 1; mas01cr@239: } mas01cr@498: /* initialize d, and mark that nothing needs freeing later. */ mas01cr@498: d = *datum; mas01cr@672: d.key = ""; mas01cr@498: datum = &d; mas01cr@498: } else if (datum->key) { mas01cr@498: uint32_t track_id; mas01cr@498: if((track_id = audiodb_key_index(adb, datum->key)) == (uint32_t) -1) { mas01cr@498: return 1; mas01cr@498: } mas01cr@498: audiodb_track_id_datum(adb, track_id, &d); mas01cr@498: } else { mas01cr@498: return 1; mas01cr@239: } mas01cr@239: mas01cr@498: /* FIXME: check the overflow logic here */ mas01cr@498: if(sequence_start + sequence_length > d.nvectors) { mas01cr@498: if(datum != &d) { mas01cr@580: audiodb_really_free_datum(&d); mas01cr@498: } mas01cr@498: return 1; mas01cr@498: } mas01cr@239: mas01cr@498: audiodb_datum_qpointers(&d, sequence_length, vector_data, vector, qpointers); mas01cr@498: mas01cr@498: /* Finally, if applicable, set up the moving qpointers. */ mas01cr@498: if(spec->qid.flags & ADB_QID_FLAG_EXHAUSTIVE) { mas01cr@498: /* the qpointers are already at the start, and so correct. */ mas01cr@498: } else { mas01cr@498: /* adjust the qpointers to point to the correct place in the sequence */ mas01cr@498: *vector = *vector_data + spec->qid.sequence_start * d.dim; mas01cr@498: qpointers->l2norm = qpointers->l2norm_data + spec->qid.sequence_start; mas01cr@498: if(d.power) { mas01cr@498: qpointers->power = qpointers->power_data + spec->qid.sequence_start; mas01cr@239: } mas01cr@498: qpointers->nvectors = sequence_length; mas01cr@239: } mas01cr@498: mas01cr@498: /* Clean up: free any bits of datum that we have ourselves mas01cr@498: * allocated. */ mas01cr@498: if(datum != &d) { mas01cr@580: audiodb_really_free_datum(&d); mas01cr@498: } mas01cr@498: mas01cr@498: return 0; mas01cr@239: } mas01cr@239: mas01cr@498: static int audiodb_set_up_dbpointers(adb_t *adb, const adb_query_spec_t *spec, adb_qpointers_internal_t *dbpointers) { mas01cr@498: uint32_t nvectors = adb->header->length / (adb->header->dim * sizeof(double)); mas01cr@498: uint32_t sequence_length = spec->qid.sequence_length; mas01mc@292: mas01cr@498: bool using_power = spec->refine.flags & (ADB_REFINE_ABSOLUTE_THRESHOLD|ADB_REFINE_RELATIVE_THRESHOLD); mas01cr@498: bool using_times = spec->refine.flags & ADB_REFINE_DURATION_RATIO; mas01cr@498: double *times_table = NULL; mas01cr@498: mas01cr@498: mas01cr@498: dbpointers->nvectors = nvectors; mas01cr@498: dbpointers->l2norm_data = new double[nvectors]; mas01cr@498: mas01cr@498: double *snpp = dbpointers->l2norm_data, *sppp = 0; mas01cr@596: lseek_set_or_goto_error(adb->fd, adb->header->l2normTableOffset); mas01cr@498: read_or_goto_error(adb->fd, dbpointers->l2norm_data, nvectors * sizeof(double)); mas01cr@498: mas01cr@498: if (using_power) { mas01cr@509: if (!(adb->header->flags & ADB_HEADER_FLAG_POWER)) { mas01cr@498: goto error; mas01cr@498: } mas01cr@498: dbpointers->power_data = new double[nvectors]; mas01cr@498: sppp = dbpointers->power_data; mas01cr@596: lseek_set_or_goto_error(adb->fd, adb->header->powerTableOffset); mas01cr@498: read_or_goto_error(adb->fd, dbpointers->power_data, nvectors * sizeof(double)); mas01mc@292: } mas01mc@292: mas01cr@498: for(unsigned int i = 0; i < adb->header->numFiles; i++){ mas01cr@498: size_t track_length = (*adb->track_lengths)[i]; mas01cr@498: if(track_length >= sequence_length) { mas01cr@498: audiodb_sequence_sum(snpp, track_length, sequence_length); mas01cr@498: audiodb_sequence_sqrt(snpp, track_length, sequence_length); mas01cr@498: if (using_power) { mas01cr@498: audiodb_sequence_sum(sppp, track_length, sequence_length); mas01cr@498: audiodb_sequence_average(sppp, track_length, sequence_length); mas01cr@498: } mas01mc@324: } mas01cr@498: snpp += track_length; mas01cr@498: if (using_power) { mas01cr@498: sppp += track_length; mas01mc@324: } mas01mc@292: } mas01mc@292: mas01cr@498: if (using_times) { mas01cr@509: if(!(adb->header->flags & ADB_HEADER_FLAG_TIMES)) { mas01cr@498: goto error; mas01cr@498: } mas01mc@292: mas01cr@498: dbpointers->mean_duration = new double[adb->header->numFiles]; mas01cr@498: mas01cr@596: malloc_and_fill_or_goto_error(double *, times_table, adb->header->timesTableOffset, 2 * nvectors * sizeof(double)); mas01cr@498: for(unsigned int k = 0; k < adb->header->numFiles; k++) { mas01cr@498: size_t track_length = (*adb->track_lengths)[k]; mas01cr@498: unsigned int j; mas01cr@498: dbpointers->mean_duration[k] = 0.0; mas01cr@498: for(j = 0; j < track_length; j++) { mas01cr@498: dbpointers->mean_duration[k] += times_table[2*j+1] - times_table[2*j]; mas01mc@292: } mas01cr@498: dbpointers->mean_duration[k] /= j; mas01mc@292: } mas01cr@498: mas01cr@498: free(times_table); mas01cr@498: times_table = NULL; mas01mc@292: } mas01cr@498: mas01cr@498: dbpointers->l2norm = dbpointers->l2norm_data; mas01cr@498: dbpointers->power = dbpointers->power_data; mas01cr@498: return 0; mas01cr@498: mas01cr@498: error: mas01cr@596: maybe_delete_array(dbpointers->l2norm_data); mas01cr@596: maybe_delete_array(dbpointers->power_data); mas01cr@596: maybe_delete_array(dbpointers->mean_duration); mas01cr@596: maybe_free(times_table); mas01cr@498: return 1; mas01cr@498: mas01mc@292: } mas01mc@292: mas01cr@498: int audiodb_query_queue_loop(adb_t *adb, const adb_query_spec_t *spec, adb_qstate_internal_t *qstate, double *query, adb_qpointers_internal_t *qpointers) { mas01cr@498: adb_qpointers_internal_t dbpointers = {0}; mas01mc@292: mas01cr@498: uint32_t sequence_length = spec->qid.sequence_length; mas01cr@498: bool power_refine = spec->refine.flags & (ADB_REFINE_ABSOLUTE_THRESHOLD|ADB_REFINE_RELATIVE_THRESHOLD); mas01cr@239: mas01cr@498: if(qstate->exact_evaluation_queue->size() == 0) { mas01cr@498: return 0; mas01cr@239: } mas01cr@239: mas01cr@498: /* We are guaranteed that the order of points is sorted by: mas01cr@498: * {trackID, spos, qpos} so we can be relatively efficient in mas01cr@498: * initialization of track data. We assume that points usually mas01cr@498: * don't overlap, so we will use exhaustive dot product evaluation mas01cr@498: * (instead of memoization of partial sums, as in query_loop()). mas01cr@498: */ mas01cr@498: double dist; mas01cr@498: double *dbdata = 0, *dbdata_pointer; mas01cr@589: uint32_t currentTrack = 0x80000000; // KLUDGE: Initialize with a value outside of track index range mas01cr@589: uint32_t npairs = qstate->exact_evaluation_queue->size(); mas01cr@498: while(npairs--) { mas01cr@498: PointPair pp = qstate->exact_evaluation_queue->top(); mas01cr@498: if(currentTrack != pp.trackID) { mas01cr@509: maybe_delete_array(dbdata); mas01cr@509: maybe_delete_array(dbpointers.l2norm_data); mas01cr@509: maybe_delete_array(dbpointers.power_data); mas01cr@509: maybe_delete_array(dbpointers.mean_duration); mas01cr@498: currentTrack = pp.trackID; mas01cr@498: adb_datum_t d = {0}; mas01cr@498: if(audiodb_track_id_datum(adb, pp.trackID, &d)) { mas01cr@498: delete qstate->exact_evaluation_queue; mas01cr@498: return 1; mas01cr@498: } mas01cr@498: if(audiodb_datum_qpointers(&d, sequence_length, &dbdata, &dbdata_pointer, &dbpointers)) { mas01cr@498: delete qstate->exact_evaluation_queue; mas01cr@580: audiodb_really_free_datum(&d); mas01cr@498: return 1; mas01cr@498: } mas01cr@580: audiodb_really_free_datum(&d); mas01cr@498: } mas01cr@589: uint32_t qPos = (spec->qid.flags & ADB_QID_FLAG_EXHAUSTIVE) ? pp.qpos : 0; mas01cr@589: uint32_t sPos = pp.spos; // index into l2norm table mas01cr@498: // Test power thresholds before computing distance mas01cr@498: if( ( (!power_refine) || audiodb_powers_acceptable(&spec->refine, qpointers->power[qPos], dbpointers.power[sPos])) && mas01cr@498: ( qPosnvectors-sequence_length+1 && sPos<(*adb->track_lengths)[pp.trackID]-sequence_length+1 ) ){ mas01cr@498: // Compute distance mas01mc@768: dist = 1.0e9; mas01mc@768: if (spec->params.distance==ADB_DISTANCE_EUCLIDEAN_NORMED || spec->params.distance==ADB_DISTANCE_EUCLIDEAN) mas01mc@768: dist = audiodb_dot_product(query + qPos*adb->header->dim, dbdata + sPos*adb->header->dim, adb->header->dim*sequence_length); mas01mc@768: else if(spec->params.distance==ADB_DISTANCE_KULLBACK_LEIBLER_DIVERGENCE) mas01mc@768: dist = audiodb_kullback_leibler(query + qPos*adb->header->dim, dbdata + sPos*adb->header->dim, adb->header->dim*sequence_length); mas01cr@498: double qn = qpointers->l2norm[qPos]; mas01cr@498: double sn = dbpointers.l2norm[sPos]; mas01cr@498: switch(spec->params.distance) { mas01cr@498: case ADB_DISTANCE_EUCLIDEAN_NORMED: mas01cr@498: dist = 2 - (2/(qn*sn))*dist; mas01cr@498: break; mas01cr@498: case ADB_DISTANCE_EUCLIDEAN: mas01cr@498: dist = qn*qn + sn*sn - 2*dist; mas01cr@498: break; mas01cr@498: } mas01cr@498: if((!(spec->refine.flags & ADB_REFINE_RADIUS)) || mas01cr@509: dist <= (spec->refine.radius + ADB_DISTANCE_TOLERANCE)) { mas01cr@498: adb_result_t r; mas01cr@672: r.ikey = (*adb->keys)[pp.trackID].c_str(); mas01cr@672: r.qkey = spec->qid.datum->key; mas01cr@498: r.dist = dist; mas01cr@498: r.qpos = pp.qpos; mas01cr@498: r.ipos = pp.spos; mas01cr@610: if(qstate->set->find(r) == qstate->set->end()) { mas01cr@610: qstate->set->insert(r); mas01cr@610: qstate->accumulator->add_point(&r); mas01cr@610: } mas01cr@239: } mas01cr@239: } mas01cr@498: qstate->exact_evaluation_queue->pop(); mas01mc@292: } mas01mc@474: mas01mc@315: // Cleanup mas01cr@509: maybe_delete_array(dbdata); mas01cr@509: maybe_delete_array(dbpointers.l2norm_data); mas01cr@509: maybe_delete_array(dbpointers.power_data); mas01cr@509: maybe_delete_array(dbpointers.mean_duration); mas01cr@498: delete qstate->exact_evaluation_queue; mas01cr@498: return 0; mas01mc@292: } mas01mc@292: mas01cr@498: int audiodb_query_loop(adb_t *adb, const adb_query_spec_t *spec, adb_qstate_internal_t *qstate) { mas01cr@498: mas01cr@498: double *query, *query_data; mas01cr@498: adb_qpointers_internal_t qpointers = {0}, dbpointers = {0}; mas01mc@292: mas01cr@498: bool power_refine = spec->refine.flags & (ADB_REFINE_ABSOLUTE_THRESHOLD|ADB_REFINE_RELATIVE_THRESHOLD); mas01cr@239: mas01cr@509: if(adb->header->flags & ADB_HEADER_FLAG_REFERENCES) { mas01cr@498: /* FIXME: actually it would be nice to support this mode of mas01cr@498: * operation, but for now... */ mas01cr@498: return 1; mas01cr@498: } mas01mc@324: mas01cr@498: if(audiodb_query_spec_qpointers(adb, spec, &query_data, &query, &qpointers)) { mas01cr@498: return 1; mas01cr@498: } mas01cr@239: mas01cr@498: if(audiodb_set_up_dbpointers(adb, spec, &dbpointers)) { mas01cr@498: return 1; mas01cr@498: } mas01cr@239: mas01cr@663: unsigned j,k,track,trackOffset=0; mas01cr@498: unsigned wL = spec->qid.sequence_length; mas01cr@239: double **D = 0; // Differences query and target mas01cr@239: double **DD = 0; // Matched filter distance mas01cr@239: mas01cr@498: D = new double*[qpointers.nvectors]; // pre-allocate mas01cr@498: DD = new double*[qpointers.nvectors]; mas01cr@239: mas01cr@675: unsigned qhop, ihop; mas01cr@663: mas01cr@663: if(spec->refine.flags & ADB_REFINE_HOP_SIZE) { mas01cr@675: qhop = spec->refine.qhopsize; mas01cr@675: qhop = qhop ? qhop : 1; mas01cr@675: ihop = spec->refine.ihopsize; mas01cr@675: ihop = ihop ? ihop : 1; mas01cr@663: } else { mas01cr@675: qhop = 1; mas01cr@675: ihop = 1; mas01cr@663: } mas01cr@239: off_t trackIndexOffset; mas01cr@239: mas01cr@239: // Track loop mas01cr@239: size_t data_buffer_size = 0; mas01cr@239: double *data_buffer = 0; mas01cr@498: lseek(adb->fd, adb->header->dataOffset, SEEK_SET); mas01cr@239: mas01cr@498: std::set::iterator keys_end = qstate->allowed_keys->end(); mas01cr@498: for(track = 0; track < adb->header->numFiles; track++) { mas01cr@498: unsigned t = track; mas01cr@498: mas01cr@498: while (qstate->allowed_keys->find((*adb->keys)[track]) == keys_end) { mas01cr@498: track++; mas01cr@498: if(track == adb->header->numFiles) { mas01cr@498: goto loop_finish; mas01cr@239: } mas01cr@239: } mas01cr@498: trackOffset = (*adb->track_offsets)[track]; mas01cr@498: if(track != t) { mas01cr@498: lseek(adb->fd, adb->header->dataOffset + trackOffset, SEEK_SET); mas01cr@498: } mas01cr@498: trackIndexOffset = trackOffset / (adb->header->dim * sizeof(double)); // dbpointers.nvectors offset mas01cr@239: mas01cr@498: if(audiodb_read_data(adb, adb->fd, track, &data_buffer, &data_buffer_size)) { mas01cr@498: return 1; mas01mc@292: } mas01cr@498: if(wL <= (*adb->track_lengths)[track]) { // test for short sequences mas01cr@498: mas01cr@498: audiodb_initialize_arrays(adb, spec, track, qpointers.nvectors, query, data_buffer, D, DD); mas01mc@292: mas01cr@498: if((!(spec->refine.flags & ADB_REFINE_DURATION_RATIO)) || mas01cr@498: fabs(dbpointers.mean_duration[track]-qpointers.mean_duration[0]) < qpointers.mean_duration[0]*spec->refine.duration_ratio) { mas01cr@239: mas01cr@239: // Search for minimum distance by shingles (concatenated vectors) mas01cr@675: for(j = 0; j <= qpointers.nvectors - wL; j += qhop) { mas01cr@675: for(k = 0; k <= (*adb->track_lengths)[track] - wL; k += ihop) { mas01cr@498: double thisDist = 0; mas01cr@498: double qn = qpointers.l2norm[j]; mas01cr@498: double sn = dbpointers.l2norm[trackIndexOffset + k]; mas01cr@498: switch(spec->params.distance) { mas01cr@498: case ADB_DISTANCE_EUCLIDEAN_NORMED: mas01cr@498: thisDist = 2-(2/(qn*sn))*DD[j][k]; mas01cr@498: break; mas01cr@498: case ADB_DISTANCE_EUCLIDEAN: mas01cr@498: thisDist = qn*qn + sn*sn - 2*DD[j][k]; mas01cr@498: break; mas01cr@498: case ADB_DISTANCE_DOT_PRODUCT: mas01cr@498: thisDist = DD[j][k]; mas01cr@498: break; mas01cr@498: } mas01cr@239: // Power test mas01cr@498: if ((!power_refine) || audiodb_powers_acceptable(&spec->refine, qpointers.power[j], dbpointers.power[trackIndexOffset + k])) { mas01cr@239: // radius test mas01cr@498: if((!(spec->refine.flags & ADB_REFINE_RADIUS)) || mas01cr@509: thisDist <= (spec->refine.radius + ADB_DISTANCE_TOLERANCE)) { mas01cr@498: adb_result_t r; mas01cr@672: r.ikey = (*adb->keys)[track].c_str(); mas01cr@672: r.qkey = spec->qid.datum->key; mas01cr@498: r.dist = thisDist; mas01cr@498: if(spec->qid.flags & ADB_QID_FLAG_EXHAUSTIVE) { mas01cr@498: r.qpos = j; mas01cr@498: } else { mas01cr@498: r.qpos = spec->qid.sequence_start; mas01cr@498: } mas01cr@498: r.ipos = k; mas01cr@498: qstate->accumulator->add_point(&r); mas01cr@239: } mas01cr@239: } mas01cr@239: } mas01cr@239: } mas01cr@239: } // Duration match mas01cr@498: audiodb_delete_arrays(track, qpointers.nvectors, D, DD); mas01cr@239: } mas01cr@239: } mas01cr@239: mas01cr@498: loop_finish: mas01cr@498: mas01cr@239: free(data_buffer); mas01cr@596: maybe_delete_array(query_data); mas01cr@596: maybe_delete_array(qpointers.power_data); mas01cr@596: maybe_delete_array(qpointers.l2norm_data); mas01cr@596: maybe_delete_array(qpointers.mean_duration); mas01cr@596: maybe_delete_array(dbpointers.power_data); mas01cr@596: maybe_delete_array(dbpointers.l2norm_data); mas01cr@596: maybe_delete_array(dbpointers.mean_duration); mas01cr@596: maybe_delete_array(D); mas01cr@596: maybe_delete_array(DD); mas01cr@498: mas01cr@498: return 0; mas01cr@239: }