NDLI: DRESS: dimensionality reduction for efficient sequence search

Content Provider	Springer Nature Link
Author	Kotsifakos, Alexios Stefan, Alexandra Athitsos, Vassilis Das, Gautam Papapetrou, Panagiotis
Copyright Year	2015
Abstract	Similarity search in large sequence databases is a problem ubiquitous in a wide range of application domains, including searching biological sequences. In this paper we focus on protein and DNA data, and we propose a novel approximate method method for speeding up range queries under the edit distance. Our method works in a filter-and-refine manner, and its key novelty is a query-sensitive mapping that transforms the original string space to a new string space of reduced dimensionality. Specifically, it first identifies the $$t$$ most frequent codewords in the query, and then uses these codewords to convert both the query and the database to a more compact representation. This is achieved by replacing every occurrence of each codeword with a new letter and by removing the remaining parts of the strings. Using this new representation, our method identifies a set of candidate matches that are likely to satisfy the range query, and finally refines these candidates in the original space. The main advantage of our method, compared to alternative methods for whole sequence matching under the edit distance, is that it does not require any training to create the mapping, and it can handle large query lengths with negligible losses in accuracy. Our experimental evaluation demonstrates that, for higher range values and large query sizes, our method produces significantly lower costs and runtimes compared to two state-of-the-art competitor methods.
Starting Page	1280
Ending Page	1311
Page Count	32
File Format	PDF
ISSN	13845810
Journal	Data Mining and Knowledge Discovery
Volume Number	29
Issue Number	5
e-ISSN	1573756X
Language	English
Publisher	Springer US
Publisher Date	2015-03-21
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Similarity search Alphabet reduction Biological sequences Data Mining and Knowledge Discovery Artificial Intelligence (incl. Robotics) Information Storage and Retrieval Statistics for Engineering, Physics, Computer Science, Chemistry and Earth Sciences
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Information Systems Computer Science Applications

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

Survey on distance metric learning and dimensionality reduction in data mining

On measuring similarity for sequences of itemsets

Efficient and effective community search

An efficient and effective similarity measure to enable data mining of petroglyphs

Operators for Similarity Search: Semantics, Techniques and Usage Scenarios

Dependence maps, a dimensionality reduction with dependence distance for high-dimensional data

Manifold elastic net: a unified framework for sparse dimension reduction

Using the minimum description length to discover the intrinsic cardinality and dimensionality of time series

Learning sequential classifiers from long and noisy discrete-event sequences efficiently

DRESS: dimensionality reduction for efficient sequence search

Similar Documents

Survey on distance metric learning and dimensionality reduction in data mining

On measuring similarity for sequences of itemsets

Efficient and effective community search

An efficient and effective similarity measure to enable data mining of petroglyphs

Operators for Similarity Search: Semantics, Techniques and Usage Scenarios

Dependence maps, a dimensionality reduction with dependence distance for high-dimensional data

Manifold elastic net: a unified framework for sparse dimension reduction

Using the minimum description length to discover the intrinsic cardinality and dimensionality of time series

Learning sequential classifiers from long and noisy discrete-event sequences efficiently

DRESS: dimensionality reduction for efficient sequence search