A lot of information stored in data

A lot of information stored in databases consists of sequences.Our query model is very simple: We assume that the user specifies a query sequence and wants to retrieve all data sequences that are similar to the query sequence. Similarity search is different from `normal' queries in that we are not only interested in sequences that match the query sequence exactly, but also in sequences that differ only slightly from the query sequence.

A data sequence X is a series of numbers X = (x 1 .....x k ). Sometimes X is also called a time series. We call k the length of the sequence. A subsequence Z = ( z 1 ...z j ) is obtained from another sequence X = (x 1 ;:::;x k )by deleting numbers from the front and back of the sequence X. Formally, Z is a subsequence of X if z1 = x i ;z2 = x i 1 .... zj = z i j ? 1 for some .Given two sequences X =( x 1 ....x k ) and Y = ( y 1 .... yk ) , we can dene the Euclidean norm as the distance between the two sequences as follows:-

Similarity queries over sequences can be classified into two types.

Complete sequence matching: The query sequence and the sequences in the database have the same length. Given a user-specified threshold parameter ,our goal is to retrieve all sequences in the database that are within -distance to the query sequence.

Subsequence matching: The query sequence is shorter than the sequences in the database.

An Algorithm to Find Similar Sequences

Given a collection of data sequences, a query sequence, and a distance threshold how can we efficiently find all sequences that are within -distance from the query sequence?

One possibility is to scan the database, retrieve each data sequence, and compute its distance to the query sequence. Even though this algorithm is very simple, it always retrieves every data sequence.

Because we consider the complete sequence matching problem, all data sequences and the query sequence have the same length. We can think of this similarity search as a high-dimensional indexing problem. Each data sequence and the query sequence can be represented as a point in a k-dimensional space. Thus, if we insert all data sequences into a multidimensional index, we can retrieve data sequences that exactly match the query sequence by querying the index. But since we want to retrieve not only data sequences that match the query exactly, but also all sequences that are within -distance from the query sequence, we do not use a point query as defined by the query sequence. Instead, we query the index with a hyper-rectangle that has side-length 2 and the query sequence as center, and we retrieve all sequences that fall within this hyper-rectangle. We then discard sequences that are actually further than only a distance of away from the query sequence.

Using the index allows us to greatly reduce the number of sequences that we consider and decreases the time to evaluate the similarity query significantly. The references at the end of the chapter provide pointers to further improvements.

ผลลัพธ์ (ไทย) 1:

จำนวนมากของข้อมูลที่เก็บในฐานข้อมูลประกอบด้วยลำดับแบบสอบถามของเราคือง่ายมาก: เราสมมติว่า ผู้ใช้ระบุลำดับการสอบถาม และต้องการเรียกลำดับข้อมูลทั้งหมดที่คล้ายกับแบบสอบถามลำดับนั้น ค้นหาความคล้ายคลึงกันจะแตกต่างจากแบบสอบถาม 'ปกติ' ที่เราสนใจไม่เฉพาะในลำดับที่ตรงลำดับแบบสอบถาม แต่ยังอยู่ ในลำดับที่แตกต่างกันเพียงเล็กน้อยจากลำดับแบบสอบถาม

ข้อมูลลำดับ X คือ ชุดของตัวเลข X = (x 1 ... .x k) X บางครั้งจะเรียกว่าชุดครั้ง เราเรียก k ความยาวของลำดับ Subsequence Z = (z 1 ... เจ.z) รับจากอื่นลำดับ X = (x 1;:::; x k) โดยลบตัวเลข จากด้านหน้า และลำดับ x. อัพอย่างเป็นกิจจะลักษณะ Z เป็น subsequence ของ X ถ้า z1 = x ฉัน z2 = x 1...ผม zj = z ผมเจ 1 บางกำหนดลำดับ X 2 = (x 1 ... .x k) และ Y = (y 1...วาย), เราสามารถอเครสดีนปกติ Euclidean เป็นระยะห่างระหว่างสองลำดับดังนี้: -

คล้ายแบบสอบถามผ่านลำดับสามารถแบ่งได้เป็นสองชนิดได้

กรอกลำดับที่ตรงกัน: แบบสอบถามลำดับที่และลำดับที่ในฐานข้อมูลมีความยาว กำหนดพารามิเตอร์ผู้ใช้ระบุขีดจำกัด เป้าหมายของเราคือการ เรียกลำดับทั้งหมดในฐานข้อมูลที่อยู่ใน - ห่างจากลำดับแบบสอบถาม

Subsequence ตรง: ลำดับแบบสอบถามจะสั้นกว่าลำดับในฐานข้อมูล

อันอัลกอริทึมการค้นหาลำดับคล้าย

รับคอลเลกชันข้อมูลลำดับ ลำดับการสอบถาม และขีดจำกัดระยะความสามารถเรามีประสิทธิภาพค้นหาทั้งหมดลำดับที่ภายใน - ห่างจากลำดับสอบถาม?

โอกาสหนึ่งสแกนฐานข้อมูล เรียกแต่ละลำดับข้อมูล ท่องเที่ยวกับแบบสอบถามลำดับคำนวณ แม้ว่าอัลกอริทึมนี้จะง่ายมาก มันจะดึงข้อมูลลำดับทุก

เนื่องจากเราพิจารณาปัญหาตรงสมบูรณ์ลำดับ ลำดับข้อมูลทั้งหมดและลำดับแบบสอบถามมีความยาว เราสามารถคิดค้นหาความคล้ายคลึงกันนี้เป็นปัญหาดัชนีสูงมิติ แต่ละลำดับข้อมูลและลำดับการสอบถามสามารถแสดงเป็นจุดในพื้นที่ k มิติ ดังนั้น ถ้าเราใส่ลำดับข้อมูลทั้งหมดในดัชนีหลาย เราสามารถดึงข้อมูลลำดับที่ตรงลำดับแบบสอบถาม โดยสอบถามดัชนี แต่เนื่องจากเราต้องการเรียกใช้ไม่เพียงแต่ลำดับข้อมูลที่ตรงกับแบบสอบถามทุกประการ แต่ยังลำดับทั้งหมดที่อยู่ภายใน - ห่างจากลำดับแบบสอบถาม เราไม่ได้ใช้แบบสอบถามจุดตามที่กำหนดไว้ตามลำดับที่สอบถาม แทน เราสอบถามดัชนีกับไฮเปอร์สี่เหลี่ยมที่มีด้านยาว 2 และลำดับสอบถามศูนย์ และเราเรียกลำดับทั้งหมดที่อยู่ภายในนี้ไฮเปอร์สี่เหลี่ยม เรายกเลิกลำดับที่จริงอำนวยเท่าความห่างของลำดับการสอบถาม แล้ว

ใช้ดัชนีช่วยให้เราสามารถลดจำนวนของลำดับที่เราพิจารณาอย่างมาก และลดเวลาในการประเมินแบบสอบถามความคล้ายคลึงกันมาก อ้างอิงท้ายบทมีตัวชี้การปรับปรุงต่อไป

ผลลัพธ์ (ไทย) 2:

จำนวนมากของข้อมูลที่เก็บไว้ในฐานข้อมูลที่ประกอบด้วยรูปแบบแบบสอบถาม sequences.Our ง่ายมาก: เราคิดว่าผู้ใช้ระบุลำดับการค้นหาและต้องการที่จะดึงลำดับข้อมูลทั้งหมดที่มีความคล้ายคลึงกับลำดับการค้นหา ค้นหาความคล้ายคลึงกันจะแตกต่างจาก `คำสั่งปกติในการที่เราจะไม่เพียง แต่ให้ความสนใจในลำดับที่ตรงกับลำดับการค้นหาว่า แต่ยังอยู่ในลำดับที่แตกต่างกันเพียงเล็กน้อยจากลำดับแบบสอบถามลำดับข้อมูล X เป็นชุดของตัวเลข x = ( x 1 ..... XK) บางครั้ง X จะเรียกว่าอนุกรมเวลา เราเรียก k ความยาวของลำดับ subsequence Z = (z 1 ... ZJ) จะได้รับจากการลำดับอื่น X = (x 1; :::; XK) โดยการลบตัวเลขจากด้านหน้าและด้านหลังของเอ็กซ์ลำดับอย่างเป็นทางการ Z เป็น subsequence ของ X ถ้า z1 = xi; z2 = xi 1 .... ZJ = Zij? 1. สำหรับบางคนที่ได้รับสองลำดับ X = (x 1 .... XK) และ y = (y 1 .... YK) เราสามารถ Dene บรรทัดฐานยุคลิดเป็นระยะห่างระหว่างสองลำดับดังต่อไปนี้: - การค้นหาความคล้ายคลึงกัน กว่าลำดับสามารถแบ่งได้เป็นสองประเภทการจับคู่ที่สมบูรณ์แบบลำดับ: ลำดับแบบสอบถามและลำดับในฐานข้อมูลมีความยาวเดียวกัน ป.ร. ให้ไว้ ณ พารามิเตอร์เกณฑ์ที่ผู้ใช้ระบุเป้าหมายของเราคือเพื่อเรียกลำดับทั้งหมดในฐานข้อมูลที่อยู่ภายในระยะที่จะสอบถามลำดับการจับคู่ subsequence: ลำดับแบบสอบถามสั้นกว่าลำดับในฐานข้อมูลขั้นตอนวิธีการหาลำดับที่คล้ายกันให้ การเก็บรวบรวมข้อมูลลำดับลำดับแบบสอบถามและเกณฑ์ระยะทางวิธีที่เราสามารถได้อย่างมีประสิทธิภาพหาลำดับทั้งหมดที่อยู่ภายในระยะทางจากลำดับแบบสอบถาม? หนึ่งเป็นไปได้คือการสแกนฐานข้อมูลเรียกแต่ละลำดับข้อมูลและการคำนวณระยะทางในการ ลำดับแบบสอบถาม ถึงแม้ว่าขั้นตอนวิธีนี้ง่ายมากก็มักจะเรียกลำดับข้อมูลทุกเพราะเราพิจารณาปัญหาลำดับการจับคู่ที่สมบูรณ์ทุกลำดับข้อมูลและลำดับแบบสอบถามมีความยาวเดียวกัน เราสามารถคิดของการค้นหาความคล้ายคลึงกันนี้เป็นปัญหาการจัดทำดัชนีสูงมิติ แต่ละลำดับข้อมูลและลำดับแบบสอบถามสามารถแสดงเป็นจุดในพื้นที่ k มิติ ดังนั้นถ้าเราใส่ลำดับข้อมูลทั้งหมดลงในดัชนีหลายมิติที่เราสามารถดึงข้อมูลลำดับที่ตรงกับลำดับการค้นหาโดยการสอบถามดัชนี แต่เนื่องจากเราต้องการที่จะดึงข้อมูลลำดับไม่เพียง แต่ที่ตรงกับคำค้นหาว่า แต่ยังวนเวียนอยู่ทั้งหมดที่อยู่ภายในระยะทางจากลำดับแบบสอบถามที่เราไม่ได้ใช้แบบสอบถามจุดตามที่กำหนดโดยลำดับแบบสอบถาม แต่เราค้นหาดัชนีที่มีไฮเปอร์สี่เหลี่ยมที่มีด้านยาว 2 และลำดับการค้นหาเป็นศูนย์และเราเรียกลำดับทั้งหมดที่อยู่ภายในนี้ไฮเปอร์สี่เหลี่ยมผืนผ้า จากนั้นเราจะทิ้งลำดับที่เป็นจริงมากไปกว่าเพียง แต่ระยะห่างจากลำดับการค้นหาโดยใช้ดัชนีช่วยให้เราสามารถช่วยลดจำนวนของลำดับที่เราพิจารณาและลดเวลาในการประเมินผลแบบสอบถามความคล้ายคลึงกันอย่างมีนัยสำคัญ อ้างอิงที่ส่วนท้ายของบทที่ให้คำแนะนำเพื่อการปรับปรุง

ผลลัพธ์ (ไทย) 3:

มากของข้อมูลที่จัดเก็บในฐานข้อมูลประกอบด้วยลำดับ รุ่นแบบสอบถามของเราคือง่ายมาก : เราคิดว่าผู้ใช้ระบุแบบสอบถามลำดับและต้องการดึงข้อมูลทั้งหมดลำดับที่คล้ายกับการลำดับ ค้นหาความเหมือนที่แตกต่างจาก ` ปกติ ' ในแบบสอบถามที่เราไม่เพียง แต่สนใจในลำดับที่ตรงกับแบบสอบถามลำดับแน่นอนแต่ยังอยู่ในลำดับที่แตกต่างกันเพียงเล็กน้อยจากแบบสอบถามลำดับ .

ลำดับข้อมูล X คือชุดของตัวเลข X = ( x 1 . . . . . x K ) บางครั้งก็เรียกว่าเวลา X Series เราเรียก K ความยาวของลำดับ เป็นพลังใจ Z ( Z = 1 . . . . . . . Z J ) ได้มาจากอีกลำดับ X = ( X 1 ; : : : ; x K ) โดยการลบตัวเลขจากด้านหน้าและด้านหลังของลำดับ X อย่างเป็นทางการZ เป็นพลังใจของ x ถ้า Z1 x = x = i ; กขึ้นผม 1 . . . . . . . ZJ = Z ฉันเจ 1 . ให้สองลำดับ x = ( x 1 . . . . . . . x K ) Y ( y = 1 . . . . . . . YK ) เราสามารถคาดการใช้บรรทัดฐานที่ระยะห่างระหว่างสองลำดับดังนี้ : -

สอบถามมากกว่าความเหมือนลำดับสามารถแบ่งได้เป็น 2 ประเภท

สมบูรณ์ลำดับการจับคู่ :แบบสอบถามลำดับและอนุกรม ในฐานข้อมูลมีความยาวเดียวกัน ให้ผู้ใช้กำหนดพารามิเตอร์เกณฑ์ เป้าหมายของเราคือเพื่อดึงข้อมูลทั้งหมดในฐานข้อมูลที่เป็นลำดับในระยะห่างแบบสอบถามลำดับ

จากนั้นจับคู่ : แบบสอบถามลำดับเตี้ยกว่าลำดับในฐานข้อมูล

ขั้นตอนวิธีการค้นหาที่คล้ายกันลำดับ

ให้คอลเลกชันของลำดับข้อมูลแบบสอบถามลำดับและระยะห่างของวิธีการที่เราสามารถมีประสิทธิภาพหาลำดับทั้งหมดที่อยู่ภายในระยะทางจากแบบสอบถามลำดับ ?

คนหนึ่งเป็นไปได้คือการสแกนฐานข้อมูลดึงแต่ละลำดับข้อมูล และคำนวณหาระยะห่างของการค้นหาลำดับ ถึงแม้ว่าวิธีนี้จะง่ายมาก มันก็ดึงข้อมูลทุก

ตามลําดับเพราะเราถือว่าสมบูรณ์ลำดับการจับคู่ปัญหาลำดับข้อมูลและแบบสอบถามลำดับมีความยาวเดียวกัน เราคิดว่านี่เป็นปัญหาการค้นหาความคล้ายคลึงกันสูง - มิติ . แต่ละลำดับข้อมูลและแบบสอบถามลำดับที่สามารถแสดงเป็นจุดในพื้นที่ k-dimensional . ดังนั้น ถ้าเราใส่ข้อมูลทั้งหมดลงในดัชนีลำดับแบบพหุมิติเราสามารถดึงข้อมูลลำดับที่ตรงกับแบบสอบถามลำดับ โดยข้อมูลดัชนี แต่เนื่องจากเราต้องการดึงข้อมูลที่ไม่เพียง แต่ลำดับตรงกับแบบสอบถามทั้งหมดแน่ แต่ยังดับอยู่ภายในระยะทางจากแบบสอบถามลำดับ เราไม่ใช้ แบบสอบถามเป็นแบบสอบถามจุดกำหนด โดยลำดับ แทนเราค้นหาดัชนีกับรูปสี่เหลี่ยมผืนผ้าที่มีด้านยาว 2 ไฮเปอร์และลำดับการเป็นศูนย์และเราเรียกลำดับทั้งหมดที่อยู่ภายในรูปสี่เหลี่ยมไฮเปอร์นี้ เราแล้วทิ้ง ลำดับที่เป็นจริงเพิ่มเติมกว่าเพียงระยะทางห่างจากแบบสอบถามลำดับ .

การใช้ดัชนีที่ช่วยให้เราสามารถลดจำนวนของลำดับที่เราพิจารณา และลดเวลาที่ใช้ในการประเมิน แบบสอบถามมีความคล้ายคลึงกันอย่างมาก การอ้างอิงในตอนท้ายของบทที่ให้คำแนะนำเพื่อปรับปรุงต่อไป