I detta papper försöker vi att approximera och indexera en ddimensionell (d ≥ 1) spatio-temporal bana med en låg order kontinuerlig polynom. Det finns många möjliga sätt att välja polynom, inklusive (kontinuerlig) Fourier transformer, splines, icke-linjär regression, etc. Vissa av dessa möjligheter har faktiskt studerats tidigare. Vi tror att en av de bästa möjligheterna är polynomet som minimerar den maximala avvikelsen från det sanna värdet, som kallas minimax polynom. Minimax approximation är särskilt betydelsefull för indexering eftersom i en gren-och-bundet sökning (dvs. för att hitta närmaste grannar), ju mindre maximal avvikelse, desto fler beskärningsmöjligheter finns. Men i allmänhet, bland alla polynom av samma grad, den optimala minimax polynom är mycket svårt att beräkna. Det har dock visat sig att Chebysjev approximationen är nästan identisk med den optimala minimax polynom, och är lätt att beräkna [16]. Därför undersöker vi i detta dokument hur man använder Chebysjev polynom som grund för tillnärmning och indexering av d-dimensionella banor. Det viktigaste analytiska resultatet av denna uppsats är Lower Bounding Lemma. Det vill säga, vi visar att det euklideiska avståndet mellan två d-dimensionella banor begränsas lägre av det viktade Euklideiska avståndet mellan de två vektorerna av Chebysjevkoefficienter. Denna lemma är inte trivial att visa, och det säkerställer att indexering med Chebysjev koefficienter medger inga falska negativa. För att komplettera det analytiska resultatet genomförde vi en omfattande experimentell utvärdering med verkliga och genererade 1-dimensionella till 4-dimensionella datamängder. Vi jämförde det föreslagna systemet med Adaptive Piecewise Constant Caimation (APCA). Våra preliminära resultat indikerar att i alla situationer som vi testade, Chebysjev indexering dominerar APCA i beskärning effekt, I/O och CPU kostnader.
I REF, Cai et al. använda Chebysjev polynom som grund för att hantera problemet med approximering och indexering av ddimensionella banor och tidsserier.
Indexing spatio-temporal trajectories with Chebyshev polynomials
{'venue': "SIGMOD '04", 'journal': None, 'mag_field_of_study': ['Computer Science']}