Tidsseriemotiv är par av individuella tidsserier, eller undersekvenser av en längre tidsserie, som är mycket lika varandra. Som med deras diskreta analoger i beräkningsbiologin antyder denna likhet på struktur som har bevarats av någon anledning och därför kan vara av intresse. Sedan formalismen i tidsseriemotiv 2002 har dussintals forskare använt dem för olika tillämpningar inom många olika områden. Eftersom den uppenbara algoritmen för att beräkna motiv är kvadratisk i antalet objekt, har mer än ett dussin approximativa algoritmer för att upptäcka motiv föreslagits i litteraturen. I detta arbete visar vi för första gången en exakt algoritm för att hitta tidsseriemotiv. Som vi ska visa genom omfattande experiment, vår algoritm är upp till tre storleksordningar snabbare än brute-force sökning i stora datauppsättningar. Vi visar vidare att vår algoritm är tillräckligt snabb för att användas som subrutin i högre nivå data mining algoritmer för när som helst klassificering, nära-duplicera upptäckt och summering, och vi anser detaljerade fallstudier i domäner så olika som elektroencefalograph tolkning och entomologisk telemetri data mining. I detta arbete visar vi för första gången en exakt algoritm för att hitta tidsseriemotiv. Medan vår exakta algoritm fortfarande är värsta fallet, visar vi att vi kan minska den tid som krävs med tre storleksordningar. I själva verket, under de mest realistiska förhållanden vår exakta algoritm är snabbare än den nuvarande linjära tid approximativa algoritmer, eftersom de har så stora konstanta faktorer. Som vi ska visa, vår algoritm tillåter oss att ta itu med problem som tidigare har ansetts svårhanterliga, till exempel automatiskt bygga "lexikon" av återkommande mönster från elektroencefalografer. Vi visar vidare att vår algoritm är tillräckligt snabb för att användas som en subrutin i högre nivå data mining algoritmer för summering, nära-duplicera upptäckt och när som helst klassificering [34]. NYCKELORD
Deras algoritm är upp till tre storleksordningar snabbare än brute-force algoritm REF.
Exact Discovery of Time Series Motifs
{'venue': 'SDM', 'journal': None, 'mag_field_of_study': ['Medicine', 'Computer Science']}