NDLI: Measuring Similarity for Multidimensional Sequences

Content Provider	IEEE Xplore Digital Library
Author	Hui Wang Zhiwei Lin McClean, S. Jun Liu
Copyright Year	2010
Abstract	Multidimensional sequences are common, and measuring their similarity is a key to any analysis of such data. There is a wealth of similarity measures for sequences in the literature, but most of them are designed for a special type of sequence and later extended to more general types. These extensions are usually ad hoc, and the extended versions may lose the original conceptual interpretation of the measure. In this paper we consider the problem of how to measure similarity for the general type of multidimensional sequences effectively in a conceptually uniform way. We show that the subsequence concept behind longest common subsequence and all common subsequences can be extended from the temporal dimension to the spatial dimension, and we generalize the all common subsequences similarity to multidimensional sequences. The hard problem is how to compute the generalized similarity. We present a theorem that combines the temporal and spatial dimensions in a simple formula. This theorem suggests a dynamic programming algorithm to compute the generalized similarity. A preliminary experiment shows that this similarity produces competitive outcomes. However, this approach counts some subsequences multiple times when a sequence has repeated elements. We present a theorem that allows counting of distinct common subsequences.
Starting Page	281
Ending Page	287
File Size	277140
Page Count	7
File Format	PDF
ISBN	9781424492442
DOI	10.1109/ICDMW.2010.202
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-12-13
Publisher Place	Australia
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis dynamic time warping Accuracy all common subsequences Heuristic algorithms similarity Electrocardiography multidimensional sequences Dynamic programming Data mining Indexes the longest common subsequence
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Research on longest common subsequence fast algorithm

A Multidimensional Sequence Approach to Measuring Tree Similarity

Batch source-code plagiarism detection using an algorithm for the bounded longest common subsequence problem

An Improved Longest Common Subsequence Algorithm for Reducing Memory Complexity in Global Alignment of DNA Sequences

Nice to be a Chimera: A hybrid algorithm for the longest common transposition-invariant subsequence problem

A Novel Algorithm for Counting All Common Subsequences

Fast longest common subsequences for bioinformatics dynamic programming.

Longest Common Subsequence using Chemical Reaction Optimization

A relative position based algorithm to find out the longest common subsequence from multiple biological sequences

Measuring Similarity for Multidimensional Sequences

Similar Documents

Research on longest common subsequence fast algorithm

A Multidimensional Sequence Approach to Measuring Tree Similarity

Batch source-code plagiarism detection using an algorithm for the bounded longest common subsequence problem

An Improved Longest Common Subsequence Algorithm for Reducing Memory Complexity in Global Alignment of DNA Sequences

Nice to be a Chimera: A hybrid algorithm for the longest common transposition-invariant subsequence problem

A Novel Algorithm for Counting All Common Subsequences

Fast longest common subsequences for bioinformatics dynamic programming.

Longest Common Subsequence using Chemical Reaction Optimization

A relative position based algorithm to find out the longest common subsequence from multiple biological sequences

Measuring Similarity for Multidimensional Sequences